xuezuo网站建设,宁波网页设计制作公司,wordpress网页后台,站群系列服务器做视频网站一#xff0c;2833. 距离原点最远的点 这道题的意思是#xff0c;遇到 L 向左走#xff0c;遇到 R 向右走#xff0c;遇到 _ 左右都可以走#xff0c;那么要想找到距离原点最远的点#xff0c;就是在找 | L R2833. 距离原点最远的点 这道题的意思是遇到 L 向左走遇到 R 向右走遇到 _ 左右都可以走那么要想找到距离原点最远的点就是在找 | L R | _
代码如下
class Solution {public int furthestDistanceFromOrigin(String moves) {int _cnt 0, L 0, R 0;for(int i0; imoves.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所以我们只能得到[0sum]中的数说明不可能得到 target 直接 return -1.
2. 当 sum target 时求最少的操作次数最好的情况是nums中有一个数 或 小于target的几个数的和 恰好等于 target 这样看来要求最小的操作次数我们就要从二进制的低位向高位去考虑因为我们要先考虑能不能直接用小于target的数凑出target。 3. target 的第 i 个二进制位的获取方法
如果 nums 中 2^i 的值的和 2^i 那么一定可以直接凑出 2^i 直接continue如果和小于 2^i那么我们只能在nums中找到大于2^i 的值 2^j (j i)然后通过不断的 /2 来得到 2^i又因为 /2 的值都会重新放入数组 nums 中所以 target 中第 i 到 第 j-1 的二进制位都不需要再算了直接从第 j 个二进制位开始。 证明1s表示2^i的数字之和
当 i 1s 2^1 时
1nums中存在2很明显结论正确。
2) nums中不存在2那么nums中 2^1 的数是 1而 1 1 也能得到2结论成立。
当 i 2 s 2^2 时
1nums中存在4很明显结论正确。
2nums中不能在4那么nums中 2^2 的数有 1/2即2^1s 2^2 2^1根据上面得出的结论可以得到一个2那么剩下的 s-2 2同理也成立。
当 i 3s 2^3 时
1nums中存在8很明显结论正确。
2nums中不存在8那么nums中 2^3 的数是 1/2/4即2^2s 2^3 2^2根据上面的结论可以得到一个4那么剩下的 s-4 4同理也成立。
由此类推我们就可以得出结论如果 nums 中 2^i 的值的和 2^i 那么一定可以直接凑出 2^i
代码如下
class Solution {public int minOperations(ListInteger nums, int target) {long sum 0;//31是根据数据范围确定从前往后依次代表的是2^0 2^1....int[] cnt new int[31];for(int x : nums){sum x;for(int i0; i31; i){//类似于哈希记录nums数组中2^i有几个cnt[i] x i 1;}}if(sum target) return -1;int i 0, ans 0, s 0;while(1Li target){s cnt[i]*(1i);// 2^i的数的和int mask (1(i1))-1;//jii 1;if(s (targetmask)){// targetmask 是得到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(ListInteger 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[i1][x] dp[i][dp[i][x]];sum[i1][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;}
}
