This is the multi-page printable view of this section. Click here to print.

Return to the regular view of this page.

0050-0099

Solutions to LeetCode Problems 0050-0099.

1: 0050.Pow(x, n)
2: 0051.N 皇后
3: 0052.N皇后 II
4: 0053.最大子数组和
5: 0054.螺旋矩阵
6: 0055.跳跃游戏
7: 0056.合并区间
8: 0057.插入区间
9: 0058.最后一个单词的长度
10: 0059.螺旋矩阵 II
11: 0060.排列序列
12: 0061.旋转链表
13: 0062.不同路径
14: 0063.不同路径 II
15: 0064.最小路径和
16: 0065.有效数字
17: 0066.加一
18: 0067.二进制求和
19: 0068.文本左右对齐
20: 0069.x 的平方根
21: 0070.爬楼梯
22: 0071.简化路径
23: 0072.编辑距离
24: 0073.矩阵置零
25: 0074.搜索二维矩阵
26: 0075.颜色分类
27: 0076.最小覆盖子串
28: 0077.组合
29: 0078.子集
30: 0079.单词搜索
31: 0080.删除有序数组中的重复项 II
32: 0081.搜索旋转排序数组 II
33: 0082.删除排序链表中的重复元素 II
34: 0083.删除排序链表中的重复元素
35: 0084.柱状图中最大的矩形
36: 0085.最大矩形
37: 0086.分隔链表
38: 0087.扰乱字符串
39: 0088.合并两个有序数组
40: 0089.格雷编码
41: 0090.子集 II
42: 0091.解码方法
43: 0092.反转链表 II
44: 0093.复原 IP 地址
45: 0094.二叉树的中序遍历
46: 0095.不同的二叉搜索树 II
47: 0096.不同的二叉搜索树
48: 0097.交错字符串
49: 0098.验证二叉搜索树
50: 0099.恢复二叉搜索树

1 - 0050.Pow(x, n)

方法一：递归

时间复杂度 $O(\log n)$，空间复杂度 $O(\log n)$。

func myPow(x float64, n int) float64 {
	if n == 0 {
		return 1.0
	} else if n < 0 {
		return myPow(1/x, -n)
	}

	ans := myPow(x, n>>1)
	if n&1 == 1 {
		return x * ans * ans
	}
	return ans * ans
}

方法二：快速乘

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

func myPow(x float64, n int) float64 {
	if n < 0 {
		x, n = 1/x, -n
	}
	ans, c := 1.0, x
	for n != 0 {
		if n&1 == 1 {
			ans *= c
		}
		c *= c
		n >>= 1
	}
	return ans
}

2 - 0051.N 皇后

https://leetcode.cn/problems/n-queens/

方法一：回溯

时间复杂度 $O(n^3)$，空间复杂度 $O(n)$。

func hasConflict(vals []string, x, y int) bool {
	n := len(vals)
	// 上方
	for i := x - 1; i >= 0; i-- {
		if vals[i][y] == 'Q' {
			return false
		}
	}
	// 右上方
	for i, j := x-1, y+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if vals[i][j] == 'Q' {
			return false
		}
	}
	// 左上方
	for i, j := x-1, y-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if vals[i][j] == 'Q' {
			return false
		}
	}
	return true
}

func solveNQueens(n int) [][]string {
	ans, vals := [][]string{}, make([]string, n)
	for i := 0; i < n; i++ {
		vals[i] = strings.Repeat(".", n)
	}
	var backtrack func(row int)
	backtrack = func(row int) {
		if row == n {
			ans = append(ans, append([]string{}, vals...))
			return
		}
		for i := 0; i < n; i++ {
			if hasConflict(vals, row, i) {
				tmp := []byte(vals[row])
				tmp[i] = 'Q'
				vals[row] = string(tmp)
				backtrack(row + 1)
				tmp[i] = '.'
				vals[row] = string(tmp)
			}

		}
	}
	backtrack(0)
	return ans
}

3 - 0052.N皇后 II

https://leetcode.cn/problems/n-queens-ii/

方法一：回溯

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。

func totalNQueens(n int) int {
	ans, vals := 0, make([][]byte, n)
	for i := 0; i < n; i++ {
		vals[i] = make([]byte, n)
		for j := 0; j < n; j++ {
			vals[i][j] = '.'
		}
	}
	var backtrack func(row int)
	backtrack = func(row int) {
		if row == n {
			ans++
			return
		}
		for i := 0; i < n; i++ {
			if isValid(vals, row, i) {
				vals[row][i] = 'Q'
				backtrack(row + 1)
				vals[row][i] = '.'
			}
		}
	}
	backtrack(0)
	return ans
}

func isValid(vals [][]byte, x, y int) bool {
	n := len(vals)
	for i := x - 1; i >= 0; i-- {
		if vals[i][y] == 'Q' {
			return false
		}
	}
	for i, j := x-1, y+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if vals[i][j] == 'Q' {
			return false
		}
	}
	for i, j := x-1, y-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if vals[i][j] == 'Q' {
			return false
		}
	}
	return true
}

4 - 0053.最大子数组和

https://leetcode.cn/problems/maximum-subarray

方法一：遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

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

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut ans = nums[0];
        let mut sum = 0;
        for v in nums {
            sum += v;
            if sum > ans {
                ans = sum;
            }
            if sum < 0 {
                sum = 0;
            }
        }
        ans
    }
}

