Leetcode—2950. 可整除子串的数量【中等】Plus（前缀和题型）
2024每日刷题（一零八）
Leetcode—2950. 可整除子串的数量
算法思想
让 f ( c ) = d , 其中 d = 1 , 2 , . . . , 9 f(c) = d, 其中d = 1, 2, ..., 9 f(c)=d,其中d=1,2,...,9.
// f(c1) + f(c2) + ... + f(ck) / k = avg
// => f(c1) + f(c2) + ... + f(ck) - k * avg, where avg in [1, 9].
实现代码
class Solution {
public:int f(char c) {return 9 - ('z' - c) / 3;}int countDivisibleSubstrings(string word) {int ans = 0;for(int avg = 1; avg <= 9; avg++) {int prefix = 0;unordered_map<int, int> m{{0, 1}};for(auto c: word) {prefix += f(c) - avg;ans += m[prefix]++;}}return ans;}
};
运行结果
之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！