今天主要刷hash table的題目宝踪，主要按照frequency從高到低的順序。
- two sum: 使用HashMap
- 3 sum： 一開始以為是簡單的for loop?two sum的解法碍扔，但實(shí)際上把代碼寫出來后發(fā)現(xiàn)自己完全忽視了duplicates的情況瘩燥。對于有duplicate的情況，一般需要先把a(bǔ)rrray排序不同。
加入重復(fù)性考慮后厉膀，pseudocode變成這樣：
// sort the array
Arrays.sort(nums)
for i = 0 to nums.length-2:
low = i+1, high = nums.length-1;
// skip duplicates
if (i == 0 || (i > 0 && nums[i] == nums[i-1]:
while (low < high) :
sum = nums[i] + nums[low] + nums[high]
if (sum == 0):
add to the result
// doing skipping duplicates here
low++; high--;
else if (sum < 0):
// doing skipping duplicates here
low++
else:
// doing skipping duplicates here
high--;
最后放上完整的代碼：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
// skip duplicates
if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
int low = i+1, high = nums.length-1, sum = 0 - nums[i];
while (low < high) {
if (nums[low] + nums[high] == sum) {
res.add(Arrays.asList(new Integer[]{nums[i], nums[low], nums[high]}));
// skip duplicates
while (low < high && nums[low] == nums[low+1]) {
low++;
}
while (low < high && nums[high] == nums[high-1]) {
high--;
}
low++;
high--;
} else if (nums[low] + nums[high] < sum) {
// skip duplicates
while (low < high && nums[low] == nums[low+1]) {
low++;
}
low++;
} else {
// skip duplicates
while (low < high && nums[high] == nums[high-1]) {
high--;
}
high--;
}
}
}
}
return res;
}
}
- 4 Sum: 思路基本和3 Sum相同，就是比3 Sum多了一個(gè)for loop
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 3; i++) {
if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
for (int j = i+1; j < nums.length - 2; j++) {
if (j == i+1 || (j > i+1 && nums[j] != nums[j-1])) {
int lo = j+1, hi = nums.length-1, sum = target-nums[i]-nums[j];
while (lo < hi) {
if (nums[lo] + nums[hi] == sum) {
res.add(Arrays.asList(new Integer[]{nums[i], nums[j], nums[lo], nums[hi]}));
while (lo < hi && nums[lo] == nums[lo+1]) {
lo++;
}
while (lo < hi && nums[hi] == nums[hi-1]) {
hi--;
}
lo++;
hi--;
} else if (nums[lo] + nums[hi] < sum) {
while (lo < hi && nums[lo] == nums[lo+1]) {
lo++;
}
lo++;
} else {
while (lo < hi && nums[hi] == nums[hi-1]) {
hi--;
}
hi--;
}
}
}
}
}
}
return res;
}
}
- Jewels and Stones
把只包含字母的string轉(zhuǎn)化為固定長度的array來表示可以節(jié)省一些時(shí)間二拐。 - Single Number
所有數(shù)都出現(xiàn)兩次逢渔，除了一個(gè)數(shù)只出現(xiàn)一次。
第一反應(yīng)是a ^ a = 0
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int n: nums) {
res ^= n;
}
return res;
}
}
但鑒于這是一個(gè)hash table的問題系奉，再用繁瑣一點(diǎn)的hash table解法來做一次矮瘟。但是慢多了。
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int n: nums) {
if (map.containsKey(n)) {
map.remove(n);
} else {
map.put(n,1);
}
}
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
return entry.getKey();
}
return 0;
}
}