5 - 0054.螺旋矩阵

https://leetcode.cn/problems/spiral-matrix/

方法一：按层模拟

时间复杂度 $O(m \times n)$，空间复杂度 $O(1)$，m 和 n 表示输入矩阵的行数和列数。

func spiralOrder(matrix [][]int) []int {
	ans := []int{}
	top, bottom, left, right := 0, len(matrix)-1, 0, len(matrix[0])-1
	for top <= bottom && left <= right {
		for i := left; i <= right; i++ {
			ans = append(ans, matrix[top][i])
		}
		top += 1
		for i := top; i <= bottom; i++ {
			ans = append(ans, matrix[i][right])
		}
		right -= 1
		if top > bottom || left > right {
			break
		}
		for i := right; i >= left; i-- {
			ans = append(ans, matrix[bottom][i])
		}
		bottom -= 1
		for i := bottom; i >= top; i-- {
			ans = append(ans, matrix[i][left])
		}
		left += 1
	}
	return ans
}

impl Solution {
    pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
        let (mut i, mut j, mut m, mut n) = (0, 0, matrix.len(), matrix[0].len());
        let mut ans = Vec::new();
        while i < m && j < n {
            for y in j..n {
                ans.push(matrix[i][y]);
            }
            i += 1;
            for x in i..m {
                ans.push(matrix[x][n - 1]);
            }
            n -= 1;
            if i >= m || j >= n {
                break;
            }
            for y in (j..n).rev() {
                ans.push(matrix[m - 1][y]);
            }
            m -= 1;
            for x in (i..m).rev() {
                ans.push(matrix[x][j]);
            }
            j += 1;
        }
        ans
    }
}

6 - 0055.跳跃游戏

https://leetcode.cn/problems/jump-game/

方法一：贪心

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

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

7 - 0056.合并区间

https://leetcode.cn/problems/merge-intervals/

方法一：排序 + 遍历

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	ans := [][]int{intervals[0]}
	for i := 1; i < len(intervals); i++ {
		x, y := intervals[i][0], intervals[i][1]
		if x > ans[len(ans)-1][1] {
			ans = append(ans, []int{x, y})
		} else if y > ans[len(ans)-1][1] {
			ans[len(ans)-1][1] = y
		}
	}
	return ans
}

impl Solution {
    pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut intervals = intervals;
        intervals.sort_by(|a, b| a[0].cmp(&b[0]));
        let mut ans = Vec::new();

        for v in intervals {
            if ans.is_empty() {
                ans.push(v);
                continue;
            }
            let last = ans.last_mut().unwrap();
            if v[0] > last[1] {
                ans.push(v);
            } else if v[1] > last[1] {
                last[1] = v[1];
            }
        }
        ans
    }
}

8 - 0057.插入区间

https://leetcode.cn/problems/insert-interval/

方法一：模拟

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func insert(intervals [][]int, newInterval []int) [][]int {
	ans, first := [][]int{}, false
	for _, interval := range intervals {
		if interval[1] < newInterval[0] {
			ans = append(ans, interval)
		} else if interval[0] > newInterval[1] {
			if !first {
				ans, first = append(ans, newInterval), true
			}
			ans = append(ans, interval)
		} else {
			if interval[0] < newInterval[0] {
				newInterval[0] = interval[0]
			}
			if interval[1] > newInterval[1] {
				newInterval[1] = interval[1]
			}
		}
	}
	if !first {
		ans = append(ans, newInterval)
	}
	return ans
}

9 - 0058.最后一个单词的长度

https://leetcode.cn/problems/length-of-last-word/

方法一：扫描

时间复杂度 $O(n)$，空间复杂度 $O(1)$，n 表示字符串的长度。

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

10 - 0059.螺旋矩阵 II

https://leetcode.cn/problems/spiral-matrix-ii/

方法一：模拟

时间复杂度 $O(n^2)$，空间复杂度 $O(1)$。

func generateMatrix(n int) [][]int {
	ans := make([][]int, n)
	for i := 0; i < n; i++ {
		ans[i] = make([]int, n)
	}
	top, bottom, left, right, v := 0, n-1, 0, n-1, 1
	for top <= bottom && left <= right {
		for i := left; i <= right; i++ {
			ans[top][i], v = v, v+1
		}
		top += 1
		for i := top; i <= bottom; i++ {
			ans[i][right], v = v, v+1
		}
		right -= 1
		if top > bottom || left > right {
			break
		}
		for i := right; i >= left; i-- {
			ans[bottom][i], v = v, v+1
		}
		bottom -= 1
		for i := bottom; i >= top; i-- {
			ans[i][left], v = v, v+1
		}
		left += 1
	}
	return ans
}

11 - 0060.排列序列

https://leetcode.cn/problems/permutation-sequence/

方法一：模拟

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

func getPermutation(n int, k int) string {
	ans, visable := "", make([]bool, n+1)
	for i := 0; i < n; i++ {
		factor := 1
		for j := 1; j < n-i; j++ {
			factor *= j
		}
		for j := 1; j <= n; j++ {
			if !visable[j] {
				if k > factor {
					k -= factor
				} else {
					ans += fmt.Sprintf("%c", '0'+j)
					visable[j] = true
					break
				}
			}
		}
	}
	return ans
}

