Week4

The largest subsequence and

Title Description ：
Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .
Subarray Is a continuous part of the array .
Example 1：

Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray [4,-1,2,1] And the biggest , by 6 .
Example 2：

Input ：nums = [1]
Output ：1
Example 3：

Input ：nums = [5,4,-1,7,8]
Output ：23

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/maximum-subarray
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

** Ideas ：** We just need to find the f(i)f(i), Then return ff The maximum value in the array . So how do we ask f(i)f(i) Well ？ We can consider \textit{nums}[i]nums[i] Be alone or join f(i-1)f(i−1) The corresponding paragraph , It depends. \textit{nums}[i]nums[i] and f(i-1) + \textit{nums}[i]f(i−1)+nums[i] Size , We hope to get a bigger , So we can write such a dynamic programming transfer equation ：

f(i) = \max { f(i-1) + \textit{nums}[i], \textit{nums}[i] }
f(i)=max{f(i−1)+nums[i],nums[i]}

It is not difficult to give a time complexity O(n)O(n)、 Spatial complexity O(n)O(n) The implementation of the , Which is a ff Array to hold f(i)f(i) Value , Use a loop to find all f(i)f(i). in consideration of f(i)f(i) And the only f(i-1)f(i−1) relevant , So we can use only one variable \textit{pre}pre To maintain the current f(i)f(i) Of f(i-1)f(i−1) What's the value of , Thus, the space complexity is reduced to O(1)O(1), It's kind of similar 「 Scrolling array 」 Thought .
Code ：

func maxArray(nums []int)  int{
    
	max:=nums[0]
	for i:=1;i<len(nums);i++ {
    
		if nums[i]<nums[i-1]+nums[i] {
    
			nums[i]+=nums[i-1]
		}
		if nums[i]>max {
    
			max=nums[i]
		}
	}
	return max
}

Run a screenshot ：

Submit screenshots ：

Problems encountered ：
1.if nums[i]<nums[i-1]+nums[i] Here it is written by mistake <=. If it's written <= Words ,nums[i] Will cross the border ,i It's from o To n-1, and len(nums) yes n.
2. max:=nums[0] I wrote it wrong max:=0. If the array has only one element , Always output 0, Instead of outputting array elements .

Length of last word

Title Description ：
Give you a string s, It consists of several words , Words are separated by some space characters . Return string the last one The length of the word .
word It's just letters 、 The largest substring that does not contain any space characters .
Example 1：

Input ：s = “Hello World”
Output ：5
explain ： The last word is “World”, The length is 5.
Example 2：

Input ：s = " fly me to the moon "
Output ：4
explain ： The last word is “moon”, The length is 4.
Example 3：

Input ：s = “luffy is still joyboy”
Output ：6
explain ： The last word is... In length 6 Of “joyboy”.

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/length-of-last-word
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas ：
Reverse traversal
The title requires the length of the last word in the string , You can traverse the string in reverse , Find the last word and calculate its length .

Because there is at least one word in the string , So there must be letters in the string . First find the last letter in the string , This letter is the last letter of the last word .

Continue to traverse the string in reverse from the last letter , Until you encounter a space or reach the beginning of the string . Each letter traversed is the letter in the last word , Therefore, the number of letters traversed is the length of the last word .

author ：LeetCode-Solution
link ：https://leetcode-cn.com/problems/length-of-last-word/solution/zui-hou-yi-ge-dan-ci-de-chang-du-by-leet-51ih/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .
Code ：

func Lastword(s string)  int{
    
	if s = strings.TrimSpace(s); len(s) == 0 {
    
		//strings.TrimSpace(s string) Will return a string Type of slice, And put the front and back ASCII Remove the defined spaces , The space in the middle will not be removed , If \0 And other characters will be regarded as non spaces .
		return 0
	}
	ans := 0
	byteS := []byte(s)
	for i := len(s) - 1; i >= 0 ; i-- {
    
		if byteS[i] == ' ' {
    
			break
		}// Stop traversing when it's not a letter 
		ans++
	}
	return ans

}

Run a screenshot ：

Submit screenshots ：

The key point of this algorithm is trim.space() Use of functions . This function returns a string Type of slice, And put the front and back ASCII Remove the defined spaces , The space in the middle will not be removed , If \0 And other characters will be regarded as non spaces .

The longest common prefix

 ** Title Description ：** Write a function to find the longest common prefix in the string array .

If no common prefix exists , Returns an empty string “”.
Example 1：

Input ：strs = [“flower”,“flow”,“flight”]
Output ：“fl”
Example 2：

Input ：strs = [“dog”,“racecar”,“car”]
Output ：“”
explain ： Input does not have a common prefix .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-common-prefix
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：
Lateral scan ：

Traverse the elements in the string array , For the array of each string traversed , Update the longest common prefix sequence . So here are two functions , One is to update the function of the longest common prefix , The other is the function of traversing strings .

Code ：

func longestCommonPrefix(strs []string) string {
    
	if len(strs) == 0 {
    
		return ""
	}
	prefix := strs[0]
	count := len(strs)
	for i := 1; i < count; i++ {
    
		prefix = lcp(prefix, strs[i])
		if len(prefix) == 0 {
    
			break
		}
	}
	return prefix
}

func lcp(str1, str2 string) string {
    
	length := min(len(str1), len(str2))
	index := 0
	for index < length && str1[index] == str2[index] {
    
		index++
	}
	return str1[:index]
}

func min(x, y int) int {
    
	if x < y {
    
		return x
	}
	return y
}


func main() {
    
var strx=[]string{
    "ddddd","dddfg","ddddddddf","dddddcd"}
	fmt.Printf("%s",longestCommonPrefix(strx) )
}

result ：

func longestCommonPrefix(strs []string) string {
    
	if len(strs) == 0 {
    
		return ""
	}
	prefix := strs[0]
	count := len(strs)
	for i := 1; i < count; i++ {
    
		prefix = lcp(prefix, strs[i])
		if len(prefix) == 0 {
    
			break
		}
	}
	return prefix
}

func lcp(str1, str2 string) string {
    
	length := min(len(str1), len(str2))
	index := 0
	for index < length && str1[index] == str2[index] {
    
		index++
	}
	return str1[:index]
}

func min(x, y int) int {
    
	if x < y {
    
		return x
	}
	return y
}


func main() {
    
var strx=[]string{
    "aaasdr","aaasdfgtg","aaasdrglk","aaasdrbbl"}
	fmt.Printf("%s",longestCommonPrefix(strx) )
}

Realization strStr()

  Title Description ：
     Realization  strStr()  function .

Here are two strings haystack and needle , Please come in haystack Find in string needle The first place the string appears （ Subscript from 0 Start ）. If it doesn't exist , Then return to -1 .

explain ：

When needle When it's an empty string , What value should we return ？ This is a good question in an interview .

For this question , When needle When it's an empty string, we should return 0 . This is related to C Linguistic strstr() as well as Java Of indexOf() The definition matches .

Example 1：

Input ：haystack = “hello”, needle = “ll”
Output ：2
Example 2：

Input ：haystack = “aaaaa”, needle = “bba”
Output ：-1
source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/implement-strstr
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

package main
func strStr(haystack, needle string) int {
    
	n, m := len(haystack), len(needle)
outer:
	for i := 0; i+m <= n; i++ {
    
		for j := range needle {
    
			if haystack[i+j] != needle[j] {
    
				continue outer
			}
		}
		return i
	}
	return -1
}

func main() {
    
        print(strStr("aaaasssdssaaaassdd","sss"))
}

Run a screenshot ：