不积跬步，无以至千里；不积小流，无以成江海

时间：2020-5-29 讨论： 代码地址：https://leetcode.cn/contest/weekly-contest-295

A: 重排字符形成目标字符串

思路：木桶原理，统计
关键点：

  1. function rearrangeCharacters(s: string, target: string): number {
  2.     let cnt1 = new Array(128).fill(0),
  3.     cnt2 = new Array(128).fill(0);
  4.     for (let i of target) {
  5.         cnt1[i.charCodeAt(0)]++;
  6.     }
  7.     for (let i of s) {
  8.         cnt2[i.charCodeAt(0)]++;
  9.     }
  10.     const max = Number.MAX_SAFE_INTEGER;
  11.     let ans = max;
  12.     for (let i = 0; i < 128; i++) {
  13.         if (cnt1[i] === 0) continue;
  14.         ans = Math.min(ans, Math.floor(cnt2[i] / cnt1[i]));
  15.     }
  16.     return ans === max ? 0 : ans;
  17. };

总结：

B: 价格减免

思路：

  1. 转为数组
  2. 匹配合法数据
    1. 针对目标数据进行操作
    2. 保留两位小数
  3. 还原为字符串

关键点：

1. 判断非负实数正则

new RegExp(/^(\$)(([1-9]\d.?\d)|(0.\d*))$/g);
下载.png

2. String.prototype.replace

str.replace(regexp|substr, newSubStr|function)
截屏2022-05-29 下午5.23.40.png

  1. function discountPrices(sentence: string, discount: number): string {
  2.     const sell = (100 - discount) / 100;
  3.     let reg = new RegExp(/^(\$)(([1-9]\d*\.?\d*)|(0\.\d*))$/g);
  4.     let arr = sentence.split(' ').map(d => {
  5.         if (!reg.test(d)) return d;
  6.         return d.replace(reg, (s, $1, $2) => {
  7.             return `$${(sell * $2).toFixed(2)}`;
  8.         });
  9.     });
  10.     return arr.join(' ');
  11. };

总结：

C: 使数组按非递减顺序排列

思路：
关键点：单调栈

  1. function totalSteps(nums: number[]): number {
  2.     let ans = 0;
  3.     let stack = [];
  4.     for (let num of nums) {
  5.         let max = 0;
  6.         while (stack.length && stack[0][0] <= num) {
  7.             max = Math.max(stack[0][1], max);
  8.             stack.shift();
  9.         }
  10.         if (stack.length) max++;
  11.         ans = Math.max(max, ans);
  12.         stack.unshift([num, max]);
  13.     }
  14.     return ans;
  15. };

总结：

case: [10,1,2,3,4,5,6,1,2,3]

练习： 单调栈

D: 到达角落需要移除障碍物的最小数目

最短路径问题
思路：
关键点：0-1BFS

  1. function minimumObstacles(grid: number[][]): number {
  2.     const m = grid.length, n = grid[0].length;
  3.     const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  4.     let ans = Array.from({ length: m }, v => new Array(n).fill(Infinity));
  5.     ans[0][0] = 0;
  6.     let deque = [[0, 0]];
  7.     while (deque.length) {
  8.         let [x, y] = deque.shift();
  9.         for (let [dx, dy] of dirs) {
  10.             let [i, j] = [x + dx, y + dy];
  11.             if (i < 0 || i > m - 1 || j < 0 || j > n - 1) continue;
  12.             const cost = grid[i][j];
  13.             if (ans[x][y] + cost >= ans[i][j]) continue;
  14.             ans[i][j] = ans[x][y] + cost;
  15.             deque.push([i, j]);
  16.             // if (cost) deque.push([i, j]);
  17.             // else deque.unshift([i, j]);
  18.         }
  19.     }
  20.     return ans[m - 1][n - 1];
  21. };

总结：使用双向队列超时

练习：

1368. 使网格图至少有一条有效路径的最小代价

复盘

image.png

A: 基础题
B: 依赖谷歌正则表达式 -> 巩固正则
C: 缺失单调栈积累
D: 缺失最优路径问题积累

反思：
js语言在缺失内置复杂数据类型、较复杂类型下超时
考虑提升CD类型通过率， 切换其他类型语言并加大练习