最近在刷 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))
}