最近在刷 LeetCode, 今天顺手总结两道题目的题解~
14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
- Example 1:
- > Input: ["flower","flow","flight"]
- > Output: "fl"
复制代码
- Example 2:
- > Input: ["dog","racecar","car"]
- > Output: ""
- > Explanation: There is no common prefix among the input strings.
复制代码
Note: All given inputs are in lowercase letters a-z.
简单的说就是求最长公共前缀, 解法的思路如图,
就是每两个字符串进行对比, 寻找最大的前缀, 然后找到的前缀与下一个字符串进行前缀匹配, 当然也可以先把字符串根据长度排序, 用最短的那个字符串作为最开始的前缀来进行匹配查找, 因为最长公共前缀的长度不会超过最短的字符串长度~
- Solution
- package main
- import (
- "fmt"
- "strings"
- )
- func longestCommonPrefix(strs []string) string {
- // 如果数组是空的, 那么返回 ""
- if(len(strs) == 0) {
- return ""
- }
- // 取第一个字符串作为初始的前缀
- prefix := strs[0]
- for i := 1; i <len(strs); i++{
- // 这个循环的目的是, 根据查找前缀的位置来判断是否已经找到公共前缀
- for ; strings.Index(strs[i], prefix) != 0; {
- // 没找到, 则去掉最后一位, 继续尝试
- prefix = prefix[0:len(prefix) - 1]
- // 如果没有公共前缀, 就返回 ""
- if(len(prefix) == 0) {
- return ""
- }
- }
- }
- return prefix
- }
- func main() {
- a := []string{"flower", "flow", "flight"}
- fmt.Println(longestCommonPrefix(a))
- a = []string{"aa", "a"}
- fmt.Println(longestCommonPrefix(a))
- }
复制代码
53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
- Example:
- > Input: [-2,1,-3,4,-1,2,1,-5,4],
- > Output: 6
- > Explanation: [4,-1,2,1] has the largest sum = 6.
复制代码
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
题面如上~ 简单的说, 就是要求子区间的最大和~ O(n) 复杂度的解是使用了 Kadane 算法, 这个算法是专门用于求最大子序列的和~
Kadane's algorithm
简单来说, kadane 算法就是, 当 index = i 时,
如果 sum(a[0:i]) <0, 那么就取 a[i] 作为 sum
如果 sum(a[0:i])> 0, 那么就取 sum + a[i] 作为 sum
同时, 还存在一个变量来记录过程中有过的最大值, 因为 sum + a[i], 其中 a[i] 有可能是负数, 如果以 sum 作为结果, 可能就无法获取到最大的和, 思想其实就是 DP 的思想啦~
状态转移方程就是,
- sum = max(a[i], sum+a[i])
- max = max(sum, max)
复制代码
- Solution
- package main
- import (
- "fmt"
- )
- func getMax(a int, b int) int {
- if a> b {
- return a
- }
- return b
- }
- func maxSubArray(nums []int) int {
- // 这里注意需要初始化为 nums[0] 或者一个极小值, 不能初始化为 0
- // bad case: [-1] output: 0
- sum, max := nums[0], nums[0]
- for i := 1; i < len(nums); i++ {
- sum = getMax(nums[i], sum + nums[i])
- max = getMax(sum, max)
- }
- return max
- }
- func main() {
- a := []int{-2,1,-3,4,-1,2,1,-5,4}
- fmt.Println(maxSubArray(a))
- }
复制代码
来源: https://juejin.im/post/5b45f10cf265da0f9c678c84