lc375
区间dp
枚举区间长度和分割点，计算在 1~n 内猜数字时保证能赢的最小花费
方向: 长度大的 需要从长度小的转移过来
//构造avl树
class Solution {
public:
int dp[207][207];
int getMoneyAmount(int n) {
for (int len = 2; len <= n; len++) {//长度
for (int i = 1; i + len - 1 <= n; i++) {//左
int j = i + len - 1;//右
dp[i][j] = 1e9 + 7;
for (int k = i; k <= j; k++) {//中间
dp[i][j] = min(dp[i][j], k + max(dp[i][k - 1], dp[k + 1][j]));
}
}
}
return dp[1][n];
}
};
lc2760
3 ou begin; ou ji; ≤thre
左指针找“偶数且≤阈值”的起始位，向右扩展子数组直到不满足“奇偶交替+≤阈值”，记录最长长度，最后返回结果
左找 右扩展 update
class Solution {
public:
int longestAlternatingSubarray(vector<int>& nums, int threshold)
{
int n = nums.size();
int ret = 0;
int l = 0;
while (l < n) {
if (nums[l] % 2 == 0 && nums[l] <= threshold) {
int r = l;
// 扩展
while (r + 1 < n
&& nums[r + 1] <= threshold
&& nums[r] % 2 != nums[r + 1] % 2)
r++;
ret = max(ret, r - l + 1);
l = r + 1;// 跳过当前子数组
} else
l++;// 不满足起始条件，移动左指针
}
return ret;
}
};
lc2489
公式化简之后就是两数之和
class Solution {
public:
long long fixedRatio(string s, int num1, int num2) {
long long ans = 0, a = 0, b = 0;
unordered_map<long long, long long> mp;
mp[0]++;
for(auto c : s) {
if(c == '0') a++;
else b++;
ans += mp[a * num2 - b * num1]++;
}
return ans;
}
};
