刷题记录

因为考试周在复习的原因，假期开始前没有刷太多的题目，加上7.5号生病休息，，
报告记录7.6号到7.7号的刷题记录：

Problem - 1708C - Codeforces
Codeforces Round 808 (Div. 2) - C. Doremy's IQ
标签：二分，贪心，1600
思考：
1. 考虑二分查找比赛的场数，因为可以比赛的场数和智力值是成单调性的
2. 考虑贪心编写二分的check条件，我们把降低智力的比赛称为“坏比赛”，把无影响的比赛称为“好比赛”，显然尽量地把坏比赛安排在后面参加是最优的，如果查找是否可以进行x场比赛，那么我们就可以跳过n-x场比赛，那么我们就要尽量在前面跳过n-x场比赛，即记录r=n-x，逃一次比赛就r--，如果还有r就可以继续逃

2181. 合并零之间的节点 - 力扣（LeetCode）
标签：链表，leetcode中等
思考：
1. 开左右l，r指针记录0的位置是很方便的
2. 开一个tail指针，用尾插法是很方便的

100182. 与敌人战斗后的最大分数 - 力扣（LeetCode）
"你可以通过以下操作 之一 任意次（也可以 0 次）来得分"

  • 选择一个 未标记 且满足 currentEnergy >= enemyEnergies[i] 的敌人 i 。在这个操作中：
    • 你会获得 1 分。
    • 你的能量值减少 enemyEnergies[i] ，也就是说 currentEnergy = currentEnergy - enemyEnergies[i] 。
  • 如果你目前 至少 有 1 分，你可以选择一个 未标记 的敌人 i 。在这个操作中：
    • 你的能量值增加 enemyEnergies[i] ，也就是说 currentEnergy = currentEnergy + enemyEnergies[i] 。
    • 敌人 i 被标记 。
      依据题意，容易得出最大的分数可以通过以下贪心的策略得出：
      设能力值为x，敌人i能力值为p，则：
  1. 每次都选择 abs(x-p) 最小的敌人，使得亏损最小
  2. 当能量不足时候，每次都选择未被标记的p最大的敌人，使得收益最大
    具体实现可以通过对原数组排序一次，记录两个指针即可

100351. 交替组 II - 力扣（LeetCode）
思考：考虑使用双指针，如果新进来的元素打破了交替性，那么l=r=r+1，
如果满足交替性，那么r++，如果同时满足abs(r-l)==k-1，那么l++ (移动区间)，ans++
注意到数组是一个环，r 需要对size()取模

198. 打家劫舍 - 力扣（LeetCode）
思考：一维动态规划
如果偷了x家，那么x-1的家就偷不了，总价值是x-2的价值加上x家
如果不偷x家，那么价值维持x-1家
状态转移方程：dp[i] = max(dp[i-1], dp[i-2]+nums[i])

2915. 和为目标值的最长子序列的长度 - 力扣（LeetCode）
思考：01背包问题
朴素dp写法，dp[i][j] 表示前 i 个数合为 j 的序列的最长长度

class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        using namespace std;
        const int mod = 1001;
        int dp[mod][mod]; //dp[i][j]表示在前i个数中和为j的最长序列长度
        int n = nums.size();

        for (int i = 0; i < n; i++)
            for (int j = 0; j <= target; j++)
                dp[i][j] = -1; //-1表示无法得到子序列

        dp[0][0] = 0; //0个数的和为0，长度为0
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 0; //前i个数中，和为0的最长序列为0
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i-1][j]; // 不选当前元素
                if (j-nums[i-1] >= 0 && dp[i-1][j-nums[i-1]] != -1) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-nums[i-1]] + 1); // 选元素
                }
            }
        }
        return dp[n][target];
    }
};