A 距离原点最远的点
串中的 “_” 处要么都向左走要么都向右走
class Solution {
public:
int furthestDistanceFromOrigin(string moves) {
int t = 0;
for (auto x: moves)
if (x != 'R')
t--;
else
t++;
int res = abs(t);
t = 0;
for (auto x: moves)
if (x != 'L')
t++;
else
t--;
res = max(res, abs(t));
return res;
}
};
B 找出美丽数组的最小和
贪心:升序枚举正数,用集合维护当前数组中已有的数
class Solution {
public:
long long minimumPossibleSum(int n, int target) {
long long res = 0;
set<int> vis;
for (int i = 1; vis.size() != n; i++)
if (!vis.count(target - i)) {
res += i;
vis.insert(i);
}
return res;
}
};
C 使子序列的和等于目标的最少操作次数
贪心:首先只有 n u m s nums nums 的数组和小于 t a r g e t target target 才无解,若有解则从低位到高位枚举 t a r g e t target target 的二进制表示的各位,设当前位对应 2 i 2^i 2i ,且 t a r g e t target target 第 i i i 位为 1 1 1,有两种情况:
- n u m s nums nums中不超过 2 i 2^i 2i 的数的和 ≥ \ge ≥ 2 i 2^i 2i :则一定存在若干个不超过 2 i 2^i 2i 的数之和恰好为 2 i 2^i 2i
- n u m s nums nums中不超过 2 i 2^i 2i 的数的和 < < < 2 i 2^i 2i :需要把 n u m s nums nums 中一个最小的大于 2 i 2^i 2i 的数 2 j 2^j 2j 操作若干次来生成一个 2 i 2^i 2i
第二种情况会产生操作数,枚举过程种注意维护不超过 2 i 2^i 2i 的数的和。
class Solution {
public:
int minOperations(vector<int> &nums, int target) {
if (accumulate(nums.begin(), nums.end(), 0LL) < target)
return -1;
unordered_map<int, int> cnt;
for (auto x: nums)
cnt[x]++;
int res = 0;
long long ps = 0;//nums中不超过2^i的数之和
for (int i = 0, e = 1; i < 31; i++, e <<= 1) {//逐位枚举
ps += 1LL * cnt[e] * e;
if (!(target >> i & 1))
continue;
if (ps >= e) {
ps -= e;
continue;
}
int j = i + 1;
while (cnt[1 << j] <= 0)//找nums中大于2^i的最小的2^j
j++;
res += j - i;//记录操作数
cnt[1 << j]--;
for (int k = i + 1; k < j; k++)
cnt[1 << k] = 1;
ps += e;
}
return res;
}
};
D 在传球游戏中最大化函数值
倍增:设 g [ i ] [ j ] g[i][j] g[i][j] 为球最初在 i i i 手里,传 2 j 2^j 2j 次球的过程中每次接触球玩家的编号之和。设 v [ i ] [ j ] v[i][j] v[i][j] 表示球最初在 i i i 手里,传 2 j 2^j 2j 次球后球在 v [ i ] [ j ] v[i][j] v[i][j]手里。预处理求处理 g g g 和 v v v,之后枚举 i ∈ [ 0 , n ) i \in [0,n) i∈[0,n),然后枚举 k k k 二进制各位来求 f [ i ] f[i] f[i]。
class Solution {
public:
long long getMaxFunctionValue(vector<int> &receiver, long long k) {
int n = receiver.size();
long long g[n][35], v[n][35];
for (int j = 0; j < 35; j++)
for (int i = 0; i < n; i++)
if (j != 0) {
g[i][j] = g[i][j - 1] + g[v[i][j - 1]][j - 1] - v[i][j - 1];
v[i][j] = v[v[i][j - 1]][j - 1];
} else {
g[i][j] = i + receiver[i];
v[i][j] = receiver[i];
}
long long res = 0;
for (int i = 0; i < n; i++) {
long long cur = 0;
int last = i;
for (long long j = 0; j < 35; j++)
if (k >> j & 1) {//枚举k二进制各位
cur += g[last][j] - last;
last = v[last][j];
}
res = max(res, i + cur);
}
return res;
}
};