深圳网站建设 设计首选公司,外贸机械加工网,宝安网站设计哪家好,首服网页游戏开服表子串的最大出现次数 给你一个字符串 s #xff0c;请你返回满足以下条件且出现次数最大的 任意 子串的出现次数#xff1a; 子串中不同字母的数目必须小于等于 maxLetters 。 子串的长度必须大于等于 minSize 且小于等于 maxSize 。
首先能想到的是从MinSize开始遍历查找请你返回满足以下条件且出现次数最大的 任意 子串的出现次数 子串中不同字母的数目必须小于等于 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_mapstring, int occ;int ans 0;for (int i 0; i n - minSize 1; i) {string cur s.substr(i, minSize);unordered_setchar exist(cur.begin(), cur.end());if (exist.size() maxLetters) {string cur s.substr(i, minSize);occ[cur];ans max(ans, occ[cur]);}}return ans;}
};
你能从盒子里获得的最大糖果数 给你 n 个盒子每个盒子的格式为 [status, candies, keys, containedBoxes] ,请你按照上述规则返回可以获得糖果的 最大数目 。
广度优先遍历对于暂时无法打开的存在队列中等待后续机会。
class Solution {
public:int maxCandies(vectorint status, vectorint candies, vectorvectorint keys, vectorvectorint containedBoxes, vectorint initialBoxes) {int n status.size();vectorbool can_open(n), has_box(n), used(n);for (int i 0; i n; i) {can_open[i] (status[i] 1);}queueint 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;}
};
将每个元素替换为右侧最大元素 给你一个数组 arr 请你将每个元素用它右边最大的元素替换如果是最后一个元素用 -1 替换。完成所有替换操作后请你返回这个数组。
逆向遍历一遍即可。
class Solution {
public:vectorint replaceElements(vectorint arr) {int n arr.size();vectorint 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;}
};
转变数组后最接近目标值的数组和 给你一个整数数组 arr 和一个目标值 target 请你返回一个整数 value 使得将数组中所有大于 value 的值变成 value 后数组的和最接近 target 最接近表示两者之差的绝对值最小。如果有多种使得和最接近 target 的方案请你返回这些整数中的最小值。请注意答案不一定是 arr 中的数字。
因为value的改变导致数组和单调变化所以一定是在不超过target最接近的value和value1中选一个。采用二分法确定value上界为max in arr然后比较和即可。
class Solution {
public:int check(const vectorint arr, int x) {int ret 0;for (const int num: arr) {ret (num x ? x : num);}return ret;}int findBestValue(vectorint arr, int target) {sort(arr.begin(), arr.end());int n arr.size();vectorint 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;}
};
最大得分的路径数目 给你一个正方形字符数组 board 你从数组最右下方的字符 ‘S’ 出发。 你的目标是到达数组最左上角的字符 ‘E’ 数组剩余的部分为数字字符 1, 2, …, 9 或者障碍 ‘X’。在每一步移动中你可以向上、向左或者左上方移动可以移动的前提是到达的格子没有障碍。 一条路径的 「得分」 定义为路径上所有数字的和。 请你返回一个列表包含两个整数第一个整数是 「得分」 的最大值第二个整数是得到最大得分的方案数请把结果对 10^9 7 取余。 如果没有任何路径可以到达终点请返回 [0, 0] 。
因为只能向上、左、左上所以动态规划解题是很容易想到的。
using PII pairint, int;class Solution {
private:static constexpr int mod (int)1e9 7;public:void update(vectorvectorPII 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;}}}vectorint pathsWithMaxScore(vectorstring board) {int n board.size();vectorvectorPII dp(n, vectorPII(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 ? vectorint{0, 0} : vectorint{dp[0][0].first, dp[0][0].second};}
};
层数最深叶子节点的和 给你一棵二叉树的根节点 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::listTreeNode* NodeList;if (root)NodeList.push_back(root);while (NodeList.size()){size NodeList.size();sum 0;for (int i 0; i size; i){std::listTreeNode*::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;}
};和为零的 N 个不同整数 给你一个整数 n请你返回 任意 一个由 n 个 各不相同 的整数组成的数组并且这 n 个数相加和为 0 。
很无聊的一道题直接镜像对称或者从0累加最后来个-sum都可以。
class Solution {
public:vectorint sumZero(int n) {vectorint 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;}
};
