天津建站服务,江苏企业建设网站公司,网站建设产品,手机怎么做图纸设计这道题时间复杂度我感觉设置的不是很好#xff0c;应该最好是有一个1000变成10000就行。 因为我在做这道题的时候被误导了#xff0c;以为双重循环暴力判断一下也能过#xff0c;因为1000*1000 *26的时间复杂度没有到1亿#xff0c;那么我刚开始认为是能过的#xff0c;结… 这道题时间复杂度我感觉设置的不是很好应该最好是有一个1000变成10000就行。 因为我在做这道题的时候被误导了以为双重循环暴力判断一下也能过因为1000*1000 *26的时间复杂度没有到1亿那么我刚开始认为是能过的结果卡在最后一个用例上了 那么后期我就开始想怎么优化掉那个2626刚好可以用bitmap(状态压缩)和位运算的思想 这样我们可以优化掉那个26的复杂度这样我们就能过了 附上第一次暴力解法(卡在最后一个用例)
class Solution {
public:int vv[1100][32];int maxProduct(vectorstring words) {int n words.size();for(int i 0;i n;i){for(int j 0;j words[i].size();j){if(words[i][j] a || words[i][j] z) continue;int index words[i][j]- a;vv[i][index];}}int ans -0x3f3f3f3f;for(int i 0;i n;i){for(int j 0;j n;j){if(i j) continue;else{bool flag false;if(words[i].size() words[j].size()){for(int c 0;c words[i].size();c){int index words[i][c]- a;if(vv[i][index] vv[j][index]){flag true;break;}}}else{for(int c 0;c words[j].size();c){int index words[i][c]- a;if(words[i][c] a || words[i][c] z) continue;if(vv[i][index] vv[j][index]){flag true;break;}}}if(!flag) {int a words[i].size();int b words[j].size();ans max(ans,a * b);}}}}return ans -0x3f3f3f3f ? 0 : ans;}
}; 正确解法 利用int类型有32位刚好可以通过32位来映射对应的26位小写字母来达到 比如 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 来了一个字符串aaccb 那么就可以映射成 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 有些不喜欢思考的人还会问为什么aa这些都映射在一个地方呢 因为我们根据题目要求的是找到两个字符串中没有相同的字符 所以一个字符串有重复的字符就可以默认只有一个这样的字符 因为假设aab ,ac 和 ab , ac,一个字符串中少一个重复字符和多一个重复 字符没什么区别所以我们可以将一个字符串中的相同的字符直接映射到同一个位上 1代表该字符串有该字符0代表没有 映射完之后我们怎么办呢 //既然用到用整数进行状态压缩了那么我们就可以根据经验也就是位运算来判断了 1 1 1 0 0 0 0 0 --- aaabbc 1 0 1 0 0 0 0 0 --- aaaccc 两个数字一下可以得出一个数字 得到 这个数字代表的是两个字符串中相同的字符置为1不相同的字符置为0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 --- aaaccc 0 1 0 0 0 1 0 0 --- bbbffff 得到 这个数字代表的色两个字符串中相同的字符置为1不相同的字符置为0 0 0 0 0 0 0 0 0 那么我们得出一个结论
如果数字大于0说明两个字符串中有相同的字符
如果数字等于0说明两个字符串中没有相同的字符
本题还有一个很小很小的优化
就是双重循环的时候我们可以去重
假设
1 2 3 4
每个数只与前面的数进行判断那么就可以去除掉重复的组合了
class Solution {
public:int mask[1100];int maxProduct(vectorstring words) {int n words.size();for(int i 0;i n;i){for(int j 0;j words[i].size();j){mask[i] | (1 (words[i][j] - a));//状态压缩}}int ans -0x3f3f3f3f;for(int i 0;i n;i){for(int j 0;j i;j){if(!(mask[i] mask[j])){int a words[i].size();int b words[j].size();ans max(ans,a * b);}}}return ans -0x3f3f3f3f ? 0 : ans;}
};
