代碼隨想錄算法訓(xùn)練營day28 | 題目93丧叽、題目78门岔、題目90
題目一描述
有效 IP 地址 正好由四個(gè)整數(shù)（每個(gè)整數(shù)位于 0 到 255 之間組成向瓷，且不能含有前導(dǎo) 0）扔字，整數(shù)之間用 '.' 分隔征唬。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址亚皂，但是 "0.011.255.245"丢烘、"192.168.1.312" 和 "192.168@1.1" 是 無效 IP 地址柱宦。
給定一個(gè)只包含數(shù)字的字符串 s ，用以表示一個(gè) IP 地址铅协，返回所有可能的有效 IP 地址捷沸，這些地址可以通過在 s 中插入 '.' 來形成。你 不能 重新排序或刪除 s 中的任何數(shù)字狐史。你可以按 任何 順序返回答案痒给。
示例 1：
輸入：s = "25525511135"
輸出：["255.255.11.135","255.255.111.35"]
示例 2：
輸入：s = "0000"
輸出：["0.0.0.0"]
示例 3：
輸入：s = "101023"
輸出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20
s 僅由數(shù)字組成
解題思路
回溯的樹深度是4，注意在第三層的時(shí)候骏全，對(duì)剩余元素的處理苍柏。
代碼實(shí)現(xiàn)
方法一：
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
List<String> path = new ArrayList<>();
backtracking(s, res, path, 0);
return res;
}
private void backtracking(String s, List<String> res, List<String> path, int startIndex) {
if (path.size() == 4) { // 控制分段數(shù)量，控制樹的深度姜贡。
res.add(String.join(".", path));
return;
}
for (int i = startIndex; i < s.length(); i++) {
String sub = "";
if (path.size() == 3) {
sub = s.substring(startIndex, s.length());
i = s.length() - 1; // 直接把剩下的字符串切出成為第四段试吁，同時(shí)也要注意把i置為字符串末端，這也符合下一次回溯的開始位
} else {
sub = s.substring(startIndex, i + 1);
}
if (!check(sub)) {
continue;
}
path.add(sub);
backtracking(s, res, path, i + 1);
path.remove(path.size() - 1);
}
}
private boolean check(String sub) {
if (sub.length() > 3 || sub.length() > 1 && sub.charAt(0) == '0' || Integer.valueOf(sub) > 255) {
return false;
}
return true;
}
}
技巧總結(jié)
學(xué)會(huì)String.join("分隔符", 集合或者數(shù)組)
題目二描述
給你一個(gè)整數(shù)數(shù)組 nums ，數(shù)組中的元素 互不相同 熄捍。返回該數(shù)組所有可能的子集（冪集）烛恤。
解集 不能 包含重復(fù)的子集。你可以按 任意順序 返回解集余耽。
示例 1：
輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
輸入：nums = [0]
輸出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
解題思路
模版題缚柏，本質(zhì)是收集每個(gè)回溯樹的結(jié)點(diǎn)的值。
代碼實(shí)現(xiàn)
方法一：
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtracking(nums, res, path, 0);
return res;
}
private void backtracking(int[] nums, List<List<Integer>> res, List<Integer> path, int startIndex) {
res.add(new ArrayList(path));
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backtracking(nums, res, path, i + 1);
path.remove(path.size() - 1);
}
}
}
題目三描述
給你一個(gè)整數(shù)數(shù)組 nums 碟贾，其中可能包含重復(fù)元素币喧，請(qǐng)你返回該數(shù)組所有可能的 子集（冪集）。
解集 不能 包含重復(fù)的子集袱耽。返回的解集中杀餐，子集可以按 任意順序 排列。
示例 1：
輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
輸入：nums = [0]
輸出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
解題思路
先排序后去重剪枝即可朱巨。
代碼實(shí)現(xiàn)
方法一：
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
Arrays.sort(nums);
backtracking(nums, res, path, 0);
return res;
}
private void backtracking(int[] nums, List<List<Integer>> res, List<Integer> path, int startIndex) {
res.add(new ArrayList(path));
for (int i = startIndex; i < nums.length; i++) {
if (i > startIndex && nums[i] == nums[i - 1]) {
continue;
}
path.add(nums[i]);
backtracking(nums, res, path, i + 1);
path.remove(path.size() - 1);
}
}
}
