静态双语企业网站后台源码,海外贸易平台有哪些,wordpress个人博客带会员,做网站一定要会ps么题目部分
题目计算最大乘积难度易题目说明给定一个元素类型为小写字符串的数组#xff0c;请计算两个没有相同字符的元素长度乘积的最大值。 如果没有符合条件的两个元素#xff0c;返回 0。输入描述输入为一个半角逗号分隔的小写字符串的数组#xff0c;2 数组长度请计算两个没有相同字符的元素长度乘积的最大值。 如果没有符合条件的两个元素返回 0。输入描述输入为一个半角逗号分隔的小写字符串的数组2 数组长度1000 字符串长度 50。输出描述两个没有相同字符的元素长度乘积的最大值。补充说明无------------------------------------------------------示例示例1输入iwdvpbn,hk,iuop,iikd,kadgpf输出14说明数组中有 5 个元素。 iwdvpbn 与 hk 无相同的字符满足条件iwdvpbn 长度为 7hk 长度为 2乘积为 14 7 * 2。 iwdvpbn 与 iuop、iikd、kadgpf 都有相同的字符不满足条件。 iuop 与 iikd、kadgpf 均有相同的字符不满足条件。 iikd 与 kadgpf 有相同的字符不满足条件。 因此输出为 14。 解读与分析
题目解读
给定一个长字符串以 “,” 为间隔符分隔成多个字符串。请从这些字符串中找出两个字符串保证在这两个字符串中不存在相同字符的前提下使两个字符串的长度的乘积最大。
分析与思路
此题的步骤可以分为解析字符串排序、数据初始化、遍历详细说明如下 1. 解析字符串。对输入的字符串以 “,” 为间隔符把它们解析成多个字符串放到数组 stringArr 中。 2. 对数组 stringArr 排序。排序规则为长度最长的字符串排在最前面。 3. 数据初始化。对已排序的 stringArr统计每个元素字符串所包含的字符放到集合中计算字符串的长度。创建两个数组第一个数组为 charSetArr其第 i 个元素为 stringArr 中第 i 个元素包含的字符结合第二个数组 lengArr其第 i 个元素为 stringArr 中第 i 个元素的长度。 4. 遍历。 1) 初始化乘积设为 maxProduct初始值 0。 2) 两两比较字符串。把字符串 stringArr[0] 分别与 stringArr[1]、stringArr[2] …… stringArr[n -1] 进行比较之后把字符串 stringArr[1] 分别与 stringArr[2]、stringArr[3] …… stringArr[n -1] 比较。 比较规则是在比较时如果不存在交集即charSetArr[0] 与 charSetArr[i] 不存在交集则计算 lengthArr[0] 与 lengthArr[i] 的乘积设为 tmpProduct如果 tmpProduct 大于 maxProduct则把 tmpProduct 赋值个 maxProduct。当找到 charSetArr[0] 与 charSetArr[i] 不存在交集后不再判断 charSetArr[0] 与 其他字符串是否存在交集因为已经不存在乘积比它更大。
此方法的时间复杂度为 O()空间复杂度为O()。 代码实现
Java代码
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;/*** 计算最大乘积* * version 0.1* author Frank**/
public class StringLengthMaxProduct {public static void main(String[] args) {Scanner sc new Scanner(System.in);while (sc.hasNext()) {String input sc.nextLine();processStringLengthMaxProduct( input );}}private static void processStringLengthMaxProduct( String input ){String[] strArr input.split( , );Arrays.sort( strArr, new ComparatorString() {Overridepublic int compare(String o1, String o2) {// 长度最长的排在最前面return o2.length() - o1.length();}});Set[] charSetArr new HashSet[ strArr.length ];int[] lengthArr new int[ strArr.length ];initCharSetInfo( strArr, charSetArr, lengthArr );int ret getMaxProduct( charSetArr, lengthArr );System.out.println( ret );}private static void initCharSetInfo( String[] strArr, Set[] charSetArr,int[] lengthArr ){for( int i 0; i strArr.length; i ){String curStr strArr[i];lengthArr[i] curStr.length();SetCharacter curSet new HashSetCharacter();for( int j 0; j curStr.length(); j ){curSet.add( curStr.charAt( j ) );}charSetArr[i] curSet;}}private static int getMaxProduct( Set[] charSetArr,int[] lengthArr ){int maxProduct 0;int size charSetArr.length;boolean needBreak false;for( int i 0; i size; i ){for( int j i 1; j size; j ){if( ( j i 1 ) ( lengthArr[i] * lengthArr[j] maxProduct ) ){needBreak true;break;}// 包含相同字符if( !Collections.disjoint( charSetArr[i], charSetArr[j])){continue;}int product lengthArr[i] * lengthArr[j];if( product maxProduct){maxProduct product;}break;}if( needBreak ){break;}}return maxProduct;}
} JavaScript代码
const rl require(readline).createInterface({ input: process.stdin });
var iter rl[Symbol.asyncIterator]();
const readline async () (await iter.next()).value;
void async function() {while (line await readline()) {processStringLengthMaxProduct(line);}
}();function processStringLengthMaxProduct(input) {var strArr input.split(,);strArr.sort(function(a, b) {return b.length - a.length;});var charSetArr new Array();var lengthArr new Array();initCharSetInfo(strArr, charSetArr, lengthArr);var ret getMaxProduct(charSetArr, lengthArr);console.log(ret);
}function initCharSetInfo(strArr, charSetArr, lengthArr) {for (var i 0; i strArr.length; i) {var curStr strArr[i];lengthArr[i] curStr.length;var curSet new Set();for (var j 0; j curStr.length; j) {curSet.add(curStr.charAt(j));}charSetArr[i] curSet;}
}function getMaxProduct(charSetArr, lengthArr) {var maxProduct 0;var size charSetArr.length;var needBreak false;for (var i 0; i size; i) {for (var j i 1; j size; j) {if ((j i 1) (lengthArr[i] * lengthArr[j] maxProduct)) {needBreak true;break;}// 包含相同字符if (!isSetDisjoint(charSetArr[i], charSetArr[j])) {continue;}var product lengthArr[i] * lengthArr[j];if (product maxProduct) {maxProduct product;}break;}if (needBreak) {break;}}return maxProduct;
}function isSetDisjoint(charSet1, charSet2) {for (var ele of charSet2) {if (charSet1.has(ele)) {return false;}}return true;
} (完)
