21.合并兩個有序鏈表(高頻)

題目：兩個升序鏈表，合并成一個 https://leetcode-cn.com/problems/merge-two-sorted-lists

題解：

• 需要一個空的頭節(jié)點做輔助，head.Next就是結果
• 每次遍歷始終維護上一個節(jié)點prev，初始值prev=head
• 循環(huán)遍歷兩個鏈表，循環(huán)條件都不為空，每次把當前節(jié)點更小的取出來即可

prev.Next = l1
prev = l1
l1 = l1.Next

• 最后加入有不為空的節(jié)點，則直接賦值

if l1!=nil{
    prev.Next = l1
}else{
    prev.Next = l2
}

完整代碼

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
 head := &ListNode{
  Val:0,
  Next:nil,
 }
 prev := head
 for l1!=nil && l2!=nil{
  if l1.Val < l2.Val{
   prev.Next= l1
   prev = l1
   l1 = l1.Next
  }else{
   prev.Next = l2
   prev = l2
   l2 = l2.Next
  }
 }
 if l1!=nil{
  prev.Next = l1
 }else{
  prev.Next = l2
 }
 return head.Next
}

53.最大子序和(高頻)

題目：求和加起來最大的連續(xù)子數(shù)組 https://leetcode-cn.com/problems/maximum-subarray

題解：

• 一次循環(huán)，數(shù)組里有可能出現(xiàn)負數(shù)，且只需要統(tǒng)計和即可
• 需要兩個計數(shù)器，一個存儲全局最大的子序列和，只要出現(xiàn)更大的就更新
• 另一個存儲當前最大的子序和，判斷當前最大子序和的方法是比較子序和與當前值哪個大
• 有可能當前值比子序列和大，就更新子序 max(nums[i],nums[i]+last)

核心代碼

last = max(nums[i],nums[i]+last)
resMax = max(resMax,last)

完整代碼

func maxSubArray(nums []int) int {
 n := len(nums)
 if n<1{
  return 0
 }
 last,resMax := nums[0],nums[0]
 for i:=1;i<n;i++{
  // 要不就是自成一派，要不就是和前面連續(xù)的放在一起
  last = max(nums[i],nums[i]+last)
  resMax = max(resMax,last)
 }
 return resMax
}
func max(x,y int)int{
 if x>y{
  return x
 }
 return y
}