开个博客记录一下每日刷题，也算是一种recap了。

刷题记录

Leetcode十月挑战

1288. Remove Covered Intervals （10.04）

题目简介：

Given a list of intervals, remove all intervals that are covered by another interval in the list.

Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d.

After doing so, return the number of remaining intervals.

基本思路：

Greedy算法，如何判断一个interval是否被另一个cover了？—> 根据起始点排序，然后判断终点位置

将整个数组按照起始点从小到大排序，若起始点相同的，根据长度从长到短排序
遍历整个数组，若当前curr_end > prev_end，则uncovered++ & prev_end = curr_end；否则什么都不做

因为我们已经将整个数组根据起始点大小进行排序，所以我们遍历的时候只需要考虑终点的大小即可。

1009. Complement of Base 10 Integer (10.05)

题目简介：

将输入的十进制数字（对应的二进制表示），每一位都翻转，然后输出结果。

思路：

先用一个while循环计算出输入数字对应的二进制表示有多少位，然后从最高位开始逐位翻转并“append”到输出

// output left shift once
ans <<= 1;
// get the highest bit ((N >> cnt) & 1) (& 1 iis used to set all other bits to 0)
// flip it ^ 1
ans |= ((N >> cnt) & 1) ^ 1;

701. Insert into a Binary Search Tree (10.06)

题目简介：

将一个新的元素插入一个BST（二叉搜索树）

思路：

就是常规的BST插入即可，判断当前节点的值和待插入值的相对大小，比待插入节点大则往左走，否则往右走；可以用迭代或者递归两种方式实现。

61. Rotate List (10.07)

题目简介：

将一个链表向右”旋转”（循环移位）k次

思路：

基础思路很简单，找到len-k那个元素，把链表分成两部分，然后交换前后顺序即可，注意几个点

k = k % len，因为旋转len次等于没有旋转
判断k != 0，因为k=0等于没有旋转
判断head != nullptr，因为空链表怎么旋转都一样

170. Two Sum III - Data structure design (10.08)

题目简介：

Two Sum那题的延伸，让你设计一个Data Structure，有add和find两个函数

思路：

运用和Two Sum那题一样的思路即可，维持一个HashMap（不能用set是因为可能会有重复元素的出现），就可以保证add操作是O(1)；find操作是O(N)（遍历整个map）

449. Serialize and Deserialize BST (10.09)

题目简介：

序列化和反序列化一个二叉搜索树，常见的考点，很有实际应用价值。

思路：

序列化的时候，只需要对树进行preorder或者postorder遍历，然后输出一个字符串即可（为了优化程序，C++最好使用stringstream，Java最好使用StringBuilder）
反序列化的时候，只需要将输入的字符串逐个数字提取，然后插入到二叉搜索树里面即可（具体的插入算法可以用递归的方式实现）

452. Minimum Number of Arrows to Burst Balloons (10.10)

题目简介：

在二维空间上有一系列的圆形气球，从x轴开始向上垂直的射箭（箭飞向无穷远），问最少需要多少只箭才可以射爆所有气球。输入为一个二维数组，每一行有两个元素，分别是气球的$x_{start}$和$x_{end}$，只要箭的位置x满足$x_{start} \le x \le x_{end}$，就可以射爆该气球。

思路：

将气球根据起始坐标从小到大排序（相同的话则按照终止坐标从小到大排序），然后遍历整个数组，基本判断条件如下

if (points[i][0] <= end) {
    end = min(points[i][1], end);
} else {
    cnt++;
    end = points[i][1];
}

end保存了到当前时刻之前所有气球重叠区域的终点位置，故最新的气球若是起点小于end，则有重叠，可以一起射爆；反之，需要额外一箭。

316. Remove Duplicate Letters (10.11)

题目简介：

输入一个字符串，删除里面所有重复出现的字符，保证每个字符出现有且仅有一次；并且，保证输出的字符串是the smallest in lexicographical order

思路：

Greedy的思路，用一个list记录最终结果，从头到尾遍历输入字符串，针对每个字符，如果不在输出结果里面，则判断该字符和list尾部元素的大小，如果该字符小于list尾部元素，并且list尾部元素后面还会出现，则删除list尾部元素（while删除），然后插入新字符。遍历一遍后，list即为最终结果。Greedy之处在于，我们会尽可能的把最小的字符放在最前面的位置。

为此我们需要一个HashSet记录输出已经有的元素；一个HashMap记录整个字符串里面每一个字符最后出现的位置（用于判断元素后面还会不会出现）

859. Buddy Strings (10.12)

题目简介：

注意题目要求仅且交换一次，意味着只有两种情况是Buddy String

两个字符串只有两处不同，并且满足A[i] == B[j] && A[j] == B[i]
两个字符串完全相同，但是至少有一个字母重复出现了两次及以上

思路：

分两种情况讨论，相同则遍历一遍检查是否有重复出现的字母，不相同则遍历一遍检查是否只有两处不同且满足A[i] == B[j] && A[j] == B[i]

