leetcode17号问题
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
image
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
class Solution {
Map<String, String> phone = new HashMap<String, String>() {{
put("2", "abc");
put("3", "def");
put("4", "ghi");
put("5", "jkl");
put("6", "mno");
put("7", "pqrs");
put("8", "tuv");
put("9", "wxyz");
}};
List<String> output = new ArrayList<String>();
public void backtrack(String combination, String next_digits) {
// if there is no more digits to check
if (next_digits.length() == 0) {
// the combination is done
output.add(combination);
}
// if there are still digits to check
else {
// iterate over all letters which map
// the next available digit
String digit = next_digits.substring(0, 1);
String letters = phone.get(digit);
for (int i = 0; i < letters.length(); i++) {
String letter = phone.get(digit).substring(i, i + 1);
// append the current letter to the combination
// and proceed to the next digits
backtrack(combination + letter, next_digits.substring(1));
}
}
}
public List<String> letterCombinations(String digits) {
if (digits.length() != 0)
backtrack("", digits);
return output;
}
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
这道题适合使用回溯算法
回溯法
是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认 不是 一个解的话（或者至少不是 最后一个 解），回溯算法会通过在上一步进行一些变化抛弃该解，即 回溯 并且再次尝试。
这里有一个回溯函数，使用第一个整数的索引作为参数 backtrack(first)。
如果第一个整数有索引 n，意味着当前排列已完成。
遍历索引 first 到索引 n - 1 的所有整数。Iterate over the integers from index first to index n - 1.
在排列中放置第 i 个整数，
即 swap(nums[first], nums[i]).
继续生成从第 i 个整数开始的所有排列: backtrack(first + 1).
现在回溯，即通过 swap(nums[first], nums[i]) 还原.
.
class Solution {
public void backtrack(int n,
ArrayList<Integer> nums,
List<List<Integer>> output,
int first) {
// if all integers are used up
if (first == n)
output.add(new ArrayList<Integer>(nums));
for (int i = first; i < n; i++) {
// place i-th integer first
// in the current permutation
Collections.swap(nums, first, i);
// use next integers to complete the permutations
backtrack(n, nums, output, first + 1);
// backtrack
Collections.swap(nums, first, i);
}
}
public List<List<Integer>> permute(int[] nums) {
// init output list
List<List<Integer>> output = new LinkedList();
// convert nums into list since the output is a list of lists
ArrayList<Integer> nums_lst = new ArrayList<Integer>();
for (int num : nums)
nums_lst.add(num);
int n = nums.length;
backtrack(n, nums_lst, output, 0);
return output;
}
}
链接：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode/
77. 组合
难度中等231 收藏 分享 切换为英文 关注 反馈
给定两个整数 n 和 k，返回 1 ... *n *中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
class Solution {
List<List<Integer>> res = new LinkedList();
public void generate(int n,int k,int start,LinkedList<Integer> c){
if(c.size()==k)
{res.add(new LinkedList(c));
// System.out.println(res);
return;}
for(int i=start;i<=n;i++){ //从1到n，start是从1开始，但是后面不会考虑1.去重。已经找到的存入c中
c.add(i);
generate(n,k,i+1,c);
// System.out.println(c);//之前已经放入了i
c.removeLast();
}
return;
}
public List<List<Integer>> combine(int n, int k) {
if(n<=0||k<=0||k>n)
return res;
LinkedList<Integer> c = new LinkedList();
generate(n,k,1,c);
return res;
}
}
这个程序可以优化
比如在1234中4可以不取，这步可以优化
回溯法的剪枝
改为for（int i=staart;i<-=n-(k-c.size())+1;i++）
二维平面上使用回溯法
79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
class Solution {
int [][] d=new int[][] {{-1,0},{0,1},{1,0},{0,-1}};
int m,n;
boolean[][] visited;//检查是否访问过
public boolean exist(char[][] board, String word) {
m=board.length;
n=board[0].length;
visited = new boolean[m][n];
for(int i=0;i<board.length;i++)
for(int j=0;j<board[i].length;j++)
if(searchword(board,word,0,i,j))
return true;
return false;
}
private boolean in(int x,int y){//判断点是否在区域内
return x>=0&&x<m&&y>=0&&y<n;
}
private boolean searchword(char[][] board,String word,int index,int startx,int starty){ //从borad[x][y]开始寻找
if(index==(word.length()-1))
return board[startx][starty]==word.charAt(index);
if(board[startx][starty]==word.charAt(index)){
//从startx，starty出发，向四个方向寻找
visited[startx][starty]=true;
for(int i=0;i<4;i++)
{
int newx=startx+d[i][0];
int newy=starty+d[i][1];//这样就可以向四个方法行动
if(in(newx,newy)&&!visited[newx][newy]){//检查是否在区域内且是否遍历过
if(searchword(board,word,index+1,newx,newy))
return true;
}
}
visited[startx][starty]=false;//没找到重置为false
}
return false;
}
}
floodfill算法
来自leetcode200
200. 岛屿数量
难度中等413 收藏 分享 切换为英文 关注 反馈
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
</pre>
示例 2:
输入:
11000
11000
00100
00011
输出: 3
class Solution {
int [][] d=new int[][] {{0,1},{1,0},{0,-1},{-1,0}};
int m,n;
boolean[][] visited;//检查是否访问过
public int numIslands(char[][] grid) {
m=grid.length;
int res=0;
if(grid.length==0)
return res;
n=grid[0].length;
visited = new boolean[m][n];
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(grid[i][j]=='1' && !visited[i][j]){
res++;
dfs(grid,i,j);
}
return res;
}
private boolean in(int x,int y){//判断点是否在区域内
return x>=0&&x<m&&y>=0&&y<n;
}
//从grid[x][y]开始，进行floodfill
void dfs(char[][] grid,int x,int y){
visited[x][y]=true;
for(int i=0;i<4;i++)
{int newx=x+d[i][0];
int newy=y+d[i][1];
if(in(newx,newy) && !visited[newx][newy] && grid[newx][newy]=='1')
dfs(grid,newx,newy);
}
return;
}
}
回溯法是经典人工智能的基础
51. N皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
image
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 *n *皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。</pre>
来源于题解
https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode/
class Solution {
int rows[];
// "hill" diagonals
int hills[];
// "dale" diagonals
int dales[];
int n;
// output
List<List<String>> output = new ArrayList();
// queens positions
int queens[];
public boolean isNotUnderAttack(int row, int col) {
int res = rows[col] + hills[row - col + 2 * n] + dales[row + col];
return (res == 0) ? true : false;
}
public void placeQueen(int row, int col) {
queens[row] = col;
rows[col] = 1;
hills[row - col + 2 * n] = 1; // "hill" diagonals
dales[row + col] = 1; //"dale" diagonals
}
public void removeQueen(int row, int col) {
queens[row] = 0;
rows[col] = 0;
hills[row - col + 2 * n] = 0;
dales[row + col] = 0;
}
public void addSolution() {
List<String> solution = new ArrayList<String>();
for (int i = 0; i < n; ++i) {
int col = queens[i];
StringBuilder sb = new StringBuilder();
for(int j = 0; j < col; ++j) sb.append(".");
sb.append("Q");
for(int j = 0; j < n - col - 1; ++j) sb.append(".");
solution.add(sb.toString());
}
output.add(solution);
}
public void backtrack(int row) {
for (int col = 0; col < n; col++) {
if (isNotUnderAttack(row, col)) {
placeQueen(row, col);
// if n queens are already placed
if (row + 1 == n) addSolution();
// if not proceed to place the rest
else backtrack(row + 1);
// backtrack
removeQueen(row, col);
}
}
}
public List<List<String>> solveNQueens(int n) {
this.n = n;
rows = new int[n];
hills = new int[4 * n - 1];
dales = new int[2 * n - 1];
queens = new int[n];
backtrack(0);
return output;
}
}
网友评论