力扣1-100题解

2023-12-13 05:50:40

本篇博客是用Go语言编写的详尽简洁代码,这里没有写算法思路,若要看具体思路,请移步力扣官网查看相关高赞题解。本篇博客的特点是代码简洁明了,包含多种写法,适合读者后期复盘巩固,加深理解。前一百题是面试高频题,建议读者认真阅读,背诵记忆。欢迎点赞+收藏+关注~~

LC1 两数之和

func twoSum(nums []int, target int) []int {
    mp := map[int]int{}
    for i, x := range nums {
        y := target - x
        if _, ok := mp[y]; ok {
            return []int{mp[y], i}
        }
        mp[nums[i]] = i
    }
    return []int{}
}

LC2 两数相加

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  dummy := &ListNode{-1, nil}
  cur := dummy
  t := 0
  for l1 != nil || l2 != nil || t != 0 {
    if l1 != nil {
      t += l1.Val
      l1 = l1.Next
    }
    if l2 != nil {
      t += l2.Val
      l2 = l2.Next
    }
    cur.Next = &ListNode{t % 10, nil}
    cur = cur.Next
    t /= 10
  }

  return dummy.Next
}

LC3 无重复字符的最长子串

func lengthOfLongestSubstring(s string) int {
    mp := map[byte]int{}
    ans := 0
    for l, r := 0, 0; r < len(s); r ++ {
        mp[s[r]] ++ 
        for mp[s[r]] > 1 {
            mp[s[l]] --
            l ++
        }
        ans = max(ans, r - l + 1)
    }
    return ans
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

LC4 寻找两个正序数组的中位数

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    n, m := len(nums1), len(nums2)
    tot := n + m
    if tot & 1 != 0 {
        return float64(getKth(nums1, 0, n - 1, nums2, 0, m - 1, tot / 2 + 1))
    } else {
        a := float64(getKth(nums1, 0, n - 1, nums2, 0, m - 1, tot / 2))
        b := float64(getKth(nums1, 0, n - 1, nums2, 0, m - 1, tot / 2 + 1))
        return (a + b) / 2.0
    }
}

func getKth(nums1 []int, s1, e1 int, nums2 []int, s2, e2, k int) int {
    l1, l2 := e1 - s1 + 1, e2 - s2 + 1
    if l1 > l2 {
        return getKth(nums2, s2, e2, nums1, s1, e1, k)
    }
    if l1 == 0 {
        return nums2[s2 + k - 1]
    }
    if k == 1 {
        return min(nums1[s1], nums2[s2])
    }
    
    i, j := s1 + min(k / 2, l1) - 1, s2 + min(k / 2, l2) - 1
    if nums1[i] > nums2[j] {
        return getKth(nums1, s1, e1, nums2, j + 1, e2, k - (j - s2 + 1))
    } else {
        return getKth(nums1, i + 1, e1, nums2, s2, e2, k - (i - s1 + 1))
    }
}

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

LC5 最长回文子串

func longestPalindrome(s string) string {
    n := len(s)
    if n < 2 {
        return s
    }

    ans := ""
    for i := 0; i < n; i ++  {
        l, r := i, i + 1
        for l >= 0 && r < n && s[l] == s[r] {
            l -- 
            r ++ 
        }
        if r - l - 1 > len(ans) {
            ans = s[l + 1 : r]
        }

        l, r = i - 1, i + 1
        for l >= 0 && r < n && s[l] == s[r] {
            l -- 
            r ++
        }
        if r - l - 1 > len(ans) {
            ans = s[l + 1 : r]
        }
    }

    return ans
}

LC6 N字形变换

func convert(s string, n int) string {
    if n < 2 {
        return s
    }

    t := make([]string, n)
    i, flag := 0, -1
    for _, c := range s {
        t[i] += string(c)
        if i == 0 || i == n - 1 {
            flag = -flag
        }
        i += flag
    }

    ans := ""
    for _, v := range t {
        ans += v
    }

    return ans
}

LC7 整数反转

func reverse(x int) int {
    ans := 0
    for x != 0 {
        t := x % 10
        if ans > 214748364 || (ans == 214748364 && t > 7) {
            return 0
        }
        if ans < -214748364 || (ans == -214748364 && t < -8) {
            return 0
        }
        ans = ans * 10 + t
        x /= 10
    }
    return ans
}

LC8 字符串转换整数(atoi)

func myAtoi(s string) int {
  k, ans, sign, n := 0, 0, 1, len(s)
  for k < n && s[k] == ' ' {
    k ++ 
  }
  if k == n {
    return 0
  }
  if s[k] == '+' {
    k ++ 
  } else if s[k] == '-' {
    sign = -1
    k ++ 
  }

  for k < n && s[k] >= '0' && s[k] <= '9' {
    t := int(s[k] - '0')
    if sign == 1 && (ans > 214748364 || ans == 214748364 && t > 7) {
      return math.MaxInt32
    }
    if sign == -1 && (-ans < -214748364 || -ans == -214748364 && t > 7) {
      return math.MinInt32
    }
    ans = ans * 10 + t
    t /= 10
    k ++ 
  }

  return sign * ans
}

LC9 回文数

func isPalindrome(x int) bool {
    if x < 0 || (x % 10 == 0 && x != 0) {
        return false
    }
    y := 0
    for x > y {
        y = y * 10 + x % 10
        x /= 10
    }
    return x == y || x == y / 10
}

LC10 正则表达式匹配

func isMatch(s string, p string) bool {
	n, m := len(s), len(p)
	s = " " + s
	p = " " + p

	f := make([][]bool, n + 1)
	for i := 0; i <= n; i ++ {
		f[i] = make([]bool, m + 1)
	}

	f[0][0] = true
	for i := 0; i <= n; i ++ {
		for j := 1; j <= m; j ++ {
			if p[j] != '*' {
				f[i][j] = i > 0 && f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.')
			} else {
				f[i][j] = (j >= 2 && f[i][j - 2]) || (i > 0 && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.'))
			}
		}
	}

	return f[n][m]
}

LC11 盛最多水的容器

func maxArea(h []int) int {
    l, r, ans := 0, len(h) - 1, 0
    for l < r {
        ans = max(ans, min(h[l], h[r]) * (r - l))
        if h[l] < h[r] {
            l ++
        } else {
            r --
        }
    }
    return ans
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

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

LC12 整数转罗马数字

type PIS struct {
  Value int
  Roman string
}

func intToRoman(num int) string {
    mp := []PIS{
        {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
        {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
        {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"},
    }

    ans := ""
    for _, p := range mp {
      for num >= p.Value {
        num -= p.Value
        ans += p.Roman
      }
      if num == 0 {
        break
      }
    }

    return ans
}

LC13 罗马数字转整数

func romanToInt(s string) int {
    mp := map[byte]int{
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000,
    }

    ans, n := 0, len(s)
    for i := 0; i < n; {
        if i + 1 < n && mp[s[i]] < mp[s[i + 1]] {
            ans += mp[s[i + 1]] - mp[s[i]]
            i += 2
        } else {
            ans += mp[s[i]]
            i ++
        }
    }

    return ans
}

LC14 最长公共前缀

func longestCommonPrefix(strs []string) string {
  base, ans := strs[0], ""
  for i := 0; i < len(base); i ++ {
    for _, s := range strs {
      if i >= len(s) || s[i] != base[i] {
        return ans
      }
    }
    ans += string(base[i])
  }
  return ans
}

LC15 三数之和

func threeSum(nums []int) [][]int {
    n := len (nums)
    ans := [][]int{}
    if n == 0 || n < 3 {
      return ans
    }

    sort.Ints(nums)
    for i := 0; i < n - 2; i ++ {
      if nums[i] > 0 {
        break
      }
      if i > 0 && nums[i] == nums[i - 1] {
        continue
      }
      if nums[i] + nums[i + 1] + nums[i + 2] > 0 {
        break
      }
      if nums[i] + nums[n -1] + nums[n - 2] < 0 {
        continue
      }

      l, r := i + 1, n - 1
      for l < r {
        s := nums[i] + nums[l] + nums[r]
        if s < 0 {
          l ++
        } else if s > 0 {
          r --
        } else {
          ans = append(ans, []int{nums[i], nums[l], nums[r]})
          l ++
          for l < r && nums[l] == nums[l - 1] {
            l ++ 
          }
          r -- 
          for l < r && nums[r] == nums[r + 1] {
            r -- 
          }
        }
      }
    }

    return ans
}

LC16 最接近的三数之和

func threeSumClosest(nums []int, target int) int {
    n := len(nums)
    sort.Ints(nums)
    ans := nums[0] + nums[1] + nums[2]
    for i := 0; i < n; i ++ {
      l, r := i + 1, n - 1
      for l < r {
        s := nums[i] + nums[l] + nums[r]
        if abs(s - target) < abs(ans - target) {
          ans = s
        }
        if s < target {
          l ++
        } else if s > target {
          r --
        } else {
          return ans
        }
      }
    }
    return ans
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

LC17 电话号码的字母组合

var (
  s []string
  ans []string
)

func dfs(digits string, u int, path string) {
    if u == len(digits) {
      ans = append(ans, path)
      return 
    }

    for _, c := range s[digits[u] - '0'] {
      dfs(digits, u + 1, path + string(c))
    }
}

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }

    s = []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
    ans = []string{}

    dfs(digits, 0, "")

    return ans
}

LC18 四数之和

func fourSum(nums []int, target int) [][]int {
    n := len(nums)
    ans := [][]int{}
    if n == 0 || n < 4 {
        return ans
    }

    sort.Ints(nums)
    for i := 0; i < n - 3; i ++ {
        if i > 0 && nums[i] == nums[i - 1] {
            continue
        }
        for j := i + 1; j < n - 2; j ++ {
            if j > i + 1 && nums[j] == nums[j - 1] {
                continue
            }
            l, r := j + 1, n - 1
            for l < r {
                s := nums[i] + nums[j] + nums[l] + nums[r]
                if s < target {
                    l ++
                } else if s > target {
                    r -- 
                } else {
                    ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
                    l ++ 
                    for l < r && nums[l] == nums[l - 1] {
                        l ++ 
                    }
                    r -- 
                    for l < r && nums[r] == nums[r + 1] {
                        r -- 
                    }
                }
            }
        }
    }

    return ans
}

LC19 删除链表的倒数第N个结点

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{-1, head}
    slow, fast := dummy, dummy

    for i := 0; i <= n; i ++ {
      fast = fast.Next
    }

    for fast != nil {
      slow = slow.Next
      fast = fast.Next
    }

    slow.Next = slow.Next.Next

    return dummy.Next
}

LC20 有效的括号

func isValid(s string) bool {
    stk := []byte{}
    for _, c := range s {
      if c == '(' || c == '[' || c == '{' {
        stk = append(stk, byte(c))
      } else {
        if len(stk) == 0 {
          return false
        }
        x := stk[len(stk) - 1]
        stk = stk[ : len(stk) - 1]
        if c == ')' && x != '(' {
          return false
        }
        if c == ']' && x != '[' {
          return false
        }
        if c == '}' && x != '{' {
          return false
        }
      }
    }
    return len(stk) == 0
}

LC21 合并两个有序链表

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{-1, nil}
    cur := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
          cur.Next =l1
          cur = cur.Next
          l1 = l1.Next
        } else {
          cur.Next = l2
          cur = cur.Next
          l2 = l2.Next
        }
    }
    if l1 != nil {
        cur.Next = l1
    }
    if l2 != nil {
        cur.Next = l2
    }

    return dummy.Next
}

