手机网站上线左右滑动,wordpress点评插件,电商网站建设网络公司,网络推广中心Leetcode 第 361 场周赛题解 Leetcode 第 361 场周赛题解题目1#xff1a;2843. 统计对称整数的数目思路代码复杂度分析 题目2#xff1a;生成特殊数字的最少操作思路代码复杂度分析 题目3#xff1a;统计趣味子数组的数目思路代码复杂度分析 题目4#xff1a;边权重均等查… Leetcode 第 361 场周赛题解 Leetcode 第 361 场周赛题解题目12843. 统计对称整数的数目思路代码复杂度分析 题目2生成特殊数字的最少操作思路代码复杂度分析 题目3统计趣味子数组的数目思路代码复杂度分析 题目4边权重均等查询 Leetcode 第 361 场周赛题解
题目12843. 统计对称整数的数目
思路
枚举。
代码
class Solution
{
public:int countSymmetricIntegers(int low, int high){int count 0;for (int num low; num high; num)if (check(num))count;return count;}// 辅函数 - 判断 x 是不是一个对称整数bool check(int x){vectorint digits;while (x){digits.push_back(x % 10);x / 10;}if (digits.size() % 2 1)return false;int sum 0;for (int i 0; i digits.size() / 2; i)sum digits[i];for (int i digits.size() / 2; i digits.size(); i)sum - digits[i];return sum 0;}
};取巧做法将数字转化为字符串。
class Solution
{
public:int countSymmetricIntegers(int low, int high){int count 0;for (int num low; num high; num){string s to_string(num);if (s.size() % 2 0 accumulate(s.begin(), s.begin() s.size() / 2, 0) accumulate(s.begin() s.size() / 2, s.end(), 0))count;}return count;}
};复杂度分析
时间复杂度O((high−low)*log(high))。
空间复杂度O(log(high))。
题目2生成特殊数字的最少操作
思路
贪心。
一个数能被 25 整除有如下五种情况
这个数是 0。这个数以 00 结尾。这个数以 25 结尾。这个数以 50 结尾。这个数以 75 结尾。
设字符串的长度为 n。
我们从字符串的末尾往开头遍历设当前数位为 digit使用数组 count 记录数位的出现次数。
假设我们遍历到第 i 位有 digit num[i] - ‘0’此时
当 count[0] 2 时不管 digit 是什么我们都可以构建一个以 00 结尾的数字。第 0 位到第 i 位的数字可以保留后面两个 0 可以保留其他位删除所以一共需要删除 n - (i 3) 位数字。当 digit 2 count[5] 0 时我们都可以构建一个以 25 结尾的数字。第 0 位到第 i 位的数字可以保留后面的 5 也可以保留其他位删除所以一共需要删除 n - (i 2) 位数字。同理当 digit 5 count[0] 0 时我们都可以构建一个以 50 结尾的数字一共需要删除 n - (i 2) 位数字当 digit 7 count[5] 0 时我们都可以构建一个以 75 结尾的数字一共需要删除 n - (i 2) 位数字。最后别忘了 count[digit]。
其他情况我们都必须将字符串删到只剩 0 为止删除次数为 n - count[0]。
代码
/** lc appleetcode.cn id2844 langcpp** [2844] 生成特殊数字的最少操作*/// lc codestart
class Solution
{
public:int minimumOperations(string num){int n num.size();vectorint count(10, 0);for (int i n - 1; i 0; i--){int digit num[i] - 0;// 以00结尾if (count[0] 2)return n - i - 3;// 以25/50/75结尾if ((digit 2 count[5]) || (digit 5 count[0]) || (digit 7 count[5]))return n - i - 2;count[digit];}// 删到只剩0return n - count[0];}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 为字符串 num 的长度。
空间复杂度O(n)其中 n 为字符串 num 的长度。
题目3统计趣味子数组的数目
思路
前缀和。
对于本题由于需要统计 cnt我们可以把满足 nums[i] % modulo k 的 nums[i] 视作 1不满足则视作 0。
用数组 fun 记录上述结果。
如此转换后算出 fun 的前缀和数组 preSum那么题目中的 cnt 等价于 preSum[right 1] - preSum[left]。
枚举 left 和 right计算趣味子数组的数目即满足 (preSum[right 1] - preSum[left]) % modulo k 的个数。
/** lc appleetcode.cn id2845 langcpp** [2845] 统计趣味子数组的数目*/// lc codestart
class Solution
{
public:long long countInterestingSubarrays(vectorint nums, int modulo, int k){int n nums.size();vectorint fun(n, 0);for (int i 0; i n; i)if (nums[i] % modulo k)fun[i] 1;vectorint preSum(n 1, 0);for (int i 1; i n; i)preSum[i] preSum[i - 1] fun[i - 1];long long ans 0;for (int left 0; left n; left)for (int right left; right n; right){int cnt preSum[right 1] - preSum[left];if (cnt % modulo k)ans;}return ans;}
};
// lc codeend结果超时了 优化
(preSum[right 1] - preSum[left]) % modulo k 等价于 preSum[left] % modulo (preSum[right 1] − k) % modulo。
根据上式我们可以一边枚举 right一边用一个哈希表统计有多少个 preSum[right 1] % modulo这样可以快速知道有多少个 (preSum[right 1] − k) % modulo也就是 preSum[left] % modulo 的个数把个数加到答案中。
代码
/** lc appleetcode.cn id2845 langcpp** [2845] 统计趣味子数组的数目*/// lc codestart
class Solution
{
public:long long countInterestingSubarrays(vectorint nums, int modulo, int k){int n nums.size();vectorint fun(n, 0);for (int i 0; i n; i)if (nums[i] % modulo k)fun[i] 1;vectorint preSum(n 1, 0);for (int i 1; i n; i)preSum[i] preSum[i - 1] fun[i - 1];long long ans 0;unordered_mapint, int cnt;cnt[0] 1; // 把 preSum[0] 0 算进去for (int right 0; right n; right){ans cnt[(preSum[right 1] - k modulo) % modulo];cnt[preSum[right 1] % modulo];}return ans;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 是数组 nums 的长度。
空间复杂度O(n)其中 n 是数组 nums 的长度。
题目4边权重均等查询
超出能力范围。
题解LCA 模板Python/Java/C/Go
