6.
给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。同时给你两个二维整数数组 guards 和 walls ，其中 guards[i] = [rowi, coli] 且 walls[j] = [rowj, colj] ，分别表示第 i 个警卫和第 j 座墙所在的位置。
一个警卫能看到 4 个坐标轴方向（即东、南、西、北）的 所有 格子，除非他们被一座墙或者另外一个警卫 挡住 了视线。如果一个格子能被 至少 一个警卫看到，那么我们说这个格子被 保卫 了。
请你返回空格子中，有多少个格子是 没被保卫 的。
class Solution {
int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
int ans = 0;
char[][] arr = new char[m][n];
for (int[] g : guards) {
arr[g[0]][g[1]] = 'G';
}
for (int[] w : walls) {
arr[w[0]][w[1]] = 'W';
}
for (int[] g : guards) {
for (int i = 0; i < 4; i++) {
int x = g[0] + dir[i][0];
int y = g[1] + dir[i][1];
while (x >= 0 && y >= 0 && x < m && y < n && arr[x][y] != 'W' && arr[x][y] != 'G') {
arr[x][y] = 'I';
x += dir[i][0];
y += dir[i][1];
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] != 'G' && arr[i][j] != 'W' && arr[i][j] != 'I') ans++;
}
}
return ans;
}
}
5.HashMap
给你一个整数数组 cards ，其中 cards[i] 表示第 i 张卡牌的 值 。如果两张卡牌的值相同，则认为这一对卡牌 匹配 。
返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回 -1 。
示例 1：
输入：cards = [3,4,2,3,4,7]
输出：4
解释：拿起卡牌 [3,4,2,3] 将会包含一对值为 3 的匹配卡牌。注意，拿起 [4,2,3,4] 也是最优方案。
class Solution {
public int minimumCardPickup(int[] cards) {
HashMap map = new HashMap<>();
int res = Integer.MAX_VALUE;
for (int i = 0; i < cards.length; i++) {
if (map.containsKey(cards[i])) {
res = Math.min(res,i - map.get(cards[i]) + 1);
map.put(cards[i],i);
}else
map.put(cards[i],i);
}
if (res == Integer.MAX_VALUE)
return -1;
return res;
}
} 4.滑动窗口
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：
输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
示例 2：
输入：nums = [1,2,3], k = 0
输出：0
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int n = nums.length,res = 0;
int sum = 1,j = 0;
for (int i = 0; i < n; i++) {
sum *= nums[i];
while (j <= i && sum >= k) {
sum /= nums[j];
j++;
}
res += i - j + 1;
}
return res;
}
}3.约瑟夫环问题
共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
游戏遵循如下规则：
从第 1 名小伙伴所在位置 开始 。
沿着顺时针方向数 k 名小伙伴，计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤 2 继续执行。
否则，圈子中最后一名小伙伴赢得游戏。
给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。
输入：n = 5, k = 2
输出：3
解释：游戏运行步骤如下：
1) 从小伙伴 1 开始。
2) 顺时针数 2 名小伙伴，也就是小伙伴 1 和 2 。
3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。
4) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 4 。
5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。
6) 顺时针数 2 名小伙伴，也就是小伙伴 5 和 1 。
7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。
8) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 5 。
9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。
class Solution {
public int findTheWinner(int n, int k) {
Queue queue = new LinkedList<>();
for (int i = 1; i <= n; i++) {
queue.add(i);
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < k; j++) {
queue.add(queue.poll());
}
queue.poll();
}
return queue.poll();
}
} 2.
给你一个日志数组 logs。每条日志都是以空格分隔的字串，其第一个字为字母与数字混合的 标识符 。
有两种不同类型的日志：
字母日志：除标识符之外，所有字均由小写字母组成
数字日志：除标识符之外，所有字均由数字组成
请按下述规则将日志重新排序：
所有 字母日志 都排在 数字日志 之前。
字母日志 在内容不同时，忽略标识符后，按内容字母顺序排序；在内容相同时，按标识符排序。
数字日志 应该保留原来的相对顺序。
返回日志的最终顺序。
示例 1：
输入：logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
输出：["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]
解释：
字母日志的内容都不同，所以顺序为 "art can", "art zero", "own kit dig" 。
数字日志保留原来的相对顺序 "dig1 8 1 5 1", "dig2 3 6" 。
import java.util.Arrays;
class Solution {
public String[] reorderLogFiles(String[] logs) {
Arrays.sort(logs, (log1, log2) -> {//运用到了java里的泛型，第二个参数重新定义排序规则
String[] split1 = log1.split(" ", 2); //将log1 按分隔符“ ” ，分成2份，即把标识符分开来
String[] split2 = log2.split(" ", 2);
boolean isDigit1 = Character.isDigit(split1[1].charAt(0));//判断除标识符外的第一个字符是数字true，字母false
boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
if (!isDigit1 && !isDigit2) { //如果两个日志都是字母日志
int cmp = split1[1].compareTo(split2[1]); //先比较内容字母split1>split2则返回1，等于返0，小于返-1
if (cmp != 0) return cmp;
return split1[0].compareTo(split2[0]);//若内容字母相同则比较标识符
}
return isDigit1 ? (isDigit2 ? 0 : 1) : -1;
//如果split1是数字字符，且split2是数字字符返回0，
// 如果split1是数字字符，且split2是字母字符返回1，即split1>split2,从小到大排序，split2提前
// 如果split1是字母字符，返回-1，
});
return logs;
}
}1.前缀和
给你一个下标从 0 开始长度为 n 的整数数组 nums 。
下标 i 处的 平均差 指的是 nums 中 前 i + 1 个元素平均值和 后 n - i - 1 个元素平均值的 绝对差 。两个平均值都需要 向下取整 到最近的整数。
请你返回产生 最小平均差 的下标。如果有多个下标最小平均差相等，请你返回 最小 的一个下标。
注意：
两个数的 绝对差 是两者差的绝对值。
n 个元素的平均值是 n 个元素之 和 除以（整数除法） n 。
0 个元素的平均值视为 0 。
示例 1：
输入：nums = [2,5,3,9,5,3]
输出：3
解释：
- 下标 0 处的平均差为：|2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3 。
- 下标 1 处的平均差为：|(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2 。
- 下标 2 处的平均差为：|(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2 。
- 下标 3 处的平均差为：|(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0 。
- 下标 4 处的平均差为：|(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1 。
- 下标 5 处的平均差为：|(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4 。
下标 3 处的平均差为最小平均差，所以返回 3 。
class Solution {
public int minimumAverageDifference(int[] nums) {
long[] sum = new long[nums.length + 1];
for (int i = 1; i < nums.length + 1; i++) {
sum[i] = sum[i - 1] + nums[i - 1];
}
int min = (int) 1e9;
int[] arr = new int[nums.length + 1];
for (int i = 1; i < nums.length + 1; i++) {
long left = sum[i];
long right = sum[nums.length] - sum[i];
arr[i] = (int) Math.abs(left / i - (i < nums.length ? right / (nums.length - i) : 0));
min = Math.min(min, arr[i]);
}
for (int i = 1; i <= nums.length; i++) {
if (arr[i] == min)
return i - 1;
}
return -1;
}
}欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）