12 - 0061.旋转链表

https://leetcode.cn/problems/rotate-list/

方法一：快慢指针

时间复杂度 $O(n)$，空间复杂度 $O(1)$，n 表示链表的长度。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	n, p, q, ans := 0, head, head, head
	for ; p != nil; p = p.Next {
		n++
	}
	k, p = k%n, head
	for i := 0; i < k; i++ {
		p = p.Next
	}
	for p != nil && p.Next != nil {
		p = p.Next
		q = q.Next
	}
	if k != 0 {
		ans = q.Next
		p.Next, q.Next = head, p.Next
	}
	return ans
}

13 - 0062.不同路径

https://leetcode.cn/problems/unique-paths/

方法一：动态规划

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。

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

方法二：数学

易知解法数目为：$C_{m+n-2}^{m-1} = \frac{(m+n-2)(m+n-3)···n}{(m-1)!}$，故时间复杂度 $O(m)$，空间复杂度 $O(1)$。

func uniquePaths(m int, n int) int {
	ans := 1
	for i, v := 1, n; i < m; i, v = i+1, v+1 {
		ans = ans * v / i
	}
	return ans
}

14 - 0063.不同路径 II

https://leetcode.cn/problems/unique-paths-ii/

方法一：动态规划

时间复杂度 $O(m \times n)$，空间复杂度 $O(n)$，其中 m 和 n 分别表示 obstacleGrid 数组的行数和列数。

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	dp, m, n := make([]int, len(obstacleGrid[0])), len(obstacleGrid), len(obstacleGrid[0])

	for i := 0; i < n && obstacleGrid[0][i] != 1; i++ {
		dp[i] = 1
	}

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

15 - 0064.最小路径和

https://leetcode.cn/problems/minimum-path-sum/

方法一：动态规划

时间复杂度 $O(m \times n)$，空间复杂度 $O(n)$，其中 m 和 n 分别表示 grid 数组的行数和列数。

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

func minPathSum(grid [][]int) int {
	dp, m, n := make([]int, len(grid[0])), len(grid), len(grid[0])
	dp[0] = grid[0][0]
	for i := 1; i < n; i++ {
		dp[i] = grid[0][i] + dp[i-1]
	}
	for i := 1; i < m; i++ {
		for j := 0; j < n; j++ {
			if j > 0 {
				dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
			} else {
				dp[j] += grid[i][j]
			}
		}
	}
	return dp[n-1]
}

16 - 0065.有效数字

https://leetcode.cn/problems/valid-number/

方法一：分类讨论

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func isNumber(s string) bool {
	if len(s) > 0 && (s[0] == '+' || s[0] == '-') {
		s = s[1:]
	}
	if len(s) == 0 {
		return false
	}
	point := false
	for i := 0; i < len(s); i++ {
		if s[i] == '.' && !point {
			if (i > 0 && s[i-1] >= '0' && s[i-1] <= '9') || (i+1 < len(s) && s[i+1] >= '0' && s[i+1] <= '9') {
				point = true
				continue
			}
			return false
		} else if strings.ToUpper(s[i:i+1]) == "E" && i+1 < len(s) && i > 0 {
			for j := i + 1; j < len(s); j++ {
				if s[j] == '.' || strings.ToUpper(s[j:j+1]) == "E" {
					return false
				}
			}
			return isNumber(s[i+1:])
		} else if s[i] < '0' || s[i] > '9' {
			return false
		}
	}
	return true
}

17 - 0066.加一

https://leetcode.cn/problems/plus-one/

方法一：找出最长的后缀 9

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func plusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		if digits[i] != 9 {
			digits[i] += 1
			for j := i + 1; j < len(digits); j++ {
				digits[j] = 0
			}
			return digits
		}
	}
	ans := make([]int, len(digits)+1)
	ans[0] = 1
	return ans
}

18 - 0067.二进制求和

https://leetcode.cn/problems/add-binary/

方法一：模拟加法

时间复杂度 $O(max(len(a), len(b)))$，空间复杂度 $O(1)$。

func addBinary(a string, b string) string {
	ans, pa, pb := "", len(a)-1, len(b)-1
	for mod := 0; pa >= 0 || pb >= 0 || mod != 0; {
		x, y := 0, 0
		if pa >= 0 {
			x, pa = int(a[pa]-'0'), pa-1
		}
		if pb >= 0 {
			y, pb = int(b[pb]-'0'), pb-1
		}
		ans = fmt.Sprintf("%d", (x+y+mod)%2) + ans
		mod = (x + y + mod) / 2
	}
	return ans
}

19 - 0068.文本左右对齐

https://leetcode.cn/problems/text-justification/

方法一：字符串模拟

时间复杂度 $O(m)$，空间复杂度 $O(1)$，其中 m 表示所有字符串的总长度。

// 放置以 index 结尾的 num 个单词，确保字符串长度为 maxWidth
func placestr(words []string, index, num, length, maxWidth int) string {
	if num == 1 {
		return words[index] + strings.Repeat(" ", maxWidth-length)
	}
	space, mod, substr := (maxWidth-length)/(num-1), (maxWidth-length)%(num-1), ""
	if index == len(words)-1 {
		space, mod = 1, maxWidth-length-num+1
	}
	for i := index - num + 1; i < index; i++ {
		numspace := space
		if mod > 0 && index != len(words)-1 {
			numspace, mod = numspace+1, mod-1
		}
		substr += words[i] + strings.Repeat(" ", numspace)
	}
	substr += words[index] + strings.Repeat(" ", mod)
	return substr
}

