202011第4周

本周关键词

• 滑动窗口
• 每日一题

做题数据

• 题目通过总数 10; 题目提交总数 10; 通过的提交数 17; 总提交数 42
• 困难 4; 中等 4; 简单 2

题目及代码

名字	难度	题目	解答	tag
0001.两数之和	简单	题目	代码	数组
0002.两数相加	中等	题目	代码	链表
0003.无重复字符的最长子串	中等	题目	代码	滑动窗口
0076.最小覆盖子串	困难	题目	代码	滑动窗口
0164.最大间距	困难	题目	代码	滑动窗口(每日一题)
0239.滑动窗口最大值	困难	题目	代码	滑动窗口
0424.替换后的最长重复字符	中等	题目	代码	滑动窗口
0454.四数相加II	中等	题目	代码	哈希表(每日一题)
0493.翻转对	困难	题目	代码	排序(每日一题)
1370.上升下降字符串	简单	题目	代码	排序(每日一题)

本周总结

本周是开始做LeetCode的第一周，初步定下了按照tag刷题的顺序。最先开始的tag是滑动窗口。做题途中顺便学习了滑动窗口、桶排序、归并排序、最大堆的知识，其中我认为最难的一题是 0239.滑动窗口最大值，用上了最大堆的知识。后期在刷 堆tag 的时候要仔细学习。

• 滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。其中比较重要的几点就是：
  • 搞清楚什么时候该移动左指针，什么时候该移动右指针；
  • 分析满足题目要求的条件该如何转换为代码。例如题目：0424.替换后的最长重复字符的条件，就可以转换为当前子串中最多的字符个数 N、可替换字符个数 k 的和是否能够大于等于字串长度 L ，也就是 N+k>=L。因此，分析题目是十分重要的一环。
• 归并排序的算法，由于来自每日一题，因此只是大致浏览，日后做到排序题时仍需仔细学习。
• Python标准库中的collections十分好用，以及其他的工具详见 Python库
• 总结大体的做题方法:
  1. 分析题目要求；
  2. 思考实现流程；
  3. 编写详细代码。

  在进行这一步时，不要思考下一步的内容，一步步来。做题首先考虑实现，再考虑优化，遍历永远是最好用的办法。