DFS和BFS例题
-
机器人的运动范围：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/ ，使用bfs和dfs
import java.util.*;
public class P面试题13JiQiRenDeYunDongFanWeiLcof {
//输入：m = 2, n = 3, k = 1
//输出：3
public static void main(String[] args) {
Solution solution = new P面试题13JiQiRenDeYunDongFanWeiLcof().new Solution();
// TO TEST
System.out.println(solution.movingCount(2, 3, 1));
System.out.println(solution.movingCount1(2, 3, 1));
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
int count = dfs(m, n, visited, 0, 0, k);
return count;
}
public int movingCount1(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
LinkedList<int[]> queue = new LinkedList<>();
queue.push(new int[]{0, 0});
int count = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = size; i > 0; i--) {
int[] value = queue.poll();
int row = value[0];
int col = value[1];
if (check(m, n, visited, row, col, k)) {
visited[row][col] = true;
count++;
queue.push(new int[]{row + 1, col});
queue.push(new int[]{row, col + 1});
queue.push(new int[]{row - 1, col});
queue.push(new int[]{row, col - 1});
}
}
}
return count;
}
private int dfs(int m, int n, boolean[][] visited, int row, int col, int k) {
int count = 0;
if (check(m, n, visited, row, col, k)) {
visited[row][col] = true;
count = 1 + dfs(m, n, visited, row + 1, col, k) +
dfs(m, n, visited, row, col + 1, k) +
dfs(m, n, visited, row - 1, col, k) +
dfs(m, n, visited, row, col - 1, k);
}
return count;
}
private boolean check(int m, int n, boolean[][] visited, int row, int col, int k) {
if (row >= 0 && col >= 0 && row < m && col < n && !visited[row][col] && getSum(row, col, k)) {
return true;
}
return false;
}
private boolean getSum(int row, int col, int k) {
int sum = 0;
while (row > 0) {
sum += (row % 10);
row /= 10;
}
while (col > 0) {
sum += (col % 10);
col /= 10;
}
if (sum <= k) {
return true;
}
return false;
}
}
}
-
矩阵中的路径：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/ ，dfs
public class P面试题12JuZhenZhongDeLuJingLcof{
public static void main(String[] args) {
Solution solution = new P面试题12JuZhenZhongDeLuJingLcof().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public boolean exist(char[][] board, String word) {
int n = board.length;
int m = board[0].length;
boolean[][] visit = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (hasPath(board, visit, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean hasPath(char[][] board, boolean[][] visit, String word, int row, int col, int pathLength) {
if (pathLength >= word.length()) { //结束条件
return true;
}
boolean has = false;
if (row >= 0 && col >= 0 && //可行情况处理
row < board.length &&
col < board[0].length &&
board[row][col] == word.charAt(pathLength) &&
!visit[row][col]) {
++pathLength;
visit[row][col] = true; //处理标记
has = hasPath(board, visit, word, row + 1, col, pathLength) ||
hasPath(board, visit, word, row, col + 1, pathLength) ||
hasPath(board, visit, word, row - 1, col, pathLength) ||
hasPath(board, visit, word, row, col - 1, pathLength);
if (!has) { //还原标记
--pathLength;
visit[row][col] = false;
}
}
return has;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
-
全排列：https://leetcode-cn.com/problems/permutations/ ，dfs
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class P46Permutations {
//输入: [1,2,3]
public static void main(String[] args) {
Solution solution = new P46Permutations().new Solution();
// TO TEST
System.out.println(solution.permute(new int[]{1, 2, 3}));
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
if (nums == null) {
return lists;
}
ArrayList<Integer> output = new ArrayList<>();
for (int num : nums) {
output.add(num);
}
dfs(lists, output, 0);
return lists;
}
private void dfs(List<List<Integer>> lists, ArrayList<Integer> output, int position) {
int len = output.size();
if (position == len - 1) { //到达了最后一个元素则不需要在递归了
lists.add(new ArrayList<>(output));
return;
}
for (int i = position; i < len; i++) {
Collections.swap(output, position, i); //交换
dfs(lists, output, position + 1); //递归
Collections.swap(output, position, i); //还原
}
}
}
}
-
面试题34. 二叉树中和为某一值的路径：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
-
dfs：减少dfs中参数个数，去掉当前路径以及总路径集合
class Solution {
public List<List<Integer>> lists = new ArrayList<>();
public List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null) {
return lists;
}
dfs(root, sum, 0, path);
return lists;
}
private void dfs(TreeNode root, int sum, int num, List<Integer> path) {
if (root == null) {
return;
}
path.add(root.val);
num = num + root.val;
if (sum == num && root.left == null && root.right == null) {
lists.add(new ArrayList<>(path));
}
dfs(root.left, sum, num, path);
dfs(root.right, sum, num, path);
path.remove(path.size() - 1);
}
}