93. 復(fù)原IP地址

題目描述

給定一個(gè)只包含數(shù)字的字符串 s，復(fù)原它并返回所有可能的有效 IP 地址格式。

一個(gè)有效的 IP 地址 由四個(gè)整數(shù)部分組成，每部分的取值范圍是 0-255，每個(gè)部分不能包含前導(dǎo)零。

解題思路

這道題目要求我們將一個(gè)數(shù)字字符串分割成四個(gè)有效的 IP 地址部分?？梢允褂没厮菟惴▉?lái)解決這個(gè)問(wèn)題?；厮莘梢詭椭覀儽闅v所有可能的分割方式，然后驗(yàn)證每個(gè)分割是否符合有效 IP 地址的規(guī)則。

關(guān)鍵點(diǎn)：

1. 回溯法：從字符串的起始位置開始，遞歸地嘗試分割出每一部分，每一部分必須是一個(gè)有效的數(shù)字，并且不能超過(guò) 255。
2. 有效 IP 地址的條件：
   • 每部分?jǐn)?shù)字的范圍是 0 到 255。
   • 每部分不能有前導(dǎo)零，除非部分的值是 “0”。
   • 最終結(jié)果必須包含四個(gè)部分。
3. 分割條件：每次遞歸時(shí)，檢查當(dāng)前子串是否符合條件。如果符合條件，遞歸繼續(xù)處理剩余的部分。

步驟：

1. 分割字符串：從字符串的起始位置開始分割，每次分割出一個(gè)子串，檢查該子串是否有效。
2. 遞歸處理：如果當(dāng)前部分有效，遞歸處理剩余的部分，直到分割出四個(gè)部分。
3. 回溯：每當(dāng)分割出一個(gè)有效部分后，恢復(fù)狀態(tài)，繼續(xù)嘗試其他可能的分割方式。
4. 結(jié)束條件：當(dāng)分割出四個(gè)部分且整個(gè)字符串處理完畢時(shí)，將該分割方式保存到結(jié)果列表中。

代碼實(shí)現(xiàn)

class Solution {List<String> result = new ArrayList<>();public List<String> restoreIpAddresses(String s) {if(s.length()>12)return result;treebuilding(s,0,0);return result;}public void treebuilding(String s,int startIndex,int pointSum) {if(pointSum==3){if(check(s,startIndex,s.length()-1)){result.add(s);}return;}for(int i=startIndex;i<s.length();i++){if(check(s,startIndex,i)){s = s.substring(0,i+1)+"."+s.substring(i+1);pointSum++;treebuilding(s,i+2,pointSum);pointSum--;s = s.substring(0,i+1)+s.substring(i+2);}else {break;}}}public boolean check(String s,int start,int end) {if(start>end){return false;}if(s.charAt(start) == '0' && start!=end){return false;}int num = 0;for(int i = start;i<=end;i++){if(s.charAt(i)>'9' || s.charAt(i) < '0'){return false;}num = num*10+(s.charAt(i)-'0');if(num>255){return false;}}return true;}
}

78. 子集

題目描述

給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。

說(shuō)明：

• 解集不能包含重復(fù)的子集。

解題思路

這道題目要求我們找到數(shù)組 nums 的所有可能子集。由于子集的數(shù)量為 2^n，其中 n 是數(shù)組的長(zhǎng)度，因此可以使用回溯算法生成所有可能的子集。

關(guān)鍵點(diǎn)：

1. 回溯法：通過(guò)回溯法可以在每一層遞歸中選擇或不選擇當(dāng)前元素，來(lái)生成所有的子集。
2. 子集生成：每次遞歸時(shí)，都會(huì)向當(dāng)前路徑中添加一個(gè)新的元素，同時(shí)遞歸生成后續(xù)的子集。每次遞歸結(jié)束后，都會(huì)移除當(dāng)前元素，以嘗試其他可能性。
3. 路徑管理：使用一個(gè) path 列表來(lái)存儲(chǔ)當(dāng)前子集的元素，并在遞歸過(guò)程中進(jìn)行更新。

步驟：

1. 從空子集開始，逐漸向路徑中添加元素，形成一個(gè)新的子集。
2. 對(duì)于每個(gè)元素，可以選擇加入子集或不加入子集。
3. 遞歸處理每個(gè)可能的選擇，直到遍歷完所有元素。
4. 每次遞歸時(shí)，加入當(dāng)前路徑到結(jié)果集 result 中，最終返回所有的子集。

代碼實(shí)現(xiàn)

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {treebuilding(nums,0);return result;}public void treebuilding(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]);treebuilding(nums,i+1);path.removeLast();}}
}

