1792. 最大平均通过率

已知每个班级的学生人数和可以通过的人数，现在再给一个额外的必定能通过考试的学生人数，求能班级平均通过率最大的分配方法。

当前平均通过率 $ave=\sum_{1}^{n}\frac{pass_i}{total_i}/n$

所以要怎么使 ave最大？首先越小的 $total$ 越容易增大通过率

那么应该如何分配呢？可以转换一下问题，在计算 ave 的时候， n 是不变的，也就是说，我们要尽可能的使通过率的和变大。显然把这些人分配给人数比较少的班级收益比较大一些。通过率增加的会比放入人较少的班级更多，那么应该分配给通过率比较高的班级还是通过率比较低的班级呢？

举个例子，对于 4/5 和 3/5 的通过率，只有一个人可以分配，分配给第一班，则通过率和是 5/6 + 3/5 = 43/30 ；分配第二班，则通过率和是 4/5 + 4/6 = 44/30 ，可以看出分配给通过率低的班级收益大一点。为什么呢？比如说 4/5 ，增加一个合格的人，通过率固然会提高，但是它稀释的负面效应对于这种总通过人数多的比增加一个还大。

152. 乘积最大子数组*

对于以 nums[i] 为尾的子数组的最大乘积。

暂时还是没有理解到精髓。。。

3025. 人员站位的方案数

给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。

计算点对 (A, B) 的数量，其中

A 在 B 的左上角，并且
它们形成的长方形中（或直线上）没有其它点（包括边界）。

返回数量。

A 在 B 的左上角，说明 A.x < B.x && A.y>B.y , 形成的长方形上没有其它直线，那么可以先遍历一遍这个 points 数组，如果有对于已加入的点，当前遍历到的点满足 x 在已加入的点之间且 y 也在已加入点的 y之间，那么肯定不满足条件 2。

可以先按横坐标递增来排序，然后反向遍历。

这样后面遍历的点，横坐标位置肯定在第一次遍历的里面，也就是第二次遍历后面的点，如果

class Solution {
    public int numberOfPairs(int[][] points) {
        int n = points.length;
        int ans = 0;
        Arrays.sort(points,(x,y)->{
            return x[0]-y[0];
        });
        for(int i=0;i<n;i++){
            int[] p1 = points[i];
            for(int j=n-1;j>i;j--){
                int[] p2 = points[j];
                if(((p1[0]<p2[0]&&p1[1]>=p2[1])||(p1[0]==p2[0]))&&isFit(i,j,points))
                    ans++;
            }
        }
        return ans;


    }
    private boolean isFit(int i,int j,int[][] points){
        int x1 = points[i][0];
        int y1 = points[i][1];
        int x2 = points[j][0];
        int y2 = points[j][1];
        for(int k=0;k<points.length;k++){
            int[] p = points[k];
            if(k==i||k==j)
                continue;
            if(p[0]>=x1 && p[0]<=x2 &&((p[1]<=y1&&p[1]>=y2)||( p[1]<=y2&&p[1]>=y1)))
                return false;
        }
        return true;


    }
}

416. 分割等和子集

第二次做了，希望一遍ac

其实只用考虑一个子集的分割问题，sum-set1 = set2 ，问题就是，找到一个子集 set1 使得上式成立。

只用到子集型回溯会超时，增加一个记忆化搜索。那么要考虑一下状态是如何标志的。对于不同位置，选或不选会有不同的子集和，而这些子集和是会重复计算的。

相当于能否在找到和为 sum/2 的子集

当前操作：选或不选 nums[i]

子问题：
选： dp[i-1][j-nums[i]] 是否为真
不选: dp[i-1][j] 是否为真

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;

        
        for(int n2:nums){
            sum+=n2;
        }
        if(sum%2!=0)
            return false;
        int[] memo = new int[sum/2+1];

        if(nums[0]<=sum/2) 
            memo[nums[0]]=1;
        else
            return false;

        for(int i=1;i<n;i++){
            for(int j=sum/2;j>=nums[i];j--){
                    memo[j] = memo[j-nums[i]]==1|| memo[j]==1?1:-1;
            }
        }
        return memo[(sum)/2]==1;

        
    }
}

3027. 人员站位的方案数 II

简化一下就是，给你一个点集，找到点 a 和 b，使其 a.x<=b.x && a.y>=b.y ,然后还要满足点集中任意一个点 p都不满足 p.x>=a.x && p.x<=b.x && p.y<=a.y && p.y>=b.y

2749. 得到整数零需要执行的最少操作数

每次减去的 $2^i+num2$ 不能大于 $num1$ , 且需要 $i$ 尽可能的大，那么可以让 num1 = num1-num2 ，然后对其取 2 的对数 $\log(num1-num2)$ 。如果这个对数大于 60 ，那么就直接取 60, 如果小于 60，那么就可以向下取整，然后再重复执行上述操作；如果这个数小于0，那么说明没有可能的 i ，直接返回 -1 。

边界条件？当 (num1-num2)<=0时，再考虑到 $2^i$ ，显然没有办法让 num1 等于 0 了。直接返回 -1。如果对数小于 0 呢？

假设操作了 k 次，那么问题就转换成了能不能找到 k 满足 x = num1 - num2*k ， x 能否表示为 k 个 2 的幂。每次 $2^i$ 都取最小值 1，也就是按次数最多来分，有 $k*2^0 = x$ ，所以 k<=x,按次数最少分，也就是每一个二进制位刚好用一个 $2^i$ 来表示，就需要
Long.bitCount(x)次来表示，只要 k 在这两个数中间，就说明 x 可以被表示成 k 个 2的幂。

