5910. 检查两个字符串是否几乎相等
如果两个字符串 word1 和 word2 中从 'a' 到 'z' 每一个字母出现频率之差都 不超过 3 ，那么我们称这两个字符串 word1 和 word2 几乎相等 。
给你两个长度都为 n 的字符串 word1 和 word2 ，如果 word1 和 word2 几乎相等 ，请你返回 true ，否则返回 false 。
一个字母 x 的出现 频率 指的是它在字符串中出现的次数。
示例 1：
输入：word1 = “aaaa”, word2 = “bccb”
输出：false
解释：字符串 “aaaa” 中有 4 个 ‘a’ ，但是 “bccb” 中有 0 个 ‘a’ 。
两者之差为 4 ，大于上限 3 。
示例 2：
输入：word1 = “abcdeef”, word2 = “abaaacc”
输出：true
解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
- ‘a’ 在 word1 中出现了 1 次，在 word2 中出现了 4 次，差为 3 。
- ‘b’ 在 word1 中出现了 1 次，在 word2 中出现了 1 次，差为 0 。
- ‘c’ 在 word1 中出现了 1 次，在 word2 中出现了 2 次，差为 1 。
- ‘d’ 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。
- ‘e’ 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。
- ‘f’ 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。
示例 3：
输入：word1 = “cccddabba”, word2 = “babababab”
输出：true
解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
- ‘a’ 在 word1 中出现了 2 次，在 word2 中出现了 4 次，差为 2 。
- ‘b’ 在 word1 中出现了 2 次，在 word2 中出现了 5 次，差为 3 。
- ‘c’ 在 word1 中出现了 3 次，在 word2 中出现了 0 次，差为 3 。
- ‘d’ 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。
提示：
n == word1.length == word2.length1 <= n <= 100word1和word2都只包含小写英文字母。
思路：
使用哈希表统计每个字符串中各字符出现次数，对比每个字符的次数的差的绝对值，若 > 3 说明两个字符串不相等，返回false，若每一个字符都几乎相等，返回true
class Solution {public boolean checkAlmostEquivalent(String word1, String word2) {int[] c1 = new int[26], c2 = new int[26];for (int i = 0; i < word1.length(); i++) {c1[word1.charAt(i) - 'a']++;}for (int i = 0; i < word2.length(); i++) {c2[word2.charAt(i) - 'a']++;}for (int i = 0; i < 26; i++) {if (Math.abs(c1[i] - c2[i]) > 3)return false;}return true;}}
5911. 模拟行走机器人 II
给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0) ，右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人 初始 在格子 (0, 0) ，方向为 "East" 。
机器人可以根据指令移动指定的 步数 。每一步，它可以执行以下操作。
- 沿着当前方向尝试 往前一步 。
- 如果机器人下一步将到达的格子 超出了边界 ，机器人会 逆时针 转 90 度，然后再尝试往前一步。
如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。
请你实现 Robot 类：
Robot(int width, int height)初始化一个width x height的网格图，机器人初始在(0, 0)，方向朝"East"。void move(int num)给机器人下达前进num步的指令。int[] getPos()返回机器人当前所处的格子位置，用一个长度为 2 的数组[x, y]表示。String getDir()返回当前机器人的朝向，为"North"，"East"，"South"或者"West"。
示例 1：
输入：
[“Robot”, “move”, “move”, “getPos”, “getDir”, “move”, “move”, “move”, “getPos”, “getDir”]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出：
[null, null, null, [4, 0], “East”, null, null, null, [1, 2], “West”]
解释：
Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.move(2); // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.move(2); // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 “East”
robot.move(2); // 朝东移动 1 步到达 (5, 0) ，并朝东。
// 下一步继续往东移动将出界，所以逆时针转变方向朝北。
// 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.move(1); // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。
robot.move(4); // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
// 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 “West”
提示：
2 <= width, height <= 1001 <= num <= 10move，getPos和getDir总共 调用次数不超过10次。
思路：
模拟题，分类处理，考察取模运算
一圈的总步数是 len = ``n + m - 1 + n - 1 + m - 2 = 2 * n + 2 * m - 4 ，每次读取输入步数后对len取模，得到其在一圈中的对应位置
- 向东
Eaststep = [1, n - 1]，位置坐标为(step, 0) - 向北
Northstep = [n, n + m - 2]位置坐标为(n - 1, step - (n - 1)) - 向西
Weststep = [n + m - 1, 2 * n + m - 3]位置坐标为((n - 1) - (step - (n + m - 2)), m - 1) - 向南
Southstep = [2 * n + m - 2, 2 * n + 2 * m - 4]位置坐标为(0, (m - 1) - (step - (2 * n + m - 3)))
注意：题目不仅问了位置，还可能问当前的方向，故在每次位置发生变化时同时记录新的位置和方向
还有一点，起点是(0, 0)此时方向向东，若再次到 (0, 0) 方向变为向南！！！
class Robot {final String[] dd = {"East", "North", "West", "South"};int len, step;int n, m;int dir;int[] pos = new int[]{0, 0};public Robot(int width, int height) {n = width;m = height;len = 2 * width + 2 * height - 4;}public void move(int num) {step = (step + num) % len;if (step >= 1 && step <= n - 1) {dir = 0;pos[0] = step;pos[1] = 0;} else if (step >= n && step <= n + m - 2) {dir = 1;pos[0] = n - 1;pos[1] = step - (n - 1);} else if (step >= n + m - 1 && step <= 2 * n + m - 3) {dir = 2;pos[0] = (n - 1) - (step - (n + m - 2));pos[1] = m - 1;} else {dir = 3;if (step == 0)pos[0] = pos[1] = 0;else {pos[0] = 0;pos[1] = (m - 1) - (step - (2 * n + m - 3));}}}public int[] getPos() {return pos;}public String getDir() {return dd[dir];}}/*** Your Robot object will be instantiated and called as such:* Robot obj = new Robot(width, height);* obj.move(num);* int[] param_2 = obj.getPos();* String param_3 = obj.getDir();*/
5912. 每一个查询的最大美丽值
给你一个二维整数数组 items ，其中 items[i] = [price, beauty] 分别表示每一个物品的 价格 和 美丽值 。
同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为 0 。
请你返回一个长度与 queries 相同的数组 answer，其中 answer[j]是第 j 个查询的答案。
示例 1：
输入：items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
输出：[2,4,5,5,6,6]
解释：
- queries[0]=1 ，[1,2] 是唯一价格 <= 1 的物品。所以这个查询的答案为 2 。
- queries[1]=2 ，符合条件的物品有 [1,2] 和 [2,4] 。
它们中的最大美丽值为 4 。
- queries[2]=3 和 queries[3]=4 ，符合条件的物品都为 [1,2] ，[3,2] ，[2,4] 和 [3,5] 。
它们中的最大美丽值为 5 。
- queries[4]=5 和 queries[5]=6 ，所有物品都符合条件。
所以，答案为所有物品中的最大美丽值，为 6 。
示例 2：
输入：items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
输出：[4]
解释：
每个物品的价格均为 1 ，所以我们选择最大美丽值 4 。
注意，多个物品可能有相同的价格和美丽值。
示例 3：
输入：items = [[10,1000]], queries = [5]
输出：[0]
解释：
没有物品的价格小于等于 5 ，所以没有物品可以选择。
因此，查询的结果为 0 。
提示：
1 <= items.length, queries.length <= 10items[i].length == 21 <= price, beauty, queries[j] <= 10
思路：
开辟一个与 items 等长的数组记录小于等于每个物品价格的最大的美丽值，按价格从低到高对items排个序，从前往后扫描一遍即可求出每个小于等于每个物品价格的最大美丽值
扫描queries二分查找其对应物品位置并记录结果
时间复杂度：O(nlogn)
空间复杂度：O(n)
class Solution {public int[] maximumBeauty(int[][] items, int[] queries) {Arrays.sort(items, (o1, o2) -> o1[0] - o2[0] == 0 ? o2[1] - o1[1] : o1[0] - o2[0]);int n = items.length;int[] pre = new int[n];int max = 0;for (int i = 0; i < n; i++) {max = Math.max(max, items[i][1]);pre[i] = max;}int[] res = new int[queries.length];int idx = 0;for (int x : queries) {int l = 0, r = n - 1;while (l < r) {int mid = l + r + 1 >> 1;if (items[mid][0] > x)r = mid - 1;elsel = mid;}if (items[l][0] <= x)res[idx] = pre[l];idx++;}return res;}}
5913. 你可以安排的最多任务数目
难度困难6收藏分享切换为英文接收动态反馈
给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成 一个 任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。
除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸。
给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回 最多 有多少个任务可以被完成。
示例 1：
输入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 2（0 + 1 >= 1）
- 1 号工人完成任务 1（3 >= 2）
- 2 号工人完成任务 0（3 >= 3）
示例 2：
输入：tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
输出：1
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 0（0 + 5 >= 5）
示例 3：
输入：tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
输出：2
解释：
我们可以按照如下方案安排药丸：
- 给 0 号和 1 号工人药丸。
- 0 号工人完成任务 0（0 + 10 >= 10）
- 1 号工人完成任务 1（10 + 10 >= 15）
示例 4：
输入：tasks = [5,9,8,5,9], workers = [1,6,4,2,6], pills = 1, strength = 5
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 2 号工人药丸。
- 1 号工人完成任务 0（6 >= 5）
- 2 号工人完成任务 2（4 + 5 >= 8）
- 4 号工人完成任务 3（6 >= 5）
提示：
n == tasks.lengthm == workers.length1 <= n, m <= 5 * 100 <= pills <= m0 <= tasks[i], workers[j], strength <= 10
思路：
二分 + 贪心 + 双端队列
对任务力量和工人体力按从小到大排序
二分答案mid，选择最少力量的mid个任务和最大力量的mid个工人，如果能完成，考虑右半部分，否则考虑左半部分（此处就是贪心的思想，用最大力量的工人们完成需要力量最小的mid个任务）
选出的mid个工人每人都必须完成一个任务！
按力量从小到大考虑每一个工人，将其能通过嗑药完成的所有任务入队(任务按力量从小到大考虑)。
- 若他不嗑药就能完成当前队头任务，队头元素出队，完成任务数加一
- 由于他必须得完成一个任务且不嗑药没有一个他能完成，所以他必须嗑药
- 有药能吃，吃药，选择当前队尾任务完成，完成任务数加一，若队列为空直接返回false(吃了药也一个都完不成当然不行)
- 没药可吃，返回false，因为他没完成任务
这里为什么吃了药后选他能完成的所需力量最大的任务呢？
若他直接完成队头任务，可能出现这样一种情况，后面的一个工人在不嗑药的情况下能完成队头任务，但不能完成队尾任务，为了最大化收益，选择让吃了药的工人完成其能完成的所需力量最大的任务。
class Solution {int n, m, p, s;int[] t, w;public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {Arrays.sort(tasks);Arrays.sort(workers);n = tasks.length;m = workers.length;t = tasks;w = workers;p = pills;s = strength;int l = 0, r = Math.min(n, m);while (l < r) {int mid = l + r + 1 >> 1;if (check(mid))l = mid;elser = mid - 1;}return l;}boolean check(int cnt) {int i = 0, sum = p;Deque<Integer> q = new LinkedList<>();for (int j = m - cnt; j < m; j++) {while (i < cnt && t[i] <= w[j] + s) {q.offer(t[i]);i++;}if (q.isEmpty()) //磕不嗑药都不能完成任务return false;if (w[j] >= q.peek()) {q.poll();} else if (sum > 0) {sum--;q.pollLast();} elsereturn false;}return true;}}
若有收获，就点个赞吧
0 人点赞
