网站制作知识,网站制作软件小学,2021年世界500强榜单,网站配色 蓝绿39.组合总数46.全排列—478.子集79.单词搜索—1连续差相同的数字—1
39.组合总数
/*** param {number[]} candidates* param {number} target* return {number[][]}*/
// 思路
// dfs传参#xff0c;传idx#xff0c; 剩余target
// dfs返回#xff1a; 0 收集#xff0c…39.组合总数46.全排列—478.子集79.单词搜索—1连续差相同的数字—1
39.组合总数
/*** param {number[]} candidates* param {number} target* return {number[][]}*/
// 思路
// dfs传参传idx 剩余target
// dfs返回 0 收集 0 false
var combinationSum function (candidates, target) {const sets [];const subset [];dfs(0, target, subset);// console.log(sets);return sets;/**** param {*} idx 下标开始* param {*} target 剩余目标值* returns*/function dfs(idx, target, subset) {if (target 0) return;if (target 0) {sets.push([...subset]);return;}for (let j idx; j candidates.length; j) {subset.push(candidates[j]);dfs(j, target - candidates[j], subset);subset.pop();}}
};
combinationSum([2, 3, 6, 7], 7);
46.全排列—4
/*** param {number[]} nums* return {number[][]}*/
// 思路
// 数量相等
// 剪枝 used ii-1var permuteUnique function (nums) {const sets [];const subset [];const used Array(nums.length).fill(0);dfs(subset);console.log(sets);function dfs(subset) {for (let i 0; i nums.length; i) {if (subset.length nums.length) {sets.push([...subset]);return;}if (used[i] 1) continue;if (i 0 nums[i] nums[i - 1] used[i - 1] 1) continue;used[i] 1;subset.push(nums[i]);dfs(subset);subset.pop();used[i] 0;}}
};
permuteUnique([1, 1, 2]);
// nums [1,1,2]
78.子集
/*** param {number[]} nums* return {number[][]}*/
// 思路
// dfs idx传参是依次递增
var subsets function (nums) {const sets [];const subset [];dfs(0, subset);// console.log(sets);return sets;function dfs(idx, subset) {if (subset.length nums.length) return;sets.push([...subset]);for (let i idx; i nums.length; i) {subset.push(nums[i]);dfs(i 1, subset);subset.pop();}}
};
subsets([1, 2, 3]);
// nums [1,2,3]
79.单词搜索—1
/*** param {character[][]} board* param {string} word* return {boolean}*/
// 思路
// dfs四个方向的或值 并返回
// dfs 什么时候进入
// dfs 返回值 长度相等时
var exist function (board, word) {const m board.length;const n board[0].length;for (let i 0; i m; i) {for (let j 0; j n; j) {if (board[i][j] word[0]) {if (dfs(0, i, j)) return true;}}}return false;function dfs(idx, x, y) {if (x 0 || x m || y 0 || y n) return false;if (board[x][y] ! word[idx]) return false;if (idx word.length - 1) return true;board[x][y] null;const res dfs(idx 1, x 1, y) ||dfs(idx 1, x - 1, y) ||dfs(idx 1, x, y 1) ||dfs(idx 1, x, y - 1);board[x][y] word[idx];return res;}
};console.log(exist([[A, B, C, E],[S, F, C, S],[A, D, E, E],],ABCCED)
);
console.log(exist([[A, B, C, E],[S, F, C, S],[A, D, E, E],],ABCB)
);
// board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCCED
// [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCB
连续差相同的数字—1
/*** param {number} n* param {number} k* return {number[]}*/
// 思路
// 进入下一轮dfs条件
// 首个或者 绝对值差为k
// dfs 返回 subset 长度等于n 并且首位不能为0
var numsSameConsecDiff function (n, k) {const sets [];const subset [];dfs(subset);// console.log(sets);return sets;function dfs(subset) {for (let i 0; i 10; i) {if (subset.length n) {if (subset[0] ! 0) {sets.push(subset.join());}return;}if (subset.length 0 ||Math.abs(subset[subset.length - 1] - i) k) {subset.push(i);dfs(subset);subset.pop();}}}
};
numsSameConsecDiff(3, 7);// 输入n 3, k 7
// 输出[181,292,707,818,929]
// 解释注意070 不是一个有效的数字因为它有前导零。
