1. 被围绕的区域
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
解法：
首先对边界上每一个’O’做深度优先搜索，将与其相连的所有’O’改为’-’。然后遍历矩阵，将矩阵中所有’O’改为’X’,将矩阵中所有’-‘变为’O’。
public class Solution {
private int row,col;
public void solve(char[][] board) {
if(board==null || board.length==0 || board[0].length==0) return;
row=board.length;
col=board[0].length;
//dfs遍历左右两条边
for(int i=0;i<row;i++){
dfs(board,i,0);
dfs(board,i,col-1);
}
//dfs遍历上下两条边
for(int j=1;j<col-1;j++){
dfs(board,0,j);
dfs(board,row-1,j);
}
//遍历所有元素。将‘O’改为‘X’，将‘-’改为‘O’
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(board[i][j]=='O'){
board[i][j]='X';
}
if(board[i][j]=='-'){
board[i][j]='O';
}
}
}
return;
}
private void dfs(char[][] board,int i,int j){
if(i>=row || i<0 || j>=col || j<0 || board[i][j]!='O'){
return;
}
board[i][j]='-';
dfs(board,i-1,j);
dfs(board,i+1,j);
dfs(board,i,j-1);
dfs(board,i,j+1);
return;
}
}
2. 单词接龙
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出: 5
解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的长度 5。
示例 2:
输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出: 0
解释: endWord “cog” 不在字典中，所以无法进行转换。
解法：
使用BFS(广度优先搜索)，先找和beginWord相差一个字符的单词，再找与该单词相差一个字符的单词，直至找到endWord。注意每次从字典中删除遍历过的单词。
import java.util.*;
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if(!wordList.contains(endWord)) return 0;
Queue<String> queue=new LinkedList<>();
queue.offer(beginWord);
wordList.remove(beginWord);
int i=1;
while(!queue.isEmpty()){
int size=queue.size();
while(size != 0){
String temp=queue.poll();
if(helper(endWord,temp)){
return ++i;
}
//在字典中找和temp相差一个字符的字符串
Iterator<String> iterator = wordList.iterator();
while(iterator.hasNext()){
String s = iterator.next();
if(helper(s,temp)){
queue.offer(s);
iterator.remove();//删除遍历过的单词，注意删除方式
}
}
size--;
}
i++;
}
return 0;
}
private boolean helper(String s,String p){
int count=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i) != p.charAt(i)){
count++;
}
}
return count == 1;
}
}
3. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]
给定 word = “ABCCED”, 返回 true.
给定 word = “SEE”, 返回 true.
给定 word = “ABCB”, 返回 false.
解法：
DFS，注意回溯！！！
public class Solution {
private int row,col;
private boolean[][] flag;
public boolean exist(char[][] board, String word) {
if(board == null || board.length == 0 || board[0].length == 0) return false;
if(word == null || word.length() == 0) return true;
row = board.length;
col = board[0].length;
flag = new boolean[row][col];
for(int i = 0;i < row;i++){
for(int j = 0;j < col;j++){
if(dfs(board, i, j, word, 0))//以每个元素为起点，进行DFS
return true;
}
}
return false;
}
private boolean dfs(char[][] board, int i, int j, String word, int index){
if(index == word.length()) return true;
if(i < 0 || i >= row || j < 0 || j >= col || flag[i][j] || board[i][j] != word.charAt(index)){
return false;
}
index++;
flag[i][j] = true;
if(dfs(board, i-1, j, word, index) || dfs(board, i+1, j, word, index)
|| dfs(board, i, j-1, word, index) || dfs(board, i, j+1, word, index)){
return true;
}
flag[i][j] = false;//回溯
return false;
}
}
4. 组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解法：DFS+回溯
递归过程：
import java.util.ArrayList;
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
int n;
int k;
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
this.n = n;
this.k = k;
backtrack(1,new ArrayList<Integer>());
return res;
}
private void backtrack(int first,ArrayList<Integer> curr){
if(curr.size() == k){
res.add(new ArrayList<Integer>(curr));
}
for(int i = first;i < n+1;i++){
// add i into the current combination
curr.add(i);
// use next integers to complete the combination
backtrack(i+1,curr);
// backtrack
curr.remove(curr.size()-1);
}
}
}
5. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括 target）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解法：DFS+回溯，注意与上题不同，一个元素可以重复多次。
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
private ArrayList<Integer> curr = new ArrayList<>();
private int[] candidates;
public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
this.candidates = candidates;
Arrays.sort(candidates);
backtrack(0,target);
return res;
}
private void backtrack(int start,int target){
if(target < 0) return;
if(target == 0){
res.add(new ArrayList<>(curr));
return;
}
for(int i = start;i < candidates.length;i++){
curr.add(candidates[i]);
//candidates[i]可以被重复选取
backtrack(i,target - candidates[i]);
curr.remove(curr.size()-1);
}
return;
}
}
6. 组合总和||
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
解法：和上一题的区别是 candidates 可能有重复元素，每个数字在每个组合中只能使用一次。
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
private ArrayList<Integer> curr = new ArrayList<>();
private int[] candidates;
public ArrayList<ArrayList<Integer>> combinationSum2(int[] candidates, int target) {
this.candidates = candidates;
Arrays.sort(candidates);
backtrack(0,target);
return res;
}
private void backtrack(int start,int target){
if(target < 0) return;
if(target == 0){
res.add(new ArrayList<>(curr));
return;
}
for(int i = start;i < candidates.length;i++){
//如果当前选择的第一个数和上一个数相同，则跳过
if(i > start && candidates[i] == candidates[i-1]) continue;
curr.add(candidates[i]);
//candidates[i]只能被选择一次
backtrack(i+1,target - candidates[i]);
curr.remove(curr.size()-1);
}
return;
}
}
京公网安备 11010502036488号