LeetCode算法小抄--田忌赛马问题、游戏随机匹配机制问题
LeetCode算法小抄--田忌赛马问题、游戏随机匹配机制问题
-
-
- 田忌赛马问题
-
- [870. 优势洗牌](https://leetcode.cn/problems/advantage-shuffle/)
- 带权重的随机选择算法
-
- 算法框架
- [528. 按权重随机选择](https://leetcode.cn/problems/random-pick-with-weight/)[Cisco笔试题]
- [剑指 Offer II 071. 按权重生成随机数](https://leetcode.cn/problems/cuyjEf/)
-
⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计4077字,阅读大概需要3分钟
🌈更多学习内容, 欢迎👏关注👀【文末】我的个人微信公众号:不懂开发的程序猿
个人网站:https://jerry-jy.co/
田忌赛马问题
870. 优势洗牌
给定两个大小相等的数组 nums1
和 nums2
,nums1
相对于 nums2
的优势可以用满足 nums1[i] > nums2[i]
的索引 i
的数目来描述。
返回 nums1 的任意排列,使其相对于 nums2
的优势最大化。
思路:
给你输入两个长度相等的数组 nums1
和 nums2
,请你重新组织 nums1
中元素的位置,使得 nums1
的「优势」最大化。
如果 nums1[i] > nums2[i]
,就是说 nums1
在索引 i
上对 nums2[i]
有「优势」。优势最大化也就是说让你重新组织 nums1
,尽可能多的让 nums1[i] > nums2[i]
。
class Solution {public int[] advantageCount(int[] nums1, int[] nums2) {int n = nums1.length;// 给 nums2 降序排序PriorityQueue<int[]> maxpq = new PriorityQueue<>((int[] pair1, int[] pair2)->{return pair2[1] - pair1[1];});for(int i = 0; i< n; i++){maxpq.offer(new int[]{i, nums2[i]});}// 给 nums1 升序排序Arrays.sort(nums1);// nums1[left] 是最小值,nums1[right] 是最大值int left = 0, right = n - 1;int[] res = new int[n];while (!maxpq.isEmpty()) {int[] pair = maxpq.poll();// maxval 是 nums2 中的最大值,i 是对应索引int i = pair[0], maxval = pair[1];if (maxval < nums1[right]) {// 如果 nums1[right] 能胜过 maxval,那就自己上res[i] = nums1[right];right--;} else {// 否则用最小值混一下,养精蓄锐res[i] = nums1[left];left++;}}return res;}
}
带权重的随机选择算法
算法框架
class Solution {// 前缀和数组private int[] preSum;private Random rand = new Random();public Solution(int[] w) {int n = w.length;// 构建前缀和数组,偏移一位留给 preSum[0]preSum = new int[n + 1];preSum[0] = 0;// preSum[i] = sum(w[0..i-1])for (int i = 1; i <= n; i++) {preSum[i] = preSum[i - 1] + w[i - 1];}}public int pickIndex() {int n = preSum.length;// Java 的 nextInt(n) 方法在 [0, n) 中生成一个随机整数// 再加一就是在闭区间 [1, preSum[n - 1]] 中随机选择一个数字int target = rand.nextInt(preSum[n - 1]) + 1;// 获取 target 在前缀和数组 preSum 中的索引// 别忘了前缀和数组 preSum 和原始数组 w 有一位索引偏移return left_bound(preSum, target) - 1;}// 搜索左侧边界的二分搜索private int left_bound(int[] nums, int target) {int left = 0, right = nums.length - 1;// 搜索区间为 [left, right]while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {// 搜索区间变为 [mid+1, right]left = mid + 1;} else if (nums[mid] > target) {// 搜索区间变为 [left, mid-1]right = mid - 1;} else if (nums[mid] == target) {// 收缩右侧边界right = mid - 1;}}// 判断 target 是否存在于 nums 中// 此时 target 比所有数都大,返回 -1if (left == nums.length) return -1;// 判断一下 nums[left] 是不是 targetreturn nums[left] == target ? left : -1;}
}
528. 按权重随机选择[Cisco笔试题]
给你一个 下标从 0 开始 的正整数数组 w
,其中 w[i]
代表第 i
个下标的权重。
请你实现一个函数 pickIndex
,它可以 随机地 从范围 [0, w.length - 1]
内(含 0
和 w.length - 1
)选出并返回一个下标。选取下标 i
的 概率 为 w[i] / sum(w)
。
- 例如,对于
w = [1, 3]
,挑选下标0
的概率为1 / (1 + 3) = 0.25
(即,25%),而选取下标1
的概率为3 / (1 + 3) = 0.75
(即,75%
)。
思路:
1、根据权重数组 w
生成前缀和数组 preSum
。
2、生成一个取值在 preSum
之内的随机数,用二分搜索算法寻找大于等于这个随机数的最小元素索引。
3、最后对这个索引减一(因为前缀和数组有一位索引偏移),就可以作为权重数组的索引,即最终答案
前缀和数组中 0 本质上是个占位符
class Solution {private Random random = new Random();private int[] preSum;private int n;public Solution(int[] w) {this.n = w.length;// 前缀数组,下标0就是原数组w[0]preSum = new int[n];// 下标0就是原数组w[0]preSum[0] = w[0];for (int i = 1; i < n; i++) {preSum[i] = preSum[i-1] + w[i];}}public int pickIndex() {// 保证取到[1, preSum[n-1]]的闭区间int target = random.nextInt(preSum[n-1]) + 1;// right可以从n-1开始,也可以从n开始,对结果的正确性没有影响int left = 0, right = n;while (left < right) {int mid = left + (right - left) / 2;// 如果找到了,直接去当前的下标if (preSum[mid] == target) {left =mid;break;} else if (preSum[mid] > target) {// 向左找,因为当前mid的值大于target,可能是"第一个大于target"的值,所以不能丢弃mid// 如果mid的值不再需要了(最终不会取到现在的mid),那么就可以right=mid-1;right = mid;} else {// 向右找,因为当前的mid的值比target小,永远不会取到了。所以left=mid+1;left = mid + 1;}}// left代表的含义:// 当目标元素 target 不存在数组 nums 中时,搜索左侧边界的二分搜索的返回值可以做以下几种解读:// 1、返回的这个值是 nums 中大于等于 target 的最小元素索引。// 2、返回的这个值是 target 应该插入在 nums 中的索引位置。// 3、返回的这个值是 nums 中小于 target 的元素个数。return left;}
}
下面这道题目和上面👆一模一样
剑指 Offer II 071. 按权重生成随机数
给定一个正整数数组 w
,其中 w[i]
代表下标 i
的权重(下标从 0
开始),请写一个函数 pickIndex
,它可以随机地获取下标 i
,选取下标 i
的概率与 w[i]
成正比。
例如,对于 w = [1, 3]
,挑选下标 0
的概率为 1 / (1 + 3) = 0.25
(即,25%),而选取下标 1
的概率为 3 / (1 + 3) = 0.75
(即,75%)。
也就是说,选取下标 i
的概率为 w[i] / sum(w)
。
class Solution {private Random random = new Random();private int[] preSum;private int n;public Solution(int[] w) {this.n = w.length;// 前缀数组,下标0就是原数组w[0]preSum = new int[n];// 下标0就是原数组w[0]preSum[0] = w[0];for (int i = 1; i < n; i++) {preSum[i] = preSum[i-1] + w[i];}}public int pickIndex() {// 保证取到[1, preSum[n-1]]的闭区间int target = random.nextInt(preSum[n-1]) + 1;// right可以从n-1开始,也可以从n开始,对结果的正确性没有影响int left = 0, right = n;while (left < right) {int mid = left + (right - left) / 2;// 如果找到了,直接去当前的下标if (preSum[mid] == target) {left =mid;break;} else if (preSum[mid] > target) {// 向左找,因为当前mid的值大于target,可能是"第一个大于target"的值,所以不能丢弃mid// 如果mid的值不再需要了(最终不会取到现在的mid),那么就可以right=mid-1;right = mid;} else {// 向右找,因为当前的mid的值比target小,永远不会取到了。所以left=mid+1;left = mid + 1;}}// left代表的含义:// 当目标元素 target 不存在数组 nums 中时,搜索左侧边界的二分搜索的返回值可以做以下几种解读:// 1、返回的这个值是 nums 中大于等于 target 的最小元素索引。// 2、返回的这个值是 target 应该插入在 nums 中的索引位置。// 3、返回的这个值是 nums 中小于 target 的元素个数。return left;}
}
–end–