350. 两个数组的交集 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]

具体题目链接

Python

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        n1,n2,n1_len,n2_len=0,0,len(nums1),len(nums2)
        intersection=[]
        while n1<n1_len and n2<n2_len:
            if nums1[n1]==nums2[n2]:
                intersection.append(nums1[n1])
                n1+=1
                n2+=1
            elif nums1[n1]>nums2[n2]:
                n2+=1
            else:
                n1+=1
        return intersection

思路：通过对nums1和nums2重排，通过对两个列表循环，两列表对比的元素若相同则添加到intersection列表中，若不相等则小元素相应的列表，指针进行向后挪动一位。直至结束，即可返回交集。

GO

func intersect(nums1 []int, nums2 []int) []int {
    if len(nums1)>len(nums2){
        return intersect(nums2,nums1)
    }
    nums1_map:=map [int]int{}
    for _,value:=range nums1{
        nums1_map[value]++
    }
    intersection:=[]int{}
    for  _,value:=range nums2{
        if nums1_map[value]>0{
            intersection=append(intersection,value)
            nums1_map[value]--
        }
    }
    return intersection
}

思路：对长度短的列表进行建立字典，通过循环长列表来实现找出交集。

121. 买卖股票的最佳时机

给定一个数组 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。

具体题目链接

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        Lowest=prices[0]
        ans=0
        for price in prices[1:]:
            Lowest=min(Lowest,price)
            ans=max(ans,price-Lowest)
        return ans

思路：Lowest是最低点，通过循环过程中不断更新记录已知的最低点来确定买股票的价钱，之后通过与已知的盈利ans与当前价格与最低点差值price-Lowest来对比，若price-Lowest大则证明price卖出更赚钱，反之则证明不如之前划算。其思路相当于动态规划。

GO

func maxProfit(prices []int) int {
    ans,Lowest:=0,prices[0]
    for _,price:=range prices[1:]{
        if Lowest<=price{
            if ans<=price-Lowest{
                ans=price-Lowest
            }
        }else{Lowest=price}
    }
    return ans
}

思路：同python