leetCode

[[toc]]

两数之和

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum = function(nums, target) {
let obj={};
const len=nums.length;
if(len<2)return;
for (let i=0;i<len;i++){
let otherNum=target-nums[i]
if(otherNum in obj){
return [obj[otherNum],i]
}
obj[nums[i]]=i
}
};

var twoSum = function(nums, target) {
for(var i = 0; i < nums.length; i++) {
let diff = target - nums[i]
for(let j = i + 1; j < nums.length; j++) {
if (nums[j] === diff) {
return [i, j]
}
}
}
};

1,2,3,5,8…求第一百个数

function findIndexNum(n){
let ary = [1,2,3,5]
if(ary.length>=n){
return ary[n-1]
}
Array.from(Array(n-4), (key, index) => index).forEach(()=>{
let len =ary.length;
let sum = ary[len-2]+ary[len-1]
ary.push(sum)
})
return ary[n-1]
}
findIndexNum(100)

求数组中连续数最大个数

给定一个数组, 里面的元素全部由0和1组成, 计算其中最大连续1的个数

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1, 所以最大连续1的个数是3
let arr = [1,1,0,1,1,1]
function isBiggest(arr) {
let count = null;
let arg = [];
for(var i = 0; i < arr.length; i++) {
if (arr[i] !== arr[i + 1]) {
count++;
arg.push(count);
count = 0;
continue;
} else {
count++;
}
}
return Math.max(...arg)
}

组合总和 III

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

  1. 先找出来能组成的所有数组,然后在根据长度和和找出适合的数组
let k = 4, n = 10;
let combinationSum3 = function (k, n) {
let number = [[]];
let ary = []
let numbers = [...Array(9)].map((item, index) => index + 1)
for (let i = 0; i < numbers.length + 1; i++) {
let turn = number.map(v => [...v, numbers[i]])
number = number.concat(turn);
}
for (let i = 0; i < number.length; i++) {
if (number[i].length === k) {
if (sum(number[i]) === n) {
ary.push(number[i])
}
}
}
return ary;ary
};

function sum(arr) {
return arr.reduce((prev, curr) => prev + curr)
}

console.log(combinationSum3(k,n))
  1. 回溯+剪纸

如果当前组合数组的长度超过了题目给定的k,那么没有必要继续回溯,进行剪纸
由于遍历[start, 9]的过程中,我们是从小到大排序的,那么如果当前的组合总和sum加上了[start, 9]中的某个数字num后,使得sum + num > n,这里假设num的下标是i,那么很明显,[i, 9]区间的数字就没有必要再遍历回溯了,因为什么组合的和都会大于n,进行剪纸。
于是可以写出代码如下:

let k = 3, n = 10;

let ans;
let combinationSum3 = function (k, n) {
ans = [];
back(k, n, [], 0, 1);
return ans;
};

/*
* @params {Array} nowArr 当前回溯组合
* @params {number} sum 当前回溯组合的总和
* @params {number} start 下次回溯的起点坐标
*/
function back(k, n, nowArr, sum, start) {
// 符合双重条件
if (nowArr.length === k && sum === n) {
return ans.push(nowArr);
}
// 递归找到合适的数组
for (let i = start; i <= 9; i++) {
if (sum + i > n || nowArr.length > k) break;
back(k, n, [...nowArr, i], sum + i, i + 1);
}
}

console.log(combinationSum3(k, n));