#分糖果问题（贪心算法）
描述：一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
- 每个孩子不管得分多少，起码分到一个糖果。
- 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果
#2022-06-23分糖果问题
class Solution:
def candy(self,arr):
nn=len(arr)
res=[1]*nn
##从左到右遍历，如果右边比左边得分高，那么右边的糖果数res[i]+1
for i in range(1,nn): #range()左闭右开
if(arr[i]>arr[i-1]):
res[i]=res[i-1]+1
else:
res[i]=1
sum=res[nn-1]
##从右到左遍历，如果左边比右边大且糖果数小于或者等于右边，则糖果数+1
for j in range(nn-1,0):
if(arr[j-1]>arr[j] and res[j-1]<=res[j]):
res[j-1]=res[j-1]+1
sum+=res[j-1]
return sum
##
arrs=[1,2,1,2,3,2,1,2] #得分列表
aa=Solution()
print(aa.candy(arrs))
分糖果.png
#对于从右至左遍历，如果没有循环更新，那么上图中的红色框内将会是1
方法二 res up down peak
##方法二
class Solution:
def candy(self,arr):
nn=len(arr)
res=1
up=0
down=0
peak=1
for i in range(0,nn-1):
res=res+1
if(arr[i+1]>arr[i]):
up=up+1
res=res+up
down=0
peak=up+1
elif(arr[i+1]<arr[i]):
res=res+down
down=down+1
up=0
if(down<=peak):
res=res+1
else:
up=0
down=0
peak=1
return res
arrs=[1,2,3,2,1,2]
aa=Solution()
print(aa.candy(arrs))
#主持人调度
描述：有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。
一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。
输入：
2,[[1,2],[2,3]]
返回值：
1
说明：
只需要一个主持人就能成功举办这两个活动
输入：
2,[[1,3],[2,4]]
返回值：
2
说明：
需要两个主持人才能成功举办这两个活动
##2022-06-24主持人调度
class Solution:
def minmumNumberOfHost(self , n , startEnd ):
start=[]
end=[]
for i in range(0,len(startEnd)):
start=start.append(startEnd[i][0])
end=end.append(startEnd[i][1])
i,j=0,0
count=0
max_num=0
while i<n and j<n:
if start[i]<end[j]:
i=i+1
count=count+1
max_num=max(max_num,count)
elif start[i]==end[j]:
j=j+1
i=i+1
else:
j=j+1
count=count-1
return max_num
#买卖股票的最好时机1
描述：假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费
数据范围： 0 <= n <= 10^5 , 0 <= val <= 10^4
要求：空间复杂度 O(1)，时间复杂度 O(n)
##2022-06-27买卖股票的最好时机
class Solution:
def maxProfit(self,prices):
nn=len(prices)
if(nn==0):
return 0
min=prices[0]
max=-1
for i in range(0,nn):
if(prices[i]<min):
min=prices[i]
if(max<prices[i]-min):
max=prices[i]-min
return max
#买卖股票的最好时机2
描述：假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
- 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
- 如果不能获取收益，请返回0
- 假设买入卖出均无手续费
数据范围： 1 <= n <= 1*10^5 1≤prices[i]≤10^4
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)
##2022-06-27买卖股票的最好时机2
class Solution:
def maxProfit(self,prices):
nn=len(prices)
if(nn==0 or nn==1):
return 0
de =0
max_num=0
for i in range(1,nn):
if(prices[i]>prices[i-1]):
de=prices[i]-prices[i-1]
max_num=max_num+de
return max_num
#买卖股票的最好时机3
描述：描述
假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
- 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
- 如果不能获取收益，请返回0
- 假设买入卖出均无手续费
数据范围：1≤n≤10^5 股票的价格满足 1≤val≤10^4
要求: 空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)
##2022-06-28买卖股票的最好时机3
class Solution:
def maxProfit(self,prices):
nn=len(prices)
if(nn==0 or nn==1):
return 0
buy1=buy2=prices[0]
profit1=profit2=0
for i in range(0,nn):
buy1=min(buy1,prices[i])
profit1=max(profit1,prices[i]-buy1)
buy2=min(buy2,prices[i]-profit1)
profit2=max(profit2,prices[i]-buy2)
return max(profit1,profit2)
这里的buy2以及profit2如何更新？
#使用异或操作实现交换两个数
##使用异或来交换两个数
arrs=[1,2]
aa=10
def myChange(a,b):
a=a^b
b=a^b
a=a^b
return [a,b]
#能这样操作的前提是两个数字的内存位置不一样
print(myChange(aa,aa))
#寻找数组中出现奇数次的数
1.只有一个数出现奇数次，其它数出现偶数次
def findNumber(arrs):
eor=0
for i in arrs:
eor=eor^i
return eor
2.共有两个数出现奇数次，其它数目出现偶数次
#一个数&与自己的取反加1就是得到该数最右位置的1
eor&(~eor+1)
def findNumber(arrs):
eor=0
for i in arrs:
eor=eor^arrs
#得到a^b
rightone=eor&(~eor+1) #得到eor最右位置为1的二进制值
onlyone=0
for j in arrs:
if((j and rightone)==1):
onlyone=onlyone^j
return [onlyone,onlyone^eor]
网友评论