优势洗牌（田忌赛马）
解题思路：原则是自己差的匹配对面最好的，好的匹配对面差的。
注意点：做比较，首先需要对两个数组进行排序，这会导致位置错乱，要想怎么去记录位置，我首先是用 HashMap 记录，但是无法处理重复值，然后看别人解题思路，学到了可以用二维数组来记录原来的数的位置，这样就可以分别相同的数
// https://leetcode-cn.com/problems/advantage-shuffle/
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
// 排序 nums1
Arrays.sort(nums1);
int n = nums1.length;
// 排序 nums2，注意sort2第一维度是值，第二维度是nums2中值的位置，保证了值得唯一性
int[][] sort2 = new int[n][2];
for (int i = 0; i < n; i ++) {
sort2[i] = new int[] {nums2[i], i};
}
// 注意按第一维度排序得写法
Arrays.sort(sort2, (a,b)->(a[0]-b[0]));
int[] res = new int[n];
int left = 0;
int right = n - 1;
for (int i = 0; i < n ; i ++) {
// 如果nums1对应位置的值大于sort2的，就记录下，小就为它匹配sort2中最大的值
if (nums1[i] <= sort2[left][0]) {
res[sort2[right--][1]] = nums1[i];
} else {
res[sort2[left++][1]] = nums1[i];
}
}
return res;
}
}
Reference:
- https://leetcode-cn.com/problems/advantage-shuffle/solution/java-tian-ji-sai-ma-by-ou-bi-jie-85ot/
- https://labuladong.gitee.io/algo/2/21/46/
二分查找
二分法主要是考虑边界情况，比如给 mid 加一减一还是直接等于等于 mid（如果 mid 位置的值会出现在下次判断的范围内，则直接等于 mid，否则对 mid 进行加一减一），while 循环中是用 <= 还是 <（如果 left 允许等于 right，那么就用 <=，不允许相等就用 <）。一般模板如下：
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
二分查找
// https://leetcode-cn.com/problems/binary-search/
// 搜索一个元素
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return -1;
}
}
在排序数组中查找元素的第一个和最后一个位置
// 个人认为这种方案好一点，设置个值判断是否修改过，比下面的判断更方便点
// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/dai-ma-sui-xiang-lu-34po-shi-wu-hua-de-e-6t89/
// 寻找左边界
// 二分查找，寻找target的左边界leftBorder（不包括target）
// 如果leftBorder没有被赋值（即target在数组范围的右边，例如数组[3,3],target为4），为了处理情况一
int getLeftBorder(vector<int>& nums, int target) {
int left = 0;
int right = nums.length - 1; // 定义target在左闭右闭的区间里，[left, right]
int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
while (left <= right) {
int mid = left + ((right - left) / 2);
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) { // 寻找左边界，就要在nums[middle] == target的时候更新right
right = mid - 1;
leftBorder = right;
} else {
left = mid + 1;
}
}
return leftBorder;
}
// 二分查找，寻找target的右边界（不包括target）
// 如果rightBorder为没有被赋值（即target在数组范围的左边，例如数组[3,3]，target为2），为了处理情况一
int getRightBorder(vector<int>& nums, int target) {
int left = 0;
int right = nums.length - 1; // 定义target在左闭右闭的区间里，[left, right]
int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
while (left <= right) { // 当left==right，区间[left, right]依然有效
int mid = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) { // 当nums[middle] == target的时候，更新left，这样才能得到target的右边界
left = mid + 1;
rightBorder = left;
} else {
left = mid + 1;
}
}
return rightBorder;
}
// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// 查找左边界
int left_bound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid - 1; // 锁定左边界
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
// 检查 left 的越界情况
if (left >= nums.length || nums[left] != target) return -1;
return left;
}
// 查找右边界
int right_bound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 锁定右边界
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
// 检查 left 的越界情况
if (right < 0 || nums[right] != target) return -1;
return right;
}
二分查找的扩展
爱吃香蕉的珂珂
// https://leetcode-cn.com/problems/koko-eating-bananas/
class Solution {
public int minEatingSpeed(int[] piles, int h) {
Arrays.sort(piles);
int n = piles.length;
// 左边范围我一开始是 piles[0]，这样无法处理数组中只有一个元素的情况，所以应该把他设置成 1
int left = 1;
int right = piles[n - 1];
while (left <= right) {
int mid = left + (right - left) / 2;
// 区别变化随题意更改
if (countSum(piles, mid) == h) {
right = mid - 1;
} else if (countSum(piles, mid) < h) {
right = mid - 1;
} else if (countSum(piles, mid) > h) {
left = mid + 1;
}
}
// 此处，在正常的找左边界时，是考虑越界情况，但是此题不需要考虑其边界情况，因为在初始化的时候我规定了上限，而且当每次吃上限时肯定符合。
// 这句是根据题意变化的异常处理的代码，需要注意
// ...
return left;
}
int countSum(int[] piles, int k) {
int res = 0;
for (int i : piles) {
res += i / k;
if (i % k != 0) {
res += 1;
}
}
return res;
}
}
在 D 天内送达包裹的能力
// https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
class Solution {
public int shipWithinDays(int[] weights, int days) {
int max = 0;
for (int i : weights) {
max = Math.max(max, i);
}
int left = max;
int right = 5 * 10000 * 500;
while (left <= right) {
int mid = left + (right - left) / 2;
if (getTotalDay(weights, mid) == days) {
right = mid - 1;
} else if (getTotalDay(weights, mid) < days) {
right = mid - 1;
} else if (getTotalDay(weights, mid) > days) {
left = mid + 1;
}
}
return left;
}
int getTotalDay(int[] weights, int E) {
int tmp = E;
int res = 0;
for (int i : weights) {
if (tmp >= i) {
tmp -= i;
} else {
res += 1;
tmp = E - i;
}
}
return res + 1;
}
}
分割数组的最大值
// https://leetcode-cn.com/problems/split-array-largest-sum/
//
class Solution {
public int splitArray(int[] nums, int m) {
int max = 0;
for (int i : nums) {
max = Math.max(max, i);
}
int sum = 0;
for (int i : nums) {
sum += i;
}
int left = max;
int right = sum;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arraysCount(nums, mid) == m) {
right = mid - 1;
} else if (arraysCount(nums, mid) < m) {
right = mid - 1;
} else if (arraysCount(nums, mid) > m) {
left = mid + 1;
}
}
return left;
}
int arraysCount(int[] nums, int sum) {
int res = 0;
int tmp = sum;
for (int i : nums) {
if (tmp >= i) {
tmp -= i;
} else {
res += 1;
tmp = sum - i;
}
}
return res + 1;
}
}
删除查找数组元素
O(1) 时间插入、删除和获取随机元素
// https://leetcode-cn.com/problems/insert-delete-getrandom-o1/
// 要完成 O(1) 的删、查，需要 HashMap 的删、查和 ArrayList 的获得随机值结合，主要思路是用哈希表记录值对应的数组的下标，从而通过哈希表快速定位到数组中，获取随机值
class RandomizedSet {
List<Integer> lis = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
Random rand = new Random();
/** Initialize your data structure here. */
public RandomizedSet() {
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (!map.containsKey(val)) {
map.put(val, lis.size());
lis.add(lis.size(), val);
return true;
} else {
return false;
}
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
} else {
int idx = map.get(val);
int lastElement = lis.get(lis.size() - 1);
map.put(lastElement, idx);
lis.set(idx, lastElement);
map.remove(val);
lis.remove(lis.size() - 1);
return true;
}
}
/** Get a random element from the set. */
public int getRandom() {
return lis.get(rand.nextInt(lis.size()));
}
}
黑名单中的随机数
// https://leetcode-cn.com/problems/random-pick-with-blacklist/)
// 需要维护黑名单，维护白名单就会超出空间限制
class Solution {
Map<Integer, Integer> map = new HashMap<>();
Random rand = new Random();
int len;
public Solution(int n, int[] blacklist) {
len = n - blacklist.length;
// 使用 HashSet 获取下标
Set<Integer> set = new HashSet<>();
for (int i = len; i < n; i++) {
set.add(i);
}
// 获取 Set 中不是黑名单的值
for (int b : blacklist) {
set.remove(b);
}
// 使用迭代器
Iterator<Integer> iter = set.iterator();
// 将黑名单中小于 len 的值进行映射 Set 中不是黑名单的值
for (int b : blacklist) {
if (b < len) {
map.put(b, iter.next());
}
}
}
public int pick() {
int index = rand.nextInt(len);
// 所有正常值都在前面（或直接，或用 Map 映射）
return map.getOrDefault(index, index);
}
}
// 官方解法
Reference:
- https://labuladong.gitee.io/algo/2/21/
- https://leetcode-cn.com/problems/