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)
- 简历哈希表，值做key次数做value
- 查询哈希表，按次数判断交集
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：贪心算法
拟定一个最小值和当前利润
遍历更新最小值和利润
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
};
科普篇
- 贪心算法：（Greedy Algorithm）
贪心算法 即经典的 —— “背包问题”
贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。
—— 贪心算法可能拿到的不一定是最优解，但一定是趋向于最优解。
- 动态规划（# Dynamic Programming）
动态规划也适用于 “背包问题” ，如果说 “贪心算法”是趋向最优解，那么动态规划就是找到动最优解。 通过分解找出各个商品的排列组合，筛选组合的时候不断的调整策略即是动态规划
推荐一本算法科普书 —— 算法图解
第八章和第九章中会通过背包问题介绍 “贪心算法” 和 “动态规划”
- 小尾巴~
本文持续更新专栏 ———— 3周攻克数据结构-LeetCode