算法刷题笔记 (20) 螺旋矩阵II 单词搜索 旋转图像 零钱兑换

螺旋矩阵 II

螺旋矩阵 II

解题思路

生成一个空的矩阵，随后模拟整个向内环绕的填入过程。定义上下左右边界up, down, left, right，设被填入的数字为num。当num <= n*n时循环，始终按照上、右、下、左的顺序填入数字

解题代码

func generateMatrix(n int) [][]int {
    // 生成一个空矩阵
    matrix := make([][]int, n)
    for i := 0; i < n; i++ {
        matrix[i] = make([]int, n)
    }
    // 定义上下左右边界
    up, down, left, right := 0, n-1, 0, n-1
    num := 1    // 待填入的数字
    // 螺旋遍历矩阵，填入数字
    for num <= n*n {
        // 填写上边界
        for i := left; i <= right; i++ {
            matrix[up][i] = num
            num++
        }
        up++
        // 填写右边界
        for i := up; i <= down; i++ {
            matrix[i][right] = num
            num++
        }
        right--
        // 填写下边界
        for i := right; i >= left; i-- {
            matrix[down][i] = num
            num++
        }
        down--
        // 填写左边界
        for i := down; i >= up; i-- {
            matrix[i][left] = num
            num++
        }
        left++
    }

    return matrix
}

单词搜索

单词搜索

解题思路

回溯算法，把从每一个字符开始进行的搜索过程看作是一棵树，因为可以有上下左右四个方向，所以这棵树的分支数为四。同时，因为字母不允许重复利用，所以可以设立二维数组chosen[m][n]来记录字母是否被选择过。

解题代码

func exist(board [][]byte, word string) bool {
    m := len(board)
    n := len(board[0])
    // 记录以及选择的节点 
    chosen := make([][]bool, m)
    for i := 0; i < m; i++ {
        chosen[i] = make([]bool, n)
    }
    // 上下左右四个方向
    directions := [][]int{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} }
    // 回溯函数
    var backtrack func(x, y, begin int) bool
    backtrack = func(x, y, begin int) bool {    // 从board[x][y]开始进行深度优先遍历，查找的字符为word[begin]
        if board[x][y] != word[begin] {
            return false
        }
        if begin == len(word)-1 {
            return true
        }
        chosen[x][y] = true     // 已经选择了board[x][y]
        // 对上下左右四个方向进行深度优先遍历
        for _, dirt := range directions {
            nextX := x + dirt[0]
            nextY := y + dirt[1]
            if nextX < 0 || nextX >= m || nextY < 0 || nextY >= n || chosen[nextX][nextY] {
                // 若越界，或者已经选择过，则跳过
                continue
            }
            if backtrack(nextX, nextY, begin+1) {
                return true
            }
        }
        // 状态恢复
        chosen[x][y] = false

        return false
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if backtrack(i, j, 0) {
                return true
            }
        }
    }

    return false
}

旋转图像

旋转图像

解题思路

1. 利用辅助数组aux，将原数组的值拷贝到辅助数组中去。注意到第i行的第j个元素，在旋转后在倒数第i列的第j个元素，所以得到关系式matrix[j][n-i-1] = aux[i][j]
2. 原地旋转，https://leetcode-cn.com/problems/rotate-image/solution/48-xuan-zhuan-tu-xiang-fu-zhu-ju-zhen-yu-jobi/

解题代码

1. 辅助数组

func rotate(matrix [][]int)  {
    n := len(matrix)
    // 辅助数组定义及其初始化
    aux := make([][]int, n)
    for i := 0; i < n; i++ {
        aux[i] = make([]int, n)
        copy(aux[i], matrix[i])     // 将原数组的值复制到辅助数组中
    }
    // 开始旋转图像
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            matrix[j][n-i-1] = aux[i][j]
        }
    }
}

2. 原地旋转

func rotate(matrix [][]int)  {
    n := len(matrix)
    for i := 0; i < n/2; i++ {
        for j := 0; j < (n+1)/2; j++ {
            temp := matrix[i][j]
            matrix[i][j] = matrix[n-j-1][i]
            matrix[n-j-1][i] = matrix[n-i-1][n-j-1]
            matrix[n-i-1][n-j-1] = matrix[j][n-i-1]
            matrix[j][n-i-1] = temp
        }
    }    
}

零钱兑换

零钱兑换

解题思路

利用动态规划，定义dp[i]为组成金额i所需要的最少硬币数量

• 初始条件：dp[0]=0
• 状态转移方程：dp[i] = min(dp[j])+1, 0<=j<len(coins)

解题代码

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)     // 声明dp数组
    for i := 1; i <= amount; i++ {
        dp[i] = math.MaxInt64
        for j := 0; j < len(coins); j++ {
            if coins[j] <= i && dp[i-coins[j]] < math.MaxInt64 {
                dp[i] = min(dp[i], dp[i-coins[j]]+1)
            }
        }
    }
    if dp[amount] == math.MaxInt64 {
        return -1
    } else {
        return dp[amount]
    }
}

func min(n1, n2 int) int {
    if n1 < n2 {
        return n1
    } else {
        return n2
    }
}