Leetcode 第 361 场周赛题解
- Leetcode 第 361 场周赛题解
-
- 题目1:2843. 统计对称整数的数目
-
- 思路
- 代码
- 复杂度分析
- 题目2:生成特殊数字的最少操作
-
- 思路
- 代码
- 复杂度分析
- 题目3:统计趣味子数组的数目
-
- 思路
- 代码
- 复杂度分析
- 题目4:边权重均等查询
Leetcode 第 361 场周赛题解
题目1:2843. 统计对称整数的数目
思路
枚举。
代码
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 app=leetcode.cn id=2844 lang=cpp
*
* [2844] 生成特殊数字的最少操作
*/
// @lc code=start
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]++;
}
// 删到只剩0
return n - count[0];
}
};
// @lc code=end
复杂度分析
时间复杂度: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 app=leetcode.cn id=2845 lang=cpp
*
* [2845] 统计趣味子数组的数目
*/
// @lc code=start
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 code=end
结果超时了:
优化:
(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 app=leetcode.cn id=2845 lang=cpp
*
* [2845] 统计趣味子数组的数目
*/
// @lc code=start
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 code=end
复杂度分析
时间复杂度:O(n),其中 n 是数组 nums 的长度。
空间复杂度:O(n),其中 n 是数组 nums 的长度。
题目4:边权重均等查询
超出能力范围。
题解:LCA 模板(Python/Java/C++/Go)
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
经过上一篇文章的学习,实现了界面驱动数据更新,接下来实现一下其它相关的指令,比如事件相关的指令,v-on 这个指令的使用频率还是很高的,所以我们先来实现这个指令。 v-on 的作用是什么,是不是可以给某一个元素绑定一个事件。 紧接着了解了 v-on 的作用之后…