歡迎關(guān)注個人公眾號：愛喝可可牛奶
LeetCode算法訓練 93.復原IP地址 78.子集 90.子集II
LeetCode 93. 復原 IP 地址
分析
字符串全部由數(shù)字組成凑队，ipv4每一段數(shù)字不能有前導0，且大小∈[0,255]
等價于將字符串進行分割，并判斷分割后的數(shù)是否滿足條件
插入一個點進行切割贪庙、判斷是否滿足條件、再插入僚纷、再判斷烤送，直到插入3個點，判斷剩下的一段是否滿足條件
代碼
class Solution {
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
if (s.length() > 12) return res; // 算是剪枝了
backTrack(s, 0, 0);
return res;
}
// startIndex: 搜索的起始位置爹土， pointNum:添加逗點的數(shù)量
private void backTrack(String s, int startIndex, int pointNum) {
if (pointNum == 3) {// 逗點數(shù)量為3時，分隔結(jié)束
// 判斷第四段?字符串是否合法踩身，如果合法就放進res中
if (isValid(s,startIndex,s.length()-1)) {
res.add(s);
}
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isValid(s, startIndex, i)) {
s = s.substring(0, i + 1) + "." + s.substring(i + 1); //在str的后?插??個逗點
pointNum++;
backTrack(s, i + 2, pointNum);// 插?逗點之后下?個?串的起始位置為i+2
pointNum--;// 回溯
s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯刪掉逗點
} else {
break;
}
}
}
// 判斷字符串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;
}
num = num * 10 + (s.charAt(i) - '0');
if (num > 255) { // 如果?于255了不合法
return false;
}
}
return true;
}
}
LeetCode 78. 子集
分析
返回<u>不含相同元素整數(shù)數(shù)組</u>的子集
收集樹的每個節(jié)點
代碼
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合條件結(jié)果的集合
LinkedList<Integer> path = new LinkedList<>();// 用來存放符合條件結(jié)果
public List<List<Integer>> subsets(int[] nums) {
subsetsHelper(nums, 0);
return result;
}
private void subsetsHelper(int[] nums, int startIndex){
//「遍歷這個樹的時候胀茵，把所有節(jié)點都記錄下來，就是要求的子集集合」挟阻。
result.add(new ArrayList<>(path));
if (startIndex >= nums.length){ //終止條件可不加
return;
}
for (int i = startIndex; i < nums.length; i++){
path.add(nums[i]);
subsetsHelper(nums, i + 1);
path.removeLast();
}
}
}
LeetCode 90. 子集 II
分析
返回<u>含相同元素整數(shù)數(shù)組</u>的子集 在前面基礎上去重
代碼
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合條件結(jié)果的集合
LinkedList<Integer> path = new LinkedList<>();// 用來存放符合條件結(jié)果
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
subsetsHelper(nums, 0);
return result;
}
private void subsetsHelper(int[] nums, int startIndex){
//「遍歷這個樹的時候琼娘，把所有節(jié)點都記錄下來峭弟，就是要求的子集集合」。
result.add(new ArrayList<>(path));
if (startIndex >= nums.length){ //終止條件可不加
return;
}
for (int i = startIndex; i < nums.length; i++){
// 注意這里不是0
//if(i > 0 && nums[i] == nums[i-1]){
if(i > startIndex && nums[i] == nums[i-1]){
continue;
}
path.add(nums[i]);
subsetsHelper(nums, i + 1);
path.removeLast();
}
}
}
總結(jié)
- 涉及范圍確定脱拼，明確開閉區(qū)間
- 去重方式 Set去重瞒瘸、used數(shù)組去重、索引去重
