中级农民
- 积分
- 108
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2020-9-2
- 最后登录
- 1970-1-1
|
9月8,
38Count and Say
except for the 1st is number 1, the rest of n(s) are count and say, which are not pure number, but the way to say the number, so for n is bigger than 1, we loop the whole int and count how many same numbers and so on:
var countAndSay = function(n) {
if (n === 1) { return '1'; }
let prev = '1';
for (let i = 2; i <= n; i++) {
let item = '', cur = prev[0], cnt = 0, j = 0;
while (j < prev.length) {
while (j < prev.length && cur === prev[j]) { cnt++; j++; }
item += cnt + cur;
cur = prev[j];
cnt = 0;
}
prev = item
}
return prev;
};
39Combination Sum:
var combinationSum = function(candidates, target) {
// we don't need to consider numbers > target
const sorted = candidates.filter(e => e <= target).sort((a,b) => a-b);
const results = [];
const helper = (arr, sum, i) => {
if (i >= sorted.length || sum + sorted[i] > target) {
return;
}
const arrIfTake = [...arr, sorted[i]];
const sumIfTake = sum + sorted[i];
if (sumIfTake === target) {
results.push(arrIfTake);
return;
}
// take, we have the option of taking again
helper(arrIfTake, sumIfTake, i);
// leave, we no longer need to consider this number
helper(arr, sum, i+1);
}
// start with empty array, 0 sum, index 0
helper([], 0, 0);
return results;
};
40Combination Sum II:
var combinationSum2 = function(candidates, target) {
// we don't need to consider numbers > target
const c = candidates.filter(e => e <= target).sort((a,b) => a-b);
let res = [];
helper(target, [], 0);
function helper(need, tmp, start) {
if(need === 0) {
res.push(tmp.slice());
} else {
for(var i=start; i<c.length; i++) {
if(c[i] > need) continue;
if(i > start && c[i-1] == c[i]) continue;
tmp.push(c[i]);
helper(need-c[i], tmp, i+1);
tmp.pop();
}
}
}
return res;
}; |
|