func fullJustify(words []string, maxWidth int) []string {
	ans, length, num := []string{}, 0, 0
	for i := 0; i < len(words); i++ {
		if length+len(words[i])+num <= maxWidth {
			length, num = length+len(words[i]), num+1
			continue
		}
		ans = append(ans, placestr(words, i-1, num, length, maxWidth))
		length, num = len(words[i]), 1
	}
	ans = append(ans, placestr(words, len(words)-1, num, length, maxWidth))
	return ans
}

20 - 0069.x 的平方根

https://leetcode.cn/problems/sqrtx/

方法一：二分查找

时间复杂度 $O(\log x)$，空间复杂度 $O(1)$。

func mySqrt(x int) int {
	a, b, ans := 0, x, 0
	for m := a + (b-a)/2; a <= b; m = a + (b-a)/2 {
		if m*m <= x {
			ans, a = m, m+1
		} else {
			b = m - 1
		}
	}
	return ans
}

21 - 0070.爬楼梯

https://leetcode.cn/problems/climbing-stairs/

方法一：动态规划

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func climbStairs(n int) int {
	if n < 3 {
		return n
	}
	first, second, three := 1, 2, 0
	for i := 3; i <= n; i++ {
		three = first + second
		first, second = second, three
	}
	return three
}

22 - 0071.简化路径

https://leetcode.cn/problems/simplify-path/

方法一：模拟

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

func simplifyPath(path string) string {
	ans, start, end := []string{}, 0, 0
	for i := 0; i < len(path); i = end + 1 {
		for start = i; start < len(path) && path[start] == '/'; {
			start++
		}
		for end = start; end < len(path) && path[end] != '/'; {
			end++
		}
		subpath := path[start:end]
		if subpath == ".." && len(ans) > 0 {
			ans = ans[:len(ans)-1]
		} else if subpath == "." || subpath == ".." {
			continue
		} else if subpath != "" {
			ans = append(ans, subpath)
		}
	}
	return "/" + strings.Join(ans, "/")
}

23 - 0072.编辑距离

https://leetcode.cn/problems/edit-distance/

方法一：动态规划

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。

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

func minDistance(word1 string, word2 string) int {
	dp, m, n := make([][]int, len(word1)+1), len(word1), len(word2)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		dp[i][0] = i
	}
	for i := 1; i <= n; i++ {
		dp[0][i] = i
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if word1[i] == word2[j] {
				dp[i+1][j+1] = dp[i][j]
			} else {
				dp[i+1][j+1] = min(dp[i][j+1], min(dp[i][j], dp[i+1][j])) + 1
			}
		}
	}
	return dp[m][n]
}

24 - 0073.矩阵置零

https://leetcode.cn/problems/set-matrix-zeroes/

方法一：使用两个标记变量

时间复杂度 $O(m \times n)$，空间复杂度 $O(1)$，m，n 分别表示 matrix 的行数和列数。

func setZeroes(matrix [][]int) {
	m, n, zero_r, zero_c := len(matrix), len(matrix[0]), false, false
	for i := 0; i < m; i++ {
		if matrix[i][0] == 0 {
			zero_r = true
			break
		}
	}
	for i := 0; i < n; i++ {
		if matrix[0][i] == 0 {
			zero_c = true
			break
		}
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[i][j] == 0 {
				matrix[i][0], matrix[0][j] = 0, 0
			}
		}
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[i][0] == 0 || matrix[0][j] == 0 {
				matrix[i][j] = 0
			}
		}
	}
	for i := 0; i < m && zero_r; i++ {
		matrix[i][0] = 0
	}
	for i := 0; i < n && zero_c; i++ {
		matrix[0][i] = 0
	}
}

