网站建设项目职责,广西建设工程质量安全监督网站,网络营销师报名官网,通州企业网站建设93.复原IP地址#xff08;已观看#xff09;
1、题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
2、文章讲解#xff1a;代码随想录
3、题目#xff1a;
给定一个只包含数字的字符串#xff0c;复原它并返回所有可能的 …93.复原IP地址已观看
1、题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2、文章讲解代码随想录
3、题目
给定一个只包含数字的字符串复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 . 分隔。
例如0.1.2.201 和 192.168.1.1 是 有效的 IP 地址但是 0.011.255.245、192.168.1.312 和 192.1681.1 是 无效的 IP 地址。
示例 1
输入s 25525511135输出[255.255.11.135,255.255.111.35]
示例 2
输入s 0000输出[0.0.0.0]
示例 3
输入s 1111输出[1.1.1.1]
示例 4
输入s 010010输出[0.10.0.10,0.100.1.0]
示例 5
输入s 101023输出[1.0.10.23,1.0.102.3,10.1.0.23,10.10.2.3,101.0.2.3]
提示
0 s.length 3000s 仅由数字组成
4、视频链接
回溯算法如何分割字符串并判断是合法IP| LeetCode93.复原IP地址_哔哩哔哩_bilibili class Solution {ListString result new ArrayList();public ListString restoreIpAddresses(String s) {if (s.length() 12) return result; // 算是剪枝了backTrack(s, 0, 0);return result;}// startIndex: 搜索的起始位置 pointNum:添加逗点的数量private void backTrack(String s, int startIndex, int pointNum) {if (pointNum 3) {// 逗点数量为3时分隔结束// 判断第四段⼦字符串是否合法如果合法就放进result中if (isValid(s, startIndex, s.length() - 1)) {result.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);// 插⼊逗点之后下⼀个⼦串的起始位置为i2pointNum--;// 回溯s s.substring(0, i 1) s.substring(i 2);// 回溯删掉逗点} else {break;}}}// 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法private Boolean isValid(String s, int start, int end) {if (start end) {return false;}if (s.charAt(start) 0 start ! end) { // 0开头的数字不合法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) { // 如果⼤于255了不合法return false;}}return true;}
}
78.子集
1、题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2、文章讲解代码随想录
3、题目
给定一组不含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明解集不能包含重复的子集。
示例: 输入: nums [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
4、视频链接
回溯算法解决子集问题树上节点都是目标集和 | LeetCode78.子集_哔哩哔哩_bilibili class Solution {ListListInteger result new ArrayList();// 存放符合条件结果的集合LinkedListInteger path new LinkedList();// 用来存放符合条件结果public ListListInteger subsets(int[] nums) {subsetsHelper(nums, 0);return result;}private void subsetsHelper(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]);subsetsHelper(nums, i 1);path.removeLast();}}
}
90.子集II已观看
1、题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2、文章讲解代码随想录
3、题目
给定一个可能包含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明解集不能包含重复的子集。
示例:
输入: [1,2,2]输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
4、视频链接
回溯算法解决子集问题如何去重| LeetCode90.子集II_哔哩哔哩_bilibili
class Solution {ListListInteger res new ArrayList();ListInteger list new ArrayList();public ListListInteger subsetsWithDup(int[] nums) {Arrays.sort(nums);backTracking(nums, 0);return res;}private void backTracking(int[] nums, int startIndex) {res.add(new ArrayList(list));for (int i startIndex; i nums.length; i) {// 跳过当前树层使用过的、相同的元素if (i startIndex nums[i] nums[i - 1]) {continue;}list.add(nums[i]);backTracking(nums, i 1);list.removeLast();}}
}
