网站建设培训价格,网络优化推广公司,网页微博怎么发文章,阿里云个人备案可以做企业网站吗华为OD机试 2024E卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试真题#xff08;Python/JS/C/C#xff09;》。
刷的越多#xff0c;抽中的概率越大#xff0c;私信哪吒#xff0c;备注华为OD#xff0c;加入华为OD刷题交流群#xff0c;… 华为OD机试 2024E卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试真题Python/JS/C/C》。
刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。
一、题目描述
给定一个小写字母组成的字符串 s请找出字符串中两个不同位置的字符作为分割点使得字符串分成三个连续子串且子串权重相等注意子串不包含分割点。
若能找到满足条件的两个分割点请输出这两个分割点在字符串中的位置下标若不能找到满足条件的分割点请返回0,0。
子串权重计算方式为子串所有字符的ASCII码数值之和。
二、输入描述
输入为一个字符串字符串由a~z26个小写字母组成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总和。前缀和的优势在于它可以在常数时间内计算任何子串的权重从而减少计算时间复杂度。
使用两层嵌套循环来找到两个分割点 (i, j)分别作为第一个和第二个分割点使字符串分成三个子串。第一层循环找到第一个分割点 ii 的范围是 1 到 n-4确保第一个子串至少包含一个字符。第二层循环找到第二个分割点 jj 的范围是 i 2 到 n - 2确保中间子串至少包含一个字符并且第二个分割点要在第一个分割点之后。子串权重比较使用前缀和数组来计算三个子串的权重分别为 第一个子串的权重sum1 prefixSum[i]第二个子串的权重sum2 prefixSum[j] - prefixSum[i 1]第三个子串的权重sum3 prefixSum[n] - prefixSum[j 1] 比较这三个权重如果相等则找到了满足条件的分割点输出结果并停止查找。如果找到满足条件的两个分割点输出它们的索引如果没有找到返回 0,0。
时间复杂度
前缀和数组构建O(n)双重循环最坏情况下需要遍历约 O(n^2) 的分割点组合但由于使用了前缀和数组每次判断子串权重的比较为常数时间。因此整体的时间复杂度接近 O(n^2)。该时间复杂度在题目给定的范围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): # 第二个分割点至少在i2最多在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) { // 第二个分割点至少在i2最多在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.hvoid 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) { // 第二个分割点至少在i2最多在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 vectorusing namespace std;string findSplitPoints(const string s) {int n s.length();if (n 5 || n 200) {// 字符串长度应在5到200之间return 0,0;}// 计算前缀和数组vectorlong 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) { // 第二个分割点至少在i2最多在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在线答疑。