148. Sort List (10.13)

题目简介：

将一个LinkedList排序

思路：

使用MergeSort保证$O(nlog_n)$的时间复杂，而且由于是LinkedList，空间复杂度可以保证是$O(1)$

213. House Robber II (10.14)

题目简介：

回顾House Robber I里面，所有的房子成一条直线，robber不能偷窃两个相邻的房子；这题里面，房子从一条直线变成了一个环。

思路：

在一条直线的情况下，用动态规划解决，$dp[k] = max(dp[k-1], dp[k-2]+A_k)$。针对第k个房子，只有两种情况，抢 or 不抢，抢的话就是$dp[k-2]+A_k$（因为不能抢相邻的房子），不抢的话就是$dp[k-1]$。

环形的情况，我们只需要考虑最后一个房子，抢的话，则问题变为$[1, len - 1]$（因为不能再抢第一个房子）；不抢的话则是$[0, len - 2]$。

337. House Robber III (10.14)

题目简介：

和上一题一样的限制条件（不能rob两个相邻的房子），在这一题里面，所有房子的排列变成了一个二叉树。

思路：

可以用递归的思路，返回一个数组，其中0号元素代表抢这个房子；1号元素代表不抢这个房子

vector<int> robHelper(TreeNode* node) {
    if (node == nullptr) {
        return vector<int>(2, 0);
    }
    vector<int> left = robHelper(node->left);
    vector<int> right = robHelper(node->right);
    // rob this node
    int tmp1 = node->val + left[1] + right[1];
    // not rob this node (can choose either rob or not each child)
    int tmp2 = max(left[0], left[1]) + max(right[0], right[1]);
    // {rob, not rob}
    return vector<int>({tmp1, tmp2});
}

189. Rotate Array (10.15)

题目简介：

输入一个数组nums，和一个数字k，将数组nums向右旋转k次。

思路：

有多种思路：

1）暴力解法，逐次旋转，直到k次（$O(kn)$）
2）新建一个数组，直接一次拷贝原数组元素 ($O(n)$)

3）（十分巧妙）循环替换，从第i个元素开始，将第i+k个元素用第i个元素替换

  int current = start;
  int prev = nums[start];
  do {
    // 计算下一个元素的位置
    int next = (current + k) % nums.length;
    // 保存下一个元素原来的值
    int temp = nums[next];
    nums[next] = prev;
    prev = temp;
    current = next;
    count++;
  } while (start != current);

253. Meeting Rooms II (10.15)

题目简介：

输入一系列的会议时间（$[[s_1, e_1], [s_2, e_2]…]$, 开始+结束时间）, 问，至少需要多少个会议室才能承担所有的会议。

思路：

一开始最直接的思路，先将所有会议按照开始时间，从小到大排列（优先满足先到的会议）
然后我们其实不在乎具体哪间会议室是空的，我们只要知道有空的就可以了；所以可以用一个min-heap（priority_queue in c++）来保存现在所有正在进行会议的结束时间
每来一个新的会议，我们只需要将其的开始时间与heap顶端元素的结束时间对比，即可知道当前有无空闲会议室

74. Search a 2D Matrix (10.16)

题目简介：

在一个二维矩阵里面寻找一个指定元素，返回true or false表示存在或者不存在；其中这个矩阵，保证每一行元素都是从小到大排列，并且每一行的第一个元素一定比上一行的最后一个元素要大。

思路：

题目已经把所有corner case都基本排除掉了，直接逐行搜索即可（先判断在不在该行，$O(1)$），再用二分搜索查找，$O(logn)$。

211. Design Add and Search Words Data Structure (10.16)

题目简介：

设计一个数据结构，支持插入和查找字符串两种操作，查找的时候，可以用.来替代任意一个字符，如.ad可以匹配bad或者pad。

思路：

1）最简单粗暴的方式就是将插入的字符串根据长度分配到不同的数组，然后查找的时候逐一匹配；

2）构建一个树，每个节点为一个字符，和N个孩子，故一个完整的字符串就是从根节点开始，一路向下直到某一个节点（可以用一个bool变量，表示该节点是否为一个字符串的结尾）。

187. Repeated DNA Sequences (10.17)

题目简介：

输入一串DNA字符串，只包含“A，C，G，T”四种字符，问输入的字符串中有多少个长为10的重复子串出现。如输入s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”，输出[“AAAAACCCCC”,”CCCCCAAAAA”]

思路：

1）最简单粗暴的方式，以10位长度的滑动窗口遍历整个字符串，用一个HashSet记录所有见过的子串；如有重复则添加到输出；

2）上一种方式的缺点在于每移动一次都需要重新获取子串，可以采用编码的方式减小这样的overhead，比如ACGT分别对应0123，然后以4进制的方式，计算整个滑动窗口内数字的大小，这样每次移动滑动窗口只需要O(1)的时间重新计算。