impl Solution {
    pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
        use std::cmp::{max, min};
        let (m, n, mut zero_r, mut zero_c) = (matrix.len(), matrix[0].len(), false, false);
        for i in 0..max(m, n) {
            if matrix[min(i, m - 1)][0] == 0 {
                zero_r = true;
            }
            if matrix[0][min(i, n - 1)] == 0 {
                zero_c = true;
            }
        }
        for i in 1..m {
            for j in 1..n {
                if matrix[i][j] == 0 {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for i in 1..m {
            for j in 1..n {
                if matrix[i][0] == 0 || matrix[0][j] == 0 {
                    matrix[i][j] = 0;
                }
            }
        }
        for i in 0..m {
            if zero_r {
                matrix[i][0] = 0;
            }
        }
        for j in 0..n {
            if zero_c {
                matrix[0][j] = 0;
            }
        }
    }
}

25 - 0074.搜索二维矩阵

https://leetcode.cn/problems/search-a-2d-matrix/

方法一：二分搜索

时间复杂度 $O(\log mn)$，空间复杂度 $O(1)$。

func searchMatrix(matrix [][]int, target int) bool {
	m, n := len(matrix), len(matrix[0])
	for left, right := 0, m*n-1; left <= right; {
		mid := left + (right-left)/2
		row, col := mid/n, mid%n
		if matrix[row][col] == target {
			return true
		} else if matrix[row][col] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return false
}

26 - 0075.颜色分类

https://leetcode.cn/problems/sort-colors/

方法一：双指针

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

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

27 - 0076.最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/

方法一：滑动窗口

时间复杂度 $O(n+m)$，空间复杂度 $O(1)$，n 和 m 分别表示字符串 s 和 t 的长度。

func minWindow(s string, t string) string {
	need, window, cond := [256]int{}, [256]int{}, 0
	for i := 0; i < len(t); i++ {
		if need[t[i]] == 0 {
			cond++
		}
		need[t[i]]++
	}
	ans, m := s+" ", 0
	for i, j := 0, 0; j < len(s); j++ {
		window[s[j]]++
		if window[s[j]] == need[s[j]] {
			m++
		}
		if m < cond {
			continue
		}

		for m == cond {
			if len(ans) > j-i+1 {
				ans = s[i : j+1]
			}
			window[s[i]]--
			if window[s[i]] < need[s[i]] {
				m--
			}
			i++
		}
	}
	if len(ans) > len(s) {
		return ""
	}
	return ans
}

impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        let (mut need, mut window) = ([0; 128], [0; 128]);
        let (s, t) = (s.as_bytes(), t.as_bytes());
        t.iter().for_each(|&v| {
            need[v as usize] += 1;
        });
        fn equal(need: &[i32; 128], window: &[i32; 128]) -> bool {
            for i in 0..128 {
                if need[i] != 0 && need[i] > window[i] {
                    return false;
                }
            }
            true
        }

        let mut ans: String = std::iter::repeat("0").take(s.len() + 1).collect();
        let mut pre = 0;
        for i in 0..s.len() {
            window[s[i] as usize] += 1;
            if !equal(&need, &window) {
                continue;
            }
            while equal(&need, &window) {
                if ans.len() > i - pre + 1 {
                    ans = String::from_utf8_lossy(&s[pre..=i]).to_string();
                }
                window[s[pre] as usize] -= 1;
                pre += 1;
            }
        }
        if ans.len() > s.len() {
            return "".to_string();
        }
        ans
    }
}

28 - 0077.组合

https://leetcode.cn/problems/combinations/

方法一：回溯

时间复杂度 $O(n \times k)$，空间复杂度 $O(n \times k)$。

func combine(n int, k int) [][]int {
	ans := [][]int{}
	var backtrack func(values []int, started int)
	backtrack = func(values []int, started int) {
		if len(values) == k {
			ans = append(ans, append([]int{}, values...))
			return
		}
		for i := started; i <= n; i++ {
			values = append(values, i)
			backtrack(values, i+1)
			values = values[:len(values)-1]
		}
	}
	backtrack([]int{}, 1)
	return ans
}

29 - 0078.子集

https://leetcode.cn/problems/subsets/

方法一：回溯

时间复杂度 $O(n \times 2^n)$，空间复杂度 $O(n)$。

func subsets(nums []int) [][]int {
	ans, n := [][]int{}, len(nums)
	var backtrack func(values []int, start int)
	backtrack = func(values []int, start int) {
		ans = append(ans, append([]int{}, values...))
		for i := start; i < n; i++ {
			values = append(values, nums[i])
			backtrack(values, i+1)
			values = values[:len(values)-1]
		}
	}
	backtrack([]int{}, 0)
	return ans
}

30 - 0079.单词搜索

https://leetcode.cn/problems/word-search/

方法一：回溯

时间复杂度 $O(mn \times 3^L)$，空间复杂度 $O(mn)$，其中 m 和 n 表示网格的长度与宽度 L 为字符串 word 的长度。

func exist(board [][]byte, word string) bool {
	visited, m, n := make([][]bool, len(board)), len(board), len(board[0])
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	var dfs func(x, y, idx int) bool
	dfs = func(x, y, idx int) bool {
		if board[x][y] != word[idx] {
			return false
		}
		if idx == len(word)-1 {
			return true
		}

		// judege top bottom left right
		dirx, diry := []int{-1, 1, 0, 0}, []int{0, 0, -1, 1}
		for i := 0; i < 4; i++ {
			j, k := x+dirx[i], y+diry[i]
			if j >= 0 && j < m && k >= 0 && k < n && !visited[j][k] {
				visited[j][k] = true
				if dfs(j, k, idx+1) {
					return true
				}
				visited[j][k] = false
			}
		}
		return false
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == word[0] {
				visited[i][j] = true
				if dfs(i, j, 0) {
					return true
				}
				visited[i][j] = false
			}
		}
	}
	return false
}

31 - 0080.删除有序数组中的重复项 II

https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/

方法一：双指针

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func removeDuplicates(nums []int) int {
	p, p1, p2 := 0, 0, 0
	for p2 < len(nums) {
		for p2 < len(nums) && nums[p1] == nums[p2] {
			p2++
		}
		nums[p], p = nums[p1], p+1
		if p2-p1 >= 2 {
			nums[p], p = nums[p1], p+1
		}
		p1 = p2
	}
	return p
}

32 - 0081.搜索旋转排序数组 II

https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/

方法一：二分搜索

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

