题目一：给定两个数组，编写一个函数来计算它们的交集。
解法1：哈希表
public int[] intersect(int[] nums1, int[] nums2) {
/**
降低空间复杂度
*/
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
Map<Integer, Integer> map = new HashMap<>();
// 得到数组1 元素出现次数
for (int i : nums1) {
if (map.containsKey(i)) {
map.put(i, map.get(i) + 1);
} else {
map.put(i, 1);
}
}
int[] res = new int[nums1.length];
int index = 0;
// 遍历数组2，map 中元素每出现一次，map 中次数 -1
for (int i : nums2) {
if (map.containsKey(i)) {
res[index++] = i;
Integer count = map.get(i);
if (count - 1 > 0) {
map.put(i,count -1);
} else {
map.remove(i);
}
}
}
return Arrays.copyOf(res, index);
}
解法2：排序
public static int[] intersect(int[] nums1, int[] nums2) {
// 排序
Arrays.sort(nums1);
Arrays.sort(nums2);
// 双指针
int index1 = 0;
int index2 = 0;
int length1 = nums1.length;
int length2 = nums2.length;
int[] res = new int[length1 < length2 ? length1 : length2];
int index = 0;
while (index1 < length1 && index2 < length2) {
int num2 = nums2[index2];
int num1 = nums1[index1];
if (num1 < num2) {
index1++;
} else if (num1 == num2) {
res[index] = num1;
index++;
index1++;
index2++;
} else {
index2++;
}
}
return Arrays.copyOf(res, index);
}
题目二：移动石子直到连续
三枚石子放置在数轴上，位置分别为 a，b，c。每一回合，我们假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]
题目分析：
有以下情况：
- 三个数连续，此时minimum_moves = 0
- 三个数有两个连续或间隔为1，此时minimum_moves = 1
- 三个数间隔均大于2，此时minimum_moves = 2
public static int[] numMovesStones(int a, int b, int c) {
// 排序
int x = a < b ? (a < c ? a : c) : (b < c ? b : c);
int z = a > b ? (a > c ? a : c) : (b > c ? b : c);
int y = a + b + c - x - z;
int[] res = new int[2];
res[0] = (y - x > 2 && z - y) > 2 ? 2 : z - x == 2 ? 0 : 1;
// 最大次数为三数间空位
res[1] = z - x - 2;
return res;
}