图像渲染
有一幅以 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
9public int sum6(int n){
int sum = 0;
if(n == 1){
sum += n;
}else{
sum = sum6(n - 6) + n;
}
return sum;
}
使用递归来解决这道题
1 | /** |
二叉树的前序遍历、中序遍历、后续遍历
- 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
5class Solution {
public List<List<String>> solveNQueens(int n) {
}
}
题意
- 入参n代表棋盘行的个数,列的个数,要摆放的皇后的个数
- 输出字符串集合,点表示不放置棋子,Q表示放置皇后
解题思路
- 定义属性,二维数组board[n][n], 解法编号count
- 定义行为,isValid(), printBoard