最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
top() – 获取栈顶元素。
getMin() – 检索栈中的最小元素。
示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

解法：
最简单的就可以想到使用列表。
但是要实现检索最小值的功能，可以想到维护一个最小值，就像前缀树中维护一个word的布尔类型一样。
注意随时更新min，可以加快运行速度

class MinStack(object):def __init__(self):"""initialize your data structure here."""self.stack = []self.min = Nonedef push(self, x):""":type x: int:rtype: None"""self.stack.append(x)if self.min == None or self.min > x:self.min = xdef pop(self):""":rtype: None"""tmp = self.stack.pop()if len(self.stack) == 0:self.min = Noneif self.min == tmp:self.min = self.stack[0]for x in self.stack:if self.min > x:self.min = xdef top(self):""":rtype: int"""return self.stack[-1]def getMin(self):""":rtype: int"""return self.min# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

数据流的中位数

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

解法
对于有序数组求中位数很简单了，但是题目给的是数据流，也就是我们必须做到可以时刻求出中位数的程度。

第一种方法:我们可以给每个从数据流出来的数进行排序,然后数组长度除以2就能得到中位数，但显然这样的做法是非常不好的，如果新进来的数是比当前排好序的所有元素都小的数，那么意味着数组中的所有数都必须向后移动一位，也就是O(n)的复杂度，假设每进来一个数都来一遍O(n)，性能还是很低的。

第二种方法:采用优先队列，也就是大根堆跟小根堆，我们将较小的n/2个数放到大根堆中，将较大的n/2个数放到小根堆中，显然，如果n是偶数，那么大根堆的堆顶跟小根堆的堆顶就是我们要找的两个中位数，将其相加除以2作为结果返回即可。如果n是奇数，那么就看大根堆跟小根堆谁的节点个数比另一个堆多一个，节点数量多的那个堆的堆顶就是我们要找的中位数，此时我们直接返回结果即可。

需要注意的是:

1.对于取堆顶元素的操作的时间复杂度是常数级别的。

2.插入新节点时我们需要判断节点的值是否小于大根堆堆顶的值或者大于小根堆堆顶的值，

如果小于大根堆堆顶的值，那么节点应该插入大根堆，反过来应该插入小根堆。

3.每次插入新节点我们还需要判断两个堆之间的元素个数是否平衡。插入新节点后，我们判断两个堆的元素个数，如果相差为2那么我们就要对堆进行调整。比如新插入一个节点到小根堆中，而此时大根堆的个数+1小于小根堆的节点个数，这个时候只需要将小根堆的堆顶元素弹出，然后将这个弹出的元素插入大根堆即可。反过来也是一样的操作。为什么可以这样做呢？这是因为我们说了小根堆保存的是较大的n/2个数，而小根堆的堆顶是小根堆中最小的元素，同时也是大根堆中最大的元素，因此我们将这个堆顶元素弹出并插入大根堆的操作并不会破坏“小根堆保存较大的n/2个数，大根堆保存较小的n/2”这样的前提。

class MedianFinder:def __init__(self):"""initialize your data structure here."""self.max_heap = []self.min_heap = []def addNum(self, num):if not self.max_heap:heapq.heappush(self.max_heap, -num)  # python的heaqp模块是小根堆，因此要保存大根堆的话需要加上一个负号returnif num > -self.max_heap[0]:heapq.heappush(self.min_heap, num)if len(self.max_heap) + 1 < len(self.min_heap):heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))  # 插入大根堆需要给值加负号else:heapq.heappush(self.max_heap, -num)if len(self.max_heap) > len(self.min_heap) + 1:heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))  # 弹出大根堆堆顶的时候需要加负号变为正数def findMedian(self):if len(self.max_heap) > len(self.min_heap):   # 大根堆元素多一个，中位数是大根堆堆顶return -self.max_heap[0]if len(self.max_heap) < len(self.min_heap):   # 小根堆元素多一个，中位数是小根堆堆顶return self.min_heap[0]else:return (-self.max_heap[0] + self.min_heap[0])/2# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

解法

• 最简单的就是给数组排序，求k这个Index位置上的数
• 使用快速排序思想，就是找第k个pointer。注意是从左到右从大到小排序，使用partition比较简单些。
• 递归，就是麻烦一点，和解法二差不多