func search(nums []int, target int) bool {
	for l, r := 0, len(nums)-1; l <= r; {
		m := l + (r-l)>>1
		if nums[m] == target {
			return true
		} else if nums[m] > nums[l] || nums[m] > nums[r] {
			if target >= nums[l] && target < nums[m] {
				r = m - 1
			} else {
				l = m + 1
			}
		} else if nums[m] < nums[l] || nums[m] < nums[r] {
			if target > nums[m] && target <= nums[r] {
				l = m + 1
			} else {
				r = m - 1
			}
		} else {
			r -= 1
		}
	}
	return false
}

33 - 0082.删除排序链表中的重复元素 II

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/

方法一：一次遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
	dummy := &ListNode{}
	p := dummy
	for head != nil {
		p1, p2 := head, head
		for p2 != nil && p1.Val == p2.Val {
			p2 = p2.Next
		}
		if p1.Next == p2 {
			p.Next, p = p1, p1
		}
		head = p2
	}
	p.Next = nil
	return dummy.Next
}

34 - 0083.删除排序链表中的重复元素

https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

方法一：一次遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	dummy := &ListNode{Next: head}
	p := dummy.Next
	for ; head != nil; head = head.Next {
		if p.Val != head.Val {
			p.Next, p = head, head
		}
	}
	p.Next = nil
	return dummy.Next
}

35 - 0084.柱状图中最大的矩形

https://leetcode.cn/problems/largest-rectangle-in-histogram/

方法一：单调栈

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

func largestRectangleArea(heights []int) int {
	left, right, stack, n := make([]int, len(heights)), make([]int, len(heights)), []int{}, len(heights)
	for i := 0; i < n; i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			stack = stack[:len(stack)-1]
		}
		left[i] = -1
		if len(stack) > 0 {
			left[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	stack = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			stack = stack[:len(stack)-1]
		}
		right[i] = n
		if len(stack) > 0 {
			right[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	ans := 0
	for i := 0; i < n; i++ {
		area := (right[i] - left[i] - 1) * heights[i]
		if area > ans {
			ans = area
		}
	}
	return ans
}

方法二：单调栈 + 常数优化

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

func largestRectangleArea(heights []int) int {
	left, right, stack, n := make([]int, len(heights)), make([]int, len(heights)), []int{}, len(heights)
	for i := 0; i < n; i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			right[stack[len(stack)-1]] = i
			stack = stack[:len(stack)-1]
		}
		left[i] = -1
		if len(stack) > 0 {
			left[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	for i := 0; i < len(stack); i++ {
		right[stack[i]] = n
	}
	ans := 0
	for i := 0; i < n; i++ {
		area := (right[i] - left[i] - 1) * heights[i]
		if area > ans {
			ans = area
		}
	}
	return ans
}

36 - 0085.最大矩形

https://leetcode.cn/problems/maximal-rectangle/

方法一：单调栈

时间复杂度 $O(m \times n)$，空间复杂度 $O(n)$，其中 m，n 表示 matrix 矩阵的长和宽。

func maximalRectangle(matrix [][]byte) int {
	ans, m, n := 0, len(matrix), len(matrix[0])
	maxArea := func(heights []int) int {
		ans, left, right, stack, n := 0, make([]int, len(heights)), make([]int, len(heights)), []int{}, len(heights)
		for i := 0; i < n; i++ {
			for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
				right[stack[len(stack)-1]], stack = i, stack[:len(stack)-1]
			}
			left[i] = -1
			if len(stack) > 0 {
				left[i] = stack[len(stack)-1]
			}
			stack = append(stack, i)
		}
		for _, v := range stack {
			right[v] = n
		}
		for i := 0; i < n; i++ {
			area := (right[i] - left[i] - 1) * heights[i]
			if area > ans {
				ans = area
			}
		}
		return ans
	}
	heights := make([]int, n)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == '1' {
				heights[j] += 1
			} else {
				heights[j] = 0
			}
		}
		area := maxArea(heights)
		if area > ans {
			ans = area
		}
	}
	return ans
}

37 - 0086.分隔链表

https://leetcode.cn/problems/partition-list/

方法一：遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
	dummy1, dummy2 := &ListNode{}, &ListNode{}
	p1, p2 := dummy1, dummy2
	for ; head != nil; head = head.Next {
		if head.Val < x {
			p1.Next, p1 = head, head
		} else {
			p2.Next, p2 = head, head
		}
	}
	p1.Next, p2.Next = dummy2.Next, nil
	return dummy1.Next
}

38 - 0087.扰乱字符串

https://leetcode.cn/problems/scramble-string/

方法一：递归 + 记忆化搜索

时间复杂度 $O(n^4)$，空间复杂度 $O(n^3)$。

