首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Js算法与数据结构拾萃(1)

Js算法与数据结构拾萃(1)

作者头像
一粒小麦
发布2020-02-25 10:06:47
7180
发布2020-02-25 10:06:47
举报
文章被收录于专栏:一Li小麦一Li小麦
Js算法与数据结构拾萃(1)

算法是为了解决某些问题所提供的精确解法,数据结构是为了支撑算法提供的一种存储结构。

本系列文章以算法刷题网站leetcode为案例来源。主要阐述一些基于JavaScript的数据结构和算法基础。

哪些是需要学习的?

•简单数据结构:栈/队列/堆/哈希表/集合•复杂数据结构:树/链表/图•所有数据结构核心:数组和链表——所有都可以从中模拟出来。•常见的算法:排序/深度和广度搜索/二分查找/递归/回溯/贪心/动态规划•衡量算法优劣程度的标志:算法复杂度

【案例1】Two Sum(两数之和)

对应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].
解法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)。在提交记录中也是一种评价比较低的解决方案。

解法2:空间换时间

应该考虑用“中心化”的思想去解决单身的问题。既然你是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)。然而提交的效率却让人大跌眼镜:

解法2的变化图

算法的思考方向是没有问题的,显然性能的开销出在拷贝数组的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)。是谓之“空间换时间”。

通过这道题,初步揭示了算法题的一般的优化思路——减低算法时间复杂度。接下来可以看第二例:三数之和。

【案例2】 3 Sum(三数之和)

对应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;
};

对应运行性能:

看了那么多条件语句可能会很恶心,但算法绝多数时候不是有大道至简这种说法的。事实上上述代码还有多处边界情况可调优,可以说,你帮电脑考虑得越周到,程序就越快。

【案例3】 Fibonacci Number(斐波拉契数列)

对应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.

还有一种人,就是从网上找到了通项公式如下:

直接用表达式来计算。都通过了测试用例。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-01-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 一Li小麦 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 【案例1】Two Sum(两数之和)
    • 解法1:直接暴力遍历:
      • 解法2:空间换时间
        • 解法2的变化图
          • 小结
          • 【案例2】 3 Sum(三数之和)
            • 思路:先排序?
              • 解法:双指针
              • 【案例3】 Fibonacci Number(斐波拉契数列)
                • 解法一:递归
                  • 解法二:递推
                    • 变化图:取巧
                    领券
                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档