没想到最难的是t3，掉了12分，下次打回来！
6078. 重排字符形成目标字符串
给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。
从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。
示例 1：
输入：s = “ilovecodingonleetcode”, target = “code” 输出：2 解释： 对于 “code” 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。 对于 “code” 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。 形成的字符串分别是 “ecod” 和 “code” ，都可以重排为 “code” 。 可以形成最多 2 个 “code” 的副本，所以返回 2 。
示例 2：
输入：s = “abcba”, target = “abc” 输出：1 解释： 选取下标为 0 、1 和 2 的字符，可以形成 “abc” 的 1 个副本。 可以形成最多 1 个 “abc” 的副本，所以返回 1 。 注意，尽管下标 3 和 4 分别有额外的 ‘a’ 和 ‘b’ ，但不能重用下标 2 处的 ‘c’ ，所以无法形成 “abc” 的第 2 个副本。
示例 3：
输入：s = “abbaccaddaeea”, target = “aaaaa” 输出：1 解释： 选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 “aaaaa” 的 1 个副本。 可以形成最多 1 个 “aaaaa” 的副本，所以返回 1 。
提示：
- 1 <= s.length <= 100
- 1 <= target.length <= 10
- s 和 target 由小写英文字母组成
思路：
看清题意即可，每个字符仅能使用一次，统计s中含target的数量(不要求顺序)
class Solution {public int rearrangeCharacters(String s, String target) {int[] cnt = new int[26];int[] c2 = new int[26];for (int i = 0; i < target.length(); i++) {cnt[target.charAt(i) - 'a']++;}for (int i = 0; i < s.length(); i++) {c2[s.charAt(i) - 'a'] ++;}int res = 0;while (true) {boolean flag = true;for (int i = 0; i < 26; i++) {if (c2[i] >= cnt[i]) {c2[i] -= cnt[i];} else {flag = false;break;}}if (flag) res++;else break;}return res;}}
6079. 价格减免
句子 是由若干个单词组成的字符串，单词之间用单个空格分隔，其中每个单词可以包含数字、小写字母、和美元符号 ‘$’ 。如果单词的形式为美元符号后跟着一个非负实数，那么这个单词就表示一个价格。
- 例如 “$100”、”$23” 和 “$6.75” 表示价格，而 “100”、”$” 和 “2$3” 不是。
注意：本题输入中的价格均为整数。
给你一个字符串 sentence 和一个整数 discount 。对于每个表示价格的单词，都在价格的基础上减免 discount% ，并 更新 该单词到句子中。所有更新后的价格应该表示为一个 恰好保留小数点后两位 的数字。
返回表示修改后句子的字符串。
示例 1：
输入：sentence = “there are $1 $2 and 5$ candies in the shop”, discount = 50 输出：“there are $0.50 $1.00 and 5$ candies in the shop” 解释： 表示价格的单词是 “$1” 和 “$2” 。 - “$1” 减免 50% 为 “$0.50” ，所以 “$1” 替换为 “$0.50” 。 - “$2” 减免 50% 为 “$1” ，所以 “$1” 替换为 “$1.00” 。
示例 2：
输入：sentence = “1 2 $3 4 $5 $6 7 8$ $9 $10$”, discount = 100 输出：“1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$” 解释： 任何价格减免 100% 都会得到 0 。 表示价格的单词分别是 “$3”、”$5”、”$6” 和 “$9”。 每个单词都替换为 “$0.00”。
提示：
- 1 <= sentence.length <= 105
- sentence 由小写英文字母、数字、’ ‘ 和 ‘$’ 组成
- sentence 不含前导和尾随空格
- sentence 的所有单词都用单个空格分隔
- 所有价格都是 正 整数且不含前导零
- 所有价格 最多 为 10 位数字
- 0 <= discount <= 100
思路：
模拟
注意$也是不合法的
需要用到String.format()方法
class Solution {public String discountPrices(String sentence, int discount) {String[] ss = sentence.split(" ");StringBuilder sb = new StringBuilder();double d = (100 - discount) / 100.0;for (String s : ss) {double v = check(s);if (v >= 0) {v = v * d;String t = String.format("$%.2f", v);sb.append(t + " ");} else {sb.append(s + " ");}}sb.deleteCharAt(sb.length() - 1);return sb.toString();}long check(String s) {if (s.charAt(0) != '$')return -1;if (s.length() <= 1)return -1;long res = 0;for (int i = 1; i < s.length(); i++) {if (!(s.charAt(i) >= '0' && s.charAt(i) <= '9'))return -1;int x = s.charAt(i) - '0';res = res * 10 + x;}return res;}}
6080. 使数组按非递减顺序排列
给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。
重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。
示例 1：
输入：nums = [5,3,4,4,7,3,6,11,8,5,11] 输出：3 解释：执行下述几个步骤： - 步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11] - 步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11] - 步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11] [5,7,11,11] 是一个非递减数组，因此，返回 3 。
示例 2：
输入：nums = [4,5,7,7,13] 输出：0 解释：nums 已经是一个非递减数组，因此，返回 0 。
提示：
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 109
思路：
方法1：正序考虑
考虑一个元素cur什么条件下会被删除？
只有当左边存在严格大于当前元素的数pre时cur才会被删除。
当前元素被删除时次数是多少？
等于pre与cur之间所有<= cur的元素被删除的最大次数t再加一
综合上述两点，可以使用单调栈解决
class Solution {public int totalSteps(int[] nums) {int n = nums.length;int max = 0;Deque<int[]> stk = new ArrayDeque<>();// 维护严格单调递减栈, 考虑每个元素被删除的时间，在每个元素入栈时更新全局最大时间// 从前往后考虑，记录每个元素的大小以及它被删除的时间for (int i = 0; i < n; i++) {int t = 0;while (!stk.isEmpty() && stk.peek()[0] <= nums[i]) {t = Math.max(t, stk.pop()[1]);}// 如果栈中还有元素，说明nums[i]也应该被删除，删除时间 + 1，否则当前元素会被保留至结果数组中if (!stk.isEmpty()) t++;else t = 0;max = Math.max(max, t);stk.push(new int[]{nums[i], t});}return max;}}
方法2：倒序，考虑一个数能删除多少个元素？
维护一个非严格单调递减栈，考虑当前元素cur，所有被当前元素弹出栈的下标都是需要被删除的数值下标，且删除次数等于弹出栈的元素个数
注意这样一个样例**[5,14,15,11,5,13,15]**
当遍历到i = 3时，能被nums[3] = 15弹出的数只有nums[4] = 11，但是能被nums[4] = 11弹出的数有nums[5], nums[6]，故f[i] = max(f[i] + 1, f[j])
class Solution {public int totalSteps(int[] nums) {int n = nums.length;int[] f = new int[n];int[] stk = new int[n];int p = -1;for (int i = n - 1; i >= 0; i--) {while (p >= 0 && nums[stk[p]] < nums[i]) {int j = stk[p--];f[i] = Math.max(f[i] + 1, f[j]);}stk[++p] = i;}// System.out.println(Arrays.toString(f));int max = 0;for (int x : f)max = Math.max(x, max);return max;}}
6081. 到达角落需要移除障碍物的最小数目
给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：
- 0 表示一个 空 单元格，
- 1 表示一个可以移除的 障碍物 。
你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。
示例 1：
输入：grid = [[0,1,1],[1,1,0],[1,1,0]] 输出：2 解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。 可以证明我们至少需要移除两个障碍物，所以返回 2 。 注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。
示例 2：
输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]] 输出：0 解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 105
- 2 <= m * n <= 105
- grid[i][j] 为 0 或 1
- grid[0][0] == grid[m - 1][n - 1] == 0
思路：
裸的01bfs
class Solution {public int minimumObstacles(int[][] g) {int n = g.length, m = g[0].length;int[] dist = new int[n * m];Arrays.fill(dist, 0x3f3f3f3f);dist[0] = 0;Deque<Integer> q = new LinkedList<>();q.offer(0);int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};while (!q.isEmpty()) {int u = q.poll();int x = u / m, y = u % m;for (int i = 0; i < 4; i++) {int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= n || b < 0 || b >= m)continue;int h = a * m + b;int d = dist[u] + g[a][b];if (d < dist[h]) {dist[h] = d;if (g[a][b] == 1)q.offer(h);elseq.offerFirst(h);}}}return dist[(n - 1) * m + m - 1];}}
若有收获，就点个赞吧
0 人点赞
