一,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 个二进制位的获取方法:
- 如果 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 个二进制位开始。
证明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. 在传球游戏中最大化函数值
这道题可以暴力枚举,但是因为数据范围太大,所以需要优化,这里使用了树上倍增的算法思想,直接看代码:文章来源:https://www.toymoban.com/news/detail-698911.html
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;
}
}
文章来源地址https://www.toymoban.com/news/detail-698911.html
到了这里,关于leetcode - 360周赛的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!