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=ii += 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^ctzs += sum[ctz][x];x = dp[ctz][x];}ans = Math.max(ans, s);}return ans;}
}