js 简单算法
2022-06-27 本文已影响0人
青城墨阕
1. 数组扁平化
let arr = [
1,2,3,4,
[5,6],
[7,[8,9]],
[10, [11, [12, 13, [14]], 15]]
];
// 方法一：ES6数组新属性flat
let newArr = arr.flat(Infinity);
// 方法二：数组toString，但是toString之后每一项都是string类型，故需要利用map将每项改成number类型
let newArr2 = arr.toString().split(',').map(item => Number(item));
/* 方法三：JSON.stringify
** JSON.stringify => '[1,2,3,4,[5,6],[7,[8,9]],[10,[11,[12,13,[14]],15]]]'，所以替换掉所有的[]
**/
let newArr5 = JSON.stringify(arr); // '[1,2,3,4,[5,6],[7,[8,9]],[10,[11,[12,13,[14]],15]]]'
newArr5 = newArr5.replace(/\[|\]/g, ''); // '1,2,3,4,5,6,7,8,9,10,11,12,13,14,15'
newArr5 = newArr5.split(',').map(item => Number(item)); // 同样需要将每项string改为number
// 方法四：利用递归
function toFlat(arr) {
if (!Array.isArray(arr)) { return false;}
let newArr = [].concat(...arr);
let flag = newArr.some(item => Array.isArray(item));
if (flag) {
return toFlat(newArr);
}
else {
return newArr;
}
}
1.1 深层数组格式化
将数组[1,[2,[3, [4, [5,[6]]]]]]格式化为[6,[5,[4,[3,[2,[1]]]]]]
function formatArr(arr, result) {
let newArr = [];
if (result.length > 0) {
newArr[1] = result
}
newArr[0] = arr[0];
if (arr.length === 2) {
return formatArr(arr[1], newArr)
}
return newArr;
}
let r = JSON.stringify(formatArr([1,[2,[3, [4, [5,[6]]]]]], []))
console.log(r)
2. 手动封装forEach & map & filter & reduce
数组的遍历方法有哪些
// forEach：无返回值
Array.prototype.myForEach = function(callback) {
for(let i = 0; i < this.length; i++) {
callback(this[i], i, this);
}
};
let arr = [1, 2, 3];
arr.myForEach((item, index) => { console.log(item, index); })
// map：有返回值
Array.prototype.myMap = function(callback) {
let result = [];
for(let i = 0; i < this.length; i++) {
result.push(callback(this[i], i, this))
}
return result;
};
let arr = [1, 2, 3];
let newArr = arr.myMap(item => item + 1); // [2, 3, 4]
/**
* reduce 实现一个 map 的封装
*/
Array.prototype.myMap = function(fn,thisArg=[]) {
// 如果fn传入的不是一个函数则抛出异常
if (typeof fn != 'function') {
throw new Error(`${fn} is not a function`);
}
return this.reduce((pre,cur,index,arr) => {
return pre.concat(fn.call(thisArg,cur,index,arr));
},[])
}
const arr = [2,3,1,5];
const temp = arr.myMap(item => item * 2); // 4, 6, 2, 10
// filter
Array.prototype.myFilter = function(fn, thisArg = []) {
if (typeof fn !== 'function') {
throw new Error(`${fn} is not a function`);
}
const result = [];
for (let i = 0; i < this.length; i++) {
if (fn.call(thisArg, this[i], i, this)) {
result.push(this[I]);
}
}
return result;
}
const arr = [2,3,1,5];
const newArr = arr.myFilter(item => item > 2);
// reduce
Array.prototype.myReduce = function(fn, initialValue) {
let hasInitVal = initialValue !== undefined;
let value = hasInitVal ? initialValue : this[0];
for(let i = hasInitVal ? 0 : 1, len= this.length; i<len; i++){
value = fn(value, arr[i], i, this);
}
return value;
};
const arr = [2,3,1,5];
const newArr = arr.myReduce((pre, curr, index, args) => {
console.log(pre, curr, index, args);
return curr + pre;
}, 1);
3. 手动封装一个new
function _new(Fn, ...arg) {
// 1. let obj = {};
// 2. obj.__proto__ = Fn.prototype;
// 与以上1 + 2 两句的实现一致
let obj = Object.create(Fn.prototype);
const ret = Fn.call(obj, ...arg);
return ret instanceof Object ? ret : obj;
}
function Person(name) {
this.name = name;
}
Person.prototype.sayHello = function() {
console.log('hello...');
}
let p2 = _new(Person, 'lisi');
4. 排序
参考：
https://juejin.cn/post/6844903582328717325
https://fe.ecool.fun/topic/807ac3c6-6e75-4cbf-9a5d-3084f860ea11?orderBy=updateTime&order=desc&tagId=10
4.1 冒泡排序 Bubble Sort
- 时间复杂度
O(n²) - 交换
O(n²) - 核心概念: 利用交换，将最大的数冒泡到最后
/**
* 基本实现
* 优化：如果某次冒泡操作没有数据交换，说明已经有序了。
*/
function bubbleSort(arr) {
for (let i = arr.length - 1; i > 0; i--) {
let exchangeFlag = false;
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
exchangeFlag = true;
}
}
// 优化：如果某次冒泡操作没有数据交换，说明已经有序了。
if (!exchangeFlag) {break;}
}
}
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
bubbleSort(arr);
/**
* 缓存 pos
* 设置一标志性变量 pos,用于记录每趟排序中最后一次进行交换的位置。
* 由于 pos 位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到 pos 位置即可。
*/
function bubbleSort(arr) {
for (let i = arr.length - 1; i > 0;) {
let pos = 0;
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
pos = j;
}
}
i = pos;
}
}
4.2 插入排序 Insertion Sort
参考：https://segmentfault.com/a/1190000015489767
- 时间复杂度
O(n²) - 核心概念: 类似于我们玩儿牌时抓牌。即开始时默认我们已经抓到一张牌，此后再抓牌时就要与手里的牌进行比较，如果抓的牌面大于手里的牌面就要将抓的牌放在手里的牌的后面。
function insertionSort(arr) {
let handle = []; // 用来存放手里的牌
handle.push(arr[0]); // 默认手里有一张牌
for (let i = 1, len = arr.length; i < len; i++) { // 逐张抓取桌面上的牌
for (let j = handle.length - 1; j >= 0; j--) { // 抓取一张桌面的牌之后与手里的牌逐张对比
if (arr[i] > handle[j]) { // 直到抓取的牌大于手里的牌，将抓取的牌插入当前牌的后面。那么此轮抓取完成，再去抓取下一张
handle.splice(j + 1, 0, arr[i]);
break;
}
else if (j === 0){ // 或者抓取的牌比手里第一张牌还小，那么直接将抓取的牌unshift。那么此轮抓取也完成
handle.unshift(arr[i]);
break;
}
}
}
return handle;
}
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
insertionSort(arr);
// 优化之后的写法
function insertionSort(arr) {
for (let i = 1, len = arr.length; i < len; i++) {
const temp = arr[i];
let preIndex = i - 1;
while (arr[preIndex] > temp) {
arr[preIndex + 1] = arr[preIndex];
preIndex -= 1;
}
arr[preIndex + 1] = temp;
}
}
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
insertionSort(arr);
4.3 快速排序 Quick Sort
核心思想:
- 找到数组的中间项midVal，将其移出当前数组，并获取其值。
- 准备两个空数组leftArr与rightArr(那么，
arr = leftArr + midVal + rightArr)。 - 遍历数组（移出中间项之后的数组），并将每一项与中间项做对比。若小于中间项，则存放在leftArr中；反之，存放在rightArr中。
- 利用递归的思想，继续处理leftArr与rightArr，直到每一项中只有一个元素。
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
let midIndex = Math.floor(arr.length / 2);
const midVal = arr.splice(midIndex, 1)[0];
let leftArr = [], rightArr = [];
for (let i = 0; i < arr.length; i++) {
arr[i] < midVal ? leftArr.push(arr[i]) : rightArr.push(arr[i]);
}
return quickSort(leftArr).concat(midVal, quickSort(rightArr));
}
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(quickSort(arr));
4.4 选择排序 Selection Sort
- 时间复杂度
O(n²) - 交换
O(n) -
核心概念: 每一次内循环遍历寻找最小的数，记录下
minIndex，并在这次内循环结束后交换minIndex和i的位置。
function selectionSort(arr) {
for (let i = 0, len = arr.length; i < len - 1; i++) {
let minIndex = I;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
}
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
selectionSort(arr);
5. 二分法查找
function binarySearch(arr, value) {
let min = 0;
let max = arr.length - 1;
while (min <= max) {
let mid = Math.floor((min + max) / 2);
if (value === arr[mid]) {
return mid;
}
else if (value > arr[mid]) {
min = mid + 1;
}
else {
max = mid - 1;
}
}
return 'not find';
}
const arr = [1, 2, 3, 4, 5];
console.log(binarySearch(arr, 2));
console.log(binarySearch(arr, 4));
6. 柯里化函数
- 柯里化（Currying）是把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数，并且返回接受余下的参数且返回结果的新函数的技术。
function currying(fn, length) {
length = length || fn.length;
let context = this;
return function(...args) {
if (args.length >= length) {
return fn.call(context, ...args);
}
return currying(fn.bind(context, ...args), length - args.length);
}
}
function add (arg1, arg2, arg3, arg4, arg5) {
return [arg1, arg2, arg3, arg4, arg5].reduce((a, b) => a + b, 0)
}
let addCurry = currying(add)
console.log('0: ', addCurry(1)(2)(3)(4)(5)) //15
console.log('1: ', addCurry(1)(2)(3)(4, 5)) //15
console.log('2: ', addCurry(1)(2)(3, 4, 5)) //15
console.log('3: ', addCurry(1)(2, 3, 4, 5)) //15
export const currying = (fn) => {
let args = [];
let context = this;
return function temp(...newArgs) {
if (newArgs.length) {
args = [
...args,
...newArgs
];
return temp;
}
else {
let val = fn.apply(context, args);
args = [];
return val;
}
}
};
function add (...args) {
//求和
return args.reduce((a, b) => a + b)
}
let addCurry = currying(add)
console.log(addCurry(1)(2)(3)(4, 5)()) //15
console.log(addCurry(1)(2)(3, 4, 5)()) //15
console.log(addCurry(1)(2, 3, 4, 5)()) //15
7. 箭头函数
1. 箭头函数与普通函数的区别
- 箭头函数在语法上更简洁；
- 箭头函数没有自己的
this,它里面的this是继承函数所处上下文的this(故用call、apply、bind等也无法改变箭头函数的this指向)； - 箭头函数没有augments(类数组)，只能通过...args获取传递的参数集合(数组)；
- 箭头函数不能被new执行(因为箭头函数没有
this，更重要的是箭头函数没有prototype)
let Fn = () => { this.x = 'aaa';};
let fn = new Fn(); // 报错: Fn is not a constructor
8. 反写一个字符串中的大小写
let str = 'It is SUNNY today, with beautiful SCENERY EVERYWHERE. 所以我们可高歌一曲 * 100次！HAHAHA。。。';
str = str.replace(/[a-zA-Z]/g, content => {
//=> content 每一次正则匹配的结果
//=> 1. 用ASCII码判断是否为大写：content.charCodeAt >= 'A'.charCodeAt() && content.charCodeAt <= 'Z'.charCodeAt()
//=> 2. 转换大写后与本身相等，则为大写
return content.toUpperCase() === content ? content.toLowerCase() : content.toUpperCase();
}); // 'iT IS sunny TODAY, WITH BEAUTIFUL scenery everywhere. 所以我们可高歌一曲 * 100次！hahaha。。。'
9. 手动封装一个indexOf
let S = 'zhufengpeixun';
let T = 'pei';
// for循环方式
String.prototype.myIndexOf = function(T) {
let lenT = T.length,
lenS = this.length,
result = -1;
for (let i = 0; i < lenS - lenT + 1; i++) {
if (this.substr(i, lenT) === T) {
result = I;
break;
}
}
return result;
};
// 正则
String.prototype.myIndexOf2 = function(T) {
return new RegExp(T).exec(this).index;
}
10. 手动封装一个instanceof
- instanceof 运算符用于判断构造函数的 prototype 属性是否出现在对象的原型链中的任何位置。
- Object.getPrototypeOf() 方法返回指定对象的原型（内部[[Prototype]]属性的值）。
function myInstanceof(left, right) {
// 获取对象的原型
let proto = Object.getPrototypeOf(left)
// 获取构造函数的 prototype 对象
let prototype = right.prototype;
// 判断构造函数的 prototype 对象是否在对象的原型链上
while (true) {
if (!proto) return false;
if (proto === prototype) return true;
// 如果没有找到，就继续从其原型上找，Object.getPrototypeOf方法用来获取指定对象的原型
proto = Object.getPrototypeOf(proto);
}
}
// 方法2
function myInstanceof(x, y) {
while (x.__proto__) {
if (x.__proto__ === y.prototype) {
return true;
}
x.__proto__ = x.__proto__.__proto__;
}
if (x.__proto__ === null) {
return false;
}
}
11. 全排列
-
用回溯的思想解决这个问题
全排列[1,2,3]的解题思路
var permute = function(nums) {
let len = nums.length,
result = [],
visited = new Array(len).fill(false);
const dfs = (nums, len, depth, path, visited) => {
// 遍历到叶子结点了，可以返回了
if(depth === len) {
result.push([...path]);
return;
}
for(let i = 0; i < len; i++) {
// 如果没遍历过
if(!visited[i]) {
// 压入 path 数组，然后是否遍历过的数组此下标处变为 true
path.push(nums[i]);
visited[i] = true;
// 继续 dfs，直到最后一层
dfs(nums, len, depth + 1, path, visited);
// 进行回溯，还原，以便下一次使用
visited[i] = false;
path.pop();
}
}
}
dfs(nums, len, 0, [], visited);
return result;
};
console.log(permute([1, 2, 3])); [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
console.log(permute([1, 2, 3, 4]));
12. 背包问题
背包问题
题干
有 N 件物品和一个容量是 W 的背包。每件物品有且只有一件。
第 i 件物品的体积是 ws[i] ，价值是 vs[i] 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
解析
这是最为基础的背包问题，每种物品只有一件，可以选择取或者不取。
=> 问题描述可以归结为：将N种物品有选择地放入容量为V的背包中，要求背包中的物品价值最大。
=> 尝试提炼其子问题：将i种物品有选择地放入容量为V的背包中，要求背包中的物品价值最大。
=> 那么由子问题转移到父问题的方程为：
f(i,V) = max{f(i-1,W), f(i-1,W-ws[i]) + vs[i]}
=> 解释如下：“将前i件物品放入容量为V的背包中”这个子问题，若只考虑第i件物品的策略（放或者不放），那么就可以转化为一个只关系到前i-1件物品的问题。
- 如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为w的背包中”；
- 如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为W-ws[i]的背包中”，此时能获得的最大价值就是f(i-1, W-ws[i])再加上通过放入第i件物品获得的价值vs[i]。
function knapsack(n, W, weights, values, selected) {
if (n == 0 || W == 0) {
//当物品数量为0，或者背包容量为0时，最优解为0
return 0;
} else {
//从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中
for (var i = n - 1; i >= 0; i--) {
//如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品
//在这种情况的最优解为f(n-1,C)
if (weights[i] > W) {
return knapsack(n - 1, W, weights, values, selected);
} else {
var a = knapsack(n - 1, W, weights, values, selected); //不选择物品i的情况下的最优解
var b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected); //选择物品i的情况下的最优解
//返回选择物品i和不选择物品i中最优解大的一个
if (a > b) {
selected[i] = 0; //这种情况下表示物品i未被选取
return a;
} else {
selected[i] = 1; //物品i被选取
return b;
}
}
}
}
}
var selected = [], ws = [2,2,6,5,4], vs = [6,3,5,4,6]
var b = knapsack( 5, 10, ws, vs, selected)
console.log(b) //15
selected.forEach(function(el,i){
if(el){
console.log("选择了物品"+i+ " 其重量为"+ ws[i]+" 其价值为"+vs[i])
}
})
13. 使用Promise实现：限制异步操作的并发个数，并尽可能快的完成全部
题干
有8个图片资源的url，已经存储在数组urls中。
urls类似于['https://image1.png', 'https://image2.png', ....]
而且已经有一个函数function loadImg，输入一个url链接，返回一个Promise，该Promise在图片下载完成的时候resolve，下载失败则reject。
但有一个要求，任何时刻同时下载的链接数量不可以超过3个。
var urls = [
"https://hexo-blog-1256114407.cos.ap-shenzhen-fsi.myqcloud.com/AboutMe-painting1.png",
"https://hexo-blog-1256114407.cos.ap-shenzhen-fsi.myqcloud.com/AboutMe-painting2.png",
"https://hexo-blog-1256114407.cos.ap-shenzhen-fsi.myqcloud.com/AboutMe-painting3.png",
"https://hexo-blog-1256114407.cos.ap-shenzhen-fsi.myqcloud.com/AboutMe-painting4.png",
"https://hexo-blog-1256114407.cos.ap-shenzhen-fsi.myqcloud.com/AboutMe-painting5.png",
"https://hexo-blog-1256114407.cos.ap-shenzhen-fsi.myqcloud.com/bpmn6.png",
"https://hexo-blog-1256114407.cos.ap-shenzhen-fsi.myqcloud.com/bpmn7.png",
"https://hexo-blog-1256114407.cos.ap-shenzhen-fsi.myqcloud.com/bpmn8.png"
];
function loadImg(url) {
return new Promise((resolve, reject) => {
const img = new Image();
img.src = url;
document.body.appendChild(img);
img.onload = function() {
console.log("一张图片加载完成");
resolve(img);
};
img.onerror = function() {
reject(new Error('Could not load image at ' + url));
};
img.src = url;
});
}
实现
function limitLoad(urls, handler, limit) {
let sequence = [].concat(urls); // 复制urls
// 这一步是为了初始化 promises 这个"容器"
let promises = sequence.splice(0, limit).map((url, index) => {
return handler(url).then(() => {
// 返回下标是为了知道数组中是哪一项最先完成
return index;
});
});
// 注意这里要将整个变量过程返回，这样得到的就是一个Promise，可以在外面链式调用
return sequence
.reduce((pCollect, url, index) => {
return pCollect
.then(() => {
return Promise.race(promises); // 返回已经完成的下标
})
.then(fastestIndex => { // 获取到已经完成的下标
// 将"容器"内已经完成的那一项替换
promises[fastestIndex] = handler(url).then(() => {
return fastestIndex; // 要继续将这个下标返回，以便下一次变量
});
})
.catch(err => {
console.error(err);
});
}, Promise.resolve()) // 初始化传入
.then(() => { // 最后三个用.all来调用
return Promise.all(promises);
});
}
limitLoad(urls, loadImg, 3)
.then(res => {
console.log("图片全部加载完毕");
console.log(res);
})
.catch(err => {
console.error(err);
});
14. 函数串行调用
class LazyManClass {
constructor(name) {
this.name = name;
this.fns = [];
console.log(`Hi I am ${this.name}`);
setTimeout(() => {
this.next();
}, 0);
return this
}
sleep(time) {
const fn = () => {
setTimeout(() => {
console.log(`sleep等待了${time}秒...`)
this.next();
}, time * 1000)
}
this.fns.push(fn);
return this;
}
sleepFirst(time) {
const fn = () => {
setTimeout(() => {
console.log(`sleepFirst等待了${time}秒...`)
this.next();
}, time * 1000)
}
this.fns.unshift(fn);
return this;
}
eat(food) {
const fn = () => {
console.log(`I am eating ${food}`);
this.next();
}
this.fns.push(fn);
return this;
}
next() {
const fn = this.fns.shift();
fn && fn();
}
}
const LazyMan = (name) => {
return new LazyManClass(name);
}
LazyMan('Tony').eat('lunch').eat('dinner').sleepFirst(5).sleep(10).eat('junk food');
15. 写一个返回数据类型的函数，要求自定义的类实例化的对象返回定义的类名
function myTypeof(data) {
var toString = Object.prototype.toString;
var dataType = data instanceof Element ? "Element" : toString.call(data).replace(/\[object\s(.+)\]/, "$1")
if(dataType === 'Object'){
return data.constructor.name
}
return dataType
};
16. 使用Promise实现每隔1秒输出1,2,3
let arr = [1, 2, 3];
arr.reduce((pre, curr) => {
return pre.then(res => {
return new Promise(resolve => {
setTimeout(() => {
console.log(curr)
resolve();
}, 1000)
})
})
}, Promise.resolve())
17. 红灯3秒亮一次，黄灯2秒亮一次，绿灯1秒亮一次；如何让三个灯不断交替重复亮灯？（用Promise实现）
function red() {
console.log('red');
}
function green() {
console.log('green');
}
function yellow() {
console.log('yellow');
}
function light(func, timer) {
return new Promise(resolve => {
setTimeout(() => {
func()
resolve();
}, timer)
})
}
function step() {
Promise.resolve()
.then(res => {
return light(red, 3000);
})
.then(res => {
return light(green, 2000);
})
.then(res => {
return light(yellow, 1000);
})
.then(res => {
return step();
})
}
step();
18. 实现mergePromise函数
实现mergePromise函数，把传进去的数组按顺序先后执行，并且把返回的数据先后放到数组data中。
const time = (timer) => {
return new Promise(resolve => {
setTimeout(() => {
resolve()
}, timer)
})
}
const ajax1 = () => time(2000).then(() => {
console.log(1);
return 1
})
const ajax2 = () => time(1000).then(() => {
console.log(2);
return 2
})
const ajax3 = () => time(1000).then(() => {
console.log(3);
return 3
})
function mergePromise () {
// 在这里写代码
}
mergePromise([ajax1, ajax2, ajax3]).then(data => {
console.log("done");
console.log(data); // data 为 [1, 2, 3]
});
// 要求分别输出
// 1
// 2
// 3
// done
// [1, 2, 3]
- 利用根据Promise的特性，
在前一个then未执行完时，是不会进行后面then的执行的 - forEach循环之后的伪代码为: Promise.resolve().then(ajax1的调用).then(ajax1的运行结果).then(ajax2的调用).then(ajax2的运行结果).then(ajax3的调用).then(ajax3的运行结果)，所以能够按照指定顺序进行运行
function mergePromise(ajaxArray) {
const data = [];
let promise = Promise.resolve();
ajaxArray.forEach(ajax => {
// 第一次的then为了用来调用ajax
// 第二次的then是为了获取ajax的结果
promise = promise.then(ajax).then(res => {
data.push(res);
return data;
})
})
return promise;
}
实现promiseAll
function promiseAll (arr) {
return new Promise(resolve => {
let count = 0;
let result = [];
let promise = Promise.resolve();
for (let i = 0; i < arr.length; i++) {
promise.then(arr[i]).then(res => {
count ++;
result[i] = res;
if (count === arr.length) {
resolve(result);
result = [];
}
})
}
});
}
promiseAll([ajax1, ajax2, ajax3]).then(data => {
console.log("done");
console.log(data); // data 为 [1, 2, 3]，但是执行顺序为 2 3 1
});
19. 给一个数组nums，判断是否存在三个元素a，b，c使a + b + c = 0
function threeSum(num) {
let result = [];
num.sort((a, b) => a - b);
console.log(nums)
for (let i = 0, len = num.length; i < len - 2; i++) {
if (num[i] === num[i - 1]) {
break;
}
let start = i + 1;
let end = len - 1;
while (start < end) {
if (num[i] + num[start] + num[end] === 0) {
result.push([num[i], num[start], num[end]]);
start ++;
end --;
while(start < end && num[start] === num[start - 1]) {
start ++;
}
while(start < end && num[end] === num[end + 1]) {
end --;
}
}
else if (num[i] + num[start] + num[end] < 0) {
start ++;
}
else {
end --;
}
}
}
return result;
}
var nums = [-1,0,1,2,-1,-4, 3, 2, 5];
console.log(threeSum(nums))
20. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
var hasPathSum = function(root, sum) {
if (root === null) {
return false;
}
if (root.left === null && root.right === null) {
return root.value === sum;
}
return hasPathSum(root.left, sum - root.value) || hasPathSum(root.right, sum - root.value);
}
