# leetcode 数据结构

• 20. Valid Parentheses
• 146 LRU Cache
• 150 Evaluate Reverse Polish Notation
• 155 Min Stack
• 187 Repeated DNA Sequences
• 208 Implement Trie (Prefix Tree)
• 211 Add and Search Word – Data structure design
• 218 The Skyline Problem
• 232 Implement Queue using Stacks
• 239 Sliding Window Maximum
• 341 Flatten Nested List Iterator
• 352 Data Stream as Disjoint Intervals
• 432 All O’one Data Structure

### 20. Valid Parentheses

Given a string containing just the characters `'('``')'``'{'``'}'``'['` and `']'`, determine if the input string is valid.

The brackets must close in the correct order, `"()"` and `"()[]{}"` are all valid but `"(]"` and `"([)]"` are not.

C++

Python

### 146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: `get` and `set`.

`get(key)` – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
`set(key, value)` – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

• get(key)： 获取Key对应的值，如果不存在返回-1
• set(key, value) ： 设置key的值为value，超过容量，那么应先删除最近最不常使用的元素，再插入

LRU是在OS课上有讲过。当我们访问过一个元素，设置一个元素的时候，都应该标记一下刚使用过。

• 构造函数中创建一个list q和一个字典dic
• get时候，如果元素存在，将q中对应的key删除，并将其插入队尾
• set时候，如果元素不存在且容量过大，删除队首元素，将新插入队尾和字典。如果元素存在，只需要设置字典，和将q中对应的调到队尾即可。（先删除后插入）

C++

Python

Java

### 150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are `+`, `-`, `*`, `/`. Each operand may be an integer or another expression.

Some examples:

### 155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

• push(x) — 把x入栈
• pop() — 删除栈顶
• top() — 获取top元素
• getMin() — 返回栈中最小元素

### 187. Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

### 208. Implement Trie (Prefix Tree)

Implement a trie with `insert`, `search`, and `startsWith` methods.

Note:
You may assume that all inputs are consist of lowercase letters `a-z`.

传送门

### 211. Add and Search Word – Data structure design

Design a data structure that supports the following two operations:

search(word) can search a literal word or a regular expression string containing only letters `a-z` or `.`. A `.` means it can represent any one letter.

For example:

Note:
You may assume that all words are consist of lowercase letters `a-z`.

C++

### 212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = `["oath","pea","eat","rain"]` and board =

Return `["eat","oath"]`.

Note:
You may assume that all inputs are consist of lowercase letters `a-z`.

79 Word Search的题解： https://www.hrwhisper.me/?p=523

### 218. The Skyline Problem

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you aregiven the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers `[Li, Ri, Hi]`, where `Li` and `Ri` are the x coordinates of the left and right edge of the ith building, respectively, and `Hi` is its height. It is guaranteed that `0 ≤ Li, Ri ≤ INT_MAX`, `0 < Hi ≤ INT_MAX`, and `Ri - Li > 0`. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: `[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] `.

The output is a list of “key points” (red dots in Figure B) in the format of `[ [x1,y1], [x2, y2], [x3, y3], ... ]` that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:`[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]`.

Notes:

• The number of buildings in any input list is guaranteed to be in the range `[0, 10000]`.
• The input list is already sorted in ascending order by the left x position `Li`.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, `[...[2 3], [4 5], [7 5], [11 5], [12 7]...]` is not acceptable; the three lines of height 5 should be merged into one in the final output as such: `[...[2 3], [4 5], [12 7], ...]`

C++

### 232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack — which means only `push to top`, `peek/pop from top`, `size`, and `is empty` operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

• push:放入input即可
• peek / pop : 若output为空，则把input中的移入output
• empty: input 和 output 均为空

C++

Python

### 239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the knumbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = `[1,3,-1,-3,5,3,6,7]`, and k = 3.

Therefore, return the max sliding window as `[3,3,5,5,6,7]`.

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Could you solve it in linear time?

Hint:

1. How about using a data structure such as deque (double-ended queue)?
2. The queue size need not be the same as the window’s size.
3. Remove redundant elements and the queue should store only elements that need to be considered.

Python

### 341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list `[[1,1],2,[1,1]]`,

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: `[1,1,2,1,1]`.

Example 2:
Given the list `[1,[4,[6]]]`,

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: `[1,4,6]`.

### 352. Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers a1, a2, …, an, …, summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:

What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

PS: C++只有lower_bound和upper_bound， 不像java treemap那么爽 ( ╯□╰ ) Python好像没看过平衡树的样子？

### 432. All O’one Data Structure

Implement a data structure supporting the following operations:

1. Inc(Key) – Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
2. Dec(Key) – If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
3. GetMaxKey() – Returns one of the keys with maximal value. If no element exists, return an empty string `""`.
4. GetMinKey() – Returns one of the keys with minimal value. If no element exists, return an empty string `""`.

Challenge: Perform all these in O(1) time complexity.

C++

Java

Python

Leetcode , , , . permalink.

### 3 thoughts on “leetcode 数据结构”

1. Tongyun Wu says:

博主， 你的155题 的 getMin( )不是O(1)复杂度吧