【每日一道剑指 Offer】 算法·每日一题（详解+多解）-- day4
【每日一道剑指 Offer】 算法·每日一题（详解+多解）-- day4
【每日一道剑指 Offer】 算法·每日一题（详解+多解）-- day4
✨博主介绍
🌊 作者主页：苏州程序大白 🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创始之一，目前合作公司富士康、歌尔等几家新能源公司
单词长度的最大乘积
给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
示例 1: 输入: words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”] 输出: 16 解释: 这两个单词为 “abcw”, “fxyz”。它们不包含相同字符，且长度的乘积最大。
示例 2: 输入: words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”] 输出: 4 解释: 这两个单词为 “ab”, “cd”。
示例 3: 输入: words = [“a”,“aa”,“aaa”,“aaaa”] 输出: 0 解释: 不存在这样的两个单词。
提示：
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母解题思路
暴力解法
时间复杂度O(N3)，空间复杂度O(N)
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int max = 0;
//暴力遍历
for (int i=0; i<n; i++){
for (int j=i+1; j<n; j++){
if (isRe(words[i], words[j])) continue;
max = Math.max(max, words[i].length() * words[j].length());
}
}
return max;
}
//使用HashSet判断两个字符串中是否存在相同的字符
public boolean isRe(String one, String two){
char[] charOne = one.toCharArray();
char[] charTwo = two.toCharArray();
HashSet<Character> set = new HashSet();
//存入第一个字符串
for (int i=0; i<charOne.length; i++) set.add(charOne[i]);
//判断第二个字符串是否有重复字符
for (int i=0; i<charTwo.length; i++)
if (set.contains(charTwo[i]))
return true;
return false;
}
}位运算
解法：
因为只有26个小写字符，所以直接使用一个int存储字符出现的情况，然后枚举最大乘积使用二进制低26位表示字母a~z。若出现过用1表示，否则用0。
用数组mask记录每个字母的位掩码1 << (ch - ‘a’)：将低26位中ch - 'a’的位置置为1当且仅当 masks[i] & masks[j] = 0时第 i 个单词和第 j 个单词没有公共字母时间复杂度O(L+N2)，空间复杂度O(N)。
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int max = 0;
int[] mask = new int[n];
for (int i = 0; i < n; i++) {
for (char ch : words[i].toCharArray()) {
mask[i] |= 1 << (ch - 'a');
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if ((mask[i] & mask[j]) == 0) {
max = Math.max(max, words[i].length() * words[j].length());
}
}
}
return max;
}
}二进制,字符串
二进制,字符串用26位二进制数表示,int有32位，只用到26位就够了 例：字符串中有a,那么32-26=6，flags[i]中的第7位为1，反之为0，有b的话，第8位为0…
class Solution {
public:
int maxProduct(vector<string>& words) {
//int数组用来使用二进制形式表示字符出串
//vector<int> flags; //未赋初值（做初始化），出问题
vector<int> flags(words.size(),0); //数组做初始化
//int flags[words.size()]; //未做初始化，会出问题，分配的内存中可能有脏数据
for(int i=0;i< words.size();i++){
for(char c: words[i]){ //使用范围for语句，这样是可以用的，开始出问题是因为数组为做初始化导致的
//for(int j=0;j<words[i].length();j++){
// flags[i] |=1<<(words[i][j]-'a'); //words[i][j]这样操作vector<string>中每个字符串中的单个字符是ok的
flags[i] |=1<<(c-'a');
}
}
int result=0;
for(int i=0;i<words.size();i++){
for(int j=i+1;j<words.size();j++){
if((flags[i]&flags[j])==0){
int prod = words[i].length() * words[j].length();
result = max(result,prod);
}
}
}
return result;
}
}
腾讯云开发者
