全排列

板子题，不解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func permute(nums []int) (ans [][]int) {
    var dfs func(begain, end int)
    dfs = func(begain, end int) {
        if begain == end {
            // 切片是引用类型，需要深拷贝一下
            tmp := make([]int, len(nums))
            copy(tmp, nums)
            ans = append(ans, tmp)
        }
        for i := begain; i <= end; i++ {
            nums[begain], nums[i] = nums[i], nums[begain]
            dfs(begain+1, end)
            nums[begain], nums[i] = nums[i], nums[begain]
        }
    }
    dfs(0, len(nums)-1)
    return
}

旋转图像

感觉纯脑筋急转弯，在草稿纸推演一波应该就行👀

1
2
3
4
5
6
7
8
9
func rotate(matrix [][]int) {
    n := len(matrix)
    for i := 0; i < n/2; i++ {
        for j := 0; j < (n+1)/2; j++ {
            matrix[i][j], matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1] =
                matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1], matrix[i][j]
        }
    }
}

字母异位词分组

没想到暴力解法时间上能击败 95% 的 Go 用户🤣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func groupAnagrams(strs []string) [][]string {
    m := make(map[string][]int)
    var ans [][]string

    for idx, str := range strs {
        tmpStr := []byte(str)
        sort.Slice(tmpStr, func(i, j int) bool {
            return tmpStr[i] < tmpStr[j]
        })
        m[string(tmpStr)] = append(m[string(tmpStr)], idx)
    }

    for _, idxs := range m {
        tmp := make([]string, len(idxs))
        for i, idx := range idxs {
            tmp[i] = strs[idx]
        }
        ans = append(ans, tmp)
    }
    return ans
}

另外一种方法是统计字符个数来区分

最大子数组和

经典 dp，但是做完了才发现有更好的方法，就是只接纳有贡献的元素（大于 0）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maxSubArray(nums []int) int {
    dp := make([]int, len(nums))
    ans := nums[0]
    dp[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        dp[i] = max(dp[i-1]+nums[i], nums[i])
        ans = max(ans, dp[i])
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

跳跃游戏

也是经典 dp，当然也有其他的方法

1
2
3
4
5
6
7
8
9
10
11
12
func canJump(nums []int) bool {
    dp := make([]bool, len(nums))
    dp[0] = true
    for i := 0; i < len(nums); i++ {
        if dp[i] {
            for j := i + 1; j <= i+nums[i] && j < len(nums); j++ {
                dp[j] = true
            }
        }
    }
    return dp[len(nums)-1]
}

合并区间

打死不看🙈题解，我手搓了一个暴力改了好几回终于也过了😭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
const SIZE = 10001

func merge(intervals [][]int) [][]int {

    end := make([]int, SIZE) // 当前区间的结束位置
    v := make([]int, SIZE)   // 被区间覆盖次数

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

    // fmt.Println(intervals)

    for idx, interval := range intervals {
        if idx+1 < len(intervals) && intervals[idx][0] == intervals[idx+1][0] && intervals[idx][1] == intervals[idx+1][1] {
            continue
        }
        for i := interval[0]; i <= interval[1]; i++ {
            end[i] = interval[1]
            v[i]++
        }
    }
    // fmt.Println(end)
    // fmt.Println(v)
    var ans [][]int

    for i := 0; i < SIZE; i++ {
        // if v[end[i]] == 0{
        //     continue
        // }
        if i != 0 && end[i] == 0 {
            continue
        }
        if v[end[i]] == 1 {
            tmp := make([]int, 2)
            tmp[0] = i
            i = end[i]
            tmp[1] = i
            ans = append(ans, tmp)
        }
        if v[end[i]] >= 2 {
            tmp := make([]int, 2)
            tmp[0] = i
            for v[end[i]] >= 2 && i != end[i] {
                i = end[i]
            }
            i = end[i]
            tmp[1] = i
            // fmt.Println(tmp)
            ans = append(ans, tmp)
        }
    }
    return ans
}

其实有更简单的方法，也是先排序（这里以左端点为例），然后按照下面的思路处理

1
2
3
4
5
if 当前区间的左端点 <= 前一个区间的右端点 {
    与 ans 的最后一个区间合并（右端点取最大值）
} else {
    直接加入 ans
}

不同路径

我写的应该是记忆化搜索（？）和 dp 感觉没什么区别了👀

当然你还可以用排列组合公式一步到位哈哈哈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const N = 128
var count [][]int

func init(){
    count = make([][]int, N)
    for i := 0; i < N; i++ {
        count[i] = make([]int, N)
    }
    count[1][1]=1
}

func uniquePaths(m int, n int) int {
    if count[m][n] != 0 {
        return count[m][n]
    }
    if m-1 >= 0 {
        count[m][n] += uniquePaths(m-1, n)
    }
    if n-1 >= 0 {
        count[m][n] += uniquePaths(m, n-1)
    }
    return count[m][n]
}

最小路径和

这个也是 dp，但是我还是写了个记忆化搜索（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const N = 256
var count [][]int

func minPathSum(grid [][]int) int {
    count = make([][]int, N)
    for i := 0; i < N; i++ {
        count[i] = make([]int, N)
    }
    for i := 0; i < N; i++ {
        for j := 0; j < N; j++ {
            count[i][j] = math.MaxInt
        }
    }
    count[0][0] = grid[0][0]

    return dfs(len(grid)-1, len(grid[0])-1, grid)

}

func dfs(m, n int, grid [][]int) int {
    if count[m][n] != math.MaxInt {
        return count[m][n]
    }
    if m-1 >= 0 {
        count[m][n] = min(count[m][n], dfs(m-1, n, grid)+grid[m][n])
    }
    if n-1 >= 0 {
        count[m][n] = min(count[m][n], dfs(m, n-1, grid)+grid[m][n])
    }
    return count[m][n]
}

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

爬楼梯

最最经典的 dp 了！

1
2
3
4
5
6
7
8
9
10
11
const N = 64
var dp = make([]int, N)

func climbStairs(n int) int {
    dp[1] = 1
    dp[2] = 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

编辑距离

哇这个题目感觉有点难度

我先从暴搜开始想，感觉纯 BFS 还是纯 DFS 都不行，得剪枝，然后我还想到 A*，就像八数码那样，但是感觉应该是我想复杂了

然后我一看标签，卧槽动态规划，我只能说这也能用 dp？然后我就去乖乖地看题解了😭

这个评论感觉讲的很清楚，主要还是要理解转移方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func minDistance(word1 string, word2 string) int {
   m, n := len(word1), len(word2)
   dp := make([][]int, m+1)
   for i := range dp {
      dp[i] = make([]int, n+1)
   }

   for i := 0; i < m+1; i++ {
      dp[i][0] = i
   }
   for j := 0; j < n+1; j++ {
      dp[0][j] = j
   }
   for i := 1; i < m+1; i++ {
      for j := 1; j < n+1; j++ {
         if word1[i-1] == word2[j-1] {
            dp[i][j] = dp[i-1][j-1]
         } else {
            dp[i][j] = 1 + Min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
         }
      }
   }
   return dp[m][n]
}

func Min(args ...int) int {
   min := args[0]
   for _, item := range args {
      if item < min {
         min = item
      }
   }
   return min
}