本文主要是介绍力扣爆刷第124天之回溯五连刷,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣爆刷第124天之回溯五连刷(分割回文、复原IP、子集)
文章目录
- 力扣爆刷第124天之回溯五连刷(分割回文、复原IP、子集)
- 一、131. 分割回文串
- 二、93. 复原 IP 地址
- 三、78. 子集
- 四、90. 子集 II
- 五、91. 非递减子序列
一、131. 分割回文串
题目链接:https://leetcode.cn/problems/palindrome-partitioning/description/
思路:常规组合题,需要起始位置,然后只需要在向下递归的时候判断一下是否是回文,是回文就递归不是就不递归。
class Solution {List<List<String>> resList = new ArrayList<>();List<String> list = new ArrayList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return resList;}void backTracking(String s, int index) {if(index == s.length()) {resList.add(new ArrayList(list));return ;}for(int i = index; i < s.length(); i++) {if(isTrue(s, index, i)) {list.add(s.substring(index, i+1));backTracking(s, i+1);list.remove(list.size()-1);}}}boolean isTrue(String s, int x, int y) {while(x < y) {if(s.charAt(x) != s.charAt(y)) {return false;}x++;y--;}return true;}
}
二、93. 复原 IP 地址
题目链接:https://leetcode.cn/problems/restore-ip-addresses/description/
思路:也是典型的组合问题,和上一题类似,都需要在向下递归的时候进行元素是否需要收集的判断,需要的话才递归。
class Solution {List<String> resList = new ArrayList<>();List<String> list = new ArrayList<>();public List<String> restoreIpAddresses(String s) {backTracking(s, 0);return resList;}void backTracking(String s, int index) {if(list.size() == 4) {if(index == s.length()) {resList.add(String.join(".", list));}return ;}for(int i = index; i < s.length(); i++) {if(list.size() == 3 && i - index > 2) return;String str = isTrue(s, index, i);if(str != null) {list.add(str);backTracking(s, i+1);list.remove(list.size()-1);}}}String isTrue(String s, int x, int y) {if(y - x > 2) return null;if(y - x >= 1 && s.charAt(x) == '0') return null;String ss = s.substring(x, y+1);Integer i = Integer.valueOf(ss);if(i >= 0 && i <= 255) return ss;return null;}
}
三、78. 子集
题目链接:https://leetcode.cn/problems/subsets/description/
思路:常规组合,元素无重,只不过收集节点时,需要收集全部节点,包括非叶子节点和叶子节点。
class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {backTracking(nums, 0);return resList;}void backTracking(int[] nums, int start) {resList.add(new ArrayList(list));for(int i = start; i < nums.length; i++) {list.add(nums[i]);backTracking(nums, i+1);list.remove(list.size()-1);}}}
四、90. 子集 II
题目链接:https://leetcode.cn/problems/subsets-ii/description/
思路:和上一题类似,不同的地方是集合有重复元素,但好消息是可以排序,这样就可以横向去重,利用相邻元素相同。
相同的地方就是都是全部节点收集。
class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);backTracking(nums, 0);return resList;}void backTracking(int[] nums, int start) {resList.add(new ArrayList(list));for(int i = start; i < nums.length; i++) {if(i > start && nums[i] == nums[i-1]) continue;list.add(nums[i]);backTracking(nums, i+1);list.remove(list.size()-1);}}
}
五、91. 非递减子序列
题目链接:https://leetcode.cn/problems/non-decreasing-subsequences/description/
思路:求非递减子序列,不能排序,集合有重复元素,要达到横向去重,需要使用set,每次递归向下都是一个新的set,横向for循环是同一个。
class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return resList;}void backTracking(int[] nums, int start) {if(list.size() > 1) {resList.add(new ArrayList(list));}Set<Integer> set = new HashSet<>();for(int i = start; i < nums.length; i++) {if(list.size() > 0 && nums[i] < list.get(list.size()-1)) continue;if(set.contains(nums[i])) continue;set.add(nums[i]);list.add(nums[i]);backTracking(nums, i+1);list.remove(list.size()-1); }}
}
这篇关于力扣爆刷第124天之回溯五连刷的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!