比如说 x=9 ，9 的二进制表示为 1001，用二进制来表示，最少也需要两位。

class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        long n1 = num1;
        long n2 = num2;
        for(int i=1;i<=64;i++){
            long x = n1-n2*i;
            if(x<i)
                return -1;
            
            if(i>=Long.bitCount(x))
                return i;
        }
        return -1;
    }
}

为什么循环终点是 64 ，因为如果 $num1<=2^{64}$ ，可以至多用64位的x表示。解释的不是很清楚，下次再看。

3495. 使数组元素都变为零的最少操作次数

不会，数学问题

32. 最长有效括号

子问题：以当前括号为结尾的子串的最长有效括号子串长度

1304. 和为零的 N 个不同整数

一个直觉就是如果 n 是偶数，那就选 n/2 对相反数即可，如果 n 是奇数，那就选 n/2 对相反数，然后再加个 0 即可。

class Solution {
    public int[] sumZero(int n) {
        int start = 1;
        int[] ans = new int[n];
        int i=0;
        if(n%2!=0){
            ans[0]=0;
            i=1;
        }
        
        for(;start<=n/2;start++){
            ans[i]=start;
            ans[i+1]=-start;
            i+=2;
        }
        return ans;
    }
}

突然感觉自己又行了😤😤😤

1317. 将整数转换为两个无零整数的和

如何判断一个正整数不包含 0？，或者说，怎么拆一个数，才能保证组成这个数的两个数不包含零？

一个直观的想法就是从 1 遍历到 n/2，然后再遍历。

2327. 知道秘密的人数

设 day[i] 是第 i 天知道秘密的人数， forget[i] 是第 i 天要遗忘的人数， know[i] 是第 i 天新增的知道秘密的人数。

那么 day[i] = day[i-1] - forget[i] + know[i]

第 i 天忘掉的人数肯定是 forget 天前新增的人数，
其中 forget[i] = know[i-forget]

第 i 天新增的人数等于 delay 天前知道秘密的人数。

delay必然小于等于forget，不然知道秘密的人数最多只有1个。

class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        int[] day = new int[n + 1];
        int[] know = new int[n + 1];
        int[] fsum = new int[n+1];
        int[] f = new int[n + 1];
        final int MOD = 1000000007;
        
        day[0] = 0;
        know[1] = 1;
        
        for (int i = 1; i <= n; i++) {
            if (i - forget >= 0) {
                f[i] = know[i - forget] % MOD;
            }
            
            fsum[i] = (fsum[i-1] + f[i]) % MOD;
            
            if (i - delay >= 0) {
                int temp = (day[i - delay] - (fsum[i] - fsum[i-delay])) % MOD;
                know[i] = (know[i] + temp + MOD) % MOD;  // 加MOD确保非负
            }
            
            day[i] = ((day[i - 1] - f[i] + know[i]) % MOD + MOD) % MOD;  // 双重模确保非负
        }
        
        return day[n] % MOD;
    }
}

day[i-1]-f[i]+know[i] 可能很大，所以先取模减小范围，又因为可能为负数，所以加一个模使其为正数。

1733. 需要教语言的最少人数

对于任意两个好友之间，显然有

好友之间有共同掌握的语言集合，这种情况不用考虑
好友之间没有共同掌握的语言，这种情况如何应对

对于第二种情况，只需要选择一种语言，使得使得这对好友能沟通。

目标：找出需要教语言的最少人数，那么我们要找出所有不能沟通的好友。然后找出一种语言，使不能沟通的好友都掌握这种语言。

选择掌握人数最多的语言 a ，因为如果这些人是好友关系，如果不选择这个语言，而选 b ，那么显然要教 b 的人数会比教 a 更多。

如果这些人不是好友关系，那么就不用教这些人，如果选 b ,那么

155. 最小栈

import sys
class Node:
    def __init__(self,val,next):
        self.val = val
        self.next = next

class MinStack:
    def __init__(self):
        self.head = None
        

    def push(self, val: int) -> None:
        node = Node(val,None)
        node.next = self.head
        self.head = node

    def pop(self) -> None:
        self.head = self.head.next

    def top(self) -> int:
        return self.head.val

    def getMin(self) -> int:
        node = self.head
        min = sys.maxsize
        while node != None:
            if min>node.val :
                min = node.val
            node = node.next
            
        return min


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

寻找最小值的方式是使用遍历，这样速度可能比较慢。

其实使用列表也可以，尾插法，列表尾部作为栈顶。

class MinStack:

    def __init__(self):
        self.st = [(0,inf)]

    def push(self, val: int) -> None:
        self.st.append((val,min(self.st[-1][1],val)))

    def pop(self) -> None:
        self.st.pop()

    def top(self) -> int:
        return self.st[-1][0]

    def getMin(self) -> int:
        return self.st[-1][1]

太牛了，维护前缀中的最小值，这样就可以实现在常数时间内找到最小值。

976. 三角形的最大周长

给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。

三角形的性质：两边之和大于第三边。

然后要想周长尽量的长，那么可以先排个序，选最长的边，与它后面两个边相比，如果满足那就是，如果不满足那就换下一个边