华为OD机试 - 无重复字符的元素长度乘积的最大值（Python/JS/C/C++ 2024 C卷 100分）

在这里插入图片描述

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

专栏导读

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

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

一、题目描述

给定一个元素类型为小写字符串的数组，请计算两个没有相同字符的元素长度乘积的最大值。

如果没有符合条件的两个元素返回0。

二、输入描述

输入为一个半角逗号分割的小写字符串数组

2<= 数组长度 <=100

0< 字符串长度 <=50

三、输出描述

两个没有相同字符的元素长度乘积的最大值。

四、测试用例

测试用例1

1、输入

iwdvpbn,hk,iuop,iikd,kadgpf

2、输出

3、说明

数组中有5个元素。
iwdvpbn与hk无相同的字符，满足条件，iwdvpbn的长度为7，hk的长度为2，乘积为14（7*2）。
iwdvpbn与iuop、iikd、kadgpf均有相同的字符，不满足条件。
iuop与iikd、kadgpf均有相同的字符，不满足条件。

测试用例2

1、输入

abc,def,gh

2、输出

3、说明

所有字符串两两之间都没有相同字符，最长的两个是abc和def，乘积为3*3=9。

五、解题思路

遍历每个字符，与其余的字符串进行比较，如果没有相同字符，则计算乘积。

获取乘积最大值即可。

需要在给定的字符串数组中找到两个字符串，它们之间没有任何共同的字符，并且它们长度的乘积最大。如果不存在这样的两个字符串，返回0。

六、Python算法源码

def max_product_no_common_chars(input_str):# 分割输入字符串为列表arr = input_str.strip().split(',')n = len(arr)masks = [0] * n  # 存储每个字符串的字符集掩码lengths = [0] * n  # 存储每个字符串的长度for i in range(n):s = arr[i]lengths[i] = len(s)for c in s:masks[i] |= 1 << (ord(c) - ord('a'))  # 设置对应字符的位max_product = 0# 双重循环比较每对字符串for i in range(n - 1):for j in range(i + 1, n):if (masks[i] & masks[j]) == 0:  # 无共同字符max_product = max(max_product, lengths[i] * lengths[j])return max_productif __name__ == "__main__":import sysinput_str = sys.stdin.readline()print(max_product_no_common_chars(input_str))

七、JavaScript算法源码

function maxProductNoCommonChars(inputStr) {// 分割输入字符串为数组const arr = inputStr.trim().split(',');const n = arr.length;const masks = new Array(n).fill(0); // 存储每个字符串的字符集掩码const lengths = new Array(n).fill(0); // 存储每个字符串的长度for (let i = 0; i < n; i++) {const s = arr[i];lengths[i] = s.length;for (let c of s) {masks[i] |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0)); // 设置对应字符的位}}let maxProduct = 0;// 双重循环比较每对字符串for (let i = 0; i < n - 1; i++) {for (let j = i + 1; j < n; j++) {if ( (masks[i] & masks[j]) === 0 ) { // 无共同字符maxProduct = Math.max(maxProduct, lengths[i] * lengths[j]);}}}return maxProduct;
}// 读取标准输入并输出结果
const readline = require('readline');
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});
rl.on('line', (input) => {console.log(maxProductNoCommonChars(input));rl.close();
});

八、C算法源码

#include <stdio.h>
#include <string.h>int main() {char input[10000];// 读取输入字符串fgets(input, sizeof(input), stdin);// 去除换行符input[strcspn(input, "\n")] = '\0';// 分割字符串char *arr[100];int n = 0;char *token = strtok(input, ",");while (token != NULL && n < 100) {arr[n++] = token;token = strtok(NULL, ",");}int masks[100] = {0}; // 存储每个字符串的字符集掩码int lengths[100] = {0}; // 存储每个字符串的长度for (int i = 0; i < n; i++) {char *s = arr[i];lengths[i] = strlen(s);for (int j = 0; j < lengths[i]; j++) {masks[i] |= 1 << (s[j] - 'a'); // 设置对应字符的位}}int max_product = 0;// 双重循环比较每对字符串for (int i = 0; i < n -1; i++) {for (int j = i +1; j < n; j++) {if ( (masks[i] & masks[j]) == 0 ) { // 无共同字符int product = lengths[i] * lengths[j];if (product > max_product) {max_product = product;}}}}printf("%d\n", max_product);return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;int main(){string input;// 读取输入字符串getline(cin, input);// 分割字符串vector<string> arr;string token;stringstream ss(input);while(getline(ss, token, ',')){arr.push_back(token);}int n = arr.size();vector<int> masks(n, 0); // 存储每个字符串的字符集掩码vector<int> lengths(n, 0); // 存储每个字符串的长度for(int i=0;i<n;i++){string s = arr[i];lengths[i] = s.length();for(char c : s){masks[i] |= 1 << (c - 'a'); // 设置对应字符的位}}int max_product = 0;// 双重循环比较每对字符串for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){if( (masks[i] & masks[j]) == 0 ){ // 无共同字符max_product = max(max_product, lengths[i] * lengths[j]);}}}cout << max_product << endl;return 0;
}