递归
编写递归要决，千万不要用人脑去递和归每一层，正确的做法是找到如何分解为子问题，然后几个子问题的关系是什么。然后翻译成代码。
leetcode17
题目描述:
| 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。  示例: 输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 |
解题思路
先说最简单的，对应数字与字符的对应关系，我们可以用数组来记录，下标为代表0到9的数字，值即为每个字符串，由于0和1都没有字符，为了使用方便，还是使用空字符来占用。即可表示为
String[] dict = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
再来说如何组合所有可能性，还不能重复。比如输入23
类比我们人脑来处理的过程就是这样：
先取2的第一个字符与后面每个字符组合，然后再取出3的每个字符与后面组合即可得到所有可能性。
使用递归还求解，需定能定义出来递推公式，可我数学公式基本已经还给老师了，实在是对不起老师呀，还是来想想处理过程吧。
递归需要我们将问题分解为多个子问题。那我们如何分解呢？
刚刚人脑的处理过程就取出数字对应的字符串，然后一个一个的遍历，与之前的字符进行组合，这是递归的处理逻辑，当我们遍历到输入数字最后一个时，就需要将每个数字组合进行记录。这是递归的终止条件。
然后我们此翻译成代码：
解题实现
| public class RecurstionSolution { private static final String[] STAT_CODE = new String[] {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; public List<String> letterCombinations(String digits) { List<String> result = new ArrayList<>(); if (digits == null || digits.isEmpty()) { return result; } String inputData = digits.trim(); // 1,将输入的字符转化为数字 int[] dataNum = new int[inputData.length()]; for (int i = 0; i < inputData.length(); i++) { dataNum[i] = inputData.charAt(i) - '0'; } String dataChar = ""; this.recurstionData(dataNum, 0, result, dataChar); return result; } private void recurstionData(int[] dataNum, int index, List<String> list, String dataChar) { // 1，递归的终止条件 if (index == dataNum.length) { list.add(new String(dataChar)); return; } // 进行递归的求解 for (int i = 0; i < STAT_CODE[dataNum[index]].length(); i++) { dataChar = dataChar + STAT_CODE[dataNum[index]].charAt(i); // 当取出一个字符后继续进行遍历 this.recurstionData(dataNum, index + 1, list, dataChar); // 当遍历完成后，需要删除当前的最后一个字符,以可以与其他进行组合 dataChar = dataChar.substring(0, dataChar.length() - 1); } } } |
leetcod22
题目描述:
| 22. 括号生成 给出 n 代表生成括号的对数，请你写出一个函数， 使其能够生成所有可能的并且有效的括号组合。 例如，给出 n = 3，生成结果为： [ "((()))", "(()())", "(())()", "()(())", "()()()" ] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/generate-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 |
解题思路：
这个题目说实话我也做错了，我开始的解题思路是以成对的括号为单位，我想的是在括号的左边 ，右边，还有中间，依次的插入号位，递归这样就可以求解了，但当我实现的时候，我发现，我的思路是错误的，因为当遍历到多层时，这个中间括号已经无法再明确的定义，需要寻找其他解法。
我又来参照了其他的方案，终于理解了这个递归的求解方法：
这个问题的求解可以分为两部分，添加左括号、和添加右括号，添加的个数正好是输入的数字，例如3，就是可以添加3个左括号和3个右括号。
那现在就是如何添加左括号和右括号的问题：
先说左括号，最大左括号不就是输入的数字么，所以需要一个左括号的索引来记录当前是第几个左括号，需要小于最大左括号。添加一个括号即可
当左括号添加了，那右括号嗯，是否和左括号一样，这个还是有点不一样呢，右括号需要与左括号成对出现，就不能出现右括号比左括号还多的情况，这样最大右括号需要小于当前的左括号数了。
递归终止条件是什么呢，当然是当前括号数满足了输入的括号数*2，例如输入3，就是6个，左路输入左右括号数，一样要是6个。现在来翻译成代码吧.
递归代码实现
| public class SolutionParthese2 { public static final String PARENTHESE_LEFT = "("; public static final String PARENTHESE_RIGHT = ")"; public List<String> generateParenthesis(int num) { List<String> result = new ArrayList<>(); if (num == 1) { result.add(PARENTHESE_LEFT + PARENTHESE_RIGHT); return result; } if (num == 0) { return result; } this.recurstion(num, 0, 0, result, ""); return result; } public void recurstion(int maxNum, int left, int right, List<String> resultLst, String data) { // 1,首先写递归的终止条件 if (data.length() == maxNum * 2) { resultLst.add(data); return; } // 添加左括号 if (left < maxNum) { this.recurstion(maxNum, left + 1, right, resultLst, data + PARENTHESE_LEFT); } // 添加右括号，右括号，需要小于左括号，否则不对成对了 if (right < left) { this.recurstion(maxNum, left, right + 1, resultLst, data + PARENTHESE_RIGHT); } } } |
leetcode39
题目描述:
| 39. 组合总和 给定一个无重复元素的数组 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] ] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 |
解题思路:
这个是一个求组合的问题，我的求解思路是这样子的，将数组中的每个元素，从当前自己开始，依次与一个元素相加，如果超过了，说明符不合，如果与预期值相同，则记录下来，未到达退出条件则继续递归。为了确保无重复的数据，可使用set来进行存储
编码实现
| public class SolutionMySelf { public List<List<Integer>> combinationSum(int[] inputSrc, int target) { if (inputSrc == null || inputSrc.length == 0) { return null; } List<Integer> currList = new ArrayList<>(); Set<List<Integer>> collect = new HashSet<>(); this.recurstion(inputSrc, target, 0, 0, currList, collect); List<List<Integer>> result = new ArrayList<>(collect); return result; } private void recurstion( int[] inputSrc, int target, int value, int startIndex, List<Integer> collect, Set<List<Integer>> resultList) { // 1,递归的终止条件 if (value == target) { resultList.add(new ArrayList<>(collect)); return; } // 2,超过出说明不符合直接退出 if (value > target) { return; } for (int i = startIndex; i < inputSrc.length; i++) { value = value + inputSrc[i]; collect.add(inputSrc[i]); this.recurstion(inputSrc, target, value, i, collect, resultList); // 当结束后，需要移除最后一个元素 collect.remove(collect.size() - 1); value = value - inputSrc[i]; } } } |
leetcode46
题目描述:
| 给定一个没有重复数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 |
解题思路:
我的解题思路就是将数组中的每个元素与剩下的两个元素进行组合，当给合的大小与数组大小一致就放入到结果集中。那如何表示剩余下元素呢，我的办法是将已经遍历过程下标通过一个boolean数组记录下来，这样就能知道了
代码实现
| public class SolutionPermute { public List<List<Integer>> permute(int[] nums) { Set<List<Integer>> data = new HashSet<>(); List<Integer> currdata = new ArrayList<>(); boolean[] exists = new boolean[nums.length]; this.recurstion(nums, data, currdata, exists); List<List<Integer>> result = new ArrayList<>(data); return result; } private void recurstion( int[] nums, Set<List<Integer>> data, List<Integer> currdata, boolean[] exists) { // 如果当前组合到达组合的结果大小，则加入到结果集中 if (currdata.size() == nums.length) { data.add(new ArrayList<>(currdata)); return; } for (int i = 0; i < nums.length; i++) { // 仅对未遍历过元素进行遍历 if (!exists[i]) { exists[i] = true; currdata.add(nums[i]); this.recurstion(nums, data, currdata, exists); currdata.remove(currdata.size() - 1); exists[i] = false; } } } } |
leetcode79
题目描述:
| 79. 单词搜索 给定一个二维网格和一个单词，找出该单词是否存在于网格中。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false. 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-search 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 |
解题思路
针对此单词搜索，因为存在4种匹配的情况：
情况1，横坐标+1可匹配
情况2，横坐标-1可匹配
情况3，纵坐标+1可匹配
情况4，纵坐标-1可匹配
递归的终止条件呢？当发生字符不匹配，搜索终止，或者搜索到匹配字符，搜索终止，那过有其他条件吗？当然有，那就是横纵坐标，必须在字符的下标范围以内
代码实现
| public class SolutionRectustionMySelf { public boolean exist(char[][] src, String data) { boolean[][] exists = new boolean[src.length][src[0].length]; boolean existsResult = false; String srcvalue = null; //搜索开始的字符位置 for (int i = 0; i < src.length; i++) { for (int j = 0; j < src[i].length; j++) { srcvalue = String.valueOf(src[i][j]); if (data.startsWith(srcvalue)) { existsResult = this.exist(src, "", data, i, j, exists); if (existsResult) { return true; } } } } return false; } public boolean exist( char[][] src, String currData, String targetData, int rowindex, int cellindex, boolean[][] exists) { if (currData.equals(targetData)) { return true; } if (rowindex < 0 || rowindex >= src.length) { return false; } if (cellindex < 0 || cellindex >= src[rowindex].length) { return false; } // 节点已经访问，则标识为false if (exists[rowindex][cellindex]) { return false; } currData = currData + src[rowindex][cellindex]; if (currData.length() > targetData.length()) { return false; } // 在进入时标识已经访问 exists[rowindex][cellindex] = true; // 当字符匹配的时，可能存在4个方向的情况 if (targetData.startsWith(currData)) { if (exist(src, currData, targetData, rowindex + 1, cellindex, exists) || exist(src, currData, targetData, rowindex, cellindex + 1, exists) || exist(src, currData, targetData, rowindex - 1, cellindex, exists) || exist(src, currData, targetData, rowindex, cellindex - 1, exists)) { return true; } } // 退出时还需要标识出未访问 exists[rowindex][cellindex] = false; return false; } } |
![#每日一题 力扣第28题 采购方案[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)