(B卷,100分)- 计算最大乘积（Java & JS & Python & C）

题目描述

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

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

输入描述

输入为一个半角逗号分隔的小写字符串的数组，2 <= 数组长度<=100，0 < 字符串长度<= 50。

输出描述

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

用例

位运算解法

具体解析可以看：

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("%dn", 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())