华为OD机试 - 字符串划分（Python/JS/C/C++ 2024 E卷 100分）

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

给定一个小写字母组成的字符串 s，请找出字符串中两个不同位置的字符作为分割点，使得字符串分成三个连续子串且子串权重相等，注意子串不包含分割点。

若能找到满足条件的两个分割点，请输出这两个分割点在字符串中的位置下标，若不能找到满足条件的分割点请返回0,0。

子串权重计算方式为：子串所有字符的ASCII码数值之和。

二、输入描述

输入为一个字符串，字符串由a~z，26个小写字母组成，5 ≤ 字符串长度 ≤ 200。

三、输出描述

输出为两个分割点在字符串中的位置下标，以逗号分隔

备注

只考虑唯一解，不存在一个输入多种输出解的情况

四、测试用例

测试用例1：

1、输入

acdbbbca

2、输出

2,5

3、说明

以位置2和5作为分割点，将字符串分割为ac, db, bb, ca三个子串，每一个的子串权重都为196，输出为：2,5

测试用例2：

1、输入

abcabc

2、输出

0,0

3、说明

找不到符合条件的分割点，输出为：0,0

五、解题思路

题目要求将字符串分成三个连续子串，且子串的ASCII码值之和相等。为了快速计算子串的权重（ASCII码值之和），使用前缀和数组来存储从字符串开头到当前位置的ASCII总和。前缀和的优势在于，它可以在常数时间内计算任何子串的权重，从而减少计算时间复杂度。

1. 使用两层嵌套循环来找到两个分割点 (i, j)，分别作为第一个和第二个分割点，使字符串分成三个子串。
2. 第一层循环：找到第一个分割点 i，i 的范围是 1 到 n-4，确保第一个子串至少包含一个字符。
3. 第二层循环：找到第二个分割点 j，j 的范围是 i + 2 到 n - 2，确保中间子串至少包含一个字符，并且第二个分割点要在第一个分割点之后。
4. 子串权重比较：使用前缀和数组来计算三个子串的权重，分别为：
   • 第一个子串的权重：sum1 = prefixSum[i]
   • 第二个子串的权重：sum2 = prefixSum[j] - prefixSum[i + 1]
   • 第三个子串的权重：sum3 = prefixSum[n] - prefixSum[j + 1]
5. 比较这三个权重，如果相等，则找到了满足条件的分割点，输出结果并停止查找。
6. 如果找到满足条件的两个分割点，输出它们的索引；如果没有找到，返回 0,0。

时间复杂度

1. 前缀和数组构建：O(n)
2. 双重循环：最坏情况下需要遍历约 O(n^2) 的分割点组合，但由于使用了前缀和数组，每次判断子串权重的比较为常数时间。因此，整体的时间复杂度接近 O(n^2)。
3. 该时间复杂度在题目给定的范围（5 ≤ n ≤ 200）内是可接受的。

六、Python算法源码

def find_split_points(s):n = len(s)if n < 5 or n > 200:# 字符串长度应在5到200之间return "0,0"# 计算前缀和数组prefix_sum = [0] * (n + 1)for i in range(n):prefix_sum[i + 1] = prefix_sum[i] + ord(s[i])# 遍历所有可能的分割点对 (i, j)found = Falsesplit1, split2 = 0, 0for i in range(1, n - 3):  # 第一个分割点至少在位置1，最多在n-4for j in range(i + 2, n - 1):  # 第二个分割点至少在i+2，最多在n-2sum1 = prefix_sum[i]sum2 = prefix_sum[j] - prefix_sum[i + 1]sum3 = prefix_sum[n] - prefix_sum[j + 1]if sum1 == sum2 == sum3:split1 = isplit2 = jfound = Truebreakif found:break# 输出结果if found:return f"{split1},{split2}"else:return "0,0"# 读取输入
if __name__ == "__main__":s = input().strip()print(find_split_points(s))

七、JavaScript算法源码

function findSplitPoints(s) {let n = s.length;if (n < 5 || n > 200) {// 字符串长度应在5到200之间return "0,0";}// 计算前缀和数组let prefixSum = new Array(n + 1).fill(0);for (let i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + s.charCodeAt(i);}// 遍历所有可能的分割点对 (i, j)let found = false;let split1 = 0, split2 = 0;for (let i = 1; i <= n - 4; i++) { // 第一个分割点至少在位置1，最多在n-4for (let j = i + 2; j <= n - 2; j++) { // 第二个分割点至少在i+2，最多在n-2let sum1 = prefixSum[i];let sum2 = prefixSum[j] - prefixSum[i + 1];let sum3 = prefixSum[n] - prefixSum[j + 1];if (sum1 === sum2 && sum2 === sum3) {split1 = i;split2 = j;found = true;break; // 找到后立即停止}}if (found) {break;}}// 输出结果if (found) {return `${split1},${split2}`;} else {return "0,0";}
}// 读取输入
const s = prompt("请输入字符串:").trim();
console.log(findSplitPoints(s));

八、C算法源码

#include <stdio.h>
#include <string.h>void findSplitPoints(char *s) {int n = strlen(s);if (n < 5 || n > 200) {// 字符串长度应在5到200之间printf("0,0\n");return;}// 计算前缀和数组long prefixSum[n + 1];prefixSum[0] = 0;for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + (int)s[i];}// 遍历所有可能的分割点对 (i, j)int found = 0;int split1 = 0, split2 = 0;for (int i = 1; i <= n - 4; i++) { // 第一个分割点至少在位置1，最多在n-4for (int j = i + 2; j <= n - 2; j++) { // 第二个分割点至少在i+2，最多在n-2long sum1 = prefixSum[i];long sum2 = prefixSum[j] - prefixSum[i + 1];long sum3 = prefixSum[n] - prefixSum[j + 1];if (sum1 == sum2 && sum2 == sum3) {split1 = i;split2 = j;found = 1;break; // 找到后立即停止}}if (found) {break;}}// 输出结果if (found) {printf("%d,%d\n", split1, split2);} else {printf("0,0\n");}
}int main() {char s[201];// 读取输入scanf("%200s", s);findSplitPoints(s);return 0;
}

九、C++算法源码

#include <iostream>
#include <string>
#include <vector>using namespace std;string findSplitPoints(const string &s) {int n = s.length();if (n < 5 || n > 200) {// 字符串长度应在5到200之间return "0,0";}// 计算前缀和数组vector<long> prefixSum(n + 1, 0);for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + (int)s[i];}// 遍历所有可能的分割点对 (i, j)bool found = false;int split1 = 0, split2 = 0;for (int i = 1; i <= n - 4; i++) { // 第一个分割点至少在位置1，最多在n-4for (int j = i + 2; j <= n - 2; j++) { // 第二个分割点至少在i+2，最多在n-2long sum1 = prefixSum[i];long sum2 = prefixSum[j] - prefixSum[i + 1];long sum3 = prefixSum[n] - prefixSum[j + 1];if (sum1 == sum2 && sum2 == sum3) {split1 = i;split2 = j;found = true;break; // 找到后立即停止}}if (found) {break;}}// 输出结果if (found) {return to_string(split1) + "," + to_string(split2);} else {return "0,0";}
}int main() {string s;// 读取输入cin >> s;cout << findSplitPoints(s) << endl;return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。