func isScramble(s1 string, s2 string) bool {
	cache := make([][][]int, len(s1))
	for i := 0; i < len(s1); i++ {
		cache[i] = make([][]int, len(s2))
		for j := 0; j < len(s2); j++ {
			cache[i][j] = make([]int, len(s1)+1)
		}
	}
	check := func(a, b, length int) bool {
		cnt_a, cnt_b := [26]int{}, [26]int{}
		for i := a; i < a+length; i++ {
			cnt_a[s1[i]-'a'] += 1
		}
		for i := b; i < b+length; i++ {
			cnt_b[s2[i]-'a'] += 1
		}
		for i := 0; i < 26; i++ {
			if cnt_a[i] != cnt_b[i] {
				return false
			}
		}
		return true
	}
	var dfs func(a, b, length int) bool
	dfs = func(a, b, length int) bool {
		if cache[a][b][length] != 0 {
			return cache[a][b][length] == 1
		}
		if s1[a:a+length] == s2[b:b+length] {
			cache[a][b][length] = 1
			return true
		} else if !check(a, b, length) {
			cache[a][b][length] = -1
			return false
		}

		for i := 1; i < length; i++ {
			if dfs(a, b, i) && dfs(a+i, b+i, length-i) {
				cache[a][b][length] = 1
				return true
			}
			if dfs(a, b+length-i, i) && dfs(a+i, b, length-i) {
				cache[a][b][length] = 1
				return true
			}
		}
		cache[a][b][length] = -1
		return false
	}
	return dfs(0, 0, len(s1))
}

39 - 0088.合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/

方法一：遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

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

40 - 0089.格雷编码

https://leetcode.cn/problems/gray-code/

方法一：对称生成

时间复杂度 $O(2^n)$，空间复杂度 $O(n)$。

func grayCode(n int) []int {
	if n == 1 {
		return []int{0, 1}
	}
	ans := grayCode(n - 1)
	for i := len(ans) - 1; i >= 0; i-- {
		ans = append(ans, ans[i]+1<<(n-1))
	}
	return ans
}

41 - 0090.子集 II

https://leetcode.cn/problems/subsets-ii/

方法一：回溯

时间复杂度 $O(n \times 2^n)$，空间复杂度 $O(n)$。

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	ans, n := [][]int{}, len(nums)
	var backtrack func(values []int, start int)
	backtrack = func(values []int, start int) {
		ans = append(ans, append([]int{}, values...))
		for i := start; i < n; i++ {
			if i > start && nums[i-1] == nums[i] {
				continue
			}
			values = append(values, nums[i])
			backtrack(values, i+1)
			values = values[:len(values)-1]
		}
	}
	backtrack([]int{}, 0)
	return ans
}

42 - 0091.解码方法

https://leetcode.cn/problems/decode-ways

方法一：动态规划

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func numDecodings(s string) int {
	if s[0] == '0' {
		return 0
	}
	a, b, c := 1, 1, 1
	for i := 1; i < len(s); i++ {
		pv, v := int(s[i-1]-'0'), int(s[i]-'0')
		c = 0
		if v != 0 {
			c = b
		}
		if pv != 0 && pv*10+v >= 1 && pv*10+v <= 26 {
			c += a
		}
		a, b = b, c
	}
	return c
}

43 - 0092.反转链表 II

https://leetcode.cn/problems/reverse-linked-list-ii/

方法一：递归

时间复杂度 $O(right)$，空间复杂度 $O(right)$。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	var poster *ListNode
	var reverseN func(head *ListNode, n int) *ListNode
	reverseN = func(head *ListNode, n int) *ListNode {
		if n == 1 {
			poster = head.Next
			return head
		}
		ans := reverseN(head.Next, n-1)
		head.Next.Next, head.Next = head, poster
		return ans
	}

	if left == 1 {
		return reverseN(head, right)
	}
	head.Next = reverseBetween(head.Next, left-1, right-1)
	return head
}

44 - 0093.复原 IP 地址

https://leetcode.cn/problems/restore-ip-addresses/

方法一：回溯

时间复杂度 $O(3^4 \times n)$，空间复杂度 $O(4)$。

func restoreIpAddresses(s string) []string {
	ans, n := []string{}, len(s)
	var backtrack func(seg []int, start int)
	backtrack = func(seg []int, start int) {
		if len(seg) == 4 && start == n {
			fmt.Println(seg)
			ipv4 := s[:seg[0]] + "." + s[seg[0]:seg[1]] + "." + s[seg[1]:seg[2]] + "." + s[seg[2]:]
			ans = append(ans, ipv4)
			return
		} else if start == n || len(seg) == 4 {
			return
		}
		if s[start] == '0' {
			seg = append(seg, start+1)
			backtrack(seg, start+1)
			return
		}
		digit := 0
		for i := start; i < n; i++ {
			digit = digit*10 + int(s[i]-'0')
			if digit > 0 && digit <= 255 {
				seg = append(seg, i+1)
				backtrack(seg, i+1)
				seg = seg[:len(seg)-1]
			} else {
				break
			}
		}
	}
	backtrack([]int{}, 0)
	return ans
}

45 - 0094.二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/

方法一：迭代法

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
	ans, stack := []int{}, []*TreeNode{}
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack, root = append(stack, root), root.Left
		}
		top := stack[len(stack)-1]
		stack, ans, root = stack[:len(stack)-1], append(ans, top.Val), top.Right
	}
	return ans
}

46 - 0095.不同的二叉搜索树 II

https://leetcode.cn/problems/unique-binary-search-trees-ii/

方法一：回溯

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
	var dfs func(l, r int) []*TreeNode
	dfs = func(l, r int) []*TreeNode {
		res := []*TreeNode{}
		if l > r {
			res = append(res, nil)
			return res
		}
		for i := l; i <= r; i++ {
			left := dfs(l, i-1)
			right := dfs(i+1, r)
			for _, lnode := range left {
				for _, rnode := range right {
					root := &TreeNode{Left: lnode, Right: rnode, Val: i}
					res = append(res, root)
				}
			}
		}
		return res
	}
	return dfs(1, n)
}

