给定两个数组,编写一个函数来计算它们的交集。 示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]
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列表中,若不相等则小元素相应的列表,指针进行向后挪动一位。直至结束,即可返回交集。
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
}
思路:对长度短的列表进行建立字典,通过循环长列表来实现找出交集。
给定一个数组 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。
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卖出更赚钱,反之则证明不如之前划算。其思路相当于动态规划。
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