leetcode解题思路分析（一百四十九）1297 - 1304 题

1297. 子串的最大出现次数
      给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：
      子串中不同字母的数目必须小于等于 maxLetters 。
      子串的长度必须大于等于 minSize 且小于等于 maxSize 。

首先能想到的是从MinSize开始遍历查找，然后利用set来保证满足maxLetters，用map来存储string出现的数量，最后取出现数量的最大值。然后因为子串的子串出现数量一定大于等于子串的出现数量，所以其实直接看minSize即可，少一圈循环。

class Solution {
public:int maxFreq(string s, int maxLetters, int minSize, int maxSize) {int n = s.size();unordered_map<string, int> occ;int ans = 0;for (int i = 0; i < n - minSize + 1; ++i) {string cur = s.substr(i, minSize);unordered_set<char> exist(cur.begin(), cur.end());if (exist.size() <= maxLetters) {string cur = s.substr(i, minSize);++occ[cur];ans = max(ans, occ[cur]);}}return ans;}
};

1298. 你能从盒子里获得的最大糖果数
      给你 n 个盒子，每个盒子的格式为 [status, candies, keys, containedBoxes] ,请你按照上述规则，返回可以获得糖果的 最大数目 。

广度优先遍历，对于暂时无法打开的存在队列中等待后续机会。

class Solution {
public:int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {int n = status.size();vector<bool> can_open(n), has_box(n), used(n);for (int i = 0; i < n; ++i) {can_open[i] = (status[i] == 1);}queue<int> q;int ans = 0;for (int box: initialBoxes) {has_box[box] = true;if (can_open[box]) {q.push(box);used[box] = true;ans += candies[box];}}while (!q.empty()) {int big_box = q.front();q.pop();for (int key: keys[big_box]) {can_open[key] = true;if (!used[key] && has_box[key]) {q.push(key);used[key] = true;ans += candies[key];}}for (int box: containedBoxes[big_box]) {has_box[box] = true;if (!used[box] && can_open[box]) {q.push(box);used[box] = true;ans += candies[box];}}}return ans;}
};

1299. 将每个元素替换为右侧最大元素
      给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。完成所有替换操作后，请你返回这个数组。

逆向遍历一遍即可。

class Solution {
public:vector<int> replaceElements(vector<int>& arr) {int n = arr.size();vector<int> ans(n);ans[n - 1] = -1;for (int i = n - 2; i >= 0; --i) {ans[i] = max(ans[i + 1], arr[i + 1]);}return ans;}
};

1300. 转变数组后最接近目标值的数组和
      给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。请注意，答案不一定是 arr 中的数字。

因为value的改变导致数组和单调变化，所以一定是在不超过target最接近的value和value+1中选一个。采用二分法确定value（上界为max in arr），然后比较和即可。

class Solution {
public:int check(const vector<int>& arr, int x) {int ret = 0;for (const int& num: arr) {ret += (num >= x ? x : num);}return ret;}int findBestValue(vector<int>& arr, int target) {sort(arr.begin(), arr.end());int n = arr.size();vector<int> prefix(n + 1);for (int i = 1; i <= n; ++i) {prefix[i] = prefix[i - 1] + arr[i - 1];}int l = 0, r = *max_element(arr.begin(), arr.end()), ans = -1;while (l <= r) {int mid = (l + r) / 2;auto iter = lower_bound(arr.begin(), arr.end(), mid);int cur = prefix[iter - arr.begin()] + (arr.end() - iter) * mid;if (cur <= target) {ans = mid;l = mid + 1;}else {r = mid - 1;}}int choose_small = check(arr, ans);int choose_big = check(arr, ans + 1);return abs(choose_small - target) <= abs(choose_big - target) ? ans : ans + 1;}
};

1301. 最大得分的路径数目
      给你一个正方形字符数组 board ，你从数组最右下方的字符 ‘S’ 出发。
      你的目标是到达数组最左上角的字符 ‘E’ ，数组剩余的部分为数字字符 1, 2, …, 9 或者障碍 ‘X’。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。
      一条路径的 「得分」 定义为：路径上所有数字的和。
      请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。
      如果没有任何路径可以到达终点，请返回 [0, 0] 。

因为只能向上、左、左上，所以动态规划解题是很容易想到的。

using PII = pair<int, int>;class Solution {
private:static constexpr int mod = (int)1e9 + 7;public:void update(vector<vector<PII>>& dp, int n, int x, int y, int u, int v) {if (u >= n || v >= n || dp[u][v].first == -1) {return;}if (dp[u][v].first > dp[x][y].first) {dp[x][y] = dp[u][v];}else if (dp[u][v].first == dp[x][y].first) {dp[x][y].second += dp[u][v].second;if (dp[x][y].second >= mod) {dp[x][y].second -= mod;}}}vector<int> pathsWithMaxScore(vector<string>& board) {int n = board.size();vector<vector<PII>> dp(n, vector<PII>(n, {-1, 0}));dp[n - 1][n - 1] = {0, 1};for (int i = n - 1; i >= 0; --i) {for (int j = n - 1; j >= 0; --j) {if (!(i == n - 1 && j == n - 1) && board[i][j] != 'X') {update(dp, n, i, j, i + 1, j);update(dp, n, i, j, i, j + 1);update(dp, n, i, j, i + 1, j + 1);if (dp[i][j].first != -1) {dp[i][j].first += (board[i][j] == 'E' ? 0 : board[i][j] - '0');}}}}return dp[0][0].first == -1 ? vector<int>{0, 0} : vector<int>{dp[0][0].first, dp[0][0].second};}
};

1302. 层数最深叶子节点的和
      给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。

采用深度遍历或者广度遍历均可。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int deepestLeavesSum(TreeNode* root) {int size = 0;int sum  = 0;std::list<TreeNode*> NodeList;if (root)NodeList.push_back(root);while (NodeList.size()){size = NodeList.size();sum  = 0;for (int i = 0; i < size; ++i){std::list<TreeNode*>::iterator iter = NodeList.begin();if ((*iter)->left)NodeList.push_back((*iter)->left);if ((*iter)->right)NodeList.push_back((*iter)->right);sum += (*iter)->val;NodeList.pop_front();}}return sum;}
};

1304. 和为零的 N 个不同整数
      给你一个整数 n，请你返回 任意 一个由 n 个 各不相同 的整数组成的数组，并且这 n 个数相加和为 0 。

很无聊的一道题，直接镜像对称或者从0累加最后来个-sum都可以。

class Solution {
public:vector<int> sumZero(int n) {vector<int> ret;bool isOdd = n % 2 == 0 ? false : true;int begin = 0 - n / 2;int end   = n / 2;for (int i = begin; i <= end; ++i){if (i == 0 && !isOdd)continue;ret.push_back(i);}return ret;}
};