网站流量数据分析怎么做,宿迁哪家做网站推广,苏州最新新闻事件今天,怎么制作网站ping工具Leetcode 第 126 场双周赛题解 Leetcode 第 126 场双周赛题解题目1#xff1a;3079. 求出加密整数的和思路代码复杂度分析 题目2#xff1a;3080. 执行操作标记数组中的元素思路代码复杂度分析 题目3#xff1a;3081. 替换字符串中的问号使分数最小思路代码复杂度分析 题目4… Leetcode 第 126 场双周赛题解 Leetcode 第 126 场双周赛题解题目13079. 求出加密整数的和思路代码复杂度分析 题目23080. 执行操作标记数组中的元素思路代码复杂度分析 题目33081. 替换字符串中的问号使分数最小思路代码复杂度分析 题目43082. 求出所有子序列的能量和思路代码复杂度分析 Leetcode 第 126 场双周赛题解
题目13079. 求出加密整数的和
思路
代码
/** lc appleetcode.cn id3079 langcpp** [3079] 求出加密整数的和*/// lc codestart
class Solution
{
public:int sumOfEncryptedInt(vectorint nums){int sum 0;for (int num : nums)sum encrypt(num);return sum;}// 加密函数int encrypt(int x){string s to_string(x);int maxDigit 0;for (char c : s)maxDigit max(maxDigit, c - 0);int res 0;for (int i 0; i s.length(); i){res * 10;res maxDigit;}return res;}
};
// lc codeend复杂度分析
时间复杂度O(n*m)其中 n 是数组 nums 的长度m 是每个元素的位数。
空间复杂度O(1)。
题目23080. 执行操作标记数组中的元素
思路
由于要按照元素从小到大标记但又不能直接对数组排序因为有对特定 index 的标记我们可以创建一个 ids 数组其中 ids[i]i然后对该数组按照 nums[ids[i]] 从小到大排序。注意要使用稳定排序因为相同元素值的下标需要按照下标从小到大排。也可以使用不稳定排序如快速排序但要对于相同元素值按照下标从小到大排序。
设 nums 的元素和为 s。对于每个询问我们先将 s 减少 nums[index]然后将 nums[index] 置为 0就相当于标记了这个数因为题目保证数组元素都是正数。然后依照 ids 找 k 个最小的没有被标记的数将其标记标记的同时维护 s。
代码
/** lc appleetcode.cn id3080 langcpp** [3080] 执行操作标记数组中的元素*/// lc codestart
class Solution
{
public:vectorlong longunmarkedSumArray(vectorint nums, vectorvectorint queries){int n nums.size();long long s accumulate(nums.begin(), nums.end(), 0LL);vectorint ids(n);iota(ids.begin(), ids.end(), 0);// ranges::stable_sort(ids, [](int i, int j) { return nums[i] nums[j]; });sort(ids.begin(), ids.end(), [](const int i, const int j){ if (nums[i] ! nums[j]) return nums[i] nums[j];else return i j; });vectorlong long ans;int idx 0;for (vectorint query : queries){int index query[0], k query[1];s - nums[index];nums[index] 0; // 标记for (; idx n k; idx){index ids[idx];if (nums[index] 0) // 未被标记{s - nums[index];nums[index] 0; // 标记k--;}}ans.push_back(s);}return ans;}
};
// lc codeend复杂度分析
时间复杂度O(nlogn)其中 n 是数组 nums 的长度。
空间复杂度O(n)其中 n 是数组 nums 的长度。
题目33081. 替换字符串中的问号使分数最小
思路 算法
统计字母出现次数 freq和字母组成 pair 加到一个最小堆中。设问号出现了 cnt 次。循环 cnt 次每次取出堆顶字母它是目前出现次数最小的加入一个字符串 tmp 中然后把该字母的出现次数加一重新入堆。把 tmp 从小到大排序因为题目要求字典序最小。遍历 s 中的问号按顺序填入 tmp 中的字母。
代码
/** lc appleetcode.cn id3081 langcpp** [3081] 替换字符串中的问号使分数最小*/// lc codestart// 贪心 优先队列class Solution
{
public:string minimizeStringValue(string s){vectorint freq(26, 0);for (char c : s)if (c ! ?)freq[c - a];priority_queuepairint, char, vectorpairint, char, greater pq;for (int i 0; i 26; i)pq.emplace(freq[i], i a);int cnt count(s.begin(), s.end(), ?);string tmp;for (int i 0; i cnt; i){auto [f, ch] pq.top();pq.pop();tmp.push_back(ch);pq.emplace(f 1, ch);}// 排序因为要求字典序最小sort(tmp.begin(), tmp.end());for (int i 0, j 0; i s.length(); i)if (s[i] ?)s[i] tmp[j];return s;}
};
// lc codeend复杂度分析 题目43082. 求出所有子序列的能量和
思路 二维 01 背包 代码
/** lc appleetcode.cn id3082 langcpp** [3082] 求出所有子序列的能量和*/// lc codestart
class Solution
{
private:const int mod 1e9 7;public:int sumOfPower(vectorint nums, int k){int n nums.size();// dp[i][j][c]: 前 i 个物品所选物品体积和是 j选了 c 个物品的方案数int dp[n 1][k 1][n 1];// 初始化memset(dp, 0, sizeof(dp));for (int i 0; i n; i)dp[i][0][0] 1;// 状态转移for (int i 0; i n; i){for (int j k; j 0; j--){for (int c n; c 0; c--){// 二维0/1背包dp[i 1][j][c] dp[i][j][c]; // 不选if (j nums[i]){// 选dp[i 1][j][c] (dp[i 1][j][c] dp[i][j - nums[i]][c - 1]) % mod;}}}}// 贡献法int ans 0;long p 1;for (int c n; c 0; c--){ans (ans dp[n][k][c] * p % mod) % mod;p (p * 2) % mod;}return ans;}
};
// lc codeend复杂度分析
时间复杂度O(n2k)其中 n 是数组 nums 的长度。
空间复杂度O(n2k)其中 n 是数组 nums 的长度。
