给定一个string数组dic,代表单词列表,同时给定列表的长度n,请返回最大子矩阵的面积,其中子矩阵中的行和列相同,且有相同字母组成。保证单词的大小小于等于50,且某一长度的串的数量小于等于12。
测试样例:
["aaa","aaa","aaa","bb","bb"]
返回:9
//game over import java.util.*; public class AlphaMatrix { public int findAlphaMatrix(String[] dic, int n) { // write code here if(n < 1) return 0; int res = 0; HashMap<String,Integer> map = new HashMap<>(); for(int i = 0; i < n ; i++) { if(map.containsKey(dic[i])) { map.put(dic[i], map.get(dic[i]) + 1); res = Math.max(res, map.get(dic[i]) * dic[i].length()); }else { map.put(dic[i], 1); res = Math.max(res, dic[i].length()); } } return res; } }
//利用HashMap中键的唯一性 import java.util.*; public class AlphaMatrix { public int findAlphaMatrix(String[] dic, int n) { int result = 0; HashMap<String, Integer> map = new HashMap<>(); for(int i=0; i<dic.length; i++){ if(!map.containsKey(dic[i])) map.put(dic[i], 1); else map.put(dic[i], map.get(dic[i])+1); } for(int i=0; i<dic.length; i++) result = Math.max(result, map.get(dic[i])*dic[i].length()); return result; } } /*吐槽:你在测试用例里加个中文逗号,eclipse都编译不了,你让我怎么通过,不带这么欺负人的 case通过率为96.77% 测试用例: ["abcdef","abcdef","abcdef","aaa","ccc","ddd","eee","fff"],8 对应输出应该为: 18 你的输出为: 15 */
class AlphaMatrix { public: int findAlphaMatrix(vector<string> dic, int n) { if(n<1) return 0; int Max = 0; map<string,int> m; for(int i=0;i<n;i++){ int l = dic[i].length(); if(m.find(dic[i]) != m.end()){ m[dic[i]]++; Max = max(Max, l*m[dic[i]]); }else{ m[dic[i]] = 1; Max = max(Max, l*m[dic[i]]); } } return Max; } };
class AlphaMatrix { public: int max(int a,int b) { return a>b?a:b; } int findAlphaMatrix(vector<string> dic, int n) { // write code here int res=0; map<string,int> tmp; for(int i=0;i<n;i++) { tmp[dic[i]]++; int curArea=dic[i].length()*tmp[dic[i]]; res=max(curArea,res); } return res; } };
class AlphaMatrix: def findAlphaMatrix(self, dic, n): for x in dic: k = len(x) if k in self.d: self.d[k].append(x) else: self.d[k] = [x] l = max(self.d.keys()) for z in xrange(l * l, -1, -1): for i in xrange(1, l + 1): if z % i == 0: j = z / i if j <= l and (i in self.d and j in self.d): if j not in self.m: self.m[j] = Node(self.d.get(j, [])) # 构建字典树 tree = self.m[j] if self.makeRect(i, j, [], tree) is not None: return z return 0 def __init__(self): self.d = {} # 长度->字符串序列 self.m = {} # 长度->字典树 def makeRect(self, w, h, A, tree): if len(A) == h: return A for x in self.d[w]: B = list(A) B.append(x) if self.checkRow(w, B, tree): #检查列单词是否在字典树里 t = self.makeRect(w, h, B, tree) if t: return t def checkRow(self, w, A, tree): for i in range(w): d = [] for j in range(len(A)): d.append(A[j][i]) if not tree.exist(d): return False return True class Node(): # Trie树 def __init__(self, arrStr=[]): self.child = {} # 字母->子节点 for str in arrStr: self.insert(str) def insert(self, str): p = self for c in str: if c not in p.child: p.child[c] = Node() p = p.child[c] def exist(self, d): # 检查单词是否是该字典树的前缀 p = self for c in d: if c not in p.child: return False p = p.child[c] return True
//能够组成矩阵的必定是单词一样的 public int findAlphaMatrix(String[] dic, int n) { // write code here //利用hashmap统计重复单词数,再从中挑出能组成矩阵的最大值 Map<String, Integer> hash=new HashMap<String, Integer>(); int Max=Integer.MIN_VALUE; for (int i = 0; i < n; i++) { if (hash.containsKey(dic[i])) { hash.put(dic[i], hash.get(dic[i])+1); }else { hash.put(dic[i], 1); } Max=Math.max(Max,dic[i].length()*hash.get(dic[i]) ); } return Max; }
这哪里是DP啊
import java.util.*; public class AlphaMatrix { public int findAlphaMatrix(String[] dic, int n) { HashMap<String, Integer> set = new HashMap<>(); for (int i = 0;i < dic.length; ++ i) set.put(dic[i], set.containsKey(dic[i]) ? set.get(dic[i]) + 1 : 1); int max = -1; for (String s : set.keySet()){ if (set.get(s) * s.length() > max){ max = set.get(s) * s.length(); } } return max; } }
//题目表述的真是一点都不清晰啊,就是找出现次数最多的那个单词,然后面积就是 //这个单词出现的次数*单词长度 class AlphaMatrix { public: int findAlphaMatrix(vector<string> dic, int n) { map<string,int> mapp; int res=0; for(int i=0;i<n;i++) { mapp[dic[i]]++; int t=dic[i].length()*mapp[dic[i]]; res=max(res,t); } return res; } };
public int findAlphaMatrix(String[] dic, int n) {
int[] rows = new int[n];
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
rows[i] = dic[i].length();
for (int i = 1; i < n; i++) {
if (dic[i].equals(dic[i-1]))
rows[i] += rows[i - 1];
max = Math.max(max, rows[i]);
}
return Math.max(max, rows[0]);
} //1、建立一个数组rows[n],存放每个字符串的长度
//2、从1--n-1,判断相邻两个字符串是否相等,若相等,更新rows[i]=rows[i-1]+rows[i],否则,rows[i]为该字串的长度,不变
//3、最大字母矩阵面积即为max(rows[i])(i=0,,,n-1);
return 0
题目说得不清楚啊,试过之后,发现是需要完全相同的单词才行,而串长度相同,串不一样也不行。 为了方便,使用了map。 class AlphaMatrix { public: int findAlphaMatrix(vector<string> dic, int n) { int i=0; map<string,int> count; int m=0; for(i=0;i<n;i++) { count[dic[i]]++; if(count[dic[i]]*dic[i].length()>m) { m=count[dic[i]]*dic[i].length(); } } return m; } };