8015. Furthest Point From Origin
给你一个长度为 n 的字符串 moves ，该字符串仅由字符 'L'、'R' 和 '_' 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。
你的初始位置就在原点（0），第 i 次移动过程中，你可以根据对应字符选择移动方向：
- 如果 moves[i] = 'L' 或 moves[i] = '_' ，可以选择向左移动一个单位距离
- 如果 moves[i] = 'R' 或 moves[i] = '_' ，可以选择向右移动一个单位距离
移动 n 次之后，请你找出可以到达的距离原点 最远 的点，并返回 从原点到这一点的距离 。
测试样例：
输入：moves = "L_RL__R"
输出：3
解释：
可以到达的距离原点 0 最远的点是 -3 ，移动的序列为 "LLRLLLR" 。
解答：暴力认为所有_是L或者R，分开计算一下最远距离。
class Solution {
public int furthestDistanceFromOrigin(String moves) {
int l = 0, r = 0, blank = 0;
int res = 0;
for (int i = 0; i < moves.length(); ++i) {
if (moves.charAt(i) == 'L') {
++l;
} else if (moves.charAt(i) == 'R') {
++r;
} else {
++blank;
}
}
res = Math.max(res, l + blank - r);
res = Math.max(res, r + blank - l);
return res;
}
}8022. Find the Minimum Possible Sum of a Beautiful Array
给你两个正整数：n 和 target 。
如果数组 nums 满足下述条件，则称其为 美丽数组 。
- nums.length == n.
- nums 由两两互不相同的正整数组成。
- 在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。
返回符合条件的美丽数组所可能具备的 最小 和。
测试样例：
输入：n = 2, target = 3
输出：4
解释：
nums = [1,3] 是美丽数组。
解答：这道题目需要用到贪婪算法。一个简单的思路，假设我们期望加入1，那么 k - 1 就不再符合要求。但是1和k - 1之间，我们肯定选择1，因为很直观的1更小。因为提示给的范围很小1 <= n, k <= 50。暴力计数，只要n能满足。
class Solution {
public long minimumPossibleSum(int n, int target) {
if (n == 1) {
return 1;
}
int s = 1;
long sum = 0;
Set<Integer> remove = new HashSet<>();
while (n > 0) {
if (!remove.contains(s)) {
remove.add(target - s);
sum += s;
--n;
}
++s;
}
return sum;
}
}8021. Minimum Operations to Form Subsequence With Target Sum
给你一个下标从 0 开始的数组 nums ，它包含 非负 整数，且全部为 2 的幂，同时给你一个整数 target 。
一次操作中，你必须对数组做以下修改：
- 选择数组中一个元素 nums[i] ，满足 nums[i] > 1 。
- 将 nums[i] 从数组中删除。
- 在 nums 的 末尾 添加 两个 数，值都为 nums[i] / 2 。
你的目标是让 nums 的一个 子序列 的元素和等于 target ，请你返回达成这一目标的 最少操作次数 。如果无法得到这样的子序列，请你返回 -1 。
数组中一个 子序列 是通过删除原数组中一些元素，并且不改变剩余元素顺序得到的剩余数组。
测试样例
输入：nums = [1,2,8], target = 7
输出：1
解释：
第一次操作中，我们选择元素 nums[2] 。数组变为 nums = [1,2,4,4] 。这时候，nums 包含子序列 [1,2,4] ，和为 7 。无法通过更少的操作得到和为 7 的子序列。
解答：这道题目也是贪婪算法，先统计每一个二进制的情况。接着从第0位开始遍历。如果当前数字的二进制位为1，则二进制位统计减1.如果二进制统计是负数，则从高位借数。否则查询当前二进制位能不能给高位进数。
class Solution {
public int minOperations(List<Integer> nums, int target) {
int[] count = new int[32];
int result = 0;
for (int num : nums) {
for (int i = 0; i <= 30; i++) {
count[i] += num >> i & 1;
}
}
for (int i = 0; i <= 30; i++) {
if ((target >> i & 1) == 1) {
count[i]--;
for (int j = i; count[j] < 0; j++) {
if (j == 31) {
return -1;
}
count[j] += 2;
count[j + 1]--;
result++;
}
}
count[i + 1] += count[i] / 2;
}
return result;
}
}8027. Maximize Value of Function in a Ball Passing Game
给你一个长度为 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 可能含有重复元素。
测试样例
输入：eceiver = [2,0,1], k = 4
输出：6
解释：
从表中可知，f(2) 等于 6 。
解答：这道题目，主要考察细心。。。遍历数字的时候，寻找循环数组。找到循环数组之后，就能通过循环次数和循序差值，给每个循环数组中的数计算f(x)。由于receiver可能包含重复元素，所以还是要住寻找循环数组中的数，可以进一步覆盖的数字。
class Solution {
private List<Integer>[] input;
private long loopSum, k;
private int loopSize, duplicateNodeOffset;
private long[] scores;
private boolean[] isVisit;
public long getMaxFunctionValue(List<Integer> receiver, long k) {
this.k = k;
int[] pass = new int[receiver.size()];
input = new List[pass.length];
for (int i = 0; i < input.length; ++i) {
input[i] = new ArrayList<>();
}
int offset = 0;
for (int n : receiver) {
pass[offset] = n;
input[n].add(offset);
++offset;
}
long res = 0;
isVisit = new boolean[pass.length];
scores = new long[pass.length];
for (int i = 0; i < pass.length; ++i) {
if (!isVisit[i]) {
int node = i;
long curSum = 0;
List<Integer> path = new ArrayList<>();
List<Long> score = new ArrayList<>();
while (!isVisit[node]) {
curSum += node;
isVisit[node] = true;
path.add(node);
score.add(curSum);
scores[node] = curSum;
node = pass[node];
}
int duplicateNode = node;
duplicateNodeOffset = 0;
for (int p = 0; p < path.size(); ++p) {
if (path.get(p) == duplicateNode) {
duplicateNodeOffset = p;
}
}
loopSize = path.size() - duplicateNodeOffset;
loopSum = score.get(score.size() - 1) - (duplicateNodeOffset == 0 ? 0 : score.get(duplicateNodeOffset - 1));
for (int j = 0; j < path.size(); ++j) {
int calNode = path.get(j);
res = Math.max(res, beforeDFS(path, score, scores[calNode], calNode, j == 0 ? -1 : path.get(j - 1), j, new HashMap<>()));
}
}
}
return res;
}
private long beforeDFS(List<Integer> path, List<Long> score, long lastScore, int curNode, int beforeNode, int offset, HashMap<Integer, Long> map) {
map.put(offset, lastScore);
scores[curNode] = lastScore;
long res = getScore(path, score, curNode, offset, map);
for (int n : input[curNode]) {
if (!isVisit[n]) {
isVisit[n] = true;
res = Math.max(res, beforeDFS(path, score, lastScore - curNode, n, -1, offset - 1, map));
}
}
return res;
}
private long getScore(List<Integer> path, List<Long> score, int calNode, int curOffset, HashMap<Integer, Long> scoreMark) {
long partialSum;
if (curOffset + k < path.size()) {
int tmp = (int) (curOffset + k);
partialSum = (scoreMark.containsKey(tmp) ? scoreMark.get(tmp) : score.get(tmp)) - (scores[calNode] - calNode);
} else {
partialSum = score.get(score.size() - 1) - (scores[calNode] - calNode);
long remainSpace = k - (path.size() - curOffset - 1);
partialSum += (remainSpace / loopSize) * loopSum;
remainSpace %= loopSize;
if (remainSpace != 0) {
int tmp = (int) (duplicateNodeOffset + remainSpace - 1);
partialSum += score.get(tmp) - (duplicateNodeOffset == 0 ? 0 : score.get(duplicateNodeOffset - 1));
}
}
return partialSum;
}
}