93.復(fù)原IP地址
思路
cr：代碼隨想錄
- 本題需要額外處理，需要判斷這個字串是否合法
偽代碼
//全局變量 result
private List<String> result = new ArrayList<>(); // 記錄結(jié)果
// startIndex: 搜索的起始位置桨啃，pointNum:添加逗點的數(shù)量
private void backtracking(StringBuilder s, int startIndex, int pointNum) {
if (pointNum == 3) { // 逗點數(shù)量為3時车胡，分隔結(jié)束
// 判斷第四段子字符串是否合法，如果合法就放進(jìn)result中
if (isValid(s.toString(), startIndex, s.length() - 1)) {
result.add(s.toString());
}
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isValid(s.toString(), startIndex, i)) { // 判斷 [startIndex,i] 這個區(qū)間的子串是否合法
s.insert(i + 1, '.'); // 在i的后面插入一個逗點
pointNum++;
backtracking(s, i + 2, pointNum); // 插入逗點之后下一個子串的起始位置為i+2
pointNum--; // 回溯
s.deleteCharAt(i + 1); // 回溯刪掉逗點
} else {
break; // 不合法照瘾，直接結(jié)束本層循環(huán)
}
}
}
// 判斷字符串s在左閉右閉區(qū)間[start, end]所組成的數(shù)字是否合法
private boolean isValid(String s, int start, int end) {
if (start > end) { //檢查子串是否為空匈棘。
return false;
}
if (s.charAt(start) == '0' && start != end) { // 0開頭的數(shù)字不合法
return false;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到非數(shù)字字符不合法
return false;
}
// 將字符串形式的數(shù)字轉(zhuǎn)換為整數(shù)形式
num = num * 10 + (s.charAt(i) - '0');
if (num > 255) { // 如果大于255了不合法
return false;
}
}
return true;
}
public List<String> restoreIpAddresses(String s) {
result.clear();
if (s.length() < 4 || s.length() > 12) return result; // 剪枝
backtracking(new StringBuilder(s), 0, 0);
return result;
}
class Solution {
private List<String> result = new ArrayList<>();
private void backtracking(StringBuilder s, int startIndex, int dotNum){
if(dotNum == 3) {
if(isValid(s.toString(), startIndex, s.length()-1)){
result.add(s.toString());
}
return;
}
for(int i = startIndex; i < s.length(); i++){
if(isValid(s.toString(), startIndex, i)){
s.insert(i+1, '.');
dotNum++;
backtracking(s, i+2, dotNum);
dotNum--;
s.deleteCharAt(i+1);
}else{
break;
}
}
}
private boolean isValid(String s, int start, int end) {
if(start > end) return false;
//if(s.charAt(start) == '0' && s.charAt(start) != s.charAt(end)) return false; //這里不能這樣寫
if(s.charAt(start) == '0' && start != end) return false;
int num = 0;
for(int i = start; i <= end; i++){ //注意這里是start和end
if(s.charAt(i) > '9' || s.charAt(i) < '0') return false; //注意這里比較的是char
num = num * 10 + (s.charAt(i) - '0');
if(num > 255) return false;
}
return true;
}
public List<String> restoreIpAddresses(String s) {
result.clear();
if(s.length() > 12 || s.length() < 4) return result;
backtracking(new StringBuilder(s), 0, 0);
return result;
}
}
78.子集
題目鏈接/文章講解
子集問題，就是收集樹形結(jié)構(gòu)中析命，每一個節(jié)點的結(jié)果主卫。 整體代碼其實和 回溯模板都是差不多的逃默。
思路
cr：代碼隨想錄
- 每一個子集都是一個組合
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, int startIndex) {
result.add(new ArrayList<>(path)); // 收集子集，要放在終止添加的上面簇搅，否則會漏掉自己
// 終止條件可以不加完域，因為startIndex >= nums.length，本層for循環(huán)本來也結(jié)束了
if (startIndex >= nums.length) {
return;
}
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backtracking(nums, i + 1); // 注意從i+1開始瘩将，元素不重復(fù)取吟税。比如取了(1,2)就沒有必要取（2,1）
path.remove(path.size() - 1); // 回溯
}
}
public List<List<Integer>> subsets(int[] nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3};
List<List<Integer>> subsets = solution.subsets(nums);
System.out.println(subsets); // 輸出子集組合
}
}
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
private void backtracking(int[] nums, int startIndex){ //這里一開始居然忘寫返回值了姿现。肠仪。。备典。
result.add(new ArrayList<>(path));
if(startIndex > nums.length) return;
for(int i = startIndex; i < nums.length; i++){
path.add(nums[i]);
backtracking(nums, i+1);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> subsets(int[] nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
}
90.子集II
題目鏈接/文章講解
大家之前做了 40.組合總和II 和 78.子集 异旧，本題就是這兩道題目的結(jié)合，建議自己獨立做一做提佣，本題涉及的知識吮蛹，之前都講過，沒有新內(nèi)容拌屏。
思路
-
本題中可以有重復(fù)元素潮针，所以有去重操作
image.png
使用 used 數(shù)組來去重的版本
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, int startIndex, boolean[] used) {
result.add(new ArrayList<>(path));
for (int i = startIndex; i < nums.length; i++) {
// used[i - 1] == true，說明同一樹枝 nums[i - 1] 使用過
// used[i - 1] == false倚喂，說明同一樹層 nums[i - 1] 使用過
// 而我們要對同一樹層使用過的元素進(jìn)行跳過
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtracking(nums, i + 1, used);
used[i] = false;
path.remove(path.size() - 1);
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
result.clear();
path.clear();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums); // 去重需要排序
backtracking(nums, 0, used);
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 2};
List<List<Integer>> subsets = solution.subsetsWithDup(nums);
System.out.println(subsets); // 輸出子集組合
}
}
不使用 used 數(shù)組來去重的版本
i 是當(dāng)前考慮的元素的索引然低，startIndex 是當(dāng)前遞歸層的起始索引。檢查 nums[i] == nums[i - 1] 可以檢測當(dāng)前元素是否與前一個元素相同务唐。結(jié)合 i > startIndex，可以確保這種比較只在同一層級內(nèi)進(jìn)行带兜。
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] nums, int startIndex) {
result.add(new ArrayList<>(path));
for (int i = startIndex; i < nums.length; i++) {
// 而我們要對同一樹層使用過的元素進(jìn)行跳過
if (i > startIndex && nums[i] == nums[i - 1]) { // 注意這里使用 i > startIndex
continue;
}
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
result.clear();
path.clear();
Arrays.sort(nums); // 去重需要排序
backtracking(nums, 0);
return result;
}
}
