2021 年 08 月 02 日

本文题目全部来自 LeetCode

使用 Typescript

本篇文章全部收藏于专栏 3周攻克数据结构-LeetCode

本文所有代码和解题步骤将放置 GitHub仓库

DAY3

1. 两个数组的交集 II

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]

输出:[2,2] 示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出:[4,9]

说明:

输出结果中每个元素出现的次数,应与元素在两个数组中出现次数的最小值一致。 我们可以不考虑输出结果的顺序。

进阶:

如果给定的数组已经排好序呢?你将如何优化你的算法?

如果 nums1 的大小比 nums2 小很多,哪种方法更优?

如果 nums2 的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

方法1:哈希表查询

哈希表查询 空间换时间 ——— O(n)

  1. 简历哈希表,值做key次数做value
  2. 查询哈希表,按次数判断交集
function intersect(nums1: number[], nums2: number[]): number[] {
    // 创建 哈希表
    let map = new Map()
    // 结果
    let res = []

    // 为nums1 建立 哈希表
    for (let v of nums1) {
        map.has(v) ? map.set(v, map.get(v) + 1) : map.set(v, 1)
    }

    // 遍历 nums2 查找nums1 的哈希表 找到交集
    for (let v2 of nums2) {
        if(map.has(v2)) {
            res.push(v2)
            // 找到了,次数大于 1 减一次,否则删除
            map.get(v2) > 1 ? map.set(v2, map.get(v2) - 1) : map.delete(v2)
        }
    }
    
    return res
};

方法2:双指针

function intersect(nums1: number[], nums2: number[]): number[] {
    // 创建2个数组指针
    let p1 = 0
    let p2 = 0
    // 排序2个数组
    nums1 = nums1.sort((a, b) => a - b)
    nums2 = nums2.sort((a, b) => a - b)

    let res = []
    // 取数组长度最小的一个数组做判断条件
    while (p1 < nums1.length && p2 < nums2.length ) {
        // 找到交集
        if(nums1[p1] === nums2[p2]){
            res.push(nums1[p1])
            p1 ++
            p2 ++
        // 数组1当前指针的值小于数组2的话,指针加一,用下一个数来比较
        } else if (nums1[p1] < nums2[p2]) {
            p1 ++
        // 数组2当前指针的值小于数组1的话,指针加一,用下一个数来比较
        } else {
            p2 ++
        }
    }

    return res
};

2. 买卖股票的最佳时机

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

 

示例 1:

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:

输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
 

提示:

1 <= prices.length <= 105
0 <= prices[i] <= 104

方法1:贪心算法

  1. 拟定一个最小值和当前利润
  2. 遍历更新最小值和利润
function maxProfit(prices: number[]): number {
    // 利润
    let profit = 0
    // 最小值
    let min = prices[0]

    for (let v of prices) {
        if(v < min){
            min = v

        // 如果出现比最大利润还要大的就进行重新赋值
        }else if(v  - min > profit){ 
            profit = v  - min
        }
    }

    return profit
};

方法2:动态规划

function maxProfit(prices: number[]): number {
    // 存放最小的值
    let minprice = Number.MAX_VALUE
    // 存放差值
    let maxprofit = 0
    
    for (let v of prices) {
        // 每次更新最小的值
        minprice = Math.min(v, minprice)
        // 每次计算差值
        maxprofit = Math.max(v - minprice, maxprofit)
    }

    return maxprofit
};

科普篇

  1. 贪心算法:(Greedy Algorithm)

    贪心算法 即经典的 —— “背包问题”

贪心算法,又名贪婪法,是寻找最优解问题的常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心原则,选取当前状态下最好/最优的选择(局部最有利的选择),并以此希望最后堆叠出的结果也是最好/最优的解。

—— 贪心算法可能拿到的不一定是最优解,但一定是趋向于最优解。

  1. 动态规划(# Dynamic Programming)

    动态规划也适用于 “背包问题” ,如果说 “贪心算法”是趋向最优解,那么动态规划就是找到动最优解。 通过分解找出各个商品的排列组合,筛选组合的时候不断的调整策略即是动态规划

推荐一本算法科普书 —— 算法图解

第八章和第九章中会通过背包问题介绍 “贪心算法” 和 “动态规划”


© 2021, 滇ICP备19003866号本网站版权归本站作者Ruoduan所有原创文章遵循CC BY-SA 4.0授权许可,转载请注明出处