这次题目其实挺简单的，做了 50 多分钟就做完了一轮，但是三四题没全过，结果回去改第三题改了一小时没 AC。。。

1. s 重排最多包含几个 acbcca (100%)

字符串 s 只包含小写字母，可以任意重排，问重拍后 acbcca 最多出现几次？

示例：

  1. 重排后 acbcca 包含一个 acbcca
  2. 重排后 acbcc**a**cbcca 包含两个 acbcca
  3. 重排后 acbcc**a**cbcc**a**cbcca 包含三个 acbcca

规律：

acbcca 次数 1 2 3 … n
所需 a 个数 2 3 4 n+1
所需 b 个数 1 2 3 n
所需 c 个数 3 6 9 3n

因此，统计字符串 s 中包含的 a、b、c 个数，结果就是 min(a 个数 - 1，b 个数， c 个数 / 3)

2. 见面的最小路程差 (100%)

给定一个递增数组，代表 n 个点，要求找到一个点，使得从位置 1 到该点的距离 和 位置 n 到该点的距离之差最小

直接遍历每个点即可，分别计算每个点到两端的距离，再计算距离之差，并更新全局最小值

3. 和为 7 的倍数的最大值 (64%)

从 n 个数中选择任意个数，要求和为 7 的倍数，求和的最大值

解法：

  1. 递归回溯：超时，只能过 36%
  2. 动态规划：（笔试的时候边界和状态转移没考虑对，只过了 64%）
    1. 动态规划数组 dp：dp[i][j] 代表只从前 i 个数里进行挑选数字，和对 7 取余为 j 的最大值
    2. 状态转移方程：dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i - 1][preIdx] + nums[i - 1])
      1. dp[i - 1][j] 代表不取第 i 个数，即只从前 i - 1 数里挑选数字，和对 7 取余为 j 的最大值
      2. dp[i - 1][preIdx] + nums[i - 1] 代表取第 i 个数的最大值。取了第 i 个数（nums[i - 1]），要让和模 7 为 j，则从前 i - 1 个数中选择的数字只和模 7 应为 j - nums[i - 1] % 7，为了避免出现负数的情况，所以再 + 7 再模 7，即 preIdx = ((j - nums[i - 1]) % 7 + 7) % 7
    3. 初始化：
      1. 全部初始化为负无穷：但是如果初始化为 INT_MIN，则要将 dp 数组设置为 long long。否则会溢出，因为数组中存在负数，比如第一个数是 -2，-2 + INT_MIN 就溢出了
      2. dp[0][0] 设置为 0，因为不能取数时，和为 0，模 7 取余为 0 ```cpp

        include

        include

        include

        using namespace std;

int main() { int n; cin >> n; vector nums(n); for(int i = 0; i < n; ++i) cin >> nums[i];

  1. // vector<vector<int>> dp(n + 1, vector<int>(7, -0x3f3f3f3f));
  2. vector<vector<long long>> dp(n + 1, vector<long long>(7, INT_MIN));
  3. dp[0][0] = 0;
  4. for(int i = 1; i <= n; ++i)
  5. {
  6.     for(int j = 0; j < 7; ++j)
  7.     {
  8.         dp[i][j] = max(dp[i][j], dp[i - 1][j]);
  9.         int preIdx = ((j - nums[i - 1]) % 7 + 7) % 7;
  10.         dp[i][j] = max(dp[i][j], dp[i - 1][preIdx] + nums[i - 1]);
  11.     }
  12. }
  13. cout << dp[n][0] << endl;
  15. return 0;

}

  2. <a name="zfo94"></a>
  3. # 4. 奇数长区间中位数的和 (82%)
  4. 给定一个长为 n 的数组，求所有长度为奇数的区间的中位数之和。中位数是区间排序后最中间的数。
  6. 解法：
  8. 1. 暴力：会超时，过了 82%
  9. ```cpp
  10. #include <iostream>
  11. #include <vector>
  12. #include <algorithm>
  13. using namespace std;
  15. int main()
  16. {
  17.     int n;
  18.     cin >> n;
  19.     vector<int> nums(n);
  20.     for(int i = 0; i < n; ++i)
  21.         cin >> nums[i];
  23.     int result = 0;
  24.     for(int len = 1; len <= n; len = len + 2)    // 遍历所有奇数长的区间长度
  25.     {
  26.         for(int i = 0; i + len <= n; ++i)        // 遍历区间起点
  27.         {
  28.             // 将当前区间的数存储到 temp 数组，排序，取中间的数就是中位数
  29.             vector<int> temp(len);
  30.             for(int j = i; j < i + len; ++j)
  31.                 temp[j - i] = nums[j];
  32.             sort(temp.begin(), temp.end());
  33.             result += temp[len / 2];
  34.         }
  35.     }
  36.     cout << result << endl;
  38.     return 0;
  39. }
  1. 参考：leetcode 480. 滑动窗口中位数，leetcode 求的是固定窗口长度 k。滑动窗口，求每个窗口的中位数。而本题，只需要外面再套一层循环，遍历窗口长度 k 即可（k 为奇数）