算法是为了解决某些问题所提供的精确解法,数据结构是为了支撑算法提供的一种存储结构。
本系列文章以算法刷题网站leetcode为案例来源。主要阐述一些基于JavaScript的数据结构和算法基础。
哪些是需要学习的?
•简单数据结构:栈/队列/堆/哈希表/集合•复杂数据结构:树/链表/图•所有数据结构核心:数组和链表——所有都可以从中模拟出来。•常见的算法:排序/深度和广度搜索/二分查找/递归/回溯/贪心/动态规划•衡量算法优劣程度的标志:算法复杂度
对应leetcode开篇第1题,难度:简单 https://leetcode.com/problems/two-sum/
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum = (nums, target) => {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return [i, j]
}
}
}
};
试想你组织一群单身青年参加一场相亲party,目标是配对成功一对即可!为了找到匹配的那个人,我们要求每对人必须彼此聊天,这样的操作是非常累人的。
这种题目既然给出来,就不会指望你用暴力的方法来算的。此处算法复杂度为O(n 2),空间复杂度为O(1)。在提交记录中也是一种评价比较低的解决方案。
应该考虑用“中心化”的思想去解决单身的问题。既然你是party的组织者,就考虑有一套花名册,让每个相亲的人都到花名册里翻一翻有没自己中意的,如果有,直接配对完事。否则就来登记一下自己的需求。
我们直接用测试用例nums=[2,7,11,15];target=9
来思考一下:在暴力破解法第一次遍历中,当便利到2时,就应该在余下的数组中找值等于9-2=7
的元素,以下亦然。根据此思路,一层循环即可解决该问题。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum = (nums, target) => {
for (let i = 0; i < nums.length; i++) {
const _nums = nums.slice(i+1);
const _target = target - nums[i];
const _index = _nums.indexOf(_target);
if (_index > -1) {
return [i, i+1+_index]
}
}
};
乍看之下,两层循环变成了一层循环,代码变得好看了。算法复杂度也变成了O(n)。然而提交的效率却让人大跌眼镜:
算法的思考方向是没有问题的,显然性能的开销出在拷贝数组的slice操作。如果我们能有一个动态的hashMap,存放已经遍历过的key(值)-value(下标)
映射。那么随着循环进行,终将命中需要的下标。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum = (nums, target) => {
let hashMap = {};
for (let i = 0; i < nums.length; i++) {
const _target = target - nums[i];
// hashMap[_target]判值要避开0
if (hashMap[_target] != undefined) {
return [i, hashMap[_target]]
}
hashMap[nums[i]] = i;
}
};
这下性能指标就很好看了。
改进后的解法,时间复杂度为O(n)。但是空间复杂度为O(n)。是谓之“空间换时间”。
通过这道题,初步揭示了算法题的一般的优化思路——减低算法时间复杂度。接下来可以看第二例:三数之和。
对应leetcode第15题,难度:中等 https://leetcode.com/problems/3sum/
Given an array nums
of n integers, are there elements a,b,cin nums
such that a+b+c= 0? Find all unique triplets in the array which gives the sum of zero.
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
Note:
The solution set must not contain duplicate triplets.
答案中不可以包含重复的三元组。
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
错误解法:暴力破解
在leetcode看到这种题,暴力破解一般都是跑不完测试用例的,因为暴力是个程序员都会。除了第一题。暴力破解的话,n数之和就意味着n重循环。代码也相当难看:
// 【超出时间限制】
/* 被卡测试用例:[-13,5,13,12,-2,-11,-1,12,-3,0,-3,-7,-7,-5,-3,-15,-2,14,14,13,6,-11,-11,5,-15,-14,5,-5,-2,0,3,-8,-10,-7,11,-5,-10,-5,-7,-6,2,5,3,2,7,7,3,-10,-2,2,-12,-11,-1,14,10,-9,-15,-8,-7,-9,7,3,-2,5,11,-13,-15,8,-3,-7,-12,7,5,-2,-6,-3,-10,4,2,-5,14,-3,-1,-10,-3,-14,-4,-3,-7,-4,3,8,14,9,-2,10,11,-10,-4,-15,-9,-1,-1,3,4,1,8,1]
*/
const threeSum = (nums) => {
let sumThree = [];
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
let a = nums[i] + nums[j];
for (let k = 0; k < nums.length; k++) {
if (k !== i && k !== j) {
if (nums[i] + nums[j] + nums[k] == 0) {
// 二位数组查重
let arr = [nums[i], nums[j], nums[k]];
var flag = false;
for (let x = 0; x < sumThree.length; x++) {
if (JSON.stringify(sumThree[x].sort()) == JSON.stringify(arr.sort())) {
flag = true;
break
}
}
if (!flag) {
sumThree.push(arr);
}
}
}
}
}
}
return sumThree
};
测试用例给的都是乱序的,因此,基于乱序的测试用例,如果不排序,是无法优化算法的。尤其是数组去重,能不做就不做。
所以考虑排序。那么对剩下的数组就转化为了两数月之和等于-nums[i]
的问题。设想有左右两个指针,按照一定的规律遍历数组,从而降低复杂度。
在此不实用案例1的hashMap思路来求解“转化后”的“两数之和”问题,使用双指针的思路:
•首先对数组进行排序,排序后固定一个数 nums[i];•再使用左右指针指向 nums[i]后面的两端,数字分别为 nums[j] 和 nums[k](j<k),计算三个数的和, 判断是否满足为 0,满足则添加进结果集。•如果 nums[i]大于 0,意味着参与循环的最小数大于0,则三数之和必然无法等于0,结束循环•如果 nums[i]== nums[i-1],则说明该数字重复,会导致结果重复,所以直接应该跳过该循环•三数之和 为0 时,nums[j] == nums[j+1] 则会导致结果重复,应该跳过,j右移(j++)•三数之和为0 时,nums[k]== nums[k-1] 则会导致结果重复,应该跳过,k左移(k--)•时间复杂度:两重循环,O(n2),n 为数组长度,
const threeSum = (nums) => {
// 首先需要从小到大排序
let _nums = nums.sort((a, b) => a - b);
let ret = [];
// j左指针 k右指针
for (let i = 0; i < _nums.length - 2; i++) {
// console.log(`第${i}次`, _nums[i]);
let j = i + 1;
let k = _nums.length - 1;
// 如果内容一样,跳过此次循环
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
// 转化为两数之和问题
const targ = - _nums[i];
while (j < k) {
if (_nums[j] + _nums[k] == targ) {
ret.push([_nums[i], _nums[j], _nums[k]]);
while (j < k && _nums[j] == _nums[j + 1]) {
j++;
}
while (j < k && _nums[k] == _nums[k - 1]) {
k--;
}
j++;
k--;
} else if (_nums[j] + _nums[k] < targ) {
j++;
} else if (_nums[j] + _nums[k] > targ) {
k--;
}
}
}
return ret;
};
对应运行性能:
看了那么多条件语句可能会很恶心,但算法绝多数时候不是有大道至简这种说法的。事实上上述代码还有多处边界情况可调优,可以说,你帮电脑考虑得越周到,程序就越快。
对应leetcode第509题 难度:简单 https://leetcode.com/problems/fibonacci-number/submissions/
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).
这个数列不需要翻译了。就是求fib数列第n项。这是leetcode通过率排前几名的题目之一。
根据题释,直接可以写出代码:
/**
* @param {number} N
* @return {number}
*/
const fib = (N) => {
if(N<=1){
return N;
}
if(N>=2){
return fib(N-1)+fib(N-2);
}
}
果真是“大道至简”。然而,递归在程序的世界总是恐怖的存在。
递归涉及了大量的重复计算。以求解fib(5)为例:递归树就重复了3次fib(2)的计算。
我想解法二才是需要考察的程序员思维。考虑用缓存去计算当前的项。你可以用一个数组去已经推出的斐波拉契数。第n项根据第n-1和n-2项推出。更直接的方式是互换:
/**
* @param {number} N
* @return {number}
*/
const fib = (N) => {
if (N <= 1) {
return N;
}
let before = 1;
let current = 1;
let tmp = 0;
for (let i = 2; i < N ; i++) {
tmp = current;
current += before;
before = tmp;
}
return current
};
按照此思路,运行性能终于达到了一个比较主流的情况了。
做算法题总不乏一群取巧的人。他们给出了各种有意思的答案。
测试用例仅仅能支持到N=31时的情况。于是就有了取巧的解法:
/**
* @param {number} N
* @return {number}
*/
const fib = (N) => {
if(N==0)
return 0;
if(N==1)
return 1;
if(N==2)
return 1;
if(N==3)
return 2;
if(N==4)
return 3;
// ...
if(N==30)
return 832040;
return 0;
}
Runtime: 52 ms, faster than 81.81% of JavaScript online submissions for Fibonacci Number.
Memory Usage: 33.9 MB, less than 68.18% of JavaScript online submissions for Fibonacci Number.
还有一种人,就是从网上找到了通项公式如下:
直接用表达式来计算。都通过了测试用例。