以后看到个数比较少,性能比较高,就要第一时间想到位操作!
这道题目mock没有通过。超时了。。。。。。
原来题目解法的思路非常非常好！
开始我关注于降低n*n的复杂度,但是这道题目复杂度高在每个字符串长,所以一定要问清楚题目 新做的记录：
package com.company; import java.util.*;
import java.util.List; class Solution {
public int maxProduct(String[] words) {
// int是32位,足够处理了。真的很牛逼
// 以后看到个数比较少,性能比较高,就要第一时间想到位操作!
// 开始我关注于降低n*n的复杂度,但是这道题目复杂度高在每个字符串长,所以一定要问清楚题目
List<Integer> ilist = new ArrayList<>();
for (int i=0; i<words.length; i++) {
int nb = 0;
for (int j=0; j<words[i].length(); j++) {
nb |= 1 << (words[i].charAt(j) - 'a');
}
ilist.add(nb);
}
int ret = 0;
for (int i=0; i<words.length; i++) {
for (int j=i+1; j<words.length; j++) {
if ((ilist.get(i) & ilist.get(j)) == 0) {
if (words[i].length() * words[j].length() > ret) {
ret = words[i].length() * words[j].length();
}
}
}
}
return ret;
}
} public class Main { public static void main(String[] args) {
// write your code here
System.out.println("Hello");
Solution solution = new Solution(); String[] words= {"cdea","bdd"};
int ret = solution.maxProduct(words);
System.out.printf("Get ret: %d\n", ret); }
}
原来做过的记录
https://leetcode.com/problems/maximum-product-of-word-lengths/ // 我在尽量做到比n*n效率更高
// 对比new solution和previous solution
// new solution 是纯n*n，优化在字符串比较
// 对于大数据，耗时0ms
// previous solution理论上比n*n要快，
// 但是因为涉及vector的频繁增删、复制
// 实际要慢的多，对于大数据耗时800+ms // 总的来看，stl container的复制、删除等，耗时很大 class Solution {
vector<pair<int, int>> vec;
vector<string> words;
int **DP;
// 比较的好方法
int *bits; static bool my_compair(const string &a, const string &b) {
if (a.size() > b.size()) {
return true;
}
else {
return false;
}
} void insert(int i, int j) {
int f = words[i].size() * words[j].size(); int vlen = vec.size();
int begin = 0;
int end = vlen - 1; int mid;
int tmp;
while (begin <= end) {
mid = (begin + end) / 2;
tmp = words[vec[mid].first].size() * words[vec[mid].second].size(); if (f == tmp) {
begin = mid + 1;
break;
}
else if (f > tmp) {
end = mid - 1;
}
else {
begin = mid + 1;
}
}
vec.insert(vec.begin()+begin, make_pair(i, j));
} int valid(int i, int j) {
if ((bits[i] & bits[j]) != 0) {
return 0;
}
return words[i].size() * words[j].size();
} public:
int maxProduct(vector<string>& w) {
words = w; int wlen = words.size();
if (wlen == 0) {
return 0;
}
sort(words.begin(), words.end(), my_compair); // 初始化bits
bits = new int[wlen];
memset(bits, 0, sizeof(int)*wlen);
for (int i=0; i<wlen; i++) {
string wstr = words[i];
int slen = wstr.size();
for (int j=0; j<slen; j++) {
bits[i] |= 1 << (wstr[j]-'a');
}
} // new solution(0 ms for big test case)
int result = 0;
for (int i=0; i<wlen-1; i++) {
for (int j=i+1; j<wlen; j++) {
if ((bits[i]&bits[j]) == 0) {
int tmp = words[i].size() * words[j].size();
if (tmp > result) {
result = tmp;
}
}
}
}
return result; // previous solution (800ms for big test case)
DP = new int*[wlen];
for (int i=0; i<wlen; i++) {
DP[i] = new int[wlen];
// 注意，new出来的数据初始值，不一定为0
memset(DP[i], 0, sizeof(int)*wlen);
} // 根据相乘的长度排序
vec.push_back(make_pair(0, 1));
DP[0][1] = 1; int fir;
int sec;
int tmp; while (!vec.empty()) {
fir = vec[0].first;
sec = vec[0].second;
vec.erase(vec.begin()); tmp = valid(fir, sec);
if (tmp > result) {
result = tmp;
} if (fir + 1 < sec && DP[fir+1][sec] == 0 &&
words[fir+1].size() * words[sec].size() > result) {
insert(fir+1, sec);
DP[fir+1][sec] = 1;
}
if (sec + 1 < wlen && DP[fir][sec+1] == 0 &&
words[fir].size() * words[sec+1].size() > result) {
insert(fir, sec+1);
DP[fir][sec+1] = 1;
}
}
return result;
}
}; // 下面是我在 Mock里面做的，超时了。重来。
package com.company; import java.awt.*;
import java.util.*;
import java.util.List; class Solution {
public int maxProduct(String[] words) {
// 直接用n*n*size的方法肯定不好
// 注意限制条件, lower case的字符 Map<Integer, Set<Integer>> mp = new HashMap<>(); List<Integer> clist = new ArrayList<>(); for (int i=0; i<words.length; i++) {
clist.add(i); // 过滤
char[] chs = words[i].toCharArray();
Set<Integer> wSet = new HashSet();
for (char ch :chs) {
wSet.add(ch - 'a');
}
Iterator<Integer> iter = wSet.iterator();
while (iter.hasNext()) {
int key = iter.next();
if (!mp.containsKey(key)) {
Set<Integer> st = new HashSet<>();
st.add(i);
mp.put(key, st);
}
else {
Set<Integer> st = mp.get(key);
st.add(i);
mp.put(key, st);
}
} } int ret = 0;
for (int i=0; i<words.length; i++) {
Set<Integer> oSet = new HashSet<>(clist);
char[] chs = words[i].toCharArray();
Set<Integer> wSet = new HashSet();
for (char ch :chs) {
wSet.add(ch - 'a');
}
Iterator<Integer> iter = wSet.iterator();
while (iter.hasNext()) {
int key = iter.next();
Set<Integer> st = mp.get(key);
oSet.removeAll(st);
}
iter = oSet.iterator();
while (iter.hasNext()) {
int index = iter.next();
if (words[i].length() * words[index].length() > ret) {
ret = words[i].length() * words[index].length();
}
}
}
return ret; }
} public class Main { public static void main(String[] args) {
// write your code here
System.out.println("Hello");
Solution solution = new Solution(); String[] words= {};
int ret = solution.maxProduct(words);
System.out.printf("Get ret: %d\n", ret); }
}