贪心

55跳跃游戏(可达性)/45跳跃游戏2(最小步)

55 可达性维护一个rmax

class Solution:
    def jump(self,nums):
        rmax = 0
        n = len(nums)-1
        for i in range(n):
            if i<=rmax:
                rmax = max(rmax,i+nums[i])
            if rmax>=n-1:
                return True

45 最小步维护3个变量 rmax,end,step

到当前end前都维护一个其和前end间的max(rmax,i+nums[i])作为到达当前end后下个end

相当于最大化每一个end前所能到达的下一个end
[end1,...,end2,...rmax]
      i→
[end1,...,end2,...end3]
            i

当i在end1和end2之间一直更新rmax

class Solution:
    def jump(self,nums):
        n = len(nums)
        rmax,end,step = 0,0,0
        for i in range(n):
            if i<=rmax:
                rmax = max(rmax,i+nums[i])
                if i == end:
                    end = rmax
                    step +=1
        return step

406 根据身高重建队列

先按大小降序,再按序号升序,即先把大的放完[7,0][5,0],在同样大的情况下并且先把序号低的放掉[5,0][7,0]

class Solution:
    def reconstructQueue(self,people):
        people.sort(key = lambda x:(-x[0],x[1]))
        res = []
        for i in people:
            res.insert(i[1],i)
            # res[i[1]:i[1]] = [i]
        return res

861 反转矩阵后的得分

假设翻转完的顺序无关则我们可以先翻转行再翻转列,反转行肯定要保证第一个位置是1就越大，翻转列则要保证当列的1的数量>当列的0的数量

class Solution:
    def matrixScore(self, A: List[List[int]]) -> int:
        m,n = len(A),len(A[0])
        for i in range(m):
            if A[i][0]==1:
                continue
            for j in range(n):
                A[i][j] = 1-A[i][j]
        for j in range(n):
            cntj1 = 0
            for i in range(m):
                cntj1+=1 if A[i][j]==1 else 0
            if cntj1<=m//2:
                for i in range(m):
                    A[i][j] = 1-A[i][j]
        res = 0
        for i in range(m):
            for j in range(n-1,-1,-1):
                res+=1<<(n-1-j) if A[i][j] else 0
        return res

135 分发糖果

规则定义：设学生 A 和学生 B 左右相邻，A 在 B 左边；
- 左规则：当 $ratings_{B}>ratings_{A}$ $B$的糖比$A$的糖数量多
- 右规则：当 $ratings_{A}>ratings_{B}$ $A$的糖比$B$的糖数量多
相邻的学生中，评分高的学生必须获得更多的糖果等价于所有学生满足左规则且满足右规则。

先从左至右遍历学生成绩 $ratings$，按照以下规则给糖，并记录在 $left$ 中：
1. 先给所有学生 1 颗糖；
2. 若 $ratings_{i}>ratings_{i-1}ratings_{i}>ratings_{i−1}$ ，则第 $i$ 名学生糖比第 $i−1$ 名学生多 $1$ 个。
3. 若 $ratings_i<=ratings_{i-1}ratings_{i}<=ratings_{i−1}$ ，则第 $i$ 名学生糖数量不变。（交由从右向左遍历时处理。）经过此规则分配后，可以保证所有学生糖数量满足左规则。
同理求一遍$right$
则最终$res[i] = max(left[i],right[i])$才能同时满足左规则和右规则

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        l,r = [1]*n,[1]*n
        for i in range(1,n):
            if ratings[i]>ratings[i-1]:
                l[i]=l[i-1]+1
        res = l[-1]#最后一个一定是由l决定的--不能初始化为0然后再求
        for i in range(n-2,-1,-1):
            if ratings[i]>ratings[i+1]:
                r[i]=r[i+1]+1
            res+=max(l[i],r[i])
        return res