HOT100刷题

2023.2.16

1:两数之和 注意是无序数组。要么排序用双指针要么用哈希。哈希就是unordered_map。需要注意的是hashmap.find 返回值是一个C++里面的pair类型。

2023.2.26

2.链表相加 因为是逆序的链表，实际上不难，重点在于容易忽略最后的进位。

2023.2.27

3.无重复字符的最长字串 比较简单，用滑动窗口模拟就好了。

2023.2.28

4.寻找两个正序数组的中位数

第一想法当然是用类似于归并排序的方法合起来，但是显然复杂度是(n+m)/2，大于log(m+n)。因此考虑中位数问题最常见的方法：二分（其实碰到log复杂度的大多是二分）

很高级的二分。首先目标可以转化为得到第k小的数。但是两个数组不好区分，所以采取逐次剔除掉k/2个数，然后再迭代。

既然是迭代，必须考虑边界条件和截止条件。

边界首先要考虑其中一个数组长度小于k/2。此时我们根据情况来。首先是取最后一个元素，此时就不能直接排除掉k/2个元素，而是根据具体情况判断。当数组为空，直接返回另一个的第k小。当k=1时，返回两个数组首元素的最小值即可。

emmm要注意的点是三个边界条件的优先级不一样，数组为空排在k=1 的前面，否则会越界。

很不错的一道题

2023.3.1

5.最长回文子串

脑子里面闪现了一下动态规划，但是粗想了一下感觉不好实现所以没继续…实际上就是一个动态规划。O(n^2)。

更直观的方法是遍历所有的中心，然后像向两边拓展（其实也是动规）。重点在于要考虑单字母在中心和一对在中心的情况。

代码不难，实现上可以利用pair<int , int >来返回左右边界。需要掌握pair匿名结构的生成{}以及first、second的读取。