90. 子集 II

題目描述

給定一個(gè)可能包含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。

說(shuō)明：

• 解集不能包含重復(fù)的子集。

解題思路

這道題目與第78題“子集”非常相似，但有一個(gè)額外的挑戰(zhàn)——數(shù)組可能包含重復(fù)元素，因此我們需要確保生成的子集不會(huì)重復(fù)。為了處理這個(gè)問(wèn)題，使用 used 數(shù)組來(lái)避免重復(fù)元素的選擇。

關(guān)鍵點(diǎn)：

1. 回溯法：和第78題一樣，我們使用回溯法生成所有的子集。區(qū)別在于這里我們需要處理重復(fù)元素，確保不產(chǎn)生重復(fù)的子集。
2. 重復(fù)元素的處理：為了避免重復(fù)的子集，我們?cè)诨厮葸^(guò)程中通過(guò) used 數(shù)組來(lái)標(biāo)記已經(jīng)被使用過(guò)的元素。當(dāng)遇到重復(fù)元素時(shí)，只有當(dāng)前一個(gè)相同元素已經(jīng)被選擇過(guò)時(shí)，才能選擇當(dāng)前元素。
3. 排序：我們首先對(duì) nums 數(shù)組進(jìn)行排序，這樣相同的元素會(huì)被放在一起，方便我們?cè)诨厮葸^(guò)程中跳過(guò)重復(fù)的元素。

used 數(shù)組的作用：

used 數(shù)組是用來(lái)標(biāo)記當(dāng)前元素是否已經(jīng)被使用過(guò)，以確保我們?cè)诨厮莸倪^(guò)程中不會(huì)選擇重復(fù)的元素。特別地，used 數(shù)組的作用如下：

• 標(biāo)記已經(jīng)使用的元素：在每次遞歸中，如果我們選擇了一個(gè)元素，就通過(guò)將 used[i] 設(shè)置為 true 來(lái)標(biāo)記這個(gè)元素已經(jīng)被使用。然后遞歸處理后續(xù)的元素。
• 跳過(guò)重復(fù)元素：當(dāng)我們遇到重復(fù)元素時(shí)，used 數(shù)組能夠確保我們跳過(guò)那些“重復(fù)的”分支。具體來(lái)說(shuō)，在遍歷過(guò)程中，如果當(dāng)前元素 nums[i] 和前一個(gè)元素 nums[i-1] 相等，并且前一個(gè)元素沒(méi)有被選過(guò)（即 used[i-1] == false），則跳過(guò)當(dāng)前元素 nums[i]，防止重復(fù)子集的生成。

解決重復(fù)子集的核心：

1. 排序：對(duì)數(shù)組進(jìn)行排序，使得相同的元素相鄰。這樣在回溯過(guò)程中，當(dāng)遇到重復(fù)元素時(shí)，可以判斷它是否已經(jīng)被處理過(guò)。
2. 跳過(guò)重復(fù)元素：通過(guò) used 數(shù)組來(lái)標(biāo)記每個(gè)元素是否被使用過(guò)。如果當(dāng)前元素和前一個(gè)元素相同，并且前一個(gè)元素沒(méi)有被使用過(guò)，則跳過(guò)當(dāng)前元素，這樣可以避免在同一層遞歸中重復(fù)使用相同的元素。

步驟：

1. 排序：首先對(duì)數(shù)組進(jìn)行排序，使得相同的元素相鄰，便于跳過(guò)重復(fù)元素。
2. 回溯法：遞歸地生成所有子集，每次選擇一個(gè)元素加入當(dāng)前子集。
3. 跳過(guò)重復(fù)元素：在遍歷元素時(shí)，如果當(dāng)前元素與前一個(gè)元素相同，并且前一個(gè)元素沒(méi)有被選擇，則跳過(guò)當(dāng)前元素，避免產(chǎn)生重復(fù)子集。

代碼實(shí)現(xiàn)

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<Integer>();boolean[] used;public List<List<Integer>> subsetsWithDup(int[] nums) {if(nums.length==0){result.add(path);return result;}Arrays.sort(nums);used = new boolean[nums.length];treebuilding(nums,0);return result;}public void treebuilding(int[] nums,int startIndex){result.add(new ArrayList<>(path));if(startIndex>=nums.length){return;}for(int i =startIndex;i<nums.length;i++){if(i!=0 && nums[i] == nums[i-1] && !used[i-1]){continue;}path.add(nums[i]);used[i] = true;treebuilding(nums,i+1);used[i] = false;path.removeLast();}}
}