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:

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))
}