程序员面试金典---14

颜色填充

思路：使用深搜就可解决

• 对坐标点(sr,sc)进行填充。
• 然后在此处进行扩散。

代码：

function fill(image, sr, sc, newColor) {
    // 记录初始颜色值
    const oldColor = image[sr][sc];
    // 如果新颜色与初始颜色相同则无需填充
    if (newColor === oldColor) {
        return image;
    }
    
    // 定义递归函数，用于遍历周围区域
    function dfs(i, j) {
        // 如果坐标不合法或已经填充过，则返回
        if (i < 0 || i >= image.length || j < 0 || j >= image[0].length || image[i][j] !== oldColor) {
            return;
        }
        // 填充当前坐标点
        image[i][j] = newColor;
        // 递归四个方向
        dfs(i-1, j);
        dfs(i+1, j);
        dfs(i, j-1);
        dfs(i, j+1);
    }
    
    // 调用递归函数填充周围区域
    dfs(sr, sc);
    // 返回填充后的图像
    return image;
}

硬币

思路：

动态规划->完全背包-> 循环外放物品，循环内放背包

/**
 * @param {number} n
 * @return {number}
 */
var waysToChange = function(n) {
    const value = [25, 10, 5, 1]

    const dp = new Array(n + 1).fill(0)
    dp[0] = 1
	// 外循环物品
    for(let i = 0;i < 4; i++){
        // 内循环背包
        for(let j = value[i]; j <= n; j++){
            dp[j] = (dp[j] + dp[j - value[i]]) % 1000000007
        }
    }

    return dp[n]
};