设计你的回圈队列实作， 回圈队列是一种线性资料结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个回圈，它也被称为“环形缓冲器”，

回圈队列的一个好处是我们可以利用这个队列之前用过的空间，在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间，但是使用回圈队列，我们能使用这些空间去存盘新的值，

你的实作应该支持如下操作：

MyCircularQueue(k): 构造器，设定队列长度为 k ，
Front: 从队首获取元素，如果队列为空，回传 -1 ，
Rear: 获取队尾元素，如果队列为空，回传 -1 ，
enQueue(value): 向回圈队列插入一个元素，如果成功插入则回传真，
deQueue(): 从回圈队列中洗掉一个元素，如果成功洗掉则回传真，
isEmpty(): 检查回圈队列是否为空，
isFull(): 检查回圈队列是否已满，
 

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设定长度为 3
circularQueue.enQueue(1);  // 回传 true
circularQueue.enQueue(2);  // 回传 true
circularQueue.enQueue(3);  // 回传 true
circularQueue.enQueue(4);  // 回传 false，队列已满
circularQueue.Rear();  // 回传 3
circularQueue.isFull();  // 回传 true
circularQueue.deQueue();  // 回传 true
circularQueue.enQueue(4);  // 回传 true
circularQueue.Rear();  // 回传 4
 

提示：

所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库，

给定一个整数资料流和一个视窗大小，根据该滑动视窗的大小，计算其所有整数的移动平均值，

实作 MovingAverage 类：

MovingAverage(int size) 用视窗大小 size 初始化物件，
double next(int val) 计算并回传资料流中最后 size 个值的移动平均值，
 

示例：

输入：
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]

解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 回传 1.0 = 1 / 1
movingAverage.next(10); // 回传 5.5 = (1 + 10) / 2
movingAverage.next(3); // 回传 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 回传 6.0 = (10 + 3 + 5) / 3
 

提示：

1 <= size <= 1000
-105 <= val <= 105
最多呼叫 next 方法 104 次

你被给定一个 m × n 的二维网格 rooms ，网格中有以下三种可能的初始化值：

-1 表示墻或是障碍物
0 表示一扇门
INF 无限表示一个空的房间，然后，我们用 231 - 1 = 2147483647 代表 INF，你可以认为通往门的距离总是小于 2147483647 的，
你要给每个空房间位上填上该房间到 最近门的距离 ，如果无法到达门，则填 INF 即可，

示例 1：

输入：rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
输出：[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
示例 2：

输入：rooms = [[-1]]
输出：[[-1]]
示例 3：

输入：rooms = [[2147483647]]
输出：[[2147483647]]
示例 4：

输入：rooms = [[0]]
输出：[[0]]
 

提示：

m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] 是 -1、0 或 231 - 1

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量，

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成，

此外，你可以假设该网格的四条边均被水包围，

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '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
 

提示：

1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target 不在 deadends 之中
target 和 deadends[i] 仅由若干位数字组成

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n，你需要让组成和的完全平方数的个数最少，

给你一个整数 n ，回传和为 n 的完全平方数的 最少数量 ，

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积，例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是，

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9
 
提示：

1 <= n <= 104

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

push(x) —— 将元素 x 推入堆栈中，
pop() —— 洗掉堆栈顶的元素，
top() —— 获取堆栈顶元素，
getMin() —— 检索堆栈中的最小元素，
 

示例:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 回传 -3.
minStack.pop();
minStack.top();      --> 回传 0.
minStack.getMin();   --> 回传 -2.
 

提示：

pop、top 和 getMin 操作总是在 非空堆栈 上呼叫，

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

有效字符串需满足：

左括号必须用相同型别的右括号闭合，
左括号必须以正确的顺序闭合，
 

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true

请根据每日 气温 串列 temperatures ，请计算在每一天需要等几天才会有更高的温度，如果气温在这之后都不会升高，请在该位置用 0 来代替，

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

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

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

说明：

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

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入：tokens = ["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
 

提示：

1 <= tokens.length <= 104
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数
 

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面，

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) ，
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) ，
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果，
适合用堆栈操作运算：遇到数字则入堆栈；遇到算符则取出堆栈顶两个数字进行计算，并将结果压入堆栈中，

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量，

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成，

此外，你可以假设该网格的四条边均被水包围，

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

给你无向 连通 图中一个节点的参考，请你回传该图的 深拷贝（克隆），

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

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

测验用例格式：

简单起见，每个节点的值都和它的索引相同，例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 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]]
 

提示：

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

给你一个整数阵列 nums 和一个整数 target ，

向阵列中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" ，
回传可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目，

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3
示例 2：

输入：nums = [1], target = 1
输出：1
 

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

给定一个二叉树的根节点 root ，回传它的 中序 遍历，

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[2,1]
示例 5：

输入：root = [1,null,2]
输出：[1,2]

请你仅使用两个堆栈实作先入先出队列，队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实作 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并回传元素
int peek() 回传队列开头的元素
boolean empty() 如果队列为空，回传 true ；否则，回传 false
 

说明：

你只能使用标准的堆栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的，
你所使用的语言也许不支持堆栈，你可以使用 list 或者 deque（双端队列）来模拟一个堆栈，只要是标准的堆栈操作即可，
 

进阶：

你能否实作每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间，
 

示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
 

提示：

1 <= x <= 9
最多呼叫 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会呼叫 pop 或者 peek 操作）

请你仅使用两个队列实作一个后入先出（LIFO）的堆栈，并支持普通堆栈的全部四种操作（push、top、pop 和 empty），

实作 MyStack 类：

void push(int x) 将元素 x 压入堆栈顶，
int pop() 移除并回传堆栈顶元素，
int top() 回传堆栈顶元素，
boolean empty() 如果堆栈是空的，回传 true ；否则，回传 false ，
 

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作，
你所使用的语言也许不支持队列， 你可以使用 list （串列）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可，
 

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 回传 2
myStack.pop(); // 回传 2
myStack.empty(); // 回传 False
 

提示：

1 <= x <= 9
最多呼叫100 次 push、pop、top 和 empty
每次呼叫 pop 和 top 都保证堆栈不为空
 

进阶：你能否实作每种操作的均摊时间复杂度为 O(1) 的堆栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间，你可以使用两个以上的队列，

给定一个经过编码的字符串，回传它译码后的字符串，

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

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

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

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

有一幅以二维整数阵串列示的图画，每一个整数表示该图画的像素值大小，数值在 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]内，

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离，

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

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]
 

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一个 0 

有 n 个房间，房间按从 0 到 n - 1 编号，最初，除 0 号房间外的其余所有房间都被锁住，你的目标是进入所有的房间，然而，你不能在没有获得钥匙的时候进入锁住的房间，

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间，你可以拿上所有钥匙去解锁其他房间，

给你一个阵列 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合，如果能进入 所有 房间回传 true，否则回传 false，

示例 1：

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

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

提示：

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
所有 rooms[i] 的值 互不相同