leetcode 1573. 分割字符串的方案数-Number of Ways to Split a String

张开发
• 2026/4/16 3:07:53 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

leetcode 1573. 分割字符串的方案数-Number of Ways to Split a String
Problem: 1573. 分割字符串的方案数-Number of Ways to Split a String统计1的频次前缀和统计1的频次sum只需要考虑前缀和sum/3的个数c1sum*2/3的个数c2两者的乘积就是答案全是0则是等差数列求和Codeclass Solution { public: const int mod 1e9 30 - 23; int numWays(string s) { string s1, s2, s3; int sum 0, n s.size(); vectorint prefix{0}; for(char c : s) { if(c 1) sum; prefix.push_back(sum); } if(sum0) return (((long long)(n-2)*(long long)(n-21))/2) % mod; if(sum%3 ! 0) return 0; int a1 sum/3, a2 sum * 2 / 3, c1 0, c2 0; for(int i 1; i n; i) { if(prefix[i]a1) c1; else if(prefix[i]a2) c2; else if(prefix[i] a2) return ((long long)c1 * (long long)c2) % mod; } return 0; } };

更多文章