LC22 括号生成

var (
    n, m int
    ans []string
)

func dfs(u, lc int, seq string) {
	if u == m {
		ans = append(ans, seq)
		return
	}

	if lc < n {
		dfs(u + 1, lc + 1, seq + "(")
	}
	if u - lc < lc {
		dfs(u + 1, lc, seq + ")")
	}
}

func generateParenthesis(_n int) []string {
	n, m = _n, 2*_n
    ans = []string{}
	dfs(0, 0, "")
	return ans
}

LC23 合并K个升序链表

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())  return nullptr;

        auto cmp = [](auto a, auto b) {
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q;
        
        for (int i = 0; i < lists.size(); ++ i)
            if (lists[i])
                q.push(lists[i]);
        
        auto dummy = new ListNode(-1), cur = dummy;
        while (q.size()) {
            auto t = q.top(); q.pop();
            cur = cur->next = t;
            if (t->next)  q.push(t->next);
        }

        return dummy->next;
    }
};

LC24 两两交换链表中的节点

func swapPairs(head *ListNode) *ListNode {
    n, k := 0, 2
    for p := head; p != nil; p = p.Next {
        n ++ 
    }

    dummy := &ListNode{-1, head}
    p0 := dummy
    var pre *ListNode
    pre = nil
    cur := head

    for n >= k {
        for i := 0; i < k; i ++ {
            nxt := cur.Next
            cur.Next = pre
            pre = cur
            cur = nxt
        }

        tmp := p0.Next
        p0.Next.Next = cur
        p0.Next = pre
        p0 = tmp
        n -= k
    }

    return dummy.Next
}

LC25 K个一组翻转链表

func reverseKGroup(head *ListNode, k int) *ListNode {
    n := 0
    for p := head; p != nil; p = p.Next {
        n ++ 
    }

    dummy := &ListNode{-1, head}
    p0 := dummy
    var pre *ListNode
    pre = nil
    cur := head

    for n >= k {
        for i := 0; i < k; i ++ {
            nxt := cur.Next
            cur.Next = pre
            pre = cur
            cur = nxt
        }

        tmp := p0.Next
        p0.Next.Next = cur
        p0.Next = pre
        p0 = tmp

        n -= k
    }

    return dummy.Next
}

LC26 删除有序数组中的重复项

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    k := 0
    for i := 0; i < len(nums); i ++ {
        if i == 0 || nums[i] != nums[i - 1] {
            nums[k] = nums[i]
            k ++ 
        }
    }

    return k
}

LC27 移除元素

func removeElement(nums []int, val int) int {
    k := 0
    for _, x := range nums {
        if x != val {
            nums[k] = x
            k ++ 
        }
    }
    return k
}

LC28 找出字符串中第一个匹配项的下标

func strStr(s string, p string) int {
    if len(p) == 0 {
        return 0
    }

    n, m := len(s), len(p)
    s = " " + s
    p = " " + p
    ne := make([]int, m + 1)

    ne[0] = 0
    ne[1] = 0
    for i, j := 2, 0; i <= m; i ++ {
        for j > 0 && p[i] != p[j + 1] {
            j = ne[j]
        }
        if p[i] == p[j + 1] {
            j ++
        }
        ne[i] = j
    }

    for i, j := 1, 0; i <= n; i ++ {
        for j > 0 && s[i] != p[j + 1] {
            j = ne[j]
        }
        if s[i] == p[j + 1] {
            j ++
        }
        if j == m {
            return i - m
        }
    } 

    return -1
}
func strStr(s string, p string) int {
    if len(p) == 0 {
        return 0
    }

    n, m := len(s), len(p)
    s = " " + s
    p = " " + p
    p += string(make([]byte, n + 1))
    p = p[ : m + 1] + "#" + p[m + 2 : ]
  
    ne := make([]int, n + m + 2)

    for i := 1; i <= n; i ++ {
        p = p[ : m + 1 + i] + string(s[i]) + p[m + 1 + i + 1 : ]
    }

    ne[0], ne[1] = 0, 0
    for i, j := 2, 0; i <= n + m + 1; i ++ {
        for j > 0 && p[i] != p[j + 1] {
            j = ne[j]
        }
        if p[i] == p[j + 1] {
            j ++
        }
        ne[i] = j
    }

    for i := m + 2; i <= n + m + 1; i ++ {
        if ne[i] == m {
            return i - 2 * m - 1
        }
    }

    return -1
}

LC29 两数相除

