24-周赛360
过了前三题，第四题没有想出来，那也上分啦
第四题倍增倍增，思路不难，就是很少见
距离原点最远的点【LC2833】
给你一个长度为 n 的字符串 moves ，该字符串仅由字符 'L'、'R' 和 '_' 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。
你的初始位置就在原点（0），第 i 次移动过程中，你可以根据对应字符选择移动方向：
如果 moves[i] = 'L' 或 moves[i] = '_' ，可以选择向左移动一个单位距离
如果 moves[i] = 'R' 或 moves[i] = '_' ，可以选择向右移动一个单位距离
移动 n 次之后，请你找出可以到达的距离原点 最远 的点，并返回 从原点到这一点的距离 。
思路
- 计算字符串中
'_'的个数count_和score=countR−countL
贪心：为了获得最远距离'_'的方向应该与score保持一致
- 如果
score大于0，那么最远距离为score+count_ - 如果
score小于0，那么最远距离为score-count_
实现
class Solution { public int furthestDistanceFromOrigin(String moves) { int res = 0, cur = 0; int count = 0; for (char c : moves.toCharArray()){ if (c == '_'){ count++; }else if (c == 'L'){ cur -= 1; }else{ cur += 1; } } if (cur > 0){ res = Math.max(res, cur + count); }else{ res = Math.max(res, Math.abs(cur - count)); } return res; } }
复杂度
时间复杂度：O ( n )
空间复杂度：O ( 1 )
找出美丽数组的最小和【LC2834】
给你两个正整数：n 和 target 。
如果数组 nums 满足下述条件，则称其为 美丽数组 。
nums.length == n.
nums 由两两互不相同的正整数组成。
在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。
返回符合条件的美丽数组所可能具备的 最小 和。
思路：贪心
从小到大选择n个数，将已选择的数记录在哈希表中，假设当前数为x，并且哈希表中不存在
target−x，那么可以选择数x；否则，跳过x
实现
class Solution { public long minimumPossibleSum(int n, int target) { long res = 0L; Set<Integer> set = new HashSet<>(); int num = 1, size = 0; while (size < n){ if (!set.contains(target - num)){ res += num; set.add(num); size++; } num++; } return res; } }
复杂度
时间复杂度：O ( n )
空间复杂度：O ( n )
使子序列的和等于目标的最少操作次数【LC2835】
给你一个下标从 0 开始的数组 nums ，它包含 非负 整数，且全部为 2 的幂，同时给你一个整数 target 。
一次操作中，你必须对数组做以下修改：
选择数组中一个元素 nums[i] ，满足 nums[i] > 1 。
将 nums[i] 从数组中删除。
在 nums 的 末尾 添加 两个 数，值都为 nums[i] / 2 。
你的目标是让 nums 的一个 子序列 的元素和等于 target ，请你返回达成这一目标的 最少操作次数 。如果无法得到这样的子序列，请你返回 -1 。
数组中一个 子序列 是通过删除原数组中一些元素，并且不改变剩余元素顺序得到的剩余数组。
思路：贪心+位运算
由于每个数都是以2的幂存在的，而任何数都可以表示为二进制数，如果nums中所有元素之和小于target，那么我们不能使用nums中的子序列表示target
首先先进行预处理，使用数组count记录2^i出现的次数
然后将target进行二进制分解，如果第i位为1，要满足2^i ，可以有三种方法
count[i]大于0，那么nums中存在2^i
nums中存在某些2的幂，其和为2^i
如果j > i 并且c o u n t [ j ] 大于0，那么可以将2^j分解j − i次，得到2^i
为了获得 最少操作次数 ，应优先选择方法1和方法2，方法1和方法2都不能满足时，再选择最小的j，进行分解
具体实现时，从低位开始遍历，
首先先判断第i位是否需要满足以及能否满足
能的话次数-1
不能的话，如果之前每位都可以满足才，记录下标
然后判断低位是否有不满足的下标，如果有并且count[i]>0，那么需要分解i−need次，再将c o u n t [ i ] 减一
最后由于2*2^i=2^{i+1}，因此将count[i]/2累加至count[i+1]
实现
排序计算count
class Solution { public int minOperations(List<Integer> nums, int target) { Collections.sort(nums, (o1, o2) -> o1 - o2); int res = 0, size = nums.size(); int[] count = new int[32]; long sum = 0L; for (int i = 0; i < size; i++){ count[Integer.numberOfTrailingZeros(nums.get(i))]++; sum += nums.get(i); } if (target > sum) return -1; int need = 32; for (int i = 0; i < 32; i++){ if (((target >> i) & 1) == 1){ if (count[i] == 0){ need = Math.min(need, i); }else{ count[i]--; } } if (need != 32 && count[i] > 0){ count[i]--; res += (i - need); need = 32; } if (i + 1 < 32){ count[i + 1] += count[i] / 2; } } return res; } }
复杂度
时间复杂度：O ( n + C )
空间复杂度：O ( log n + C )
实现
class Solution { public int minOperations(List<Integer> nums, int target) { long s = 0; var cnt = new long[31]; for (int x : nums) { s += x; cnt[Integer.numberOfTrailingZeros(x)]++; } if (s < target) return -1; int ans = 0, i = 0; s = 0; while ((1L << i) <= target) { s += cnt[i] << i; int mask = (int) ((1L << ++i) - 1); if (s >= (target & mask)) continue; ans++; // 一定要找更大的数操作 for (; cnt[i] == 0; i++) ans++; // 还没找到，继续找更大的数 } return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/solutions/2413344/tan-xin-by-endlesscheng-immn/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
在传球游戏中最大化函数值【LC2836】
给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。
总共有 n 名玩家，玩家 编号 互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。
你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传 恰好 k 次。
如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之 和 ，如果有玩家多次触球，则 累加多次 。换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver(k)[x] 。
你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。
请你返回函数的 最大值 。
注意：receiver 可能含有重复元素。
思路：倍增算法
实现
class Solution { public long getMaxFunctionValue(List<Integer> receiver, long k) { int n = receiver.size(); int m = 64 - Long.numberOfLeadingZeros(k);// k的二进制长度 int[][] pa = new int[m][n]; long[][] sum = new long[m][n]; for (int i = 0; i < n; i++){ pa[0][i] = receiver.get(i); sum[0][i] = receiver.get(i); } for (int i = 1; i < m; i++){ for (int x = 0; x < n; x++){ int p = pa[i - 1][x];// x节点的第2^(i-1)个祖先节点 pa[i][x] = pa[i - 1][p]; sum[i][x] = sum[i - 1][x] + sum[i - 1][p]; } } long res = 0; for (int i = 0; i < n; i++){ long s = i; int x = i; for (int j = 0; j < m; j++){ if (((k >> j) & 1) == 1){ s += sum[j][x]; x = pa[j][x]; } } res = Math.max(res, s); } return res; } }
复杂度
时间复杂度：O ( n log k )
空间复杂度：O ( n log k )
