今天主要刷hash table的题目，主要按照frequency从高到低的顺序。
- two sum: 使用HashMap
- 3 sum： 一开始以为是简单的for loop➕two sum的解法，但实际上把代码写出来后发现自己完全忽视了duplicates的情况。对于有duplicate的情况，一般需要先把arrray排序。
加入重复性考虑后，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多了一个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转化为固定长度的array来表示可以节省一些时间。 - Single Number
所有数都出现两次，除了一个数只出现一次。
第一反应是a ^ a = 0
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int n: nums) {
res ^= n;
}
return res;
}
}
但鉴于这是一个hash table的问题，再用繁琐一点的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;
}
}