func divide(a int, b int) int {
    if a == 0 {
        return 0
    }
    if a == math.MinInt32 && b == -1 {
        return math.MaxInt32
    }
    if b == math.MinInt32 {
        if a == b {
            return 1
        }
        return 0
    }

    ans := 0
    sign := ((a ^ b) < 0)

    if a == math.MinInt32 {
        a -= -abs(b)
        ans ++
    }

    x, y := abs(a), abs(b)
    for i := 31; i >= 0; i -- {
        if x >> i >= y {
            x -= y << i
            if ans > math.MaxInt32 - (1 << i) {
                return math.MinInt32
            }
            ans += 1 << i
        }
    }

    if sign {
        return -ans
    }
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

LC30 串联所有单词的子串

func findSubstring(s string, words []string) []int {
    ans := []int{}
    if len(s) == 0 {
        return ans
    }
    n, m, d := len(s), len(words), len(words[0])
    mp := map[string]int{}
    for _, x := range words {
        mp[x] ++
    }

    for i := 0; i < d; i ++ {
        wd := map[string]int{}
        cnt := 0
        for l, r := i, i; r < n - d + 1; r += d {
            x := s[r : r + d]
            wd[x] ++
            cnt ++
            for wd[x] > mp[x] {
                y := s[l : l + d]
                wd[y] --
                cnt --
                l += d
            }
            if cnt == m {
                ans = append(ans, l)
            }
        }
    }

    return ans
}

LC31 下一个排列

func nextPermutation(nums []int)  {
    n, k := len(nums), len(nums) - 2
    for k >= 0 && nums[k] >= nums[k + 1] {
        k --
    }
    if k == -1 {
        reverse(nums, 0, n - 1)
    } else {
        l, r := k + 1, n - 1
        for l < r {
            mid := (l + r + 1) >> 1
            if nums[mid] > nums[k] {
                l = mid
            } else {
                r = mid - 1
            }
        }
        nums[k], nums[l] = nums[l], nums[k]
        reverse(nums, k + 1, n - 1)
    }
}

func reverse(nums []int, l, r int) {
    for l < r {
        nums[l], nums[r] = nums[r], nums[l]
        l ++ 
        r --
    }
}

LC32 最长有效括号

func longestValidParentheses(s string) int {
    n := len(s)
    if n == 0 {
        return 0
    }
    
    f := make([]int, n)
    ans := 0
    for i := 1; i < n; i ++  {
        if s[i] == ')' {
            if s[i] == '(' {
                if i >= 2 {
                    f[i] = f[i - 2] + 2
                } else {
                    f[i] = 2
                }
            } else {
                if i - f[i - 1] - 1 >= 0 && s[i - f[i - 1] - 1] == '(' {
                    if i - f[i - 1] - 2 >= 0 {
                        f[i] = f[i - 1] + 2 + f[i - f[i - 1] - 2]
                    } else {
                        f[i] = f[i - 1] + 2
                    }
                }
            }
            if f[i] > ans {
                ans = f[i]
            }
        }
    }

    return ans
}

LC33 搜索旋转排序数组

func search(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }

    n, l, r := len(nums), 0, len(nums) - 1
    for l < r {
        mid := (l + r + 1) >> 1
        if nums[mid] >= nums[0] {
            l = mid
        } else {
            r = mid - 1
        }
    }

    if target >= nums[0] {
        l = 0
    } else {
        l, r = r + 1, n - 1
    }

    for l < r {
        mid := (l + r) >> 1
        if nums[mid] >= target {
            r = mid
        } else {
            l = mid + 1
        }
    }

    if nums[r] == target {
        return r
    }
    return -1
}

LC34 在排序数组中查找元素的第一个和最后一个位置

func searchRange(nums []int, target int) []int {
    if len(nums) == 0 {
        return []int{-1, -1}
    }

    n, l, r := len(nums), 0, len(nums) - 1
    for l < r {
        mid := (l + r) >> 1
        if nums[mid] >= target {
            r = mid
        } else {
            l = mid + 1
        }
    }
    if nums[l] != target {
        return []int{-1, -1}
    }

    left := l
    l, r = 0, n - 1
    for l < r {
        mid := (l + r + 1) >> 1
        if nums[mid] <= target {
            l = mid
        } else {
            r = mid - 1
        }
    }

    return []int{left, r}
}

LC35 搜索插入位置

