中级农民
- 积分
- 100
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2014-8-10
- 最后登录
- 1970-1-1
|
LS已经说的很好了,我就在补充几句顺便mark下复习用了:P 对lz quote的那个算法我看了下觉得有可能是因为跟leetcode里的题不太一样,那里的算法应该默认target是0,也就是他的3Sum实际是Leetcode里的4Sum。 对Ksum我的体会是总之就两种方法(hashmap或者用pointer),2sum哪种都行,反正都是Onlog(n);3sum可以sort+3pointer implement起来比较简单space还小然后两种都是O(n^2),4Sum用hashmap runtime更好可以到O(n^2),就是扫两边O(n^2)。下面是我4Sum的code,用的是hashmap的方法,很草,凑合看哈:
public class Solution {
public static List<List<Integer>> fourSum(int[] num, int target) {
if(num.length < 4) return new ArrayList<List<Integer>>();
// Arrays.sort(num);
// for(int i = 0; i < num.length; i++) System.out.print(num[i]+" ");
// System.out.println();
HashMap<Integer, HashSet<ArrayList<Integer>>> dict = new HashMap<Integer, HashSet<ArrayList<Integer>>>();
HashSet<ArrayList<Integer>> res = new HashSet<ArrayList<Integer>>();
for(int i = 0; i < num.length-1; i++) {
for(int j = i+1; j < num.length; j++) {
// System.out.println(num[i]+num[j]+" "+i+" "+j);
if(!dict.containsKey(num[i]+num[j])) {
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(i, j));
HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();
set.add(list);
dict.put(num[i]+num[j],set);
}
else{
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(i, j));
if(!dict.get(num[i]+num[j]).contains(list)) {
dict.get(num[i]+num[j]).add(list);
// System.out.println(dict.get(num[i]+num[j]));
}
}
}
}
for(int i = 0; i < num.length-1; i++) {
// while(num[i+1] == num[i]) i++;
for(int j = i+1; j < num.length; j++) {
// while (j != num.length-1 && num[j+1] == num[j]) {
// j++;
// }
if(dict.containsKey(target-num[i]-num[j])) {
HashSet<ArrayList<Integer>> set = dict.get(target-num[i]-num[j]);
for(ArrayList<Integer> list : set) {
int a = list.get(0);
int b = list.get(1);
int[] ids = new int[]{a,b,i,j};
Arrays.sort(ids);
boolean flag = true;
for(int x = 0; x < 3; x++) {
if(ids[x] == ids[x+1]) flag = false;
}
if(flag) {
ArrayList<Integer> comb = new ArrayList<Integer>(Arrays.asList(num[i],num[j],num[a],num[b]));
Collections.sort(comb);
if(!res.contains(comb)) {
res.add(comb);
// System.out.print(num[i]+num[j]-target+" ");
// System.out.print(a+" "+b+" "+i+" "+j);
// System.out.println();
}
} else continue;
}
}
}
}
// List<List<Integer>> result = new ArrayList<List<Integer>>(res);
List<List<Integer>> result = new ArrayList<List<Integer>>();
for(List<Integer> list : res) {
result.add(list);
}
return result;
}
}
作为对比,下面是我写3Sum的code,用的是3pointer:
public class Solution {
public List<List<Integer>> threeSum(int[] num) {
Arrays.sort(num);
List<List<Integer>> res = new ArrayList<List<Integer>>();
for(int i = 0; i < num.length-1; i++) {
if(i > 0 && num[i] == num[i-1]) continue;
int start = i+1;
int end = num.length-1;
while(start < end) {
if(num[start]+num[end]==-num[i]) {
List<Integer> list = new ArrayList<Integer>();
list.add(num[i]);
list.add(num[start]);
list.add(num[end]);
res.add(list);
start++;
end--;
while (start < end && num[end] == num[end + 1])
end--;
while (start < end && num[start] == num[start - 1])
start++;
} else if(num[start]+num[end]>-num[i]) {
end--;
} else start++;
}
}
return res;
}
}
Buy stocks K次这个问题是不是有点太generalize了,我感觉这种问题要不就问你没有次数限制要不就是1,2次的,现场做K次是不是有点太难了,尤其考这题的都是bank,这难度他们犯不着吧:P不过我觉得LS的思路是很对的,ls要是有这题的link我可以试着implement一下给你看。我比较水,说的不对请指正哈哈 |
|