class Solution(object):def findKthLargest(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""return self.quick(nums, 0, len(nums)-1, k-1)def quick(self, nums, l, r, k):if l == r:return nums[l]p = self.partition(nums, l, r)if p == k:return nums[p]elif k < p:return self.quick(nums, l, p-1, k)else:return self.quick(nums, p+1, r, k)def partition(self, nums, l, r):j = lfor i in range(l+1, r+1):if nums[i] > nums[l]:j+=1nums[i], nums[j] = nums[j], nums[i]nums[j], nums[l] = nums[l], nums[j]return j

解法3：

class Solution:def _partition(self, nums, l, r):j = lfor i in range(l + 1, r + 1):if nums[i] > nums[l]:j += 1nums[i], nums[j] = nums[j], nums[i]nums[l], nums[j] = nums[j], nums[l]return jdef findKthLargest(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""l, r, k = 0, len(nums) - 1, k - 1while 1:p = self._partition(nums, l, r)if k == p:return nums[p]elif k < p:r = p - 1else:l = p + 1

有序矩阵中第K小的元素

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个元素。

示例:

matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

返回 13。
说明:
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

解法：

• 利用最大堆，建一个大小为k的最大堆，遍历矩阵，将矩阵元素一一插入到堆中，堆的大小超过k后要弹出堆顶元素。这样做时间复杂度为O(N2logk)。但是这种解法没有利用到矩阵行和列分别有序的信息。
• 可以用二分查找法来做，我们由于是有序矩阵，那么左上角的数字一定是最小的，而右下角的数字一定是最大的，所以这个是我们搜索的范围。然后我们算出中间数字mid，由于矩阵中不同行之间的元素并不是严格有序的，所以我们要在每一行都查找一下mid。
  1.首先设置mid的初值为矩阵matrix，最后一个数和第一个数的平均值。
  2.统计矩阵中所有行小于mid值的个数之和。若cnt小于8，L = mid + 1，并更新mid；若该值大于8，R = mid。
  3.重复上述搜索，直至L和R不满足L < R,此时的L或者R值即为所求。

class Solution(object):def kthSmallest(self, matrix, k):""":type matrix: List[List[int]]:type k: int:rtype: int"""a, b = len(matrix), len(matrix[0])left = matrix[0][0]right = matrix[a-1][b-1]while left < right:mid = left + (right - left) / 2cnt = 0for i in range(a):j = b-1while j >=0 and matrix[i][j] > mid:j -= 1cnt += j+1if cnt < k:left = mid + 1else:right = midreturn left

滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。
示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

解法
Sliding Window法。
维护window这个数组，使得在任意时刻，window【0】都是当前Window内最大值的下标。
并且window从左到右恰恰是第一大、第二大、。。。。。第K大的元素（也就是C++中的双端队列，在队列中存储元素在数组中的位置， 并且维持队列的严格递减）
维护过程为：

1. 如果window不为空，并且 window[0] 比 i - k 小 （这就说明window[0]在当前Window的左界的左侧，应该被踢出去）， 把window【0】弄出去
2. 把从队尾倒着数的每个比item 大的元素都弄出去
3. 把item 弄进Window
4. 如果index > = k - 1， 就说明Window size 已经有k了，可以输出答案了。因为如果 index < k - 1， 说明Window size还没到k。

class Solution(object):def maxSlidingWindow(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""if not nums:return []res, window = [], []for index, item in enumerate(nums):if window and window[0] <= index - k:window.pop(0)while window and nums[window[-1]] <= item:window.pop()window.append(index)if index >= k-1:res.append(nums[window[0]])return res

基本计算器 II

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:

输入: “3+2*2”
输出: 7
示例 2:

输入: " 3/2 "
输出: 1
示例 3:

输入: " 3+5 / 2 "
输出: 5
说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

解法
计算器的实现一般是使用压栈的方式，但此处有几个注意事项：

1. 因为包含加减乘除，一般是对乘法和除法特殊处理（括号也是这样先处理）压入栈，然后再全体加起来。
2. 一般都是使用整数栈，不要再把符号压入栈了，所以对于减法只需把数字加个负号。
3. 注意题目中并没有说是十以内加减法，所以有可能出现多位数，也就是要处理数字，用num作为当前的数字，直到遇见符号的时候这个数字就结束了。
4. 由于需要用下一个符号来判断前一个数字是否结束，所以用sign来代表前一个符号。
5. 两个整数直接相除得到的结果是自动向上取整的，比如3/2=2，所以可以先转换成浮点数再取整。

class Solution(object):def calculate(self, s):""":type s: str:rtype: int"""s = s.replace(' ', '')res = []num = 0sign = '+'for idx, x in enumerate(s):if x.isdigit():num = num * 10 + int(x)if x.isdigit() == False or idx == len(s) - 1:if sign == '+':res.append(num)elif sign == '-':res.append(-num)elif sign == '*':res.append(res.pop() * num)elif sign == '/':res.append(int(float(res.pop())/float(num)))num = 0sign = xout = 0for idx, x in enumerate(res):out += xreturn out

逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：

输入: [“2”, “1”, “+”, “3”, “*”]
输出: 9
解释: ((2 + 1) * 3) = 9
示例 2：

输入: [“4”, “13”, “5”, “/”, “+”]
输出: 6
解释: (4 + (13 / 5)) = 6

示例 3：

输入: [“10”, “6”, “9”, “3”, “+”, “-11”, “", “/”, "”, “17”, “+”, “5”, “+”]
输出: 22
解释:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

解法
和计算器的方法相同，都是压栈，这个更简单，因为是后缀表达式的形式，而且不需要判断当前数字是否已经结束，因为用列表给出了。
但是要注意不能用.isdigit去判断是否是数字，因为这只能判断0-9的数字，当遇到”-11“这种就错了。

class Solution(object):def evalRPN(self, tokens):""":type tokens: List[str]:rtype: int"""res = []for idx, x in enumerate(tokens):if x != '+' and x != '-' and x != "*" and x != "/":res.append(int(x))else:b=res.pop()a=res.pop()tmp = 0if x == '+':tmp=a+belif x == '-':tmp = a - belif x == '*':tmp = a * belif x == '/':tmp = int(float(a) / float(b))res.append(tmp)return res[-1]

打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

示例 1:

输入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
输出：6
解释：
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的，
因为当拨动到 “0102” 时这个锁就会被锁定。
示例 2:

输入: deadends = [“8888”], target = “0009”
输出：1
解释：
把最后一位反向旋转一次即可 “0000” -> “0009”。
示例 3:

输入: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888”
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:

输入: deadends = [“0000”], target = “8888”
输出：-1

提示：

死亡列表 deadends 的长度范围为 [1, 500]。
目标数字 target 不会在 deadends 之中。
每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 ‘0000’ 到 ‘9999’ 中产生。

解法
首先是求“最小”次数，所以用BFS。本来用了vis另一个set保存遍历过的元素，但是发现其实可以和deadends合并，省时间和空间。
注意每次加入“树的子节点”的时候，都是加入8个（4位数，8种改变的可能）

class Solution(object):def openLock(self, deadends, target):""":type deadends: List[str]:type target: str:rtype: int"""ori = "0000"if ori in deadends:return -1q = [(ori, 0)]deadends = set(deadends)while q:top, step = q.pop(0)if top == target:return stepfor i in range(4):x = [(int(top[i]) + 1) % 10, (int(top[i]) - 1) % 10]for j in range(2):k = str(x[j])cur = top[:i] + k + top[i+1:]if cur not in deadends:deadends.add(cur)q.append((cur, step+1))return -1

有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true
示例 2:

输入: “()[]{}”
输出: true
示例 3:

输入: “(]”
输出: false
示例 4:

输入: “([)]”
输出: false
示例 5:

输入: “{[]}”
输出: true

解法
首先读懂题目，判断括号是否有效；然后找到有效的条件：

• 左右括号匹配：存在右括号，就找左括号是否存在
• 顺序不能错：存在右括号时，pop出来的第一个括号就应该是对应的左括号。
• 空字符串

class Solution(object):def isValid(self, s):""":type s: str:rtype: bool"""if not s:return Truestack = []for x in s:#print(x)if x == "(" or x == "{" or x == "[":stack.append(x)if x == ')':if not stack or stack.pop() != '(':return Falseif x == '}':if not stack or stack.pop() != '{':return Falseif x == ']':if not stack or stack.pop() != '[':return Falseif not stack:return Truereturn False

每日温度

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

解法
题意：遍历列表，得到最近的比当前值大的索引差值。分析可能的情况：

• i+1位置就比i位置值大（比如[73, 74]），res[i]=1
• i+1位置小于i位置，但是i+n位置大于i位置（比如[71, 69, 72]），res[i]=n
• 后面没有比i位置更大的数，res[i]=0

那么就可以想到用栈保存前面的数的位置，遍历当前数x的时候，就pop出最近的数比较一下是否比x小，如果是的话，取出来给res赋值（索引差）；如果不是的话，stack前面不可能有比x更小的

class Solution(object):def dailyTemperatures(self, T):""":type T: List[int]:rtype: List[int]"""res = [0] * len(T)stack = [0]for i in range(1, len(T)):while len(stack) > 0 and T[stack[-1]] < T[i]:idx = stack.pop()res[idx] = i - idxstack.append(i)return res

克隆图

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
public int val;
public List neighbors;
}

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1，第二个节点值为 2，以此类推。该图在测试用例中使用邻接列表表示。

邻接列表是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例 1：
输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

示例 2：
输入：adjList = [[]]
输出：[[]]
解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。

示例 3：
输入：adjList = []
输出：[]
解释：这个图是空的，它不含任何节点。

示例 4：
输入：adjList = [[2],[1]]
输出：[[2],[1]]

提示：

节点数介于 1 到 100 之间。
每个节点值都是唯一的。
无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
图是连通图，你可以从给定节点访问到所有节点。

解法
题意：使用图的起始节点重新构建一个相同的图。情况分析：

• 图是空的（没有节点）
• 图上只有一个节点（注意要返回节点，而不是返回空）
• 如果用队列来做的话：也就是BFS遍历，当遍历到当前节点ori，需要找到对应的新建的图上的该节点cur才能给cur赋值邻居，因此需要一个字典存储，该字典还可以用于判断ori的邻居是否在新图上已经存在；为了避免重复遍历节点（因为邻居可能重复），需要一个visit存储；为了避免重复把同一个未遍历过的邻居节点加入队列，需要判断队列中是否已经存在。

"""
# Definition for a Node.
class Node(object):def __init__(self, val = 0, neighbors = []):self.val = valself.neighbors = neighbors
"""
class Solution(object):def cloneGraph(self, node):""":type node: Node:rtype: Node"""if not node:return Noneif not node.neighbors:return Node(val=node.val)root = Node(val=node.val)dic = {1: root}q = [node]vis = set()while q:ori = q.pop(0)cur = dic[ori.val]#print(ori.val, cur.val)for x in ori.neighbors:#print(x.val, dic.keys(), vis)if x.val not in dic:tmp = Node(x.val)dic[x.val] = tmpcur.neighbors.append(dic[x.val])if x.val not in vis and x not in q:q.append(x)vis.add(ori.val)return root

目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。
注意:

数组非空，且长度不会超过20。
初始的数组的和不会超过1000。
保证返回的最终结果能被32位整数存下。

解法
题意：返回加减数组中每个数字和为目标数 S 的所有可能性。（如果用动态规划的思路的话：在背包问题中，我们要考虑物品放还是不放）
很快想到用DFS，定义函数f(i,target)表示i长度内目标为target的方法数，那么f(i,target)=f(i−1,target−nums[i])+f(i−1,target+nums[i])。直接这样做容易超时，所以可以想到用一个字典保存下来已经遍历过的方法数目。

class Solution(object):def findTargetSumWays(self, nums, S):""":type nums: List[int]:type S: int:rtype: int"""vis = {(0, 0): 1}res = self.dfs(nums, S, vis)return resdef dfs(self, nums, S, vis):if (len(nums), S) in vis:return vis[(len(nums), S)]elif len(nums) == 0:return 0vis[(len(nums), S)] = self.dfs(nums[1:], S - nums[0], vis) + self.dfs(nums[1:], S + nums[0], vis)return vis[(len(nums), S)]

二叉树的中序遍历

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]1\2/3输出: [1,3,2]

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解法
使用迭代方法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if root == None:return []res = []cur = rootstack = []while stack or cur:if cur:stack.append(cur)cur = cur.leftelse:cur = stack.pop()res.append(cur.val)cur = cur.rightreturn res

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:

s = “3[a]2[bc]”, 返回 “aaabcbc”.
s = “3[a2[c]]”, 返回 “accaccacc”.
s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.

解法
题意：类似于计算器，返回k*字符串内部子串的结果
思路：遇到不同类型的字符进行不同方式处理，几种情况：

• 数字：注意可能出现多位数
• 字母：拼成tmp子串，用于后续的重复
• 字符“]"：将重复后的tmp子串再放入栈
• 字符"["：重置数字、子串等

