玩转算法 第六天 递归回溯问题

第六天 递归回溯问题

17. 电话号码的字母组合131. 分割回文串93. 复原IP地址46. 全排列47. 全排列 II77. 组合39. 组合总和40. 组合总和 II216. 组合总和 III78. 子集90. 子集 II401. 二进制手表79. 单词搜索200. 岛屿数量130. 被围绕的区域417. 太平洋大西洋水流问题51. N 皇后52. N皇后 II

17. 电话号码的字母组合

class Solution { //一个映射表，第二个位置是"abc“,第三个位置是"def"。。。 private String letterMap[] = { " ", //0 "", //1 "abc", //2 "def", //3 "ghi", //4 "jkl", //5 "mno", //6 "pqrs", //7 "tuv", //8 "wxyz" //9 }; private ArrayList<String> res= new ArrayList<String>(); public List<String> letterCombinations(String digits) { //注意边界条件 if(digits.equals("")) return res; findCombination(digits, 0, ""); return res; } private void findCombination(String digits, int index, String s){ //如果是最后一个字符，直接返回 if(index == digits.length()){ res.add(s); return; } //map_string的下表是从0开始一直到9， c-'0'就可以取到相对的数组下标位置 //比如c=2时候，2-'0'，获取下标为2,letter_map[2]就是"abc" Character c = digits.charAt(index); String letters = letterMap[c - '0']; //遍历字符串，比如第一次得到的是2，页就是遍历"abc" for(int i = 0 ; i < letters.length() ; i ++){ //调用下一层递归 findCombination(digits, index+1, s + letters.charAt(i)); } } }

131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。 示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]

93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。 例如：“0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效的 IP 地址。 示例 1： 输入：s = “25525511135” 输出：[“255.255.11.135”,“255.255.111.35”]

46. 全排列

class Solution { List<List<Integer>> res = new LinkedList<>(); public List<List<Integer>> permute(int[] nums) { //用于记录已经选过的数字 LinkedList<Integer> track = new LinkedList<>(); //回溯法 backtarck(nums,track); return res; } private void backtarck(int[] nums,LinkedList<Integer> track){ //递归结束条件 if(track.size() == nums.length){ res.add(new LinkedList<Integer>(track)); } for(int i = 0;i < nums.length;i++){ //排除已有的数字 if(track.contains(nums[i])){ continue; } //选出一个数字 track.add(nums[i]); //进行下一级的选择 backtarck(nums,track); //递归结束，添加完成后，将元素一个个删除 //这样才能继续向下找答案 track.removeLast(); } } }

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

77. 组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { backtrack(new LinkedList<>(),n,k,0); return res; } public void backtrack(LinkedList<Integer> list,int n,int k,int count){ if(list.size() == k){ res.add(new LinkedList(list)); return; } for(int i = count+1;i <= n;i++){ list.add(i); backtrack(list,n,k,i); list.removeLast(); } } }

39. 组合总和

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 说明： 所有数字都是正整数。 解集不能包含重复的组合。

78. 子集

class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res=new ArrayList<>(); res.add(new ArrayList<>()); for(int i=0;i<nums.length;i++){ int n=res.size(); for(int j=0;j<n;j++){ List<Integer> list=new ArrayList<>(res.get(j)); if (i >0 && nums[i] == nums[i - 1]) { continue; } list.add(nums[i]); res.add(list); } } return res; } }

90. 子集 II

401. 二进制手表

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。 每个 LED 代表一个 0 或 1，最低位在右侧。

例如，上面的二进制手表读取 “3:25”。 给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。 示例： 输入: n = 1 返回: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”] 提示： 输出的顺序没有要求。 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。 超过表示范围（小时 0-11，分钟 0-59）的数据将会被舍弃，也就是说不会出现 “13:00”, “0:61” 等时间。

79. 单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution { public boolean exist(char[][] board, String word) { char[] words=word.toCharArray(); for(int i=0;i<board.length;i++){ for(int j=0;j<board[0].length;j++){ if(dfs(board,words,i,j,0)) return true; } } return false; } public boolean dfs(char[][] board,char[] words,int i,int j,int k){ if(i>=board.length||i<0||j>=board[0].length||j<0||board[i][j]!=words[k]) return false; if(k==words.length-1) return true; char temp=board[i][j]; board[i][j]=' '; boolean res=dfs(board,words,i+1,j,k+1)||dfs(board,words,i-1,j,k+1)||dfs(board,words,i,j+1,k+1)||dfs(board,words,i,j-1,k+1); board[i][j]=temp; return res; } }

200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

130. 被围绕的区域

给定一个二维的矩阵，包含 ‘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

417. 太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。 提示： 输出坐标的顺序不重要 m 和 n 都小于150 示例：

51. N 皇后

52. N皇后 II