- 计算最大乘积（Java JS Python C）)
(新卷,100分)- 计算最大乘积（Java & JS & Python & C）
题目描述
给定一个元素类型为小写字符串的数组，请计算两个没有相同字符的元素长度乘积的最大值，
如果没有符合条件的两个元素，返回0。
输入描述
输入为一个半角逗号分隔的小写字符串的数组，2 <= 数组长度<=100，0 < 字符串长度<= 50。
输出描述
两个没有相同字符的元素 长度乘积的最大值。
用例
| 输入 | iwdvpbn,hk,iuop,iikd,kadgpf |
| 输出 | 14 |
| 说明 | 数组中有5个元素。 iwdvpbn与hk无相同的字符，满足条件，iwdvpbn的长度为7，hk的长度为2，乘积为14（7*2）。 iwdvpbn与iuop、iikd、kadgpf均有相同的字符，不满足条件。 iuop与iikd、kadgpf均有相同的字符，不满足条件。 iikd与kadgpf有相同的字符，不满足条件。 因此，输出为14。 |
位运算解法
JS算法源码
/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on("line", (line) => { console.log(getResult(line.split(","))); }); function getResult(words) { let ans = 0; const n = words.length; const bits = new Array(n).fill(0); for (let i = 0; i < n; i++) { for (let j = 0; j < words[i].length; j++) { bits[i] |= 1 << (words[i][j].charCodeAt() - 97); } } for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { if ((bits[i] & bits[j]) == 0) { ans = Math.max(ans, words[i].length * words[j].length); } } } return ans; }Java算法源码
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println(getResult(sc.nextLine().split(","))); } public static int getResult(String[] words) { int ans = 0; int n = words.length; int[] bits = new int[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < words[i].length(); j++) { bits[i] |= 1 << (words[i].charAt(j) - 'a'); } } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if ((bits[i] & bits[j]) == 0) { ans = Math.max(ans, words[i].length() * words[j].length()); } } } return ans; } }Python算法源码
# 输入获取 words = input().split(",") # 算法入口 def getResult(): ans = 0 n = len(words) bits = [0] * n for i in range(n): for j in range(len(words[i])): bits[i] |= (1 << (ord(words[i][j]) - 97)) for i in range(n): for j in range(i + 1, n): if (bits[i] & bits[j]) == 0: ans = max(ans, len(words[i]) * len(words[j])) return ans # 算法调用 print(getResult())C算法源码
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX(a,b) (a) > (b) ? (a) : (b) int getResult(char ** words, int wordsSize); int main() { char s[5000]; gets(s); char* words[100]; int wordsSize = 0; char* token = strtok(s, ","); while(token != NULL) { words[wordsSize++] = token; token = strtok(NULL, ","); } printf("%d\n", getResult(words, wordsSize)); return 0; } int getResult(char ** words, int wordsSize) { int ans = 0; int* bits = (int*) calloc(wordsSize, sizeof(int)); for(int i=0; i<wordsSize; i++) { for(int j=0; j<strlen(words[i]); j++) { bits[i] |= 1 << (words[i][j] - 'a'); } } for(int i=0; i<wordsSize; i++) { for(int j=i+1; j<wordsSize; j++) { if((bits[i] & bits[j]) == 0) { ans = MAX(ans, strlen(words[i]) * strlen(words[j])); } } } return ans; }交集解法
JavaScript算法源码
/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on("line", (line) => { const arr = line.split(","); console.log(getResult(arr)); }); function getResult(arr) { let ans = 0; const sets = arr.map((s) => new Set([...s])); for (let i = 0; i < sets.length; i++) { for (let j = i + 1; j < sets.length; j++) { if (disjoint(sets[i], sets[j])) { ans = Math.max(ans, arr[i].length * arr[j].length); } } } return ans; } function disjoint(set1, set2) { for (let c of set1) { if (set2.has(c)) return false; } return true; }Java算法源码
import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] strings = sc.nextLine().split(","); System.out.println(getResult(strings)); } public static int getResult(String[] arr) { ArrayList<HashSet<Character>> list = new ArrayList<>(); for (String s : arr) { HashSet<Character> set = new HashSet<>(); for (char c : s.toCharArray()) set.add(c); list.add(set); } int ans = 0; for (int i = 0; i < list.size(); i++) { HashSet<Character> a = list.get(i); for (int j = i + 1; j < list.size(); j++) { HashSet<Character> b = list.get(j); if (Collections.disjoint(a, b)) { ans = Math.max(ans, arr[i].length() * arr[j].length()); } } } return ans; } }Python算法源码
# 输入获取 arr = input().split(",") # 算法入口 def getResult(): sets = list(map(lambda x: set(x), arr)) ans = 0 for i in range(len(sets)): for j in range(i+1, len(sets)): if sets[i].isdisjoint(sets[j]): ans = max(ans, len(arr[i]) * len(arr[j])) return ans # 算法调用 print(getResult())
