[Leetcode]两个数组的交集2&买卖股票的最佳时机
Leetcode数据结构题目集的第三天的题目。
这次分别是两个数组的交集II
和买卖股票的最佳时机
。
两个数组的交集II
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
1 | 输入:nums1 = [1,2,2,1], nums2 = [2,2] |
示例 2:
1 | 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] |
说明:
- 输出结果中每个元素出现的次数,应与元素在两个数组中出现次数的最小值一致。
- 我们可以不考虑输出结果的顺序。
进阶:
- 如果给定的数组已经排好序呢?你将如何优化你的算法?
- 如果 nums1 的大小比 nums2 小很多,哪种方法更优?
如果 nums2 的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
解题思路&题解
题目要求两个数组的交集,但没有要求顺序。
故我们可以遍历长的那个数组,用哈希表来存放数据结构为item-次数
的内容。
然后遍历短数组时,若元素在哈希表的key中则添加到结果,并将哈希表对应的内容次数减一。
代码如下:
1 | func intersect(nums1 []int, nums2 []int) []int { |
买卖股票的最佳时机
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
示例 1:
1 | 输入:[7,1,5,3,6,4] |
示例 2:
1 | 输入:prices = [7,6,4,3,1] |
提示:
1 <= prices.length <= 105
0 <= prices[i] <= 104
解题思路&题解
主要思路如下
- 记录今天之前买入的最小值
- 计算今天之前最小值,今天卖出的获利 => 今天卖出能获利多少
- 遍历的时候比较每天的获利与最大值
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13func maxProfit(prices []int) int {
min := prices[0]
max := 0
for _, item := range prices {
if item < min {
min = item
}
if item-min > max {
max = item - min
}
}
return max
}