func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums)  
    for l < r {
        mid := (l + r) >> 1
        if nums[mid] >= target {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

LC36 有效的数独

func isValidSudoku(g [][]byte) bool {
    var row, col, sub [9]int
    for i := 0; i < len(g); i++ {
        for j := 0; j < len(g[0]); j++ {
            if g[i][j] != '.' {
                k := int(g[i][j] - '0')
                idx := (i / 3) * 3 + j / 3

                if (row[i] & (1 << k)) != 0 ||
                    (col[j] & (1 << k)) != 0 || 
                    (sub[idx] & (1 << k)) != 0 {
                        return false
                    }
                
                row[i] |= 1 << k
                col[j] |= 1 << k 
                sub[idx] |= 1 << k
            }
        }
    }

    return true
}

LC37 解数独

var (
    row, col, cell []int
)

func dfs(x, y int, g [][]byte) bool {
    if y == 9 {
        x ++
        y = 0
    }
    if x == 9 {
        return true
    }

    if g[x][y] == '.' {
        for i := 1; i <= 9; i ++ {
            idx := (x / 3) * 3 + y / 3
            if row[x] & (1 << i) == 0 && col[y] & (1 << i) == 0 && cell[idx] & (1 << i) == 0 {
                row[x] |= 1 << i
                col[y] |= 1 << i
                cell[idx] |= 1 << i
                g[x][y] = byte(i) + '0'

                if dfs(x, y + 1, g) {
                    return true
                }

                row[x] ^= 1 << i
                col[y] ^= 1 << i
                cell[idx] ^= 1 << i
                g[x][y] = '.'
            }
        }
    } else if dfs(x, y + 1, g) {
        return true
    }

    return false
}

func solveSudoku(board [][]byte) {
    row, col, cell = make([]int, 9), make([]int, 9), make([]int, 9)
    for i := 0; i < 9; i ++ {
        for j := 0; j < 9; j ++ {
            if board[i][j] != '.' {
                k := int(board[i][j] - '0')
                row[i] |= 1 << k
                col[j] |= 1 << k
                cell[(i / 3) * 3 + j / 3] |= 1 << k
            }
        }
    }

    dfs(0, 0, board)
}

LC38 外观数列

func countAndSay(n int) string {
    ans := "1"
    for i := 0; i < n - 1; i ++ {
        var t string
        for j, k := 0, 1; j < len(ans); j = k {
            for k < len(ans) && ans[k] == ans[j] {
                k ++
            }
            t += strconv.Itoa(k - j) + string(ans[j])
        }
        ans = t
    }
    return ans
}

LC39 组合总和

var (
    c, path []int
    ans [][]int
)

func dfs(start, sum, target int) {
    if sum == target {
        tmp := make([]int, len(path))
        copy(tmp, path)
        ans = append(ans, tmp)
        return
    }

    for i := start; i < len(c) && sum + c[i] <= target; i ++ {
        sum += c[i]
        path = append(path, c[i])

        dfs(i, sum, target)

        sum -= c[i]
        path = path[ : len(path) - 1]
    }
}

func combinationSum(candidates []int, target int) [][]int {
    c = candidates
    ans, path = make([][]int, 0), make([]int, 0, len(c))
    sort.Ints(c)
    dfs(0, 0, target)
    return ans
}

LC40 组合总和II

var (
    c, path []int
    ans [][]int
)

func dfs(start, sum, target int) {
    if sum == target {
        tmp := make([]int, len(path))
        copy(tmp, path)
        ans = append(ans, tmp)
        return
    }

    for i := start; i < len(c) && sum + c[i] <= target; i ++ {
        if i > start && c[i] == c[i - 1] {
            continue
        }
        sum += c[i]
        path = append(path, c[i])
        
        dfs(i + 1, sum, target)

        sum -= c[i]
        path = path[ : len(path) - 1]
    }
}

func combinationSum2(candidates []int, target int) [][]int {
    c = candidates
    ans, path = make([][]int, 0), make([]int, 0, len(c))
    sort.Ints(c)
    dfs(0, 0, target)
    return ans
}

LC41 缺失的第一个正数

func firstMissingPositive(nums []int) int {
    n := len(nums)
    for i := 0; i < n; i ++ {
        for nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1] {
            nums[i], nums[nums[i] -1] = nums[nums[i] - 1], nums[i]
        }
    }

    for i := 0; i < n; i ++ {
        if nums[i] != i + 1 {
            return i + 1
        }
    }

    return n + 1
}

LC42 接雨水

func trap(h []int) int {
    l, r, lm, rm, ans := 0, len(h) -1, 0, 0, 0
    for l < r {
        lm = max(lm, h[l])
        rm = max(rm, h[r])
        if lm < rm {
            ans += lm - h[l]
            l ++
        } else {
            ans += rm - h[r]
            r --
        }
    }
    return ans
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
func trap(h []int) int {
    stk := []int {}
    ans := 0
    for i := 0; i < len(h); i ++ {
        for len(stk) > 0 && h[stk[len(stk) - 1]] < h[i] {
            mid := stk[len(stk) - 1]
            stk = stk[ : len(stk) - 1]
            if len(stk) == 0 {
                break
            }
            height := min(h[stk[len(stk) - 1]], h[i]) - h[mid]
            width := i - stk[len(stk) - 1] - 1
            ans += height * width
        }
        stk = append(stk, i)
    }
    return ans
}

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

LC43 字符串相乘

func multiply(num1 string, num2 string) string {
    A, B := []int{}, []int{}
    n, m := len(num1), len(num2)

    for i := n - 1; i >= 0; i -- {
        A = append(A, int(num1[i] - '0'))
    }
    for i := m - 1; i >= 0; i -- {
        B = append(B, int(num2[i] - '0'))
    }

    C := make([]int, n + m)
    for i := 0; i < n; i ++ {
        for j := 0; j < m; j ++ {
            C[i + j] += A[i] * B[j]
        }
    }

    for i, t := 0, 0; i < len(C); i ++ {
        t += C[i]
        C[i] = t % 10
        t /= 10
    }

    k := len(C) - 1
    for k > 0 && C[k] == 0 {
        k --
    }

    ans := ""
    for k >= 0 {
        ans += string(C[k] + '0')
        k --
    }

    return ans
}

LC44 通配符匹配

func isMatch(s string, p string) bool {
    n, m := len(s), len(p)
    s = " " + s
    p = " " + p

    f := make([][]bool, n + 1)
    for i := 0; i <= n; i ++ {
        f[i] = make([]bool, m + 1)
    }

    f[0][0] = true
    for i := 0; i <= n; i ++ {
        for j := 1; j <= m; j ++ {
            if p[j] == '*' {
                f[i][j] = f[i][j - 1] || (i > 0 && f[i - 1][j])
            } else {
                f[i][j] = i > 0 && f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?')
            }
        }
    }

    return f[n][m]
}

LC45 跳跃游戏II

func jump(nums []int) int {
    n := len(nums)
    f := make([]int, n)

    f[0] = 0
    for i, j := 1, 0; i < n; i ++  {
        for j < n && j + nums[j] < i {
            j ++
        }
        f[i] = f[j] + 1
    }

    return f[n - 1]
}

LC46 全排列

var (
    st []bool
    ans [][]int
    a, path []int
)

func dfs(u int) {
    if u == len(a) {
        tmp := make([]int, len(path))
        copy(tmp, path)
        ans = append(ans, tmp)
        return
    }

    for i := 0; i < len(a); i ++ {
        if !st[i] {
            path = append(path, a[i])
            st[i] = true
            dfs(u + 1)
            st[i] = false
            path = path[ : len(path) - 1]
        }
    }
}

func permute(nums []int) [][]int {
    a = nums
    n := len(nums)
    st = make([]bool, n)
    ans, path = make([][]int, 0), make([]int, 0, n)

    dfs(0)

    return ans
}

LC47 全排列II

var (
    st []bool
    a, path []int
    ans [][]int
)

func dfs(u int) {
    if u == len(a) {
        tmp := make([]int, len(path))
        copy(tmp, path)
        ans = append(ans, tmp)
        return 
    }

    for i := 0; i < len(a); i ++ {
        if i > 0 && a[i] == a[i - 1] && !st[i - 1] {
            continue
        }
        if !st[i] {
            path = append(path, a[i])
            st[i] = true
            dfs(u + 1)
            st[i] = false
            path = path[ : len(path) - 1]
        }
    }
}

func permuteUnique(nums []int) [][]int {
    a = nums
    n := len(nums)
    st = make([]bool, n)
    ans, path = make([][]int, 0), make([]int, 0, n)
    sort.Ints(nums)

    dfs(0)

    return ans
}

LC48 旋转图像

func rotate(g [][]int)  {
    n := len(g)

    for i := 0; i < n / 2; i ++ {
        for j := 0; j < n; j ++ {
            g[i][j], g[n - i - 1][j] = g[n - i - 1][j], g[i][j]
        }
    }

    for i := 0; i < n; i ++ {
        for j := 0; j < i; j ++ {
            g[i][j], g[j][i] = g[j][i], g[i][j]
        }
    }
}

LC49 字母异位词分组

func groupAnagrams(strs []string) [][]string {
    mp := map[string][]string{}

    for _, str := range strs {
        s := []byte(str)
        sort.Slice(s, func(i, j int) bool {
            return s[i] < s[j]
        })
        t := string(s)
        mp[t] = append(mp[t], str)
    }

    ans := [][]string{}
    for _, v := range mp {
        ans = append(ans, v)
    }

    return ans
}

LC50 Pow(x, n)

func qmi(a float64, b int) float64 {
    ans := 1.0
    if b < 0 {
        b = -b
    }
    for b > 0 {
        if b & 1 > 0 {
            ans *= a
        }
        a *= a
        b >>= 1
    }
    return ans
}

func myPow(x float64, n int) float64 {
    sign := n < 0
    ans := qmi(x, n)
    if sign {
        return 1 / ans
    }
    return ans
}

LC51 N皇后

var (
    n int
    path []string
    ans [][]string
    col, dg, udg []bool
)

func dfs(u int) {
    if u == n {
        tmp := make([]string, n)
        copy(tmp, path)
        ans = append(ans, tmp)
        return 
    }

    for i := 0; i < n; i ++ {
        if !col[i] && !dg[u + i] && !udg[u - i + n] {
            path[u] = path[u][ : i] + "Q" + path[u][i + 1 : ]
            col[i], dg[u + i], udg[u - i + n] = true, true, true
            dfs(u + 1)
            col[i], dg[u + i], udg[u - i + n] = false, false, false 
            path[u] = path[u][ : i] + "." + path[u][i + 1 : ]
        }
    }
}

func solveNQueens(_n int) [][]string {
    n = _n
    path = make([]string, n)
    ans = [][]string{}
    col, dg, udg = make([]bool, 2 * n), make([]bool, 2 * n), make([]bool, 2 * n)

    for i := range path {
        path[i] = string(make([]byte, n))
        for j := 0; j < n; j ++  {
            path[i] = path[i][ : j] + "." + path[i][j + 1 : ]
        }
    }

    dfs(0)

    return ans
}

LC52 N皇后II

var (
    n, ans int
    path []string
    col, dg, udg []bool
)

func dfs(u int) {
    if u == n {
        ans ++
        return
    }

    for i := 0; i < n; i ++ {
        if !col[i] && !dg[u + i] && !udg[u - i + n] {
            path[u] = path[u][ : i] + "Q" + path[u][i + 1 : ]
            col[i], dg[u + i], udg[u - i + n] = true, true, true
            dfs(u + 1)
            col[i], dg[u + i], udg[u - i + n] = false, false, false
            path[u] = path[u][ : i] + "." + path[u][i + 1 : ]
        }
    }
}

func totalNQueens(_n int) int {
    n, ans = _n, 0
    path = make([]string, n)
    col, dg, udg = make([]bool, 2 * n), make([]bool, 2 * n), make([]bool, 2 * n)

    for i := range path {
        path[i] = string(make([]byte, n))
        for j := 0; j < n; j ++  {
            path[i] = path[i][ : j] + "." + path[i][j + 1 : ]
        }
    }

    dfs(0)

    return ans
}

LC53 最大子数组和

func maxSubArray(nums []int) int {
    s, ans := 0, math.MinInt
    for i := 0; i < len(nums); i ++ {
        if s > 0 {
            s += nums[i]
        } else {
            s = nums[i]
        }
        if s > ans {
            ans = s
        }
    }
    return ans
}

LC54 螺旋矩阵

func spiralOrder(g [][]int) []int {
    dx := []int{0, 1, 0, -1}
    dy := []int{1, 0, -1, 0}
    n, m := len(g), len(g[0])
    st := make([][]bool, n)
    for i := 0; i < n; i ++ {
        st[i] = make([]bool, m)
    }

    ans := []int{}
    x, y, d := 0, 0, 0
    for i := 0; i < n * m; i ++ {
        ans = append(ans, g[x][y])
        st[x][y] = true
        a, b := x + dx[d], y + dy[d]
        if a < 0 || a >= n || b < 0 || b >= m || st[a][b] {
            d = (d + 1) % 4
            a, b = x + dx[d], y + dy[d]
        }
        x, y = a , b
    }

    return ans
}

LC55 跳跃游戏

func canJump(nums []int) bool {
    for i, j := 1, 0; i < len(nums); i ++ {
        for j < i && j + nums[j] < i {
            j ++ 
        }
        if j == i {
            return false
        }
    }
    return true
}

LC56 合并区间

func merge(a [][]int) [][]int {
    ans := [][]int{}
    sort.Slice(a, func(i, j int) bool {
        if a[i][0] != a[j][0] {
            return a[i][0] < a[j][0]
        }
        return a[i][1] < a[j][1]
    })

    lastL, lastR := a[0][0], a[0][1]
    for i := 1; i < len(a); i ++ {
        if a[i][0] > lastR {
            ans = append(ans, []int{lastL, lastR})
            lastL, lastR = a[i][0], a[i][1]
        } else {
            lastR = max(lastR, a[i][1])
        }
    }
    ans = append(ans, []int{lastL, lastR})

    return ans
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

lC57 插入区间

func insert(a [][]int, b []int) [][]int {
    ans := [][]int{}
    n, k := len(a), 0

    for k < n && b[0] > a[k][1] {
        ans = append(ans, a[k])
        k ++
    }

    if k < n {
        b[0] = min(b[0], a[k][0])
        for k < n && a[k][0] <= b[1] {
            b[1] = max(b[1], a[k][1])
            k ++
        }
    }
    ans = append(ans, b)

    for k < n {
        ans = append(ans, a[k])
        k ++
    }

    return ans
}

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

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

LC58 最后一个单词的长度

func lengthOfLastWord(s string) int {
    i, ans := len(s) - 1, 0
    for s[i] == ' ' {
        i --
    }
    for i >= 0 && s[i] != ' ' {
        ans ++
        i --
    }
    return ans
}

LC59 螺旋矩阵II

func generateMatrix(n int) [][]int {
    dx, dy := []int{0, 1, 0, -1}, []int{1, 0, -1, 0}
    g := make([][]int, n)
    for i := 0; i < n; i ++ {
        g[i] = make([]int, n)
    }

    x, y, d, num := 0, 0, 0, 0
    for i := 0; i < n * n; i ++ {
        num ++
        g[x][y] = num
        a, b := x + dx[d], y + dy[d]
        if a < 0 || a >= n || b < 0 || b >= n || g[a][b] != 0 {
            d = (d + 1) % 4
            a, b = x + dx[d], y + dy[d]
        }
        x, y = a, b 
    }

    return g
}

LC60 排列序列

func getPermutation(n int, k int) string {
    v := ""
    for i := 1; i <= n; i ++ {
        v += strconv.Itoa(i)
    }

    fact := make([]int, n + 1)
    fact[0] = 1
    for i := 1; i <= n; i ++ {
        fact[i] = fact[i - 1] * i
    }

    k --
    ans := ""
    for i := n; i > 0; i -- {
        t := k / fact[i - 1]
        r := k % fact[i - 1]
        k = r
        ans += string(v[t])
        v = v[ : t] + v[t + 1 :]
    }

    return ans
}

LC61旋转链表

func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil {
        return head
    }
    n := 0
    p := head
    for p != nil {
        p = p.Next
        n ++
    }

    k %= n
    if k == 0 {
        return head
    }

    slow, fast := head, head
    for k > 0 && fast != nil {
        fast = fast.Next
        k --
    }

    for fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }
    fast.Next = head
    head = slow.Next
    slow.Next = nil
    
    return head
}

LC62 不同路径

func uniquePaths(m int, n int) int {
    f := make([][]int, m)
    for i := 0; i < m; i ++ {
        f[i] = make([]int, n)
    }

    for i := 0; i < m; i ++ {
        for j := 0; j < n; j ++ {
            if i == 0 || j == 0 {
                f[i][j] = 1
            } else {
                f[i][j] = f[i - 1][j] + f[i][j - 1]
            }
        }
    }

    return f[m - 1][n - 1]
}
func uniquePaths(m int, n int) int {
    f := make([][]int, m)
    for i := 0; i < m; i ++ {
        f[i] = make([]int, n)
    }

    for i := 0; i < m; i ++ {
        for j := 0; j < n; j ++ {
            if i == 0 && j == 0 {
                f[i][j] = 1
            } else {
                if i > 0 {
                    f[i][j] += f[i - 1][j]
                }
                if j > 0 {
                    f[i][j] += f[i][ j - 1]
                }
            }
        }
    }

    return f[m - 1][n - 1]
}
func uniquePaths(m int, n int) int {
    f := make([]int, n)
    f[0] = 1
    for i := 0; i < m; i ++ {
        for j := 1; j < n; j ++ {
            f[j] += f[j - 1]
        }
    }
    return f[n - 1]
}

LC63 不同路径II

func uniquePathsWithObstacles(g [][]int) int {
    m, n := len(g), len(g[0])
    f := make([][]int, m)
    for i := 0; i < m; i ++ {
        f[i] = make([]int, n)
    }

    for i := 0; i < m; i ++ {
        for j := 0; j < n; j ++ {
            if g[i][j] == 1 {
                continue
            }
            if i == 0 && j == 0 {
                f[i][j] = 1
            } else {
                if i > 0 {
                    f[i][j] += f[i - 1][j]
                }
                if j > 0 {
                    f[i][j] += f[i][j - 1]
                }
            }
        }
    }

    return f[m - 1][n - 1]
}
func uniquePathsWithObstacles(g [][]int) int {
    m, n := len(g), len(g[0])
    f := make([][]int, m)
    for i := 0; i < m; i ++ {
        f[i] = make([]int, n)
    }

    for i := 0; i < m && g[i][0] == 0; i ++ {
        f[i][0] = 1
    }
    for j := 0; j < n && g[0][j] == 0; j ++ {
        f[0][j] = 1
    }

    for i := 1; i < m; i ++ {
        for j := 1; j < n; j ++ {
            if g[i][j] == 0 {
                f[i][j] = f[i - 1][j] + f[i][j - 1]
            }
        }
    }

    return f[m - 1][n - 1]
}
func uniquePathsWithObstacles(g [][]int) int {
    m, n := len(g), len(g[0])
    f := make([]int, n)
    if g[0][0] == 0 {
        f[0] = 1
    } else {
        f[0] = 0
    }
    
    for i := 0; i < m; i ++ {
        for j := 0; j < n; j ++ {
            if g[i][j] == 1 {
                f[j] = 0
                continue
            }
            if j > 0 && g[i][j - 1] == 0 {
                f[j] += f[j - 1]
            }
        }
    }
    return f[n - 1]
}

LC64 最小路径和

func minPathSum(g [][]int) int {
	m, n := len(g), len(g[0])

	f := make([][]int, m)
	for i := 0; i < m; i ++ {
		f[i] = make([]int, n)
		for j := 0; j < n; j++ {
			f[i][j] = math.MaxInt32
		}
	}

	for i := 0; i < m; i ++ {
		for j := 0; j < n; j ++ {
			if i == 0 && j == 0 {
				f[i][j] = g[i][j]
			} else {
				if i > 0 {
					f[i][j] = min(f[i][j], f[i - 1][j] + g[i][j])
				}
				if j > 0 {
					f[i][j] = min(f[i][j], f[i][j - 1] + g[i][j])
				}
			}
		}
	}

	return f[m - 1][n - 1]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func minPathSum(g [][]int) int {
    m, n := len(g), len(g[0])
    f := make([][]int, m)
    for i := range f {
        f[i] = make([]int, n)
    }

    for i := 0; i < m; i ++ {
        for j := 0; j < n; j ++ {
            if i == 0 && j == 0 {
                f[i][j] = g[i][j]
            } else if i == 0 {
                f[i][j] = f[i][j - 1] + g[i][j]
            } else if j == 0 {
                f[i][j] = f[i - 1][j] + g[i][j]
            } else {
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + g[i][j]
            }
        }
    }

    return f[m - 1][n - 1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func minPathSum(g [][]int) int {
    m, n := len(g), len(g[0])
    f := make([][]int, m)
    for i := 0; i < m; i ++ {
        f[i] = make([]int, n)
    }

    f[0][0] = g[0][0]
    for i := 1; i < m; i ++ {
        f[i][0] = f[i - 1][0] + g[i][0]
    }
    for j := 1; j < n; j ++ {
        f[0][j] = f[0][j - 1] + g[0][j]
    }

    for i := 1; i < m; i ++ {
        for j := 1; j < n; j ++ {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + g[i][j]
        }
    }

    return f[m - 1][n - 1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func minPathSum(g [][]int) int {
	m, n := len(g), len(g[0])

	f := make([][]int, m + 1)
	for i := 0; i <= m; i ++ {
		f[i] = make([]int, n + 1)
		for j := 0; j <= n; j ++ {
			f[i][j] = math.MaxInt32
		}
	}

	f[1][1] = g[0][0]
	for i := 1; i <= m; i ++ {
		for j := 1; j <= n; j ++ {
			if i == 1 && j == 1 {
				continue
			}
			f[i][j] = min(f[i - 1][j], f[i][j - 1]) + g[i - 1][j - 1]
		}
	}

	return f[m][n]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

LC65 有效数字

func check(s string, l, r int, mustInt bool) bool {
    if l < len(s) && (s[l] == '+' || s[l] == '-') {
        l ++
    }

    point, digit := false, false
    for i := l; i <= r && i < len(s); i++ {
        if s[i] == '.' {
            if point || mustInt {
                return false
            }
            point = true
        } else if s[i] >= '0' && s[i] <= '9' {
            digit = true
        } else {
            return false
        }
    }
    
    return digit
}

func isNumber(s string) bool {
    idx, n := -1, len(s)
    for i := 0; i < n; i++ {
        if s[i] == 'e' || s[i] == 'E' {
            if idx == -1 {
                idx = i
            } else {
                return false
            }
        }
    }

    if idx == -1 {
        return check(s, 0, n-1, false)
    }

    if idx >= n {
        return false
    }
    return check(s, 0, idx-1, false) && check(s, idx+1, n-1, true)
}

LC66 加一

func plusOne(digits []int) []int {
    t := 1
    for i := len(digits) - 1; i >= 0; i -- {
        t += digits[i]
        digits[i] = t % 10
        t /= 10
    }
    if t > 0 {
        digits = append([]int{t}, digits...)
    }
    return digits
}

LC67 二进制求和

func reverse(str string) string {
    s := []byte(str)
    for i, j := 0, len(s) - 1; i < j; i, j = i + 1, j - 1 {
        s[i], s[j] = s[j], s[i]
    }
    return string(s)
}

func addBinary(a string, b string) string {
    n, m := len(a), len(b)
    a, b = reverse(a), reverse(b)
    var ans strings.Builder

    for i, t := 0, 0; i < n || i < m || t > 0; i ++ {
        if i < n {
            t += int(a[i] - '0')
        }
        if i < m {
            t += int(b[i] - '0')
        }
        ans.WriteString(strconv.Itoa(t % 2))
        t /= 2
    }

    return reverse(ans.String())
}

LC68 文本左右对齐

func fullJustify(words []string, maxWidth int) []string {
    n := len(words)
    ans := []string{}

    for i := 0; i < n; {
        lineLen := len(words[i])
        j := i + 1
        for j < n && lineLen + 1 + len(words[j]) <= maxWidth {
            lineLen += 1 + len(words[j])
            j ++
        }

        var line strings.Builder
        if j == n || j - i == 1 {
            line.WriteString(words[i])
            for k := i + 1; k < j; k ++ {
                line.WriteByte(' ')
                line.WriteString(words[k])
            }
            line.WriteString(strings.Repeat(" ", maxWidth - line.Len()))
        } else {
            gap := j - i - 1
            if gap > 0 {
                space := maxWidth - lineLen + gap
                line.WriteString(words[i])
                for k := 0; k < space % gap; k ++ {
                    line.WriteString(strings.Repeat(" ", space / gap + 1))
                    line.WriteString(words[i + k + 1])
                }
                for k := space % gap; k < gap; k ++ {
                    line.WriteString(strings.Repeat(" ", space / gap))
                    line.WriteString(words[i + k + 1])
                }
            }
        }

        ans = append(ans, line.String())
        i = j
    }

    return ans
}

LC69 x的平方根

func mySqrt(x int) int {
    l, r := 0, x
    for l < r {
        mid := (l + r + 1) >> 1
        if mid * mid <= x {
            l = mid
        } else {
            r = mid - 1
        }
    }
    return l
}

LC70 爬楼梯

func climbStairs(n int) int {
    f := make([]int, n + 1)
    f[0], f[1] = 1, 1
    for i := 2; i <= n; i ++ {
        f[i] = f[i - 1] + f[i - 2]
    }
    return f[n]
}

LC71简化路径

func simplifyPath(path string) string {
    ans, name := "", ""
    if path[len(path) - 1] != '/' {
        path += "/"
    }
    for i := 0; i < len(path); i ++ {
        if (path[i] != '/' ) {
            name += string(path[i])
        } else {
            if name == ".." {
                for len(ans) > 0 && ans[len(ans) - 1] != '/' {
                    ans = ans[: len(ans) - 1]
                }
                if len(ans) > 0 {
                    ans = ans[: len(ans) - 1]
                }
            } else if (name != "." && name != "") {
                ans += "/" + name
            }
            name = ""
        } 
    }
    if len(ans) == 0 {
        ans = "/"
    }
    return ans
}   

LC72 编辑距离

func minDistance(a string, b string) int {
    n, m := len(a), len(b)
    a, b = " " + a, " " + b
    f := make([][]int, n + 1)
    for i := 0; i <= n; i ++ {
        f[i] = make([]int, m + 1)
    }

    for i := 0; i <= n; i ++ {
        f[i][0] = i
    }
    for j := 0; j <= m; j ++ {
        f[0][j] = j
    }

    for i := 1; i <= n; i ++ {
        for j := 1; j <= m; j ++ {
            if a[i] == b[j] {
                f[i][j] = f[i - 1][j - 1]
            } else {
                f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1
            }
        }
    }

    return f[n][m]
}

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

LC73 矩阵置零

func setZeroes(g [][]int)  {
    n, m := len(g), len(g[0])
    r0, c0 := false, false
    
    for i := 0; i < n; i ++ {
        for j := 0; j < m; j ++ {
            if g[i][j] == 0 {
                if i == 0 {
                    r0 = true
                }
                if j == 0 {
                    c0 = true
                }
                g[i][0], g[0][j] = 0, 0
            }
        }
    }

    for i := 1; i < n; i ++ {
        if g[i][0] == 0 {
            for j := 1; j < m; j ++ {
                g[i][j] = 0
            }
        }
    }

    for j := 1; j < m; j ++ {
        if g[0][j] == 0 {
            for i := 1; i < n; i ++ {
                g[i][j] = 0
            }
        }
    }

    if r0 {
        for j := 0; j < m; j ++ {
            g[0][j] = 0
        }
    }

    if c0 {
        for i := 0; i < n; i ++ {
            g[i][0] = 0
        }
    }
}

LC74 搜索二维矩阵

func searchMatrix(g [][]int, target int) bool {
    n, m := len(g), len(g[0])
    if n == 0 || m == 0 {
        return false
    }

    x, y := 0, m - 1
    for x < n && y >= 0 {
        if g[x][y] < target {
            x ++
        } else if g[x][y] > target {
            y --
        } else {
            return true
        }
    }

    return false
}

LC75 颜色分类

func sortColors(nums []int)  {
    p0, p2 := 0, len(nums) - 1
    for i := 0; i <= p2; {
        if nums[i] == 0 {
            nums[i], nums[p0] = nums[p0], nums[i]
            i ++
            p0 ++
        } else if nums[i] == 1 {
            i ++
        } else {
            nums[i], nums[p2] = nums[p2], nums[i]
            p2 --
        }
    }
}

LC76 最小覆盖子串

func minWindow(s string, t string) string {
  if len(s) < len(t) {
        return ""
    }

    mp := map[byte]int{}
    for _, c := range t {
        mp[byte(c)] ++
    }

    start, need, length := 0, len(mp), math.MaxInt32
    for l, r := 0, 0; r < len(s); r ++ {
        mp[s[r]] --
        if mp[s[r]] == 0 {
            need --
        }

        for need == 0 {
            if r - l + 1 < length {
                start = l
                length = r - l + 1
            }
            mp[s[l]] ++
            if mp[s[l]] > 0 {
                need ++
            }
            l ++
        }
    }

    if length == math.MaxInt32 {
        return ""
    }
    return s[start : start + length]
}

LC77 组合

var (
    n, k int
    path []int
    ans [][]int
)

func dfs(start int) {
    if len(path) + (n - start + 1) < k {
        return 
    }
    if k == len(path) {
        tmp := make([]int, len(path))
        copy(tmp, path)
        ans = append(ans, tmp)
        return
    }

    for i := start; i <= n; i ++ {
        path = append(path, i)
        dfs(i + 1)
        path = path[ : len(path) - 1]
    }
}

func combine(_n int, _k int) [][]int {
    n, k = _n, _k
    path, ans = make([]int, 0, k), make([][]int, 0)
    dfs(1)
    return ans
}

LC78 子集

var (
    a, path []int
    ans [][]int
)

func dfs(start int) {
    tmp := make([]int, len(path))
    copy(tmp, path)
    ans = append(ans, tmp)

    for i := start; i < len(a); i ++ {
        path = append(path, a[i])
        dfs(i + 1)
        path = path[ : len(path) - 1]
    }
}

func subsets(nums []int) [][]int {
    a = nums
    path, ans = make([]int, 0, len(a)), make([][]int, 0)
    dfs(0)
    return ans
}
var (
    a, path []int
    ans [][]int
)

func dfs(u int) {
    if u >= len(a) {
        tmp := make([]int, len(path))
        copy(tmp, path)
        ans = append(ans, tmp)
        return
    }

    dfs(u + 1)

    path = append(path, a[u])
    dfs(u + 1)
    path = path[ : len(path) - 1]
}

func subsets(nums []int) [][]int {
    a = nums
    path, ans = make([]int, 0, len(a)), make([][]int, 0)
    dfs(0)
    return ans
}
func subsets(nums []int) [][]int {
    ans := [][]int{}
    n := len(nums)

     for i := 0; i < (1 << n); i ++ {
       tmp := []int{}
        for j := 0; j < n; j ++ {
            if (i >> j & 1) != 0 {
                tmp = append(tmp, nums[j])
            }
        }
        ans = append(ans, tmp)
     }

     return ans
}

LC79 单词搜索

var (
    n, m int
    dx = [4]int{0, 1, 0, -1}
    dy = [4]int{-1, 0, 1, 0}
)

func dfs(board [][]byte, word string, u, x, y int) bool {
    if board[x][y] != word[u] {
        return false
    }
    if u >= len(word) - 1 {
        return true
    }

    t := board[x][y]
    board[x][y] = '#'

    for i := 0; i < 4; i ++ {
        a, b := x + dx[i], y + dy[i]
        if a < 0 || a >= n || b < 0 || b >= m || board[a][b] == '#' {
            continue
        }
        if dfs(board, word, u + 1, a, b) {
            return true
        }
    }

    board[x][y] = t

    return false
}

func exist(board [][]byte, word string) bool {
    n, m = len(board), len(board[0])
    for i := 0; i < n; i ++ {
        for j := 0; j < m; j ++ {
            if dfs(board, word, 0, i, j) {
                return true
            }
        }
    }
    return false
}

LC80 删除有序数组中的重复项II

func solve(nums []int, k int) int {
    i := 0
    for _, x := range nums {
        if i < k || nums[i - k] != x {
            nums[i] = x
            i ++
        }
    }
    return i
}

func removeDuplicates(nums []int) int {
    return solve(nums, 2)
}

LC81 搜索旋转排序数组II

func search(nums []int, target int) bool {
    n := len(nums) - 1
    for n >= 0 && nums[n] == nums[0] {
        n -- 
    }
    if n < 0 {
        return nums[0] == target
    }

    l, r := 0, n
    for l < r {
        mid := (l + r + 1) >> 1
        if nums[mid] >= nums[0] {
            l = mid
        } else {
            r = mid - 1
        }
    }
    if target >= nums[0] {
        l = 0
    } else {
        l, r = r + 1, n
    }

    for l < r {
        mid := (l + r) >> 1
        if nums[mid] >= target {
            r = mid
        } else {
            l = mid + 1
        }
    }

    return nums[r] == target
}

LC82 删除排序链表中的重复元素II

func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    p := dummy

    for p.Next != nil {
        q := p.Next
        for q != nil && q.Val == p.Next.Val {
            q = q.Next
        }
        if p.Next.Next == q {
            p = p.Next
        } else {
            p.Next = q
        }
    }
    return dummy.Next
}

LC83 删除排序链表中的重复元素

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    p := head
    for p.Next != nil {
        if p.Val == p.Next.Val {
            p.Next = p.Next.Next
        } else {
            p = p.Next
        }
    }

    return head
}

LC84 柱状图中的最大矩形

func largestRectangleArea(h []int) int {
    n := len(h)
    l, r := make([]int, n + 2), make([]int, n + 2)
    stk := []int{}
    h = append([]int{-1}, h...)
    stk = append(stk, 0)

    for i := 1; i <= n; i ++ {
        for h[stk[len(stk) - 1]] >= h[i] {
            stk = stk[ : len(stk) - 1]
        }
        l[i] = stk[len(stk) - 1]
        stk = append(stk, i)
    }

    stk = []int{}
    h = append(h, -1)
    stk = append(stk, n + 1)
    for i := n; i > 0; i -- {
        for h[stk[len(stk) - 1]] >= h[i] {
            stk = stk[ : len(stk) - 1]
        }
        r[i] = stk[len(stk) - 1]
        stk = append(stk, i)
    }

    ans := 0
    for i := 1; i <= n; i ++ {
        if ans < (h[i] * (r[i] - l[i] - 1)) {
            ans = h[i] * (r[i] - l[i] - 1)
        }
    }

    return ans
}
func largestRectangleArea(h []int) int {
    n := len(h)
    h = append([]int{-1}, h...)
    h = append(h, -1)
    stk := []int{}
    stk = append(stk, 0)

    ans := 0
    for i := 1; i <= n + 1; i ++ {
        for h[i] < h[stk[len(stk) - 1]] {
            mid := stk[len(stk) - 1]
            stk = stk[: len(stk) - 1]
            width := i - stk[len(stk) - 1] - 1
            height := h[mid]
            if width * height > ans {
                ans = width * height
            }
        }
        stk = append(stk, i)
    }

    return ans 
}

LC85 最大矩形

func solve(h []int) int {
    n := len(h)
    l, r := make([]int, n), make([]int ,n)
    stk := []int{}

    for i := 0; i < n; i ++ {
        for len(stk) > 0 && h[stk[len(stk) - 1]] >= h[i] {
            stk = stk[: len(stk) - 1]
        }
        if len(stk) == 0 {
            l[i] = -1
        } else {
            l[i] = stk[len(stk) - 1]
        }
        stk = append(stk, i)
    }

    stk = []int{}

    for i := n - 1; i >= 0; i -- {
        for len(stk) > 0 && h[stk[len(stk) - 1]] >= h[i] {
            stk = stk[: len(stk) - 1]
        }
        if len(stk) == 0 {
            r[i] = n
        } else {
            r[i] = stk[len(stk) - 1]
        }
        stk = append(stk, i)
    }

    ans := 0
    for i := 0; i < n; i ++ {
        ans = max(ans, h[i] * (r[i] - l[i] - 1))
    }

    return ans
}

func maximalRectangle(g [][]byte) int {
    n, m := len(g), len(g[0])
    if n == 0 || m == 0 {
        return 0
    }
    s := make([][]int, n)
    for i := 0; i < n; i ++ {
        s[i] = make([]int, m)
    }

    for i := 0; i < n; i ++ {
        for j := 0; j < m; j ++ {
            if g[i][j] == '1' {
                if i > 0 {
                    s[i][j] = s[i - 1][j] + 1
                } else {
                    s[i][j] = 1
                }
            }
        }
    }

    ans := 0
    for i := 0; i < n; i ++ {
        ans = max(ans, solve(s[i]))
    }

    return ans
}

func max(x, y int )int {
    if x > y {
        return x
    }
    return y
}
func solve(h []int) int {
	n := len(h)
	ans := 0
	h = append([]int{-1}, h...)
	h = append(h, -1)
	stk := []int{}

	for i := 0; i < n + 2; i ++ {
		for len(stk) > 0 && h[stk[len(stk) - 1]] > h[i] {
			mid := stk[len(stk) - 1]
			stk = stk[ : len(stk) - 1]
			ans = max(ans, h[mid] * (i - stk[len(stk) - 1] - 1))
		}
		stk = append(stk, i)
	}

	return ans
}

func maximalRectangle(g [][]byte) int {
    n, m := len(g), len(g[0])
    if n == 0 || m == 0 {
        return 0
    }
    s := make([][]int, n)
    for i := 0; i < n; i ++ {
        s[i] = make([]int, m)
    }

    for i := 0; i < n; i ++ {
        for j := 0; j < m; j ++ {
            if g[i][j] == '1' {
                if i > 0 {
                    s[i][j] = s[i - 1][j] + 1
                } else {
                    s[i][j] = 1
                }
            }
        }
    }

    ans := 0
    for i := 0; i < n; i ++ {
        ans = max(ans, solve(s[i]))
    }

    return ans
}

func max(x, y int )int {
    if x > y {
        return x
    }
    return y
}

LC86 分隔链表

func partition(head *ListNode, x int) *ListNode {
    small, big := &ListNode{}, &ListNode{}
    ps, pb := small, big

    for p := head; p != nil; p = p.Next {
        if p.Val < x {
            ps.Next = p
            ps = ps.Next
        } else {
            pb.Next = p
            pb = pb.Next
        }
    }

    ps.Next = big.Next
    pb.Next = nil

    return small.Next
}

LC87 扰乱字符串

func isScramble(s1 string, s2 string) bool {
    n, m := len(s1), len(s2)
    if n != m {
        return false
    }
    f := make([][][]bool, n)
    for i := 0; i < n; i ++ {
        f[i] = make([][]bool, n)
        for j := 0; j < n; j ++ {
            f[i][j] = make([]bool, n + 1)
        }
    }

    for len := 1; len <= n; len ++ {
        for i := 0; i + len - 1 < n; i ++ {
            for j := 0; j + len - 1 < n; j ++ {
                if len == 1 {
                    f[i][j][len] = (s1[i] == s2[j])
                } else {
                    for k := 1; k < len; k ++ {
                        if (f[i][j][k] && f[i + k][j + k][len - k]) || (f[i][j + len - k][k] && f[i + k][j][len - k]) {
                            f[i][j][len] = true
                            break
                        }
                    }
                }
            }
        }
    }

    return f[0][0][n]
}

LC88 合并两个有序数组

func merge(nums1 []int, m int, nums2 []int, n int)  {
    i, j, k := m - 1, n - 1,  m + n - 1
    for i >= 0 && j >= 0 {
        if nums1[i] >= nums2[j] {
            nums1[k] = nums1[i]
            k -- 
            i -- 
        } else {
            nums1[k] = nums2[j]
            k -- 
            j -- 
        }
    }
    for j >= 0 {
        nums1[k] = nums2[j]
        k -- 
        j -- 
    }
}

LC89 格雷编码

func grayCode(n int) []int {
    ans := make([]int, 1)

    head := 1
    for n != 0 {
        for i := len(ans) - 1; i >= 0; i -- {
            ans = append(ans, head + ans[i])
        }
        head <<= 1
        n -- 
    }

    return ans
}

LC90 子集II

var (
    ans [][]int
    a, path []int
)

func dfs(start int) {
    tmp := make([]int, len(path))
    copy(tmp, path)
    ans = append(ans, tmp)

    for i := start; i < len(a); i ++ {
        if i > start && a[i] == a[i - 1] {
            continue
        }
        path = append(path, a[i])

        dfs(i + 1)

        path = path[: len(path) - 1]
    } 
}

func subsetsWithDup(nums []int) [][]int {
    a, path, ans = nums, make([]int, 0, len(a)), make([][]int, 0)
    sort.Ints(a)

    dfs(0)
    return ans
}
var (
    ans [][]int
    a, path []int
    st []bool
)

func dfs(start int) {
    tmp := make([]int, len(path))
    copy(tmp, path)
    ans = append(ans, tmp)

    for i := start; i < len(a); i ++ {
        if i > 0 && a[i] == a[i - 1] && !st[i - 1]{
            continue
        }
        path = append(path, a[i])
        st[i] = true

        dfs(i + 1)

        path = path[: len(path) - 1]
        st[i] = false
    } 
}

func subsetsWithDup(nums []int) [][]int {
    a, path, ans = nums, make([]int, 0, len(a)), make([][]int, 0)
    st = make([]bool, len(a))
    sort.Ints(a)

    dfs(0)
    return ans
}

LC91 解码方法

func numDecodings(s string) int {
    n := len(s)
    s = " " + s
    f := make([]int, n + 1)
    f[0] = 1

    for i := 1; i <= n; i ++ {
        if s[i] != '0' {
            f[i] += f[i - 1]
        }
        if i >= 2 {
            t := (int(s[i - 1] - '0')) * 10 + int(s[i] - '0')
            if t >= 10 && t <= 26 {
                f[i] += f[i - 2]
            }
        }
    }

    return f[n]
}

LC92 反转链表II

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    dummy := &ListNode{-1, head}
    p0 := dummy
    for i := 0; i < left - 1; i ++ {
        p0 = p0.Next
    }

    var pre, cur *ListNode = nil, p0.Next
    for i := 0; i < right - left + 1; i ++ {
        nxt := cur.Next
        cur.Next = pre
        pre = cur
        cur = nxt
    }

    p0.Next.Next = cur
    p0.Next = pre

    return dummy.Next
}

LC93 复原IP地址

var ans []string

func dfs(s string, u, k int, path string) {
    if u == len(s) {
        if k >= 4 {
            path = path[: len(path) - 1]
            ans = append(ans, path)
            return
        }
    }

    if k >= 4 {
        return
    }

    for i, t := u, 0; i < len(s); i ++ {
        if i > u && s[u] == '0' {
            break
        }
        t = t * 10 + int(s[i] - '0')
        if t <= 255 {
            dfs(s, i + 1, k + 1, path + strconv.Itoa(t) + ".")
        } else {
            break
        }
    }
}

func restoreIpAddresses(s string) []string {
    ans = []string{}
    dfs(s, 0, 0, "")
    return ans
}

LC94 二叉树的中序遍历

var ans []int

func dfs(root *TreeNode) {
    if root == nil {
        return
    }

    dfs(root.Left)
    ans = append(ans, root.Val)
    dfs(root.Right)
}

func inorderTraversal(root *TreeNode) []int {
    ans = []int{}
    if root == nil {
        return ans
    }
    
    dfs(root)
    return ans
}
func inorderTraversal(root *TreeNode) []int {
    ans, stk := []int{}, []*TreeNode{}
    if root == nil {
        return ans
    }
    
    for len(stk) > 0 || root != nil {
        for root != nil {
            stk = append(stk, root)
            root = root.Left
        }

        root = stk[len(stk) - 1]
        stk = stk[: len(stk) - 1]
        ans = append(ans, root.Val)
        root = root.Right
    }

    return ans
}
func inorderTraversal(root *TreeNode) []int {
    ans := []int{}

    for root != nil {
        if root.Left == nil {
            ans = append(ans, root.Val)
            root = root.Right
        } else {
            p := root.Left
            for p.Right != nil && p.Right != root {
                p = p.Right
            }
            if p.Right == nil {
                p.Right = root
                root = root.Left
            } else {
                ans = append(ans, root.Val)
                p.Right = nil
                root = root.Right
            }
        }
    }

    return ans
}

LC95 不同的二叉搜索树II

func dfs(l, r int) []*TreeNode {
    if l > r {
        return []*TreeNode{nil}
    }

    ans := []*TreeNode{}

    for i := l; i <= r; i ++ {
        left, right := dfs(l, i - 1), dfs(i + 1, r)
        for _, lc := range left {
            for _, rc := range right {
                root := &TreeNode{i, nil, nil}
                root.Left, root.Right = lc, rc
                ans = append(ans, root)
            }
        }
    }

    return ans
}

func generateTrees(n int) []*TreeNode {
    if n == 0 {
        return nil
    }
    return dfs(1, n)
}

LC96 不同的二叉搜索树

func numTrees(n int) int {
    f := make([]int, n + 1)
    f[0] = 1

    for i := 1; i <= n; i ++ {
        for j := 1; j <= i; j ++ {
            f[i] += f[j - 1] * f[i - j]
        }
    }

    return f[n]
}

LC97 交错字符串

func isInterleave(s1 string, s2 string, s3 string) bool {
    n, m := len(s1), len(s2)
    if n + m != len(s3) {
        return false
    }
    f := make([][]bool, n + 1)
    for i := 0; i < n + 1; i ++ {
        f[i] = make([]bool, m + 1)
    }
    s1, s2, s3 = " " + s1, " " + s2, " " + s3

    for i := 0; i <= n; i ++ {
        for j := 0; j <= m; j ++ {
            if i == 0 && j == 0 {
                f[i][j] = true
            } else {
                if i > 0 && s1[i] == s3[i + j] {
                    f[i][j] = f[i - 1][j]
                }
                if j > 0 && s2[j] == s3[i + j] {
                    f[i][j] = f[i][j] || f[i][j - 1]
                }
            }
        }
    }

    return f[n][m]
}

LC98 验证二叉搜索树

var (
    ans bool
    pre *TreeNode
)

func dfs(root *TreeNode) {
    if root == nil {
        return
    }

    dfs(root.Left)

    if pre != nil && pre.Val >= root.Val {
        ans = false
        return
    }
    pre = root

    dfs(root.Right)
}

func isValidBST(root *TreeNode) bool {
    ans, pre = true, nil

    dfs(root)
    return ans
}
func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }

    stk := []*TreeNode{}
    pre := math.MinInt64

    for len(stk) > 0 || root != nil {
        for root != nil {
            stk = append(stk, root)
            root = root.Left
        }
        root = stk[len(stk) - 1]
        stk = stk[: len(stk) - 1]

        if root.Val <= pre {
            return false
        }

        pre = root.Val
        root = root.Right
    }

    return true
}

LC99 恢复二叉搜索树

var (
     x, y, pre *TreeNode
 )

 func dfs(root *TreeNode) {
     if root == nil {
         return
     }

     dfs(root.Left)

     if pre != nil && pre.Val > root.Val {
         if x == nil {
             x = pre
         }
         y = root
     }
     pre = root

     dfs(root.Right)
 }

func recoverTree(root *TreeNode)  {
    x, y, pre = nil, nil, nil
    dfs(root)
    x.Val, y.Val = y.Val, x.Val
}
var (
    x, y , pre *TreeNode
)

func recoverTree(root *TreeNode)  {
    x, y, pre = nil, nil, nil

    for root != nil {
        if root.Left == nil {
            if pre != nil && pre.Val > root.Val {
                if x == nil {
                    x = pre
                }
                y = root
            }
            pre = root
            root = root.Right
        } else {
            p := root.Left
            for p.Right != nil && p.Right != root {
                p = p.Right
            }
            if p.Right == nil {
                p.Right = root
                root = root.Left
            } else {
                p.Right = nil
                if pre != nil && pre.Val > root.Val {
                    if x == nil {
                        x = pre
                    }
                    y = root
                }
                pre = root
                root = root.Right
            }
        }
    } 

    x.Val, y.Val = y.Val, x.Val
}

LC100 相同的树

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    
    if p == nil || q == nil || p.Val != q.Val {
        return false
    }

    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

欢迎点赞+收藏+关注呀~~~

文章来源:https://blog.csdn.net/qq_45832461/article/details/134881140
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。