自己写的，比较麻烦：

class Solution(object):def decodeString(self, s):""":type s: str:rtype: str"""if not s:return ""stack = []for i, x in enumerate(s):if x != "]":stack.append(x)else:tmp = []while stack[-1] != "[":tmp.append(stack.pop())tmp = tmp[::-1]stack.pop()k = ""while len(stack) > 0 and stack[-1].isdigit():k = stack.pop() + kk = int(k)while k > 0:stack.extend(tmp)k -= 1return "".join(stack)

网上看的比较清晰简洁的方法：

class Solution(object):def decodeString(self, s):""":type s: str:rtype: str"""stack = []curNum = 0curString = ''for c in s:if c == '[':stack.append(curString)stack.append(curNum)curString = ''curNum = 0elif c == ']':num = stack.pop()prevString = stack.pop()curString = prevString + num * curStringelif c.isdigit():curNum = curNum * 10 + int(c)else:curString += creturn curString

图像渲染

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例 1:

输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析:
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

注意:
image 和 image[0] 的长度在范围 [1, 50] 内。
给出的初始点将满足 0 <= sr < image.length 和 0 <= sc <image[0].length。
image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

解法
很显然就是”迷宫“类问题，用dfs即可。也可以用队列解决

dfs方法：

class Solution(object):def floodFill(self, image, sr, sc, newColor):""":type image: List[List[int]]:type sr: int:type sc: int:type newColor: int:rtype: List[List[int]]"""if not image:return imagecurC = image[sr][sc]self.vis = [[False for i in range(len(image[0]))] for j in range(len(image))]image = self.dfs(image, sr, sc, curC, newColor)return imagedef dfs(self, image, r, c, curC, newC):image[r][c] = newCself.vis[r][c] = Trueif r > 0 and image[r - 1][c] == curC and not self.vis[r - 1][c]:image = self.dfs(image, r - 1, c, curC, newC)if r < len(image) - 1 and image[r + 1][c] == curC and not self.vis[r + 1][c]:image = self.dfs(image, r + 1, c, curC, newC)if c > 0 and image[r][c - 1] == curC and not self.vis[r][c - 1]:image = self.dfs(image, r, c - 1, curC, newC)if c < len(image[0]) - 1 and image[r][c + 1] == curC and not self.vis[r][c + 1]:image = self.dfs(image, r, c + 1, curC, newC)return image

