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