目录
概述
本周学习了哈希表，字符串以及栈和队列。相对于上周难度有所提升，下面对每个章节进行描述。
哈希表
上周的数组和链表，大多数题目是模拟和对于解决问题的算法的直接思考。对于哈希表，考察的往往是何时利用该结构进行问题的解决，即应用问题。
- 对于字典，一般是在需要统计数量（频率）时使用。py中一般用defaultdict方便刚开始加入时的处理，defaultdict和py内置的字典统计数量时区别如下。
dic = defaultdict(int)
for elem in lst:
dic[elem]+=1
dic2 = {}
for elem in lst:
if c not in dic2:
dic2[c] = 1
else:
dic2[c]+=1
- 对于集合，一般是在快速判断元素是否在集合中时使用。
重要题目及思路
本章中的202.快乐数中，加强了对一个数字每一位数的处理的方式.
while n:
lowdigit = n % 10 # 取出个位
# 这里处理lowdight
n //=10 #得到去除个位后的数
对于两数之和，三数之和，四数之和的思考。
- 两数之和是确定之前有无与当前位置匹配的值，可利用哈希表（字典）来加快搜索。
- 三数之和，四数之和是双指针法和去重逻辑的使用，未用到哈希表。
- 四数之和是统计前两个数组之和和后两个数组之和的出现次数，所以可以使用字典。
字符串
字符串的题目也比较难，实际也是类似对数组中元素的处理，主要是py中可以用切片来处理很多复杂的逻辑，以及py中的相关的概念。
重要题目及思路
- 反转字符串第一个想到的方法是双指针法，此外针对py,还可以用切片直接反转
lst[start:end] = lst[start:end][::-1]
- 反转字符串II 学到的方法是每次的起点是2k 所以可以利用循环步数。此外还有切片的妙用。
- 反转字符串中的单词学习到了的思路是可以先反转整体，再反转每个单词。对于py，可以转为列表后，直接反转列表，然后添加空格转为字符串。
- 关于语言的细节如切片，可变对象，浅拷贝等请看Day8 字符串part1
- KMP很久以前看过，只记得个next数组，暂时还没看，后续有时间补吧
栈和队列
关于栈和队列，主要就是应用问题。
重要题目及思路
- 用栈实现队列关键在于模拟，出队方法的实现是关键，注意条件，队列为空时返回None，out栈为空时的逻辑，是将in栈中的元素放入到out栈中，然后弹出，out栈非空的逻辑是直接弹出。
- 用队列实现栈实际只用一个队列即可，出栈的方法是遍历队列并出队直到最后一个元素。
上面两道题只是提供了一种思考方式，来应对面试，实际应用中作用不大。
- 有效的括号，删除字符串中的所有相邻重复项以及逆波兰表达式求值 均为栈的应用，即消除相邻元素。
- 滑动窗口最大值 提供了一种双端队列实现自定义滑动窗口维持队首最大值的方式
- 前 K 个高频元素 topK问题，是堆（优先级队列）的典型应用，小顶堆中添加k个元素，新来元素加入时，自动调整堆结构，将堆顶最小元素弹出。保证入堆过程中，堆中的元素一直是最大的k个。又由于是统计频率，也使用了字典处理。（这里只学习了堆的应用，关于其实现之前看过，插入删除建堆等，暂不复习）。注意py中的堆heapq的使用。