这是个典型的 data structure design trade off 问题,因为 add() 和 find() 函数总有一个会很慢,问题在于让那个慢,就要取决于具体的 workload. 真问到这种问题一定要先问清楚。
需要注意的 corner case 是,[add(0), find(0)],这类情况,还有 [add(2), add(2), find(4)] 这类。
Quick-Find:
publicclassTwoSum {HashSet<Integer> num =newHashSet<>();HashSet<Integer> sum =newHashSet<>();// Add the number to an internal data structure.publicvoidadd(int number) {if(num.contains(number)) {sum.add(number *2); } else {Iterator<Integer> iter =num.iterator();while(iter.hasNext()){int num =iter.next();sum.add(num + number); }num.add(number); } }// Find if there exists any pair of numbers which sum is equal to the value.publicbooleanfind(int value) {returnsum.contains(value); }}
事实证明,拿到 iterator 手动 iter.next 要比直接用 enhanced for loop 快。
Quick-Add:
publicclassTwoSum {HashMap<Integer,Integer> map =newHashMap<Integer,Integer>();// Add the number to an internal data structure.publicvoidadd(int number) {if(map.containsKey(number)){map.put(number,2); } else {map.put(number,1); } }// Find if there exists any pair of numbers which sum is equal to the value.publicbooleanfind(int value) {Iterator<Integer> iter =map.keySet().iterator();while(iter.hasNext()){int key =iter.next();if(map.containsKey(value - key)){if(key != value - key ||map.get(key) ==2) returntrue; } }returnfalse; }}
每个单词后面的空格数为标准 space + extra,其中 space 默认为 1, extra 默认为 0;
如果不是一行只有一个单词的情况,则根据 gap 数计算 space 与 extra 值;
space = (剩余空间 / gap 数) + 1;
extra = (剩余空间 % gap 数);
启动 StringBuilder,先把第一个单词填上;
而后进入循环按照 space 与 extra 数填充;extra 最坏情况下也只会在一个单词后面多加上一个;
如果是一个单词一行的情况,则计算剩余空白,都填上空格。
设立新起点,新一轮扫描。
publicclassSolution {publicList<String> fullJustify(String[] words,int maxWidth) {List<String> list =newArrayList<String>();int N =words.length;int right =0;for(int left =0; left < N; left = right){// Each word comes with one space;// Except the first word, so start with -1.int len =-1;for(right = left; right < N && len + words[right].length() +1<= maxWidth; right ++){ len += words[right].length() +1; }// Those are in case there's only one word picked, or in last lineint space =1;int extra =0;if(right != left +1&& right != N){// right - left - 1 is number of gaps space = (maxWidth - len) / (right - left -1) +1; extra = (maxWidth - len) % (right - left -1); }StringBuilder sb =newStringBuilder(words[left]);for(int i = left +1; i < right; i++){for(int j =0; j < space; j++) sb.append(' ');if(extra-->0) sb.append(' ');sb.append(words[i]); }int rightSpace = maxWidth -sb.length();while(rightSpace-->0) sb.append(' ');list.add(sb.toString()); }return list; }}