Leetcode—2950. 可整除子串的数量【中等】Plus（前缀和题型）

本文主要是介绍Leetcode—2950. 可整除子串的数量【中等】Plus（前缀和题型），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024每日刷题（一零八）

Leetcode—2950. 可整除子串的数量

算法思想

让$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;}
};

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！

这篇关于Leetcode—2950. 可整除子串的数量【中等】Plus（前缀和题型）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---