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

时间：2020-5-15 参赛入口：https://leetcode.cn/contest/weekly-contest-293/ 讨论： 代码地址：

A: 移除字母异位词后的结果数组

思路：字符统计
关键点：

  1. function removeAnagrams(words: string[]): string[] {
  2.     const n = words.length;
  3.     let ans = [];
  4.     ans.push(words[0]);
  5.     let pre = countWord(words[0]).join('');
  6.     for (let i = 1; i < n; i++) {
  7.         let cur = countWord(words[i]).join('');
  8.         if (pre !== cur) {
  9.             ans.push(words[i]);
  10.             pre = cur;
  11.         }
  12.     }
  13.     return ans;
  14. };
  16. function countWord (word: string): number[] {
  17.     let count = new Array(128).fill(0);
  18.     for (let i = 0; i < word.length; i++) {
  19.         count[word.charCodeAt(i)]++;
  20.     }
  21.     return count;
  22. }

总结：

B: 不含特殊楼层的最大连续楼层数

思路：排序
关键点：

  1. function maxConsecutive(bottom: number, top: number, special: number[]): number {
  2.     let nums = special.slice().sort((a, b) => a - b);
  3.     nums.unshift(bottom - 1);
  4.     nums.push(top + 1);
  5.     let ans = 0;
  6.     const n = nums.length;
  7.     for (let i = 1; i < n; i++) {
  8.         ans = Math.max(ans, nums[i] - nums[i - 1] - 1);
  9.     }
  10.     return ans;
  11. };

总结：

C: 按位与结果大于零的最长组合

思路：逐个考虑每一个比特位
关键点：
由于 2^{23} < 10^7<2^{24}，枚举比特位可以从 0 枚举到 23

  1. function largestCombination(candidates: number[]): number {
  2.     const n = 24;
  3.     let ans = 0;
  4.     for (let i = 0; i < n; i++) {
  5.         let count = 0;
  6.         for (let num of candidates) {
  7.             if (num >> i & 1) count++;
  8.         }
  9.         ans = Math.max(ans, count);
  10.     }
  11.     return ans;
  12. };

总结：

D: 统计区间中的整数数目

思路：(动态开点)线段树
关键点：

  1. class CountIntervals {
  2.     left: null | CountIntervals;
  3.     right: null | CountIntervals;
  4.     start: number;
  5.     end: number;
  6.     sum: number;
  7.     constructor(start: number = 0, end: number = 10 ** 9) {
  8.         this.left = null;
  9.         this.right = null;
  10.         this.start = start;
  11.         this.end = end;
  12.         this.sum = 0;
  13.     }
  15.     add(left: number, right: number): void {
  16.         if (this.sum == (this.end - this.start + 1)) return;
  17.         if (left <= this.start && right >= this.end) {
  18.             this.sum = this.end - this.start + 1;
  19.             return;
  20.         }
  21.         let mid = (this.start + this.end) >> 1;
  22.         if (!this.left) this.left = new CountIntervals(this.start, mid);
  23.         if (!this.right) this.right = new CountIntervals(mid + 1, this.end);
  24.         if (left <= mid) this.left.add(left, right);
  25.         if (right > mid) this.right.add(left, right);
  26.         this.sum = this.left.sum + this.right.sum;
  27.     }
  29.     count(): number {
  30.         return this.sum;
  31.     }
  32. }
  34. /**
  35.  * Your CountIntervals object will be instantiated and called as such:
  36.  * var obj = new CountIntervals()
  37.  * obj.add(left,right)
  38.  * var param_2 = obj.count()
  39.  */

总结：

线段树类型集合：

715. Range 模块

复盘

image.png

c 初步分析采用BFS， 存值出现问题卡壳。原因对位运算， 缺乏本质理解。
d 初步分析， 采用合并区间。 原因线段树类型未涉及过， 方案针对类型训练。