8. 复原IP地址
var restoreIpAddresses = function(s) {
const SEG_COUNT = 4;
const segments = new Array(SEG_COUNT);
const ans = [];
const dfs = (s, segId, segStart) => {
// 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
if (segId === SEG_COUNT) {
if (segStart === s.length) {
ans.push(segments.join('.'));
}
return;
}
// 如果还没有找到 4 段 IP 地址就已经遍历完了字符串,那么提前回溯
if (segStart === s.length) {
return;
}
// 由于不能有前导零,如果当前数字为 0,那么这一段 IP 地址只能为 0
if (s.charAt(segStart) === '0') {
segments[segId] = 0;
dfs(s, segId + 1, segStart + 1);
return;
}
// 一般情况,枚举每一种可能性并递归
let addr = 0;
for (let segEnd = segStart; segEnd < s.length; ++segEnd) {
addr = addr * 10 + (s.charAt(segEnd) - '0');
if (addr > 0 && addr <= 0xFF) {
segments[segId] = addr;
dfs(s, segId + 1, segEnd + 1);
} else {
break;
}
}
}
dfs(s, 0, 0);
return ans;
};
9. 子集
var subsets = function(nums) {
const ans = [];
const n = nums.length;
for (let mask = 0; mask < (1 << n); ++mask) {
const t = [];
for (let i = 0; i < n; ++i) {
if (mask & (1 << i)) {
t.push(nums[i]);
}
}
ans.push(t);
}
return ans;
};
10. 子集II
var subsetsWithDup = function(nums) {
nums.sort((a, b) => a - b);
let t = [], ans = [];
const n = nums.length;
for (let mask = 0; mask < (1 << n); ++mask) {
t = [];
let flag = true;
for (let i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
flag = false;
break;
}
t.push(nums[i]);
}
}
if (flag) {
ans.push(t.slice());
}
}
return ans;
};
文章来源地址https://www.toymoban.com/news/detail-818861.html
文章来源:https://www.toymoban.com/news/detail-818861.html
到了这里,关于day28打卡的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!