leetcode733图像渲染刷题笔记

图像渲染

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。

题目分析

列出自己想到的线索

  • 维护一个存储要检查的点的集合，toBeChecked

根据题解进行分析

  • 题解里看到这道题的最佳解法是使用DFS(深度优先搜索)
  • 搜索了一下DFS，DFS里可以通过自己调用自己的方法，也就是递归来实现

递归

  • 递归的特点就是自己调用自己
  • 递归由两部分组成：（1）递归操作 （2）递归终止条件

一个最简单的递归

  • 计算从1，2，3公差为1的等差数列前n项和的程序
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 递归操作，进行一次加法操作
 * 递归终止条件，当前的数字等于1
 */
public int sum(int n) {
    int sum = 0;
    if (n == 1) {
        sum += 1;
    } else {
        sum = sum(n - 1) + n;
    }
    return sum;
}

递归增加

  • 计算从1，7，13公差为6的等差数列前n项和的程序
1
2
3
4
5
6
7
8
9
public int sum6(int n){
    int sum = 0;
    if(n == 1){
        sum += n;
    }else{
        sum = sum6(n - 6) + n;
    }
    return sum;
}

使用递归来解决这道题

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
/**
 * @param image 二维数组来代表原始的图片
 * @param sr 目标点的行号
 * @param sc 目标点的列号
 * @param color 目标点的新颜色
 * @return 上好色的图片
 */
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int oldColor = image[sr][sc];
    dfs(image, oldColor, sr, sc, color);
    return image;
}

/**
 * 递归
 * 递归操作：
 * 1. dfs 行号 - 1
 * 2. dfs 行号 + 1
 * 3. dfs 列号 - 1
 * 4. dfs 列号 + 1
 * 递归终止条件：
 * 1. 当前的行号<0
 * 2. 当前的列号<0
 * 3. 当前的行号>行长
 * 4. 当前的列号>行宽
 * 5. 当前的颜色不等于oldColor
 * 6. 当前的颜色等于新颜色
 * return;
 */
public void dfs(int[][] image, int oldColor, int sr, int sc, int newColor) {
    int rLength = image.length;
    int cLength = image[0].length;
    if(sr < 0 || sc < 0 || sr >= rLength || sc >= cLength || image[sr][sc] != oldColor || image[sr][sc] == newColor){
        return;
    }
    image[sr][sc] = newColor;

    dfs(image, oldColor, sr - 1, sc, newColor);
    dfs(image, oldColor, sr + 1, sc, newColor);
    dfs(image, oldColor, sr, sc - 1, newColor);
    dfs(image, oldColor, sr, sc + 1, newColor);
}

二叉树的前序遍历、中序遍历、后续遍历

  • dfs深度优先搜索最基础的应用应该就是用在二叉树的前中后序遍历上
  • 如下为通过递归实现二叉树前序遍历的代码
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<Integer> list = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        if(root != null){
            list.add(root.val);
        }
        
        if (root != null && root.left != null) {
            preorderTraversal(root.left);
        }

        if (root != null && root.right != null) {
            preorderTraversal(root.right);
        }
        return list;
    }
}

八皇后问题

  • 题目
1
2
3
4
5
class Solution {
    public List<List<String>> solveNQueens(int n) {

    }
}

题意

  • 入参n代表棋盘行的个数，列的个数，要摆放的皇后的个数
  • 输出字符串集合，点表示不放置棋子，Q表示放置皇后

解题思路

  • 定义属性，二维数组board[n][n], 解法编号count
  • 定义行为，isValid(), printBoard