1007. Minimum Domino Rotations For Equal Row (10.19)

题目简介：

输入两列骰子，问最少需要多少次交换才能使得某一列骰子数字全部一致，或者返回-1代表无法完成。

思路：

贪心算法，由于我们最终的目标是一列数字完全一样，所以只会有三种情况：1）最终数字为A[0]；2）最终数字为B[0]；3）不可能完成。

所以我们可以有一个checker函数，输入两个数组，一个目标数字，返回使得一个数组全为该数字需要的最少交换次数。然后两次调用（目标分别为A[0]和B[0]）。

133. Clone Graph (10.20)

题目简介：

输入一个图中的某一个节点，深拷贝一个一模一样的图。

思路：

BFS的思路，常规的BFS是用一个HashSet来记录访问过哪些节点，这里改为HashMap，其中Key为原图中的已访问的节点，Value为新图中的对应节点。然后进行常规的BFS搜索，针对每一个neighbor，如果未访问，则新建一个Node，连同改neighbor一起插入map里面；然后更新新图中对应节点的neighbors数组。

735. Asteroid Collision (10.21)

题目简介：

输入一个数组，每一个数字代表一颗小行星，正数代表向右飞行，负数代表向左飞行（从当前位置开始飞行，如[-1, 2]不会碰撞，但[2, -1]会碰撞），绝对值代表小行星的大小；如果两个小行星碰撞，则小的爆炸（大的保持原样），如果两个大小一致则相互抵消一起爆炸。求剩余的小行星.

思路：

思路很直接，遍历原数组，如果是正数，插入输出数组的最后；如果是负数，则从输出数组最后面开始，逐个比较，直到数组为空，元素为负或者找到一个比该行星大的。

456. 132 Pattern (10.23)

题目简介：

输入一个数组，判断数组内是否存在三个数满足，i<j<k && nums[i] < nums[k] < nums[j]。

思路：

1）优雅版的暴力解法($O(n^2)$); 从左到右遍历数组，用一个tmp记录到当前位置为止，最小的数是多少，若nums[i] > tmp则从这个位置开始向后遍历，寻找有无数满足tmp < nums[j] < nums[i];

2）优雅解法($O(n)$); 先遍历一遍数组，生成一个等长的min数组，其中$min[i]$代表到第i个位置位置的最小值；然后从后往前遍历数组，如果当前数nums[i] > min[i]，则不断pop stack直到stack为空或者stack最上面的元素比min[i]要大。若pop完stack还有元素剩余，并且头元素小于nums[i]，则返回true，不然把当前元素压栈，继续遍历；

for(int i = nums.size() - 1; i >= 0; i--) {
    if (nums[i] > minValue[i]) {
        while(!sk.empty() && sk.top() <= minValue[i]) {
            sk.pop();
        }
        if (!sk.empty() && sk.top() < nums[i]) {
            return true;
        }
        sk.push(nums[i]);
    }
}

948. Bag of Tokens (10.24)

题目简介：

输入一个数组，每一个数代表一个token，你有一个初识P(ower)值，针对每一个token，你可以选择将其面朝上，那么你会失去token这么多的power但是score+1；也可以选择面朝下，那么你会得到token这么多的power但是score-1；注意：power和score始终都要>=0，每个token最多使用一次，但可以不使用完全部token，并且score初始值为0。请问你能获得的最大score是多少？

思路：

现将整个token数列从小到大排序，然后遍历（用start和end两个指针）；原则是，从头开始将尽可能多的token面朝上（score+1），直到power不足的时候，将最后一个token面朝下（power+token），然后继续；此过程中保证start始终小于等于end即可。因为只要start<end，那么将最后一个面朝下，至少不会使得我们的结果更坏（始终可以通过将tokens[start]面朝上来弥补score的变化）。

(10.24)

题目简介：

思路：

Leetcode每日挑战

刷题记录

Leetcode十月挑战

1288. Remove Covered Intervals （10.04）

1009. Complement of Base 10 Integer (10.05)

701. Insert into a Binary Search Tree (10.06)

61. Rotate List (10.07)

704. Binary Search (10.08)

170. Two Sum III - Data structure design (10.08)

449. Serialize and Deserialize BST (10.09)

452. Minimum Number of Arrows to Burst Balloons (10.10)

316. Remove Duplicate Letters (10.11)

859. Buddy Strings (10.12)

148. Sort List (10.13)

213. House Robber II (10.14)

337. House Robber III (10.14)

189. Rotate Array (10.15)

253. Meeting Rooms II (10.15)

74. Search a 2D Matrix (10.16)

211. Design Add and Search Words Data Structure (10.16)

187. Repeated DNA Sequences (10.17)

1007. Minimum Domino Rotations For Equal Row (10.19)

133. Clone Graph (10.20)

735. Asteroid Collision (10.21)

456. 132 Pattern (10.23)

948. Bag of Tokens (10.24)

(10.24)