队列：

class Solution(object):def floodFill(self, image, sr, sc, newColor):""":type image: List[List[int]]:type sr: int:type sc: int:type newColor: int:rtype: List[List[int]]"""m, n = len(image), len(image[0])color = image[sr][sc]image[sr][sc] = newColorvisited = [[0 for _ in range(n + 1)] for _ in range(m + 1)]dx = [1, -1, 0, 0]dy = [0, 0, 1, -1]q = deque()q.append([sr,sc])while q:x0, y0 = q.popleft()for k in range(4):x = x0 + dx[k]y = y0 + dy[k]if 0 <= x < m and 0 <= y < n and image[x][y] == color and visited[x][y] == 0:image[x][y] = newColorvisited[x][y] = 1q.append([x, y])return image

01 矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:
输入:

0 0 0
0 1 0
0 0 0
输出:

0 0 0
0 1 0
0 0 0
示例 2:
输入:

0 0 0
0 1 0
1 1 1
输出:

0 0 0
0 1 0
1 2 1

注意:
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解法
题意：找离每个1最近的0的距离
步骤：因为是最近距离，显然是BFS。开始想的方法是遍历矩阵，找到每个1之后再用BFS，显然复杂度非常高。后来看到网上的做法，其实这就相当于求每个0最近的1的距离，遍历一遍矩阵就可以了。

