LeetCode 014&053

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

1
2
> Input: ["flower","flow","flight"]
> Output: "fl"

Example 2:

1
2
3
> 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.

简单的说就是求最长公共前缀,解法的思路如图,

image-20180708134936170

就是每两个字符串进行对比,寻找最大的前缀,然后找到的前缀与下一个字符串进行前缀匹配,当然也可以先把字符串根据长度排序,用最短的那个字符串作为最开始的前缀来进行匹配查找,因为最长公共前缀的长度不会超过最短的字符串长度~

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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:

1
2
3
> 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 的思想啦~

状态转移方程就是,

1
2
sum = max(a[i], sum+a[i])
max = max(sum, max)

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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))
}