草稿图网站
java的Deque

Leetcode 93. 复原 IP 地址

题目：93. 复原 IP 地址
解析：代码随想录解析

解题思路

“.”参数初始化为0，小于3的时候，每次回溯都在结尾加上一个“.”。
回溯终止条件：“.”参数为4，开始索引等于字符串的长度。

代码

class Solution {List<String> res = new ArrayList<>();StringBuilder sb = new StringBuilder();private boolean isValidSegment(String segment) {if (segment.length() > 1 && segment.charAt(0) == '0') // 以0开头的数字段无效return false;try {int num = Integer.valueOf(segment);return num >= 0 && num <= 255;} catch (NumberFormatException e) {return false;}}private void backtracking(String s, int startIndex, int parCount) {if (startIndex == s.length() && parCount == 4) {res.add(sb.toString());return;}if (startIndex == s.length() || parCount == 4)return;for (int i = startIndex; i < s.length() && i < startIndex + 3; i++) {if (isValidSegment(s.substring(startIndex, i+1))) {int len = sb.length();sb.append(s.substring(startIndex, i + 1));if (parCount < 3)sb.append('.');//最多加三次.backtracking(s, i + 1, parCount + 1);sb.setLength(len);//直接设置为原来的长度}}}public List<String> restoreIpAddresses(String s) {backtracking(s, 0, 0);return res;}
}

总结

暂无

Leetcode 78. 子集

题目：78. 子集
解析：代码随想录解析

解题思路

退出条件不需要写

代码

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> paths = new ArrayList<>();private void backtracking(int[] nums, int startIndex) {res.add(new ArrayList<>(paths));for (int i = startIndex; i < nums.length; i++) {paths.add(nums[i]);backtracking(nums, i + 1);paths.remove(paths.size()-1);}}public List<List<Integer>> subsets(int[] nums) {backtracking(nums, 0);return res;}
}

总结

秒了

Leetcode 90. 子集 II

题目：90. 子集 II
解析：代码随想录解析

解题思路

跟上一题的区别是多一个排序和去重

代码

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> paths = new ArrayList<>();private void backtracking(int[] nums, int startIndex) {res.add(new ArrayList<>(paths));for (int i = startIndex; i < nums.length; i++) {if (i > startIndex && nums[i] == nums[i-1])continue;paths.add(nums[i]);backtracking(nums, i + 1);paths.remove(paths.size()-1);}}public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);backtracking(nums, 0);return res;}
}

总结

秒