代码随想录算法训练营第二十一天

其他:

今日总结
往期打卡

---

93. 复原 IP 地址

跳转: 93. 复原 IP 地址

学习: 代码随想录公开讲解

问题:

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

思路:

和回文串那题是一个思路,找切点传递给下一个,不同的只是校验换成了判断是否是在0-255之间的合法值

复杂度:

• 时间复杂度: $O(n^3)$
• 空间复杂度: $O(n)$

代码:

class Solution {List<String> ans = new ArrayList<>();StringBuilder sb = new StringBuilder();void dfs(String s,int startIndex,int num){if(num==3){if(verify(s,startIndex,s.length())){sb.append(s, startIndex, s.length());ans.add(sb.toString());sb.delete(sb.length()-(s.length()-startIndex),sb.length());}return;}for(int i=1;i<4&&i+startIndex<s.length();i++){int e = i+startIndex;if(verify(s,startIndex,e)){sb.append(s, startIndex, e).append('.');dfs(s,e,num+1);sb.delete(sb.length()-i-1,sb.length());}}}boolean verify(String s,int startIndex,int endIndex){if(Integer.parseInt(s.substring(startIndex,endIndex))>255) return false;return endIndex - startIndex <= 1 || s.charAt(startIndex) != '0';}public List<String> restoreIpAddresses(String s) {if(s.length()>12) return ans;dfs(s,0,0);return ans;}
}

---

78. 子集

跳转: 78. 子集

学习: 代码随想录公开讲解

问题:

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

思路:

求子集比起求组合只是每层的情况都要收集,其他的都还一样

复杂度:

• 时间复杂度: $O(2^n)$(选或不选)
• 空间复杂度: $O(n\ast 2^n)$

代码:

class Solution {List<List<Integer>> ans = new ArrayList<>();int[] nums;List<Integer> path = new ArrayList<>();int n;void dfs(int i){if(i==n) return;while(i<n){path.add(nums[i]);ans.add(new ArrayList<>(path));dfs(++i);path.remove(path.size()-1);}}public List<List<Integer>> subsets(int[] nums) {this.nums = nums;n = nums.length;ans.add(new ArrayList<>(path));dfs(0);return ans;}
}

---

90. 子集 II

跳转: 90. 子集 II

学习: 代码随想录公开讲解

问题:

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

思路:

比起上一题只是加了一步去重,和之前组合的去重思路是一致的,就是一层只能选同种元素一次,就可以保证不重复

复杂度:

• 时间复杂度: $O(2^n)$
• 空间复杂度: $O(n)$(不清楚,估计是没算ans的)

代码:

class Solution {List<List<Integer>> ans = new ArrayList<>();int[] nums;List<Integer> path = new ArrayList<>();int[] used;int n;void dfs(int i){if(i==n) return;int start = i;while(i<n){if(i>start&&nums[i]==nums[i-1]&&used[i-1]==0) {i++;continue;}path.add(nums[i]);used[i] = 1;ans.add(new ArrayList<>(path));dfs(++i);used[i-1] = 0;path.remove(path.size()-1);}}public List<List<Integer>> subsetsWithDup(int[] nums) {this.nums = nums;n = nums.length;used = new int[n];Arrays.sort(nums);ans.add(new ArrayList<>(path));dfs(0);return ans;}
}

---

2364. 统计坏数对的数目

跳转: 2364. 统计坏数对的数目

问题:

给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个 坏****数对 。

请你返回 nums 中 坏数对 的总数目。

思路:

两层for循环会超时,毕竟 $10^5$
可以采用哈希法,恒等变化很容易知道要求的是不满足nums[i]-i相等的,可以求满足的再取反.

复杂度:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$

代码:

class Solution {public long countBadPairs(int[] nums) {int n = nums.length;Map<Integer,Integer> map = new HashMap<>();long ans = 0;for(int i = 0;i<n;i++){int tmp = nums[i]-i;if(map.get(tmp)!=null){ans+=map.get(tmp);}map.put(tmp,map.getOrDefault(tmp,0)+1);}return (long)n*(n-1)/2-ans;}
}

---

总结

练习了组合回溯和子集回溯,以及每日一题哈希

往期打卡

代码随想录算法训练营第二十天

代码随想录算法训练营第十九天

代码随想录算法训练营第十八天

代码随想录算法训练营第十七天

代码随想录算法训练营周末三

代码随想录算法训练营第十六天

代码随想录算法训练营第十五天

代码随想录算法训练营第十四天

代码随想录算法训练营第十三天

代码随想录算法训练营第十二天

代码随想录算法训练营第十一天

代码随想录算法训练营周末二

代码随想录算法训练营第十天

代码随想录算法训练营第九天

代码随想录算法训练营第八天

代码随想录算法训练营第七天

代码随想录算法训练营第六天

代码随想录算法训练营第五天

代码随想录算法训练营周末一

代码随想录算法训练营第四天

代码随想录算法训练营第三天

代码随想录算法训练营第二天

代码随想录算法训练营第一天