欢迎关注个人公众号:爱喝可可牛奶
字符串全部由数字组成,ipv4每一段数字不能有前导0,且大小∈[0,255]
等价于将字符串进行分割,并判断分割后的数是否满足条件
插入一个点进行切割、判断是否满足条件、再插入、再判断,直到插入3个点,判断剩下的一段是否满足条件
class Solution {
List res = new ArrayList();
public List restoreIpAddresses(String s) {
if (s.length() > 12) return res; // 算是剪枝了
backTrack(s, 0, 0);
return res;
}
// startIndex: 搜索的起始位置, pointNum:添加逗点的数量
private void backTrack(String s, int startIndex, int pointNum) {
if (pointNum == 3) {// 逗点数量为3时,分隔结束
// 判断第四段⼦字符串是否合法,如果合法就放进res中
if (isValid(s,startIndex,s.length()-1)) {
res.add(s);
}
return;
}
for (int i = startIndex; i end) {
return false;
}
if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
return false;
}
int num = 0;
for (int i = start; i '9' || s.charAt(i) 255) { // 如果⼤于255了不合法
return false;
}
}
return true;
}
}
返回不含相同元素整数数组的子集
收集树的每个节点
class Solution {
List> result = new ArrayList();// 存放符合条件结果的集合
LinkedList path = new LinkedList();// 用来存放符合条件结果
public List> 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
返回含相同元素整数数组的子集 在前面基础上去重
class Solution {
List> result = new ArrayList();// 存放符合条件结果的集合
LinkedList path = new LinkedList();// 用来存放符合条件结果
public List> subsetsWithDup(int[] nums) {
Arrays.sort(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 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();
}
}
}
参与评论
手机查看
返回顶部