首页 > 代码库 > 好!maximum-product-of-word-lengths
好!maximum-product-of-word-lengths
以后看到个数比较少,性能比较高,就要第一时间想到位操作!
这道题目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); } }
好!maximum-product-of-word-lengths
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。