周赛复盘294

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

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

A: 字母在字符串中的百分比

思路：
关键点：

function percentageLetter(s: string, letter: string): number {
    let count = 0;
    let total = s.length;
    for (let i of s) {
        if (i === letter) count++;
    }
    return Math.floor(count / total * 100);
};

总结：

B: 装满石头的背包的最大数量

思路：
关键点：

1. 求差值
2. 排序

   function maximumBags(capacity: number[], rocks: number[], additionalRocks: number): number {
    const n = capacity.length;
    const diffs = capacity.map((c, i) => c - rocks[i]);
    diffs.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0; i < n && (diffs[i] === 0 || diffs[i] <= additionalRocks); i++) {
        ans++;
        additionalRocks -= diffs[i];
    }
    return ans;
   };

   总结：

C: 表示一个折线图的最少线段数

思路：
关键点：

1. 计算除法会导致浮点误差，改为乘法可以避免此问题
2. BigInt实现大数运算

   function minimumLines(stockPrices: number[][]): number {
    const n = stockPrices.length;
    stockPrices.sort((a, b) => a[0] - b[0]);
    let ans = 0;
    let pre = [BigInt(0), BigInt(0)];
    for (let i = 1; i < n; i++) {
        const [x1, y1] = stockPrices[i - 1];
        const [x2, y2] = stockPrices[i];
        const dx = BigInt(x2 - x1), dy = BigInt(y2 - y1);
        if (i == 1 || (dx * pre[1] !==  dy * pre[0])) ans++;
        pre = [dx, dy];
    }
    return ans;
   };

case: [[1,1],[500000000,499999999],[1000000000,999999998]]

错误📝：

D:巫师的总力量和

思路：
关键点：

1. 单调栈
2. 前缀和

错误📝：超时

练习

单调栈
左右栈

复盘

A 基础题
B 第一遍， 因为统计次数时操作数组导致超时。第二遍，针对性优化
C 未考虑到数据的边界
D 第一遍暴力超时， 单调栈、左右栈缺乏练习