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.

题目地址:leetcode Valid Parentheses

题目大意 给定三种括号组成的字符串,让你判断是否合法

思路

用栈判断即可。

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.

传送门

题意:设计一个数据结构,要求实现LRU(Least Recently Used 即最近最不常使用)功能

  • 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:

传送门

题意:给定一个字符串数组(后缀表达式)求其计算结果

思路:遇到四则运算符时候,从栈中取出两个元素进行计算。然后入栈。

我巧妙的运用了异常处理,代码更简洁、更优雅。

还有就是Python负数除法需要注意。

 


 

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,

传送门

题意:给定一个DNA字符串,返回不只出现过一次的10个字符长的子串

思路:枚举所有10字符的子串,直接用哈希表即可

 


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.

 传送门

题意:要求实现前缀树。

思路:直接写呗。。。

我是用结点上的end判断是否有以这个字母作为结束的单词。因为相同单词路径唯一。

 

 


 

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.

传送门

题意:和上一题一样,实现个数据结构,有插入和查找功能。查找的时候’.’可以代替任意字符。

思路:就是search的时候需要注意.的情况需要遍历当前层所有的点

 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题的DFS方法差不多,就是要求效率更高。所以可以使用前缀树!看看当前路径上前缀树是否有,若没有,则直接剪枝了。

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).

BuildingsSkyline Contour

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], ...]

题目地址:leetcode The Skyline Problem

题意:给定一些[L,R,H]这样的数组,L,R分别表示矩形起始和终点,H表示高度。 让你求这些矩形的外轮廓中的左端点

思路:

我觉得写不出比 https://briangordon.github.io/2014/08/the-skyline-problem.html 更好的分析了。

我简单的说下大概内容。

就是朴素的方法枚举所有可能的点(每个矩形的左边和右边),然后再枚举包括当前点的所有矩形。 当前的轮廓线取最高的那点。复杂度O(n^2)

更进一步的做法是用堆来看当前最高的高度。

此外由于C++的heap不能删除特定的点,因此用个map标记一下。

还有就是一开始预处理的时候,把左边的高度设为负数,这样就区分开了左右端点。

详见代码。

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).

题目地址:leetcode Implement Queue using Stacks

题意:要求你用栈来实现队列。

思路:栈和队列可以说恰好是相反的,栈是后进先出(LIFO),而队列是先进先出(FIFO)。

所以,这题可以进行push的时候,可以把其中一个栈的元素放到个临时的栈里,然后把新的元素push,接着把放到临时的栈里的数弄回来。比如1234(最右边的为top,这里是4) 放到临时栈为4321,然后原来栈放入5,接着把临时栈的放回来,就是51234

更好的方法是,用两个栈来做,一个负责输入input,一个负责输出output。

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

对于21354,我们先按顺序放入input,栈为:21354(右边栈顶)

如果要输出,则都放入output,  栈就变成了 45312 (直接反过来了)

接着如果有新的数push,也只要到input即可。直到output为空了,才继续从input拿

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.

Follow up:
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.

题目地址:leetcode Sliding Window Maximum

题意:给定一个数组和一个窗口大小K,要你从数组中按顺序将所有相邻的K个数中最大值输出。

思路:最暴力的方法当然是枚举起点和接下来的K个数,复杂度O(nk) 这题涉及RMQ等,有方法可以做到O(nlogn)的预处理,然后O(1)的查询,总复杂度O(nlogn) 当然这题用堆也可以。。

线性的时间怎么办? 那肯定是要观察窗口移动过程中,移出了一个数,然后加入了一个数,我也想到了双端队列。 然而感觉一个长度为K的双端队列没啥用啊?点开hint看到hint2我就醒悟了。

我们维护一个双端队列,第一个元素为最大值,对于窗口移动过程中,新加进来的元素x从队尾向前比较,把小于它的数抛弃掉。(因为x不但大而且在后面,前面的而且小的数是不会为窗口内的最大值的)。此外,若第一个元素已经在窗口外了,那么抛弃第一个即可。

由于队列的长度不可能超过n个,因此复杂度为O(n)。

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].

题目地址:leetcode Flatten Nested List Iterator

题意:给定一个NestedInteger 列表,要求把它展开。 比如[[1,1],2,[1,1]] (里面每一项均为NestedInteger类型)展开为[1,1,2,1,1].

思路:

首先来看看定义:

发现该类有3个函数,是否整数、整数就取整数、列表就取列表。

这题要实现 NestedIterator类要实现3个接口,如下:

调用方式为:

确保你已经明白题意在往下看。

看到待展开的表达式时嵌套的,就想到,可以用递归开挂~ 水水的1A。

思想是初始化先处理好全部,接下来只要从结果集合中拿就好了

 

但其实递归的方法把所有的解都存起来了,严格的说,不是迭代Iterator,不过给我们实现Iterator提供了思路,就是把递归改成迭代。

怎么改呢~ 用栈啊,当 现在的栈顶的不是整形(那就是List,调用getList),就把List取出,在压入栈,循环即可。

而实现上,比刚才的递归还要优雅:

 

 

 

 

 

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:

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

题目地址:leetcode Data Stream as Disjoint Intervals

题意:要求实现一个数据结构,可以满足不断添加数字,并进行区间的更新。

思路:

这题貌似二分查找也可以,手写BST也可以,不过还是用java的TreeMap实现起来比较方便。

我们根据区间起始位置(就是start)作为BST 的key,对于要添加的数val,查找其左右区间。。  ceil 满足 val < key , floor 满足 key <= val

然后判断其范围进行合并。 感觉没啥好说的。。

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.

题目地址:leetcode All O’one Data Structure

题目大意:要求实现一个数据结构,四个接口都需要在O(1)的时间内执行。

思路:

双向链表+hash

链表中每个节点保存对应的val,以及相应的key。

求最大和最小key只需要从头或者尾巴拿即可。

C++

由于c++有双向链表的接口,因此可以直接用:

自己写的双向链表

 

Java

 

Python

 

 

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 数据结构
本文地址:https://www.hrwhisper.me/leetcode-datastructure/

您的支持将鼓励我继续创作!

Leetcode , , , . permalink.

3 thoughts on “leetcode 数据结构

Leave a Reply

Your email address will not be published. Required fields are marked *