【每日一道剑指 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(N³)，空间复杂度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+N²)，空间复杂度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  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// flags[i] |=1<<(words[i][j]-'a');   //words[i][j]这样操作vector中每个字符串中的单个字符是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;}
};

💫点击直接资料领取💫

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！