47 - 0096.不同的二叉搜索树

https://leetcode.cn/problems/unique-binary-search-trees

方法一：回溯

func numTrees(n int) int {
	memo := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		memo[i] = make([]int, n+1)
	}
	var dfs func(l, r int) int
	dfs = func(l, r int) int {
		if l > r {
			return 1
		}
		if memo[l][r] != 0 {
			return memo[l][r]
		}
		ans := 0
		for i := l; i <= r; i++ {
			left, right := dfs(l, i-1), dfs(i+1, r)
			ans += left * right
		}
		memo[l][r] = ans
		return ans
	}
	return dfs(1, n)
}

48 - 0097.交错字符串

https://leetcode.cn/problems/interleaving-string/

方法一：动态规划

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。

func isInterleave(s1 string, s2 string, s3 string) bool {
	m, n, l, dp := len(s1), len(s2), len(s3), make([][]bool, len(s1)+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	if m+n != l {
		return false
	}
	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			k := i + j - 1
			if i > 0 {
				dp[i][j] = dp[i-1][j] && s1[i-1] == s3[k]
			}
			if j > 0 {
				dp[i][j] = dp[i][j] || (dp[i][j-1] && s2[j-1] == s3[k])
			}
		}
	}
	return dp[m][n]
}

49 - 0098.验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/

方法一：递归

时间复杂度 $O(n)$，空间复杂度 $O(n)$，之所以空间复杂度为 $O(n)$ 是考虑到最坏情况下二叉树为一条链，树的高度为 $n$，递归最深达到 $n$ 层。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	var dfs func(node *TreeNode, min, max int) bool
	dfs = func(node *TreeNode, min, max int) bool {
		if node == nil {
			return true
		}
		if node.Val <= min || node.Val >= max {
			return false
		}
		return dfs(node.Left, min, node.Val) && dfs(node.Right, node.Val, max)
	}
	return dfs(root, -1<<31-1, 1<<31)
}

50 - 0099.恢复二叉搜索树

https://leetcode.cn/problems/recover-binary-search-tree/

方法一：隐式中序遍历

时间复杂度 $O(N)$，空间复杂度 $O(H)$，其中 $N$ 为二叉搜索树的节点个数，$H$ 为二叉搜索树的高度。

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func recoverTree(root *TreeNode) {
	var pre *TreeNode = &TreeNode{Val: -1<<31 - 1}
	var first, last *TreeNode = nil, nil
	var middle func(n *TreeNode)
	middle = func(n *TreeNode) {
		if n == nil {
			return
		}
		middle(n.Left)
		if n.Val < pre.Val {
			last = n
			if first == nil {
				first = pre
			} else {
				return
			}
		}
		pre = n
		middle(n.Right)
	}
	middle(root)
	first.Val, last.Val = last.Val, first.Val
}

0050-0099

1 - 0050.Pow(x, n)

方法一：递归

方法二：快速乘

2 - 0051.N 皇后

方法一：回溯

3 - 0052.N皇后 II

方法一：回溯

4 - 0053.最大子数组和

方法一：遍历

5 - 0054.螺旋矩阵

方法一：按层模拟

6 - 0055.跳跃游戏

方法一：贪心

7 - 0056.合并区间

方法一：排序 + 遍历

8 - 0057.插入区间

方法一：模拟

9 - 0058.最后一个单词的长度

方法一：扫描

10 - 0059.螺旋矩阵 II

方法一：模拟

11 - 0060.排列序列

方法一：模拟

12 - 0061.旋转链表

方法一：快慢指针

13 - 0062.不同路径

方法一：动态规划

方法二 ：数学

14 - 0063.不同路径 II

方法一：动态规划

15 - 0064.最小路径和

方法一：动态规划

16 - 0065.有效数字

方法一：分类讨论

17 - 0066.加一

方法一：找出最长的后缀 9

18 - 0067.二进制求和

方法一：模拟加法

19 - 0068.文本左右对齐

方法一：字符串模拟

20 - 0069.x 的平方根

方法一：二分查找

21 - 0070.爬楼梯

方法一：动态规划

22 - 0071.简化路径

方法一：模拟

23 - 0072.编辑距离

方法一：动态规划

24 - 0073.矩阵置零

方法一：使用两个标记变量

25 - 0074.搜索二维矩阵

方法一：二分搜索

26 - 0075.颜色分类

方法一：双指针

27 - 0076.最小覆盖子串

方法一：滑动窗口

28 - 0077.组合

方法一：回溯

29 - 0078.子集

方法一：回溯

30 - 0079.单词搜索

方法一：回溯

31 - 0080.删除有序数组中的重复项 II

方法一：双指针

32 - 0081.搜索旋转排序数组 II

方法一：二分搜索

33 - 0082.删除排序链表中的重复元素 II

方法一：一次遍历

34 - 0083.删除排序链表中的重复元素

方法一：一次遍历

35 - 0084.柱状图中最大的矩形

方法一：单调栈

方法二：单调栈 + 常数优化

36 - 0085.最大矩形

方法一：单调栈

37 - 0086.分隔链表

方法一：遍历

38 - 0087.扰乱字符串

方法一：递归 + 记忆化搜索

方法二：数学