leetcode - 360周赛

一，2833. 距离原点最远的点

 这道题的意思是，遇到 "L" 向左走，遇到 "R" 向右走，遇到 "_" 左右都可以走，那么要想找到距离原点最远的点，就是在找 | "L" + "R" | + "_" 

代码如下：

class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        int _cnt = 0, L = 0, R = 0;
        for(int i=0; i<moves.length(); i++){
            if(moves.charAt(i) == '_'){
                _cnt++;
            }else if(moves.charAt(i) == 'L'){
                L++;
            }else{
                R++;
            }
        }
        return Math.abs(L-R)+_cnt;
    }
}

二，2834. 找出美丽数组的最小和

 这道题要我们求最小和，那么我们肯定是从1开始往后遍历，而且题目要求不存在两个不同的下标 i 和 j，使得 nums[i] + nums[j] == target，说明 当 nums[i] + nums[j] == target 时，我们只能在其中选择较小的值，例如 ：3 + 5 == 8，我们要求最小和，那么就只能选择 3 。还有一种情况，当我们遍历到的正整数 >= target 时，就不会存在上面两数相加等于target的情况，可以直接加入。

代码如下：

class Solution {
    public long minimumPossibleSum(int n, int target) {
        long sum = 0;
        int i = 1;
        int k = 0;
        while(k < n){
        // i 是 nums[i]， target-i 是 nums[j]
            if(i <= target-i){
                sum += i; 
                k++;
            }
            if(i >= target){
                sum += i;
                k++;
            }
            i++;
        }
        return sum;
    }
}

三，2835. 使子序列的和等于目标的最少操作次数

 题目告诉我们nums中存的是2的幂，所以关键是要想到使用二进制来拼凑出 target 的每一个二进制位中的 1。

1.  当 sum < target 时，因为每一个2^i 都能分成 2^i 个 1，所以我们只能得到[0，sum]中的数，说明不可能得到 target ，直接 return  -1.

2.  当 sum >= target 时，求最少的操作次数，最好的情况是，nums中有一个数 或 小于target的几个数的和 恰好等于 target， 这样看来，要求最小的操作次数，我们就要从二进制的低位向高位去考虑，因为我们要先考虑能不能直接用小于target的数凑出target。

 3. target 的第 i 个二进制位的获取方法：

1. 如果 nums 中 <= 2^i 的值的和 >= 2^i ，那么一定可以直接凑出 2^i ，直接continue
2. 如果和小于 2^i，那么我们只能在nums中找到大于2^i 的值 2^j (j > i)，然后通过不断的 /2 来得到 2^i，又因为 /2 的值都会重新放入数组 nums 中，所以 target 中第 i 到 第 j-1 的二进制位都不需要再算了，直接从第 j 个二进制位开始。

  证明1，（s表示<=2^i的数字之和）：

• 当 i = 1，s >= 2^1 时，

1）nums中存在2，很明显结论正确。

2)  nums中不存在2，那么nums中 < 2^1 的数是 1，而 1 + 1 也能得到2，结论成立。

• 当 i = 2， s >= 2^2 时，

1）nums中存在4，很明显结论正确。

2）nums中不能在4，那么nums中 < 2^2 的数有 1/2，即<=2^1，s >= 2^2 >= 2^1，根据上面得出的结论，可以得到一个2，那么剩下的 s-2 >= 2，同理，也成立。

• 当 i = 3，s >= 2^3 时，

1）nums中存在8，很明显结论正确。

2）nums中不存在8，那么nums中 < 2^3 的数是 1/2/4，即<=2^2，s >= 2^3 >= 2^2，根据上面的结论，可以得到一个4，那么剩下的 s-4 >= 4，同理，也成立。 

由此类推，我们就可以得出结论：如果 nums 中 <= 2^i 的值的和 >= 2^i ，那么一定可以直接凑出 2^i

代码如下：

class Solution {
    
    public int minOperations(List<Integer> nums, int target) {
        long sum = 0;
        //31是根据数据范围确定，从前往后依次代表的是2^0 2^1....
        int[] cnt = new int[31];
        for(int x : nums){
            sum += x;
            for(int i=0; i<31; i++){
                //类似于哈希，记录nums数组中2^i有几个
                cnt[i] += x >> i & 1;
            }
        }
        if(sum < target) return -1;
        int i = 0, ans = 0, s = 0;
        while(1L<<i <= target){
            s += cnt[i]*(1<<i);// <=2^i的数的和
            int mask = (1<<(i+1))-1;
            //j=i
            i += 1;
            if(s >= (target&mask)){// target&mask 是得到target的0~i位的二进制数
                continue;
            }
            ans += 1;//当前2^j在nums中不能通过累加或直接得到
            while(cnt[i] == 0){//在nums中找到大于2^j的数，然后一路分割
                ans += 1;
                i += 1;
            }
        }
        return ans;
    }
}

四，2836. 在传球游戏中最大化函数值

 这道题可以暴力枚举，但是因为数据范围太大，所以需要优化，这里使用了树上倍增的算法思想，直接看代码：

class Solution {
    /**
    dp[i][j]: 从j开始，走2^i所能到达的位置
   
    sum[i][j]: 从j开始，走2^i所能得到的和
     */
    public long getMaxFunctionValue(List<Integer> receiver, long K) {
        int n = receiver.size();
        int m = 64 - Long.numberOfLeadingZeros(K); //K的二进制长度
        int[][] dp = new int[m][n];
        long[][] sum = new long[m][n];
        for (int i = 0; i < n; i++) {//初始化
            dp[0][i] = receiver.get(i);
            sum[0][i] = receiver.get(i);
        }
        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                dp[i+1][x] = dp[i][dp[i][x]];
                sum[i+1][x] = sum[i][x] + sum[i][dp[i][x]];//合并节点值之和
            }
        }
 
        long ans = 0;
        for (int i = 0; i < n; i++) {
            long s = i;
            int x = i;
            for (long k = K; k > 0; k &= k-1) {
                int ctz = Long.numberOfTrailingZeros(k);//从低到高最后一个0的位置相当于要走2^ctz
                s += sum[ctz][x];
                x = dp[ctz][x];
            }
            ans = Math.max(ans, s);
        }
        return ans;
    }
}