第2周 栈、队列、哈希表
2021-11-20
7分钟阅读时长
题目数量：9+
第4课 | 栈、队列、优先队列、双端队列
1. 栈和队列的实现与特性
参考链接
2. 实战题目解析：有效的括号、最小栈等问题
预习题目
// 方法一：用map，最优写法
func isValid(s string) bool {
n := len(s)
if n % 2 != 0 {
return false
}
mp := map[byte]byte{
')': '(',
']': '[',
'}': '{',
}
stack := []byte{}
for i := range s { //课替换 for i := 0; i < n; i++ {
if mp[s[i]] > 0 {
if len(stack) == 0 || stack[len(stack) - 1] != mp[s[i]] {
return false
}
stack = stack[:len(stack) - 1]
} else {
stack = append(stack, s[i])
}
}
return len(stack) == 0
}
// 方法二： 不用map
func isValid(s string) bool {
n := len(s)
if n % 2 != 0 {
return false
}
stack := []byte{}
for i := range s {
// 左括号入栈
if s[i] == '(' || s[i] == '[' || s[i] == '{' {
stack = append(stack, s[i])
} else {
if len(stack) == 0 {
return false
} else if s[i] == ')' {
if stack[len(stack) - 1] != '(' {
return false
}
} else if s[i] == ']' {
if stack[len(stack) - 1] != '[' {
return false
}
} else if s[i] == '}' {
if stack[len(stack) - 1] != '{' {
return false
}
}
stack = stack[:len(stack) - 1]
}
}
return len(stack) == 0
}
type MinStack struct {
stack, minStack []int
}
func Constructor() MinStack {
return MinStack{
stack: []int{},
minStack: []int{},
}
}
func (this *MinStack) Push(val int) {
this.stack = append(this.stack, val)
if len(this.minStack) == 0 {
this.minStack = append(this.minStack, val)
} else {
this.minStack = append(this.minStack, min(this.minStack[len(this.minStack) - 1], val))
}
}
func (this *MinStack) Pop() {
this.stack = this.stack[:len(this.stack)-1]
this.minStack = this.minStack[:len(this.minStack)-1]
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack) - 1]
}
func (this *MinStack) GetMin() int {
return this.minStack[len(this.minStack) - 1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/
实战题目
- 84. 柱状图中最大的矩形 困难 重点
// 方法一：栈(最优解), 两种写法：
// 1.栈中初始放入 -1，
// 2.heights 末尾追加 0
func largestRectangleArea(heights []int) int {
}
- 239. 滑动窗口最大值 困难 重点
// 方法一：暴力（每次去k个数字中的最大值,共有n-k+1个窗口）
// 方法二：双端队列
func maxSlidingWindow(nums []int, k int) (res []int) {
dq := []int{}
for i, num := range nums {
// 1.移除多余的数
if len(dq) > 0 && dq[0] <= i - k {
dq = dq[1:]
}
// 2.移除比当前数小的
for len(dq) > 0 && num > nums[dq[len(dq) - 1]] {
dq = dq[:len(dq) - 1]
}
dq = append(dq, i)
// 3.加入题解
if i >= k - 1 {
res = append(res, nums[dq[0]])
}
}
return res
}
// 方法三：动态规划
课后作业
- 用 add first 或 add last 这套新的 API 改写 Deque 的代码
Deque<String> deque = new LinkedList<String>();
deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
System.out.println(deque);
String str = deque.peekFirst();
System.out.println(str);
System.out.println(deque);
while (deque.size() > 0) {
System.out.println(deque.removseFirst());
}
System.out.println(deque);
分析 Queue 和 Priority Queue 的源码
641. 设计循环双端队列 中等 重点
type MyCircularDeque struct {
queue []int
front, last, cap int
}
func Constructor(k int) MyCircularDeque {
return MyCircularDeque{
queue: make([]int, k + 1, k + 1),
cap: k + 1,
}
}
func (this *MyCircularDeque) InsertFront(value int) bool {
if this.IsFull() {
return false
}
this.front = (this.front - 1 + this.cap) % this.cap
this.queue[this.front]= value
return true
}
func (this *MyCircularDeque) InsertLast(value int) bool {
if this.IsFull() {
return false
}
this.queue[this.last]= value
this.last = (this.last + 1) % this.cap
return true
}
func (this *MyCircularDeque) DeleteFront() bool {
if this.IsEmpty() {
return false
}
this.front = (this.front + 1) % this.cap
return true
}
func (this *MyCircularDeque) DeleteLast() bool {
if this.IsEmpty() {
return false
}
this.last = (this.last - 1 + this.cap) % this.cap
return true
}
func (this *MyCircularDeque) GetFront() int {
if this.IsEmpty() {
return -1
}
return this.queue[this.front]
}
func (this *MyCircularDeque) GetRear() int {
if this.IsEmpty() {
return -1
}
return this.queue[(this.last - 1 + this.cap) % this.cap]
}
func (this *MyCircularDeque) IsEmpty() bool {
return this.front == this.last
}
func (this *MyCircularDeque) IsFull() bool {
return this.front == (this.last + 1) % this.cap
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* obj := Constructor(k);
* param_1 := obj.InsertFront(value);
* param_2 := obj.InsertLast(value);
* param_3 := obj.DeleteFront();
* param_4 := obj.DeleteLast();
* param_5 := obj.GetFront();
* param_6 := obj.GetRear();
* param_7 := obj.IsEmpty();
* param_8 := obj.IsFull();
*/
- 42. 接雨水 困难 重点
// 方法一：动态规划
func trap(height []int) int {
}
// 方法二：单调栈，递减栈
func trap(height []int) (ans int) {
stack := []int{}
for i, h := range height {
for len(stack) > 0 && h > height[stack[len(stack)-1]]{
top := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
if len(stack) == 0 {
break
}
ans += (min(h, height[stack[len(stack) - 1]]) - height[top]) * (i - stack[len(stack) - 1] - 1)
}
stack = append(stack, i)
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
// 方法三：左右双指针
func trap(height []int) int {
}
说明：改写代码和分析源码这两项作业，同学们需要在第 1 周的学习总结中完成。如果不熟悉 Java 语言，这两项作业可选做。
第5课 | 哈希表、映射、集合
1. 哈希表、映射、集合的实现与特性
参考链接
课后作业
写一个关于 HashMap 的小总结
说明：对于不熟悉 Java 语言的同学，此项作业可选做。
2. 实战题目解析：有效的字母异位词等问题
实战题目 / 课后作业
func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
mp := [26]int{} // 可以用 mp := map[byte]int{} 替代，性能没有数组高
for i := range s {
mp[s[i] - 'a']++
mp[t[i] - 'a']--
}
for _, c := range mp {
if c != 0 {
return false
}
}
return true
}
- 49. 字母异位词分组 中等 重点
// 方法一：排序
func groupAnagrams(strs []string) [][]string {
mp := map[string][]string{}
for _, str := range strs {
s := []byte(str)
sort.Slice(s, func(i, j int) bool {return s[i] < s[j]})
sortedStr := string(s)
mp[sortedStr] = append(mp[sortedStr], str)
}
ans := [][]string{}
for _, v := range mp {
ans = append(ans, v)
}
return ans
}
// 方法二：计数
func groupAnagrams(strs []string) [][]string {
mp := map[[26]int][]string{}
for _, str := range strs {
cnt := [26]int{} // var cnt [26]int
for _, c := range str {
cnt[c - 'a']++
}
mp[cnt] = append(mp[cnt], str)
}
ans := [][]string{}
for _, v := range mp {
ans = append(ans, v)
}
return ans
}
func twoSum(nums []int, target int) []int {
mp := map[int]int{}
for i, x := range nums {
if j, ok := mp[target - x]; ok {
return []int{j, i}
}
mp[x] = i
}
return nil
}
参考链接
本周作业及下周预习
本周作业
简单
- 用 add first 或 add last 这套新的 API 改写 Deque 的代码
- 分析 Queue 和 Priority Queue 的源码
说明：改写代码和分析源码这两项作业，同学们需要在第 2 周的学习总结中完成。如果不熟悉 Java 语言，这两项作业可选做。
- 写一个关于 HashMap 的小总结。
说明：对于不熟悉 Java 语言的同学，此项作业可选做。
func twoSum(nums []int, target int) []int {
mp := map[int]int{}
for i, x := range nums {
if j, ok := mp[target - x]; ok {
return []int{j, i}
}
mp[x] = i
}
return nil
}
中等
// 方法一：排序
func groupAnagrams(strs []string) [][]string {
mp := map[string][]string{}
for _, str := range strs {
s := []byte(str)
sort.Slice(s, func(i, j int) bool {return s[i] < s[j]})
sortedStr := string(s)
mp[sortedStr] = append(mp[sortedStr], str)
}
ans := [][]string{}
for _, v := range mp {
ans = append(ans, v)
}
return ans
}
// 方法二：计数
func groupAnagrams(strs []string) [][]string {
mp := map[[26]int][]string{}
for _, str := range strs {
cnt := [26]int{}
for _, c := range str {
cnt[c - 'a']++
}
mp[cnt] = append(mp[cnt], str)
}
ans := [][]string{}
for _, v := range mp {
ans = append(ans, v)
}
return ans
}
困难
func trap(height []int) int {
}
JAVA相关题目
用 add first 或 add last 这套新的 API 改写 Deque 的代码
Deque<String> deque = new LinkedList<String>();
deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
System.out.println(deque);
String str = deque.peekFirst();
System.out.println(str);
System.out.println(deque);
while (deque.size() > 0) {
System.out.println(deque.removseFirst());
}
System.out.println(deque);
分析 Queue 和 Priority Queue 的源码（待补充）
关于 HashMap 的小总结（待补充）
如果哪里有错误，请高手指出
下周预习
预习知识点
- 二叉树基础（上）：什么样的二叉树适合用数组来存储？
- 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？
- 递归树：如何借助树来求解递归算法的时间复杂度？
- 分治算法：谈一谈大规模计算框架 MapReduce 中的分治思想
- 回溯算法：从电影《蝴蝶效应》中学习回溯算法的核心思想
- 堆和堆排序：为什么说堆排序没有快速排序快？
- 堆的应用：如何快速获取到 Top 10 最热门的搜索关键词？
- 图的表示：如何存储微博、微信等社交网络中的好友关系？