Design系列问题
高频题
这类题基本上都是高频题
146. LRU Cache
这道题是很高频的题目,主要hint就是用双向链表来实现
1 | class Node: |
155. Min Stack
这道题就是用stack来存sofar的最小值
1 | class MinStack(object): |
716. Max Stack
与上一道题相类似,区别就是在popMax的时候用临时stack来记录
1 | class MaxStack(object): |
225. Implement Stack using Queues
在init的时候,每当新元素进来的时候,不断让queue的元素pop出来在加到queue尾,从而index为0 的元素就是最后加进来的
1 | class MyStack(object): |
232. Implement Queue using Stacks
用两个stack,在pop的时候,也是同样的像上一题的操作,加到另外一个stack中
1 | class MyQueue(object): |
297. Serialize and Deserialize Binary Tree
这道题就是BFS遍历树,然后BFS解析树,注意index的值
1 | # Definition for a binary tree node. |
173. Binary Search Tree Iterator
这道题也是高频题,FB面过.注意pushAll的时候是判断root!
1 | # Definition for a binary tree node |
380. Insert Delete GetRandom O(1)
用dic来记录value和对应的index,从而能保证O(1)时间内删除
1 | import random |
381. Insert Delete GetRandom O(1) - Duplicates allowed
dic里面的值用set来记录
1 | import random |
Trie类型
简单构建
在程序中需要简单构建一个Trie
1 | trie = {} |
208. Implement Trie (Prefix Tree)
基础类型
1 | from collections import defaultdict |
211. Add and Search Word - Data structure design
如何处理. 的问题,用string的slice来搞,find的递归操作
1 | from collections import defaultdict |
642. Design Search Autocomplete System
进阶版本 取前三个。很复杂的题
1 | class TrieNode(object): |
一般的题
281. Zigzag Iterator
就是正常的来
1 | class ZigzagIterator(object): |
284. Peeking Iterator
先预存next的值
1 | # Below is the interface for Iterator, which is already defined for you. |
359. Logger Rate Limiter
window的size为10
1 | class Logger(object): |
362. Design Hit Counter
因为是统计当时的hit值,所以可以维护一个全局变量hit
1 | class HitCounter(object): |