13.
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示, 在这个矩阵中:
0 表示障碍,无法触碰
1 表示地面,可以行走
比 1 大的数 表示有树的单元格,可以行走,数值表示树的高度
每一步,你都可以向上、下、左、右四个方向之一移动一个单位,如果你站的地方有一棵树,那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树,每砍过一颗树,该单元格的值变为 1(即变为地面)。
你将从 (0, 0) 点开始工作,返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树,返回 -1 。
可以保证的是,没有两棵树的高度是相同的,并且你至少需要砍倒一棵树。
class Solution {
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int cutOffTree(List<List<Integer>> forest) {
List<int[]> trees = new ArrayList<int[]>();
int row = forest.size();
int col = forest.get(0).size();
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (forest.get(i).get(j) > 1) {
trees.add(new int[]{i, j});
}
}
}
Collections.sort(trees, (a, b) -> forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]));
int cx = 0;
int cy = 0;
int ans = 0;
for (int i = 0; i < trees.size(); ++i) {
int steps = bfs(forest, cx, cy, trees.get(i)[0], trees.get(i)[1]);
if (steps == -1) {
return -1;
}
ans += steps;
cx = trees.get(i)[0];
cy = trees.get(i)[1];
}
return ans;
}
public int bfs(List<List<Integer>> forest, int sx, int sy, int tx, int ty) {
if (sx == tx && sy == ty) {
return 0;
}
int row = forest.size();
int col = forest.get(0).size();
int step = 0;
Queue<int[]> queue = new ArrayDeque<int[]>();
boolean[][] visited = new boolean[row][col];
queue.offer(new int[]{sx, sy});
visited[sx][sy] = true;
while (!queue.isEmpty()) {
step++;
int sz = queue.size();
for (int i = 0; i < sz; ++i) {
int[] cell = queue.poll();
int cx = cell[0], cy = cell[1];
for (int j = 0; j < 4; ++j) {
int nx = cx + dirs[j][0];
int ny = cy + dirs[j][1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
if (!visited[nx][ny] && forest.get(nx).get(ny) > 0) {
if (nx == tx && ny == ty) {
return step;
}
queue.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
}
return -1;
}
}
12.
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
class Solution {
public boolean isValidBST(TreeNode root) {
return find(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean find(TreeNode root,long min,long max) {
if(root == null) return true;
if(root.val <= min || root.val >= max) return false;
return find(root.left,min,root.val) && find(root.right,root.val,max);
}
}
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
if(!isValidBST(root.left)) return false;
if(root.val <= pre) return false;
pre = root.val;
return isValidBST(root.right);
}
}
11.贪心
心算项目的挑战比赛中,要求选手从 N 张卡牌中选出 cnt 张卡牌,若这 cnt 张卡牌数字总和为偶数,则选手成绩「有效」且得分为 cnt 张卡牌数字总和。
给定数组 cards 和 cnt,其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案,则返回 0。
示例 1:
输入:cards = [1,2,8,9], cnt = 3
输出:18
解释:选择数字为 1、8、9 的这三张卡牌,此时可获得最大的有效得分 1+8+9=18。
示例 2:
输入:cards = [3,3,1], cnt = 1
输出:0
解释:不存在获取有效得分的卡牌方案。
class Solution {
public int maxmiumScore(int[] cards, int cnt) {
Arrays.sort(cards);
int index = cards.length - 1;
int sum = 0;
while (cnt > 0) {
sum += cards[index--];
cnt--;
}
if (sum % 2 == 0) return sum;
for (int i = index; i >= 0; i--) {
for (int j = index + 1; j < cards.length; j++) {
sum -= cards[j];
sum += cards[i];
if (sum % 2 == 0) return sum;
sum -= cards[i];
sum += cards[j];
}
}
return 0;
}
}
10.双指针
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入:
first = “pale”
second = “ple”
输出: True
示例 2:
输入:
first = “pales”
second = “pal”
输出: False
class Solution {
public boolean oneEditAway(String first, String second) {
int n = first.length(), m = second.length();
if (Math.abs(n - m) > 1) return false;
if (n > m) return oneEditAway(second, first);
int i = 0, j = 0, cnt = 0;
while (i < n && j < m && cnt <= 1) {
char a = first.charAt(i), b = second.charAt(j);
if (a == b) {
i++;
j++;
}else {
if (n == m) {
++i;
++j;
++cnt;
}else {
++j;
++cnt;
}
}
}
return cnt <= 1;
}
}
9.贪心
由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ,其中:
如果 perm[i] < perm[i + 1] ,那么 s[i] == ‘I’
如果 perm[i] > perm[i + 1] ,那么 s[i] == ‘D’
给定一个字符串 s ,重构排列 perm 并返回它。如果有多个有效排列perm,则返回其中 任何一个
示例 1:
输入:s = “IDID”
输出:[0,4,1,3,2]
class Solution {
public int[] diStringMatch(String s) {
int[] res = new int[s.length() + 1];
int end = s.length(),start = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'I') {
res[i] = start++;
}else {
res[i] = end--;
}
}
res[res.length - 1] = start;
return res;
}
}
8.DP
为了 打出 一个字母,Alice 需要 按 对应字母 i 次,i 是该字母在这个按键上所处的位置。
比方说,为了按出字母 ‘s’ ,Alice 需要按 ‘7’ 四次。类似的, Alice 需要按 ‘5’ 两次得到字母 ‘k’ 。
注意,数字 ‘0’ 和 ‘1’ 不映射到任何字母,所以 Alice 不 使用它们。
但是,由于传输的错误,Bob 没有收到 Alice 打字的字母信息,反而收到了 按键的字符串信息 。
比方说,Alice 发出的信息为 “bob” ,Bob 将收到字符串 “2266622” 。
给你一个字符串 pressedKeys ,表示 Bob 收到的字符串,请你返回 Alice 总共可能发出多少种文字信息 。
由于答案可能很大,将它对 109 + 7 取余 后返回。
示例 1:
输入:pressedKeys = “22233”
输出:8
解释:
Alice 可能发出的文字信息包括:
“aaadd”, “abdd”, “badd”, “cdd”, “aaae”, “abe”, “bae” 和 “ce” 。
由于总共有 8 种可能的信息,所以我们返回 8 。
class Solution {
public int countTexts(String pressedKeys) {
int mod = 1000000007;
long[] dp = new long[pressedKeys.length() + 1];
dp[0] = 1;
for (int i = 1; i < pressedKeys.length() + 1; i++) {
dp[i] += dp[i - 1];
char c = pressedKeys.charAt(i - 1);
if (i - 2 >= 0 && c == pressedKeys.charAt(i - 2)) {
dp[i] += dp[i - 2];
if (i - 3 >= 0 && c == pressedKeys.charAt(i - 3)) {
dp[i] += dp[i - 3];
if ((c == '7' || c == '9') && i - 4 >= 0 && c == pressedKeys.charAt(i - 4)) {
dp[i] += dp[i - 4];
}
}
}
dp[i] %= mod;
}
return (int)dp[dp.length - 1];
}
}
7.
基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 ‘A’、’C’、’G’ 和 ‘T’ 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
例如,”AACCGGTT” –> “AACCGGTA” 就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化,只有基因库中的基因才是有效的基因序列。
给你两个基因序列 start 和 end ,以及一个基因库 bank ,请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化,返回 -1 。
注意:起始基因序列 start 默认是有效的,但是它并不一定会出现在基因库中。
示例 1:
输入:start = “AACCGGTT”, end = “AACCGGTA”, bank = [“AACCGGTA”]
输出:1
示例 2:
输入:start = “AACCGGTT”, end = “AAACGGTA”, bank = [“AACCGGTA”,”AACCGCTA”,”AAACGGTA”]
输出:2
class Solution {
public int minMutation(String start, String end, String[] bank) {
Set<String> bankSet = new HashSet<>();
Set<String> visited = new HashSet<>();
for (String str : bank)
bankSet.add(str);
char[] keys = new char[]{'A','C','G','T'};
if (start.equals(end))
return 0;
if (!bankSet.contains(end))
return -1;
Queue<String> queue = new LinkedList<>();
queue.offer(start);
int step = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String test = queue.poll();
for (int j = 0; j < 8; j++) {
for (int k = 0; k < 4; k++) {
if (keys[k] != test.charAt(j)) {
StringBuffer buffer = new StringBuffer(test);
buffer.setCharAt(j,keys[k]);
String next = buffer.toString();
if (!visited.contains(next) && bankSet.contains(next)) {
if (next.equals(end))
return step;
queue.offer(next);
visited.add(next);
}
}
}
}
}
step++;
}
return -1;
}
}
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<Integer, Integer> 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<Integer> 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;
}
}
版权声明:本文为博主作者:海边的彩虹与你原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/fffff9999/article/details/124549241