- Intersection of Two Arrays
求两个array的intersection，恰好昨天刚想了想这个问题，一个方法是A的每个元素和B的每个元素做对比，这种情况下复杂度为O(n^2), 并且还要考虑到重复元素的问题，用HashSet来解决可能有重复的问题。
另一种方法是先将两个array排序，在用两个pointer挪动来获得intersection，时间复杂度是O(n lg n)。但这种情况下一定要注意重复的问题。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0, j = 0;
List<Integer> list = new ArrayList<>();
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
list.add(nums1[i]);
while (i < nums1.length - 1 && nums1[i] == nums1[i+1]) {
i++;
}
while (j < nums2.length - 1 && nums2[j] == nums2[j+1]) {
j++;
}
i++;
j++;
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
int[] res = new int[list.size()];
int k = 0;
for (int e: list) {
res[k] = e;
k++;
}
return res;
}
}
- Largest Number
需要比较ab大还是ba大，就把这两个concat起来再比较。
答案中比较好的方法是把他们作为String来进行比较，而不要转化为integer。
因为原来是个int array，也必须要转化为integer array才能利用comparator进行比较。
class Solution {
private class LargerNumberComparator implements Comparator<String> {
@Override
public int compare(String a, String b) {
String order1 = a + b;
String order2 = b + a;
return order2.compareTo(order1);
}
}
public String largestNumber(int[] nums) {
// Get input integers as strings.
String[] asStrs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
asStrs[i] = String.valueOf(nums[i]);
}
// Sort strings according to custom comparator.
Arrays.sort(asStrs, new LargerNumberComparator());
// If, after being sorted, the largest number is `0`, the entire number
// is zero.
if (asStrs[0].equals("0")) {
return "0";
}
// Build largest number from sorted array.
String largestNumberStr = new String();
for (String numAsStr : asStrs) {
largestNumberStr += numAsStr;
}
return largestNumberStr;
}
}
- Valid Anagram
判断s是否是t的permutation。
先检查两者的长度是否相同。
因为只包含lower case，可以用一个array来记录每个character出现的次数。
traverse s的时候增加，traverse t的时候减少。当其中有个数量小于0，返回false。
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] chars = new int[26];
for (char c: s.toCharArray()) {
int index = c - 'a';
chars[index] += 1;
}
for (char c: t.toCharArray()) {
int index = c - 'a';
chars[index] -= 1;
if (chars[index] < 0) {
return false;
}
}
return true;
}
}
- Maximum Gap
bucket sort
t = (max - min)/(n-1)
t 是所有元素的平均距离，至少有两个元素的距离比t要大，因此我们要找的maximum gap肯定不会存在于同一个bucket中的两个元素，而是相邻的两个bucket。
class Solution {
public int maximumGap(int[] nums) {
if (nums.length < 2) {
return 0;
}
int minNum = Integer.MAX_VALUE, maxNum = Integer.MIN_VALUE;
for (int num: nums) {
minNum = Math.min(minNum, num);
maxNum = Math.max(maxNum, num);
}
// consider about the case all are the same
int bucketSize = Math.max(1, (maxNum - minNum) / (nums.length - 1));
// need to +1 to store the maximum element
int numOfBucket = (maxNum - minNum)/bucketSize + 1;
// store the maximum element of the bucket
int[] max = new int[numOfBucket];
int[] min = new int[numOfBucket];
Arrays.fill(max, Integer.MIN_VALUE);
Arrays.fill(min, Integer.MAX_VALUE);
for (int num: nums) {
int i = (num - minNum) / bucketSize;
max[i] = Math.max(max[i], num);
min[i] = Math.min(min[i], num);
}
int pre = max[0];
int maxGap = 0;
for (int j = 1; j < numOfBucket; j++) {
if (pre == Integer.MIN_VALUE) {
pre = max[j];
} else {
if (min[j] == Integer.MAX_VALUE) {
continue;
} else {
maxGap = Math.max(maxGap, min[j] - pre);
pre = max[j];
}
}
}
return maxGap;
}
}