class Solution(object):def updateMatrix(self, matrix):""":type matrix: List[List[int]]:rtype: List[List[int]]"""if not matrix:return matrixres = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]vis = [[False for ii in range(len(matrix[0]))] for jj in range(len(matrix))]queue = []for i in range(len(matrix)):for j in range(len(matrix[0])):if matrix[i][j] == 0:queue.append((i, j, 0))vis[i][j] = Truedx = [1, -1, 0, 0]dy = [0, 0, 1, -1]while queue:x0, y0, step = queue.pop(0)if matrix[x0][y0] == 1:res[x0][y0] = stepstep += 1for k in range(4):x = x0 + dx[k]y = y0 + dy[k]if x >= 0 and x <= len(matrix) - 1 and y >= 0 and y <= len(matrix[0]) - 1 and vis[x][y] == False:queue.append((x, y, step))vis[x][y] = Truereturn res                

钥匙和房间

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，…，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，…，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。
示例 2：

输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

提示：
1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过 3000。

解法
题意：判断是否每个房间都被visited过
方法：用队列或者栈应该都可以。

class Solution(object):def canVisitAllRooms(self, rooms):""":type rooms: List[List[int]]:rtype: bool"""if not rooms:return roomsqueue = []vis = [False for i in range(len(rooms))]vis[0] = Truefor x in rooms[0]:queue.append(x)vis[x] = Truewhile queue:top = queue.pop(0)for x in rooms[top]:if vis[x] == False:queue.append(x)vis[x] = Truefor i in range(len(vis)):if vis[i] == False:return Falsereturn True