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

时间：2020-5-1 花费： 1.5 + 2h 讨论：https://leetcode-cn.com/circle/discuss/nf6j8j/ 代码地址：

A: 移除指定数字得到的最大结果

思路：贪心
关键点：贪心

  1. function removeDigit(number: string, digit: string): string {
  2.     let nums = number.split('');
  3.     const n = nums.length;
  4.     let ans = 0;
  5.     for (let i = 0; i < n; i++) {
  6.         if (nums[i] != digit) continue;
  7.         ans = i;
  8.         if ((i + 1 < n) && (nums[i + 1] > nums[i])) break;
  9.     }
  10.     // console.log(ans)
  11.     nums.splice(ans, 1);
  12.     return nums.join('');
  13. };

总结： :::info

贪心法练习：

402. 移掉K位数字

1881. 插入后的最大值

::: 题解难点： 贪心证明推到

B: 必须拿起的最小连续卡牌数

思路：哈希表
关键点：哈希表

  1. function minimumCardPickup(cards: number[]): number {
  2.     const n = cards.length;
  3.     let hashMap = new Map<number, number>();
  4.     const max = Number.MAX_SAFE_INTEGER;
  5.     let ans = max;
  6.     for (let i = 0; i < n; i++) {
  7.         let num = cards[i];
  8.         if (hashMap.has(num)) {
  9.             ans = Math.min(i - hashMap.get(num) + 1, ans);
  10.         }
  11.         hashMap.set(num, i);
  12.     }
  13.     return ans == max ? -1 : ans;
  14. };

总结：无

C: 含最多 K 个可整除元素的子数组

思路：滑动窗口
关键点：

  • 滑动窗口
  • 借助子数组转字符串去重
  • 注意，滑动窗口的边界是第k+1个可以被整除的元素之前
    1. function countDistinct(nums: number[], k: number, p: number): number {
    2.   const n = nums.length;
    3.   const numSet = new Set(nums);
    4.   const verfiedSet = new Set<number>();
    5.   for (let i of numSet) {
    6.       if (i % p != 0) continue;
    7.       verfiedSet.add(i);
    8.   }
    9.   let ans = new Set<string>();
    10.   for (let i = 0; i < n; i++) {
    11.       let sub = [];
    12.       for (let j = i, cnt = 0; j < n; j++) {
    13.           const num = nums[j];
    14.           if (verfiedSet.has(num)) cnt++;
    15.           if (cnt > k) break;
    16.           sub.push(num);
    17.           const str = sub.join(',');
    18.           ans.add(str);
    19.       }
    20.   }
    21.   // console.log(ans);
    22.   return ans.size;
    23. };
    总结：

D: 字符串的总引力

思路：动态规划
关键点：动态规划

function appealSum(s: string): number {
    const n = s.length;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 0;
    const hashMap = new Map();
    for (let i = 0; i < n; i++) {
        const c = s.charAt(i);
        dp[i + 1] = dp[i] + i + 1 - (hashMap.get(c) || 0);
        hashMap.set(c, i + 1);
    }
    return dp.reduce((a, c) => a + c, 0);
};

总结： :::info 类似题：

改进：

  • 先实现再优化