Leetcode刷题第二天-贪心

标签：return nums int List moneys intervals 刷题 Leetcode 贪心

655:非递减数列

链接：665. 非递减数列 - 力扣（LeetCode）

直接找最大最小值进行替换不行，[1,5,4,6,7,8,9]最大最小值所处位置可能是非递减数列

如果nums[i]>nums[i+1],当前这俩个数递减，修改谁，记录前一个数，比较前一个数和当前数的大小，前一个数大，小变大，后一个数大，大变小

统计次数，出现两次，结束

 1 class Solution:
 2     def checkPossibility(self, nums: List[int]) -> bool:
 3         if(not nums):   return True
 4         count,laster=0,-1
 5         for i in range(len(nums)-1):
 6             if(i!=0):   laster=nums[i-1]
 7             if(nums[i]>nums[i+1]):  
 8                 count+=1
 9                 if(nums[i+1]<laster):
10                     nums[i+1]=nums[i]
11                 else:
12                     nums[i]=nums[i+1]
13             if(count==2):   return False
14         return True

checkPossibility

376:摆动序列

链接：376. 摆动序列 - 力扣（LeetCode）

数组长度为2，直接输出，数不一样，返回2，数一样返回1

长度超过3，遍历数组，找到连续递增或连续递减的首尾。默认前两个数之差为0，开始遍历，当前数和下一个数的差，与前两个数之差不同，结果+1，

 1 class Solution:
 2     def wiggleMaxLength(self, nums: List[int]) -> int:
 3         if(len(nums)<=1):   return len(nums)
 4         if(len(nums)==2):
 5             if(nums[0]!=nums[1]):   return len(nums)
 6             else:   return 1
 7         re=1
 8         laster=0
 9         for i in range(len(nums)-1):
10             nextre=nums[i+1]-nums[i]
11             if( (laster>=0 and nextre<0) ):
12                 re+=1
13                 laster=nextre
14             if( (laster<=0 and nextre>0) ):
15                 re+=1
16                 laster=nextre
17         return re

wiggleMaxLength

53:最大子数组和

链接：53. 最大子数组和 - 力扣（LeetCode）

数组从头开始加，和大于0，记录到最大数组和，继续加，和小于0，和从0重新开始计算，如果最后和为0，存在数组全为负数或者一正一负相加为0，返回数组最大值

 1 class Solution:
 2     def maxSubArray(self, nums: List[int]) -> int:
 3         if(not nums):   return 0
 4         if(len(nums)==1):   return nums[0]
 5         re,sums=0,0
 6         for n in nums:
 7             sums+=n
 8             if(sums>=0):
 9                 re=max(re,sums)
10             else:   sums=0
11         if(re==0):  re=max(nums)
12         return re

maxSubArray

55:跳跃

链接：55. 跳跃游戏 - 力扣（LeetCode）

跳一次，能跳的最大范围是i+num[i],在这中间的所有格子都可以跳，在能跳的最大范围内，每跳一格，更新最大范围，最大范围大于数组长度，可以，跳到最大范围边上，还没到数组长度，不可以

1 class Solution:
2     def canJump(self, nums: List[int]) -> bool:
3         if(len(nums)<=1):   return True
4         i,cover=0,0
5         while i<=cover:
6             cover=max(cover,i+nums[i])
7             if(cover>=len(nums)-1):  return True
8             i+=1
9         return False

canJump

45:跳跃2

链接：45. 跳跃游戏 II - 力扣（LeetCode）

数组长度为0，1，不用跳，和55不同的是，需要在第一次最大范围内找到跳的最远的位置

 1 import sys
 2 class Solution:
 3     def jump(self, nums: List[int]) -> int:
 4         if(len(nums)<=1):   return 0
 5         i,cover,re=0,0,0
 6         while i<len(nums):
 7             step=i+nums[i]
 8             re+=1
 9             if(step>=len(nums)-1): break
10             for j in range(i,step+1):
11                 if(j==len(nums)):   break
12                 if(j+nums[j]>step):
13                     step=j+nums[j]
14                     i=j
15                     cover=1
16             if(not cover):    
17                 re=0
18                 break
19         return re

jump

1005：k次取反后求最大和

链接：1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

每次都找最小值取反

1 class Solution:
2     def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
3         if(not nums):   return 0
4         while k:
5             min_n=min(nums)
6             min_id=nums.index(min_n)
7             nums[min_id]=-min_n
8             k-=1
9         return sum(nums)

largestSumAfterKNegations

134:加油站

链接：134. 加油站 - 力扣（LeetCode）

嘶~些微有点头疼，先确认从当前加油站走后剩余油，找剩余量大于0的，开始，依次加后面加油站剩余油量，如果出现负数，本轮失败，继续找余量大于0，开始，依次加后面加油站剩余油量大于等于0，回到开始位置，ok

 1 class Solution:
 2     def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
 3         if(not gas or not cost):    return -1
 4         if(sum(cost)>sum(gas)):   return -1
 5         if(len(gas)==1):    return 0
 6         uses={}
 7         n=len(gas)
 8         for i in range(n):
 9             uses[i]=gas[i]-cost[i]
10         usess=sorted(uses.items(),key=lambda x:x[1],reverse=True)
11         for index in usess:
12             if(index[1]>0):
13                 sums=index[1]
14                 i=index[0]
15                 while sums>=0:
16                     i+=1
17                     if(i==n):   i=0
18                     sums+=uses[i]
19                     if(i==index[0]):    return i
20                     
21                 
22                 

canCompleteCircuit

860:找零

链接：860. 柠檬水找零 - 力扣（LeetCode）

(lll￢ω￢)出现20优先找10块的。。。

 1 class Solution:
 2     def lemonadeChange(self, bills: List[int]) -> bool:
 3         if(not bills):  return True
 4         moneys={5:0,10:0,20:0}
 5         for bill in bills:
 6             moneys[bill]+=1
 7             if(bill==10):
 8                 if(moneys[5]>0):    moneys[5]-=1
 9                 else:   return False
10             if(bill==20):
11                 if(moneys[10]>0 and moneys[5]>0):
12                     moneys[5]-=1
13                     moneys[10]-=1
14                 elif(moneys[5]>2):    moneys[5]-=3
15                 else:
16                     return False
17             print(moneys)
18         return True

lemonadeChange

56:合并区间

链接：56. 合并区间 - 力扣（LeetCode）

区间左端从大到小，下一个区间尾大于等于当前区间头，合并

 1 class Solution:
 2     def merge(self, intervals: List[List[int]]) -> List[List[int]]:
 3         if(not intervals):  return intervals
 4         intervals.sort(key=lambda x:x[1],reverse=True)
 5         data=[]
 6         i=0
 7         while i<len(intervals)-1:
 8             if(intervals[i+1][1]>=intervals[i][0]):
 9                 intervals[i][0]=min(intervals[i+1][0],intervals[i][0])
10                 intervals.remove(intervals[i+1])
11             else:
12                 i+=1
13         return intervals

merge

 

标签：return,nums,int,List,moneys,intervals,刷题,Leetcode,贪心
From： https://www.cnblogs.com/xiaoruru/p/17983026