20踪古、有效的括號(hào)
給定一個(gè)只包括 '('，')'券腔，'{'伏穆，'}'，'['纷纫，']' 的字符串枕扫，判斷字符串是否有效。
有效字符串需滿足：
左括號(hào)必須用相同類型的右括號(hào)閉合辱魁。
左括號(hào)必須以正確的順序閉合烟瞧。
注意空字符串可被認(rèn)為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
class Solution:
def isValid(self, s: str) -> bool:
#定義需要匹配的格式
dic={'(':')','{':'}','[':']'}
stack=['?']
for c in s:
if c in dic:
stack.append(c) #左邊壓棧
elif dic[stack.pop()] != c: #右邊出
return False
return len(stack) == 1
42染簇、接雨水
給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖参滴，計(jì)算按此排列的柱子，下雨之后能接多少雨水锻弓。
上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖砾赔，在這種情況下，可以接 6 個(gè)單位的雨水（藍(lán)色部分表示雨水）青灼。 感謝 Marcos 貢獻(xiàn)此圖暴心。
輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6
# i位置容水量=min(max(i位置左邊位置),max(i右邊位置)）- i位置的高度
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
n=len(height)
stack=[]
res=0
for i in range(n):
while stack and height[stack[-1]]<height[i]:
tmp=stack.pop()
if not stack:
break
res+=(min(height[i],height[stack[-1]])-height[tmp])*(i-stack[-1]-1)
stack.append(i)
return res
71、簡(jiǎn)化路徑
以 Unix 風(fēng)格給出一個(gè)文件的絕對(duì)路徑杂拨，你需要簡(jiǎn)化它专普。或者換句話說(shuō)弹沽，將其轉(zhuǎn)換為規(guī)范路徑檀夹。
在 Unix 風(fēng)格的文件系統(tǒng)中，一個(gè)點(diǎn)（.）表示當(dāng)前目錄本身贷币；此外，兩個(gè)點(diǎn) （..） 表示將目錄切換到上一級(jí)（指向父目錄）亏狰；兩者都可以是復(fù)雜相對(duì)路徑的組成部分役纹。更多信息請(qǐng)參閱：Linux / Unix中的絕對(duì)路徑 vs 相對(duì)路徑
請(qǐng)注意，返回的規(guī)范路徑必須始終以斜杠 / 開(kāi)頭暇唾，并且兩個(gè)目錄名之間必須只有一個(gè)斜杠 /促脉。最后一個(gè)目錄名（如果存在）不能以 / 結(jié)尾辰斋。此外，規(guī)范路徑必須是表示絕對(duì)路徑的最短字符串瘸味。
示例 1：
輸入："/home/"
輸出："/home"
解釋：注意宫仗，最后一個(gè)目錄名后面沒(méi)有斜杠。
示例 2：
輸入："/../"
輸出："/"
解釋：從根目錄向上一級(jí)是不可行的旁仿，因?yàn)楦悄憧梢缘竭_(dá)的最高級(jí)藕夫。
示例 3：
輸入："/home//foo/"
輸出："/home/foo"
解釋：在規(guī)范路徑中，多個(gè)連續(xù)斜杠需要用一個(gè)斜杠替換枯冈。
示例 4：
輸入："/a/./b/../../c/"
輸出："/c"
示例 5：
輸入："/a/../../b/../c//.//"
輸出："/c"
示例 6：
輸入："/a//b////c/d//././/.."
輸出："/a/b/c"
# 把當(dāng)前目錄壓入棧中,遇到..彈出棧頂,最后返回棧中元素.
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
path = path.split("/")
for item in path:
if item == "..":
if stack : stack.pop()
elif item and item != ".":
stack.append(item)
return "/" + "/".join(stack)
84毅贮、 柱狀圖中最大的矩形
給定 n 個(gè)非負(fù)整數(shù)，用來(lái)表示柱狀圖中各個(gè)柱子的高度尘奏。每個(gè)柱子彼此相鄰滩褥，且寬度為 1 。
求在該柱狀圖中炫加，能夠勾勒出來(lái)的矩形的最大面積瑰煎。
以上是柱狀圖的示例，其中每個(gè)柱子的寬度為 1俗孝，給定的高度為 [2,1,5,6,2,3]酒甸。
圖中陰影部分為所能勾勒出的最大矩形面積，其面積為 10 個(gè)單位驹针。
示例:
輸入: [2,1,5,6,2,3]
輸出: 10
# 最大面積
# i柱子可構(gòu)造的最大面積=（右邊第一個(gè)小于i高度的位置-左邊第一個(gè)小于i高度的位置-1）*i的高度
# 構(gòu)造單調(diào)遞增的棧
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack=[]
heights=[0]+heights+[0]
res=0
for i in range(len(heights)):
while stack and heights[stack[-1]]>heights[i]:
tmp=stack.pop()
res=max(res,(i-stack[-1]-1)*heights[tmp])
stack.append(i)
return res
85烘挫、最大矩形
給定一個(gè)僅包含 0 和 1 的二維二進(jìn)制矩陣，找出只包含 1 的最大矩形柬甥，并返回其面積饮六。
示例:
輸入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
輸出: 6
#遍歷每行的高度，與84題解法類似
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]: return 0
row = len(matrix)
col = len(matrix[0])
height = [0] * (col + 2)
res = 0
for i in range(row):
stack = []
for j in range(col + 2):
if 1<=j<=col:
if matrix[i][j-1] == "1":
height[j] += 1
else:
height[j] = 0
while stack and height[stack[-1]] > height[j]:
cur = stack.pop()
res = max(res, (j - stack[-1] - 1)* height[cur])
stack.append(j)
return res
94苛蒲、二叉樹(shù)中序遍歷
給定一個(gè)二叉樹(shù)卤橄，返回它的中序 遍歷。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
#二叉樹(shù)中序遍歷 左根右
res=[]
def helper(root):
if not root:
return
helper(root.left)
res.append(root.val)
helper(root.right)
helper(root)
return res
103臂外、 二叉樹(shù)的鋸齒形層次遍歷
給定一個(gè)二叉樹(shù)窟扑，返回其節(jié)點(diǎn)值的鋸齒形層次遍歷。（即先從左往右漏健，再?gòu)挠彝筮M(jìn)行下一層遍歷嚎货，以此類推，層與層之間交替進(jìn)行）蔫浆。
例如：
給定二叉樹(shù) [3,9,20,null,null,15,7],
返回鋸齒形層次遍歷如下：
[
[3],
[20,9],
[15,7]
]
144殖属、二叉樹(shù)的前序遍歷
給定一個(gè)二叉樹(shù)，返回它的 前序 遍歷瓦盛。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
# 前序遍歷 根左右
res = []
p = root
stack = []
while p or stack:
while p:
res.append(p.val)
stack.append(p)
p = p.left
p = stack.pop().right
return res
145洗显、二叉樹(shù)后續(xù)遍歷
給定一個(gè)二叉樹(shù)外潜，返回它的 后序 遍歷。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
# 后續(xù)遍歷 左右根
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
stack, output = [root, ], []
while stack:
root = stack.pop()
output.append(root.val)
if root.left is not None:
stack.append(root.left)
if root.right is not None:
stack.append(root.right)
return output[::-1]
150挠唆、逆波蘭表達(dá)式求值
根據(jù)逆波蘭表示法处窥，求表達(dá)式的值。
有效的運(yùn)算符包括 +, -, *, / 玄组。每個(gè)運(yùn)算對(duì)象可以是整數(shù)滔驾，也可以是另一個(gè)逆波蘭表達(dá)式。
說(shuō)明：
整數(shù)除法只保留整數(shù)部分巧勤。
給定逆波蘭表達(dá)式總是有效的嵌灰。換句話說(shuō)，表達(dá)式總會(huì)得出有效數(shù)值且不存在除數(shù)為 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
# 遍歷序列沽瞭，數(shù)字入棧，到運(yùn)算符的時(shí)候剩瓶，出棧最后兩個(gè)數(shù)字進(jìn)行計(jì)算驹溃，結(jié)果入棧
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for t in tokens:
if t in {"+", "-", "/", "*"}:
tmp1 = stack.pop()
tmp2 = stack.pop()
stack.append(str(int(eval(tmp2+t+tmp1))))
else:
stack.append(t)
return stack.pop()
155、最小棧
設(shè)計(jì)一個(gè)支持 push延曙，pop豌鹤，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧枝缔。
push(x) -- 將元素 x 推入棧中布疙。
pop() -- 刪除棧頂?shù)脑亍?br>
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.
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.data=[]#數(shù)據(jù)棧
self.helper=[]#輔助棧
def push(self, x: int) -> None:
self.data.append(x)
if len(self.helper)==0 or x<self.helper[-1]:
self.helper.append(x)
else:
self.helper.append(self.helper[-1])
def pop(self) -> None:
if self.data:
self.helper.pop()
return self.data.pop()
def top(self) -> int:
if self.data:
return self.data[-1]
def getMin(self) -> int:
if self.helper:
return self.helper[-1]
# 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()
173灵临、二叉搜索樹(shù)迭代qi
實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)迭代器。你將使用二叉搜索樹(shù)的根節(jié)點(diǎn)初始化迭代器趴荸。
調(diào)用 next() 將返回二叉搜索樹(shù)中的下一個(gè)最小的數(shù)儒溉。
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
"""
棧
"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
def __init__(self, root: TreeNode):
self.stack=[]
self.push_stack(root)
def next(self) -> int:
"""
@return the next smallest number
"""
tmp=self.stack.pop()
if tmp.right:
self.push_stack(tmp.right)
return tmp.val
def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return bool(self.stack)
def push_stack(self,node):
while node:
self.stack.append(node)
node=node.left
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
224、基本計(jì)算器
實(shí)現(xiàn)一個(gè)基本的計(jì)算器來(lái)計(jì)算一個(gè)簡(jiǎn)單的字符串表達(dá)式的值发钝。
字符串表達(dá)式可以包含左括號(hào) ( 顿涣，右括號(hào) )，加號(hào) + 酝豪，減號(hào) -涛碑，非負(fù)整數(shù)和空格 。
示例 1:
輸入: "1 + 1"
輸出: 2
示例 2:
輸入: " 2-1 + 2 "
輸出: 3
示例 3:
輸入: "(1+(4+5+2)-3)+(6+8)"
輸出: 23
class Solution:
def calculate(self, s: str) -> int:
res = 0
stack = []
sign = 1
i = 0
n = len(s)
while i < n:
if s[i] == " ":
i += 1
elif s[i] == "-":
sign = -1
i += 1
elif s[i] == "+":
sign = 1
i += 1
elif s[i] == "(":
stack.append(res)
stack.append(sign)
res = 0
sign = 1
i += 1
elif s[i] == ")":
# print(stack)
res = res * stack.pop() + stack.pop()
i += 1
elif s[i].isdigit():
tmp = int(s[i])
i += 1
while i < n and s[i].isdigit():
tmp = tmp * 10 + int(s[i])
i += 1
res += tmp * sign
return res
225孵淘、用隊(duì)列實(shí)現(xiàn)棧
使用隊(duì)列實(shí)現(xiàn)棧的下列操作：
push(x) -- 元素 x 入棧
pop() -- 移除棧頂元素
top() -- 獲取棧頂元素
empty() -- 返回棧是否為空
注意:
你只能使用隊(duì)列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的蒲障。
你所使用的語(yǔ)言也許不支持隊(duì)列。 你可以使用 list 或者 deque（雙端隊(duì)列）來(lái)模擬一個(gè)隊(duì)列 , 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可。
你可以假設(shè)所有操作都是有效的（例如, 對(duì)一個(gè)空的棧不會(huì)調(diào)用 pop 或者 top 操作）晌涕。
# 隊(duì)列先進(jìn)先出
# 棧后進(jìn)先出
# 隊(duì)列實(shí)現(xiàn)棧-- 兩個(gè)隊(duì)列
from queue import Queue
class MyStack:
def __init__(self):
self._queue = Queue()
self._temp = Queue()
def push(self, x: int) -> None:
self._temp.put(x)
while self._queue.qsize() > 0:
self._temp.put(self._queue.get())
while self._temp.qsize() > 0:
self._queue.put(self._temp.get())
def pop(self) -> int:
if self._queue.qsize() > 0:
return self._queue.get()
else:
return None
def top(self) -> int:
if self._queue.qsize() > 0:
x = self._queue.get()
self.push(x)
return x
else:
return None
def empty(self) -> bool:
return self._queue.empty()
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
232、用棧實(shí)現(xiàn)隊(duì)列
使用棧實(shí)現(xiàn)隊(duì)列的下列操作：
push(x) -- 將一個(gè)元素放入隊(duì)列的尾部痛悯。
pop() -- 從隊(duì)列首部移除元素余黎。
peek() -- 返回隊(duì)列首部的元素。
empty() -- 返回隊(duì)列是否為空载萌。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
說(shuō)明:
你只能使用標(biāo)準(zhǔn)的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的惧财。
你所使用的語(yǔ)言也許不支持棧。你可以使用 list 或者 deque（雙端隊(duì)列）來(lái)模擬一個(gè)棧扭仁，只要是標(biāo)準(zhǔn)的棧操作即可垮衷。
假設(shè)所有操作都是有效的 （例如，一個(gè)空的隊(duì)列不會(huì)調(diào)用 pop 或者 peek 操作）乖坠。
#隊(duì)列是一種 先進(jìn)先出（first in - first out搀突， FIFO）的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列中的元素都從后端（rear）入隊(duì)（push）熊泵，從前端（front）出隊(duì)（pop）仰迁。
#棧是一種 后進(jìn)先出（last in - first out， LIFO）的數(shù)據(jù)結(jié)構(gòu)顽分，棧中元素從棧頂（top）壓入（push)徐许，也從棧頂彈出（pop）。
#兩個(gè)棧卒蘸，一個(gè)來(lái)反轉(zhuǎn)元素的入隊(duì)順序雌隅，用另一個(gè)來(lái)存儲(chǔ)元素的最終順序。
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.A = []
self.B = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.A.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if self.empty():
return
if len(self.B) == 0:
while len(self.A) != 0:
self.B.append(self.A.pop())
return self.B.pop()
else:
return self.B.pop()
def peek(self) -> int:
"""
Get the front element.
"""
if self.empty():
return
if len(self.B) == 0:
while len(self.A) != 0:
self.B.append(self.A.pop())
return self.B[-1]
else:
return self.B[-1]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
if len(self.B)==0 and len(self.A)==0:
return True
else:
return False
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
316缸沃、去除重復(fù)字母
給定一個(gè)僅包含小寫字母的字符串恰起，去除字符串中重復(fù)的字母，使得每個(gè)字母只出現(xiàn)一次和泌。需保證返回結(jié)果的字典序最写甯住（要求不能打亂其他字符的相對(duì)位置）。
示例 1:
輸入: "bcabc"
輸出: "abc"
示例 2:
輸入: "cbacdcbc"
輸出: "acdb"
# 字典序是指從前到后比較兩個(gè)字符串大小的方法武氓。
# 首先比較第 1 個(gè)字符梯皿，如果不同則第 1 個(gè)字符較小的字符串更小县恕；
# 如果相同則繼續(xù)比較第 2 個(gè)字符 …… 如此繼續(xù)东羹，比較整個(gè)字符串的大小。
# ab序列小于ba序列
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
stack=['0']
for i,_ in enumerate(s): # i 是下標(biāo)忠烛，_ 是元素
if _ not in stack:
while _ < stack[-1] and stack[-1] in s[i+1:]:
stack.pop()
stack.append(_)
return ''.join(stack[1:])
331属提、驗(yàn)證二叉樹(shù)的前序序列化
序列化二叉樹(shù)的一種方法是使用前序遍歷。當(dāng)我們遇到一個(gè)非空節(jié)點(diǎn)時(shí)，我們可以記錄下這個(gè)節(jié)點(diǎn)的值冤议。如果它是一個(gè)空節(jié)點(diǎn)斟薇，我們可以使用一個(gè)標(biāo)記值記錄，例如 #恕酸。
例如堪滨，上面的二叉樹(shù)可以被序列化為字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一個(gè)空節(jié)點(diǎn)蕊温。
給定一串以逗號(hào)分隔的序列袱箱，驗(yàn)證它是否是正確的二叉樹(shù)的前序序列化。編寫一個(gè)在不重構(gòu)樹(shù)的條件下的可行算法义矛。
每個(gè)以逗號(hào)分隔的字符或?yàn)橐粋€(gè)整數(shù)或?yàn)橐粋€(gè)表示 null 指針的 '#' 发笔。
你可以認(rèn)為輸入格式總是有效的，例如它永遠(yuǎn)不會(huì)包含兩個(gè)連續(xù)的逗號(hào)凉翻，比如 "1,,3" 了讨。
示例 1:
輸入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
輸出: true
示例 2:
輸入: "1,#"
輸出: false
示例 3:
輸入: "9,#,#,1"
輸出: false
# 前序遍歷根左右
# 用棧模擬前序遍歷遞歸建樹(shù)的過(guò)程
# 如果有兩個(gè)連續(xù)的#，則為空葉子節(jié)點(diǎn)制轰，葉子節(jié)點(diǎn)的前一個(gè)為根節(jié)點(diǎn)
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
stack=[]
preorder=preorder.split(",")
for item in preorder:
while stack and stack[-1] == "#" and item == "#":
stack.pop()
if not stack:return False
stack.pop()
stack.append(item)
return len(stack) == 1 and stack[0] == "#"
341结序、扁平化嵌套列表迭代器
給你一個(gè)嵌套的整型列表暂殖。請(qǐng)你設(shè)計(jì)一個(gè)迭代器朝刊，使其能夠遍歷這個(gè)整型列表中的所有整數(shù)负懦。
列表中的每一項(xiàng)或者為一個(gè)整數(shù)，或者是另一個(gè)列表缩滨。
示例 1:
輸入: [[1,1],2,[1,1]]
輸出: [1,1,2,1,1]
解釋: 通過(guò)重復(fù)調(diào)用 next 直到 hasNext 返回 false势就，next 返回的元素的順序應(yīng)該是: [1,1,2,1,1]。
示例 2:
輸入: [1,[4,[6]]]
輸出: [1,4,6]
解釋: 通過(guò)重復(fù)調(diào)用 next 直到 hasNext 返回 false脉漏，next 返回的元素的順序應(yīng)該是: [1,4,6]苞冯。
# 用棧模擬遞歸過(guò)程
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
# def isInteger(self) -> bool:
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# """
#
# def getInteger(self) -> int:
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# """
#
# def getList(self) -> [NestedInteger]:
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# """
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
self.stack=[]
self.stack.append(nestedList)
self.top=0 #下一個(gè)元素
self.flag=False #棧頂元素是否已處理
def next(self) -> int:
self.flag=False #棧頂元素未處理狀態(tài)
return self.top
def hasNext(self) -> bool:
if len(self.stack)==0:
return False
#棧頂待處理且不為空
while len(self.stack)>0 and not self.flag:
#取出棧頂
top=self.stack.pop()
if isinstance(top,list):
# 如果是列表，取出首元素侧巨，并將兩者都?jí)喝霔? if len(top)>0:
first=top[0]
del top[0]
self.stack.append(top)
self.stack.append(first)
else:
#如果不是列表
if top.isInteger():
#如果是整數(shù)舅锄，直接取出
self.top=top.getInteger()
self.flag=True
else:
#取出list壓入棧
self.stack.append(top.getList())
return self.flag
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())
385、迷你語(yǔ)法分析器
給定一個(gè)用字符串表示的整數(shù)的嵌套列表司忱，實(shí)現(xiàn)一個(gè)解析它的語(yǔ)法分析器皇忿。
列表中的每個(gè)元素只可能是整數(shù)或整數(shù)嵌套列表
提示：你可以假定這些字符串都是格式良好的：
字符串非空
字符串不包含空格
字符串只包含數(shù)字0-9, [, - ,, ]
示例 1：
給定 s = "324",
你應(yīng)該返回一個(gè) NestedInteger 對(duì)象，其中只包含整數(shù)值 324坦仍。
示例 2：
給定 s = "[123,[456,[789]]]",
返回一個(gè) NestedInteger 對(duì)象包含一個(gè)有兩個(gè)元素的嵌套列表：
- 一個(gè) integer 包含值 123
- 一個(gè)包含兩個(gè)元素的嵌套列表：
i. 一個(gè) integer 包含值 456
ii. 一個(gè)包含一個(gè)元素的嵌套列表
a. 一個(gè) integer 包含值 789
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
# def __init__(self, value=None):
# """
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# """
#
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def add(self, elem):
# """
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# """
#
# def setInteger(self, value):
# """
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class Solution:
def deserialize(self, s: str) -> NestedInteger:
if s[0]!='[':
return NestedInteger(int(s))
stack=[]
num,sign,is_num=0,1,False
for c in s:
if c.isdigit():
num=num*10+int(c)
is_num=True
elif c=='-':
sign=-1
elif c=='[':
stack.append(NestedInteger())
elif c==',' or c==']':
#把數(shù)字添加進(jìn)去
if is_num:
cur_list=stack.pop()
cur_list.add(NestedInteger(sign*num))
stack.append(cur_list)
num,sign,is_num=0,1,False
#此時(shí)為嵌套列表
if c==']' and len(stack)>1:
cur_list=stack.pop()
stack[-1].add(cur_list)
return stack[0]
394鳍烁、字符串解碼
給定一個(gè)經(jīng)過(guò)編碼的字符串，返回它解碼后的字符串繁扎。
編碼規(guī)則為: k[encoded_string]幔荒，表示其中方括號(hào)內(nèi)部的 encoded_string 正好重復(fù) k 次糊闽。注意 k 保證為正整數(shù)。
你可以認(rèn)為輸入字符串總是有效的爹梁；輸入字符串中沒(méi)有額外的空格右犹，且輸入的方括號(hào)總是符合格式要求的。
此外姚垃，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字傀履，所有的數(shù)字只表示重復(fù)的次數(shù) k ，例如不會(huì)出現(xiàn)像 3a 或 2[4] 的輸入莉炉。
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
# 棧
class Solution:
def decodeString(self, s: str) -> str:
stack, res, multi = [], "", 0
for c in s:
if c == '[':
stack.append([multi, res])
res, multi = "", 0
elif c == ']':
cur_multi, last_res = stack.pop()
res = last_res + cur_multi * res
elif '0' <= c <= '9':
multi = multi * 10 + int(c)
else:
res += c
return res
402、移掉k位數(shù)字
給定一個(gè)以字符串表示的非負(fù)整數(shù) num碴犬，移除這個(gè)數(shù)中的 k 位數(shù)字絮宁，使得剩下的數(shù)字最小。
注意:
num 的長(zhǎng)度小于 10002 且 ≥ k服协。
num 不會(huì)包含任何前導(dǎo)零绍昂。
示例 1 :
輸入: num = "1432219", k = 3
輸出: "1219"
解釋: 移除掉三個(gè)數(shù)字 4, 3, 和 2 形成一個(gè)新的最小的數(shù)字 1219。
示例 2 :
輸入: num = "10200", k = 1
輸出: "200"
解釋: 移掉首位的 1 剩下的數(shù)字為 200. 注意輸出不能有任何前導(dǎo)零偿荷。
示例 3 :
輸入: num = "10", k = 2
輸出: "0"
解釋: 從原數(shù)字移除所有的數(shù)字窘游，剩余為空就是0。
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
if k>=len(num):
return 0
stack=[]
cnt=k
for n in num:
while stack and stack[-1]>n and k:
stack.pop()
k-=1
stack.append(n)
return str(int("".join(stack[:len(num)-cnt])))
456跳纳、132模式
給定一個(gè)整數(shù)序列：a1, a2, ..., an忍饰，一個(gè)132模式的子序列 ai, aj, ak 被定義為：當(dāng) i < j < k 時(shí)，ai < ak < aj寺庄。設(shè)計(jì)一個(gè)算法艾蓝，當(dāng)給定有 n 個(gè)數(shù)字的序列時(shí)，驗(yàn)證這個(gè)序列中是否含有132模式的子序列斗塘。
注意：n 的值小于15000赢织。
示例1:
輸入: [1, 2, 3, 4]
輸出: False
解釋: 序列中不存在132模式的子序列。
示例 2:
輸入: [3, 1, 4, 2]
輸出: True
解釋: 序列中有 1 個(gè)132模式的子序列： [1, 4, 2].
示例 3:
輸入: [-1, 3, 2, 0]
輸出: True
解釋: 序列中有 3 個(gè)132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
le = len(nums)
if le<2: return False
mi = [nums[0]]
for i in range(1, le):
mi.append(min(nums[i], mi[-1]))
stack = []
for i in range(le-1, -1, -1):
print(stack)
if nums[i]>mi[i]:
while stack and mi[i]>=stack[-1]:
stack.pop()
if stack and stack[-1]<nums[i]:
return True
stack.append(nums[i])
return False
496馍盟、下一個(gè)更大元素I
給定兩個(gè)沒(méi)有重復(fù)元素的數(shù)組 nums1 和 nums2 于置，其中nums1 是 nums2 的子集。找到 nums1 中每個(gè)元素在 nums2 中的下一個(gè)比其大的值贞岭。
nums1 中數(shù)字 x 的下一個(gè)更大元素是指 x 在 nums2 中對(duì)應(yīng)位置的右邊的第一個(gè)比 x 大的元素八毯。如果不存在，對(duì)應(yīng)位置輸出-1瞄桨。
示例 1:
輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
解釋:
對(duì)于num1中的數(shù)字4宪彩，你無(wú)法在第二個(gè)數(shù)組中找到下一個(gè)更大的數(shù)字，因此輸出 -1讲婚。
對(duì)于num1中的數(shù)字1尿孔，第二個(gè)數(shù)組中數(shù)字1右邊的下一個(gè)較大數(shù)字是 3。
對(duì)于num1中的數(shù)字2，第二個(gè)數(shù)組中沒(méi)有下一個(gè)更大的數(shù)字活合，因此輸出 -1雏婶。
示例 2:
輸入: nums1 = [2,4], nums2 = [1,2,3,4].
輸出: [3,-1]
解釋:
對(duì)于num1中的數(shù)字2，第二個(gè)數(shù)組中的下一個(gè)較大數(shù)字是3白指。
對(duì)于num1中的數(shù)字4留晚，第二個(gè)數(shù)組中沒(méi)有下一個(gè)更大的數(shù)字，因此輸出 -1告嘲。
注意:
nums1和nums2中所有元素是唯一的错维。
nums1和nums2 的數(shù)組大小都不超過(guò)1000。
# 棧 哈希
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
stack, hashmap = list(), dict()
for i in nums2:
while len(stack) != 0 and stack[-1] < i:hashmap[stack.pop()] = i
stack.append(i)
return [hashmap.get(i,-1) for i in nums1]
503橄唬、下一個(gè)更大元素II
給定一個(gè)循環(huán)數(shù)組（最后一個(gè)元素的下一個(gè)元素是數(shù)組的第一個(gè)元素）赋焕，輸出每個(gè)元素的下一個(gè)更大元素。數(shù)字 x 的下一個(gè)更大的元素是按數(shù)組遍歷順序仰楚，這個(gè)數(shù)字之后的第一個(gè)比它更大的數(shù)隆判，這意味著你應(yīng)該循環(huán)地搜索它的下一個(gè)更大的數(shù)。如果不存在僧界，則輸出 -1侨嘀。
示例 1:
輸入: [1,2,1]
輸出: [2,-1,2]
解釋: 第一個(gè) 1 的下一個(gè)更大的數(shù)是 2；
數(shù)字 2 找不到下一個(gè)更大的數(shù)捂襟；
第二個(gè) 1 的下一個(gè)最大的數(shù)需要循環(huán)搜索咬腕，結(jié)果也是 2。
注意: 輸入數(shù)組的長(zhǎng)度不會(huì)超過(guò) 10000葬荷。
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
# 循環(huán)數(shù)組郎汪，使用i%n表示數(shù)組索引，不用復(fù)制兩個(gè)一樣的數(shù)組
# 還是單調(diào)棧的思路闯狱，其實(shí)也是雙端隊(duì)列維護(hù)qmax的思想煞赢，具體可以參考LeetCode生成窗口最大值數(shù)組
n = len(nums)
res = [0 for i in range(n)]
stack = []
# 倒著遍歷
for i in range(n*2-1,-1,-1):
while stack and stack[-1] <= nums[i%n]:
stack.pop()
if i < n:
res[i] = stack[-1] if stack else -1
stack.append(nums[i%n])
return res
591、標(biāo)簽驗(yàn)證器
給定一個(gè)表示代碼片段的字符串哄孤，你需要實(shí)現(xiàn)一個(gè)驗(yàn)證器來(lái)解析這段代碼照筑，并返回它是否合法。合法的代碼片段需要遵守以下的所有規(guī)則：
代碼必須被合法的閉合標(biāo)簽包圍瘦陈。否則凝危，代碼是無(wú)效的。
閉合標(biāo)簽（不一定合法）要嚴(yán)格符合格式：<TAG_NAME>TAG_CONTENT</TAG_NAME>晨逝。其中蛾默，<TAG_NAME>是起始標(biāo)簽，</TAG_NAME>是結(jié)束標(biāo)簽捉貌。起始和結(jié)束標(biāo)簽中的 TAG_NAME 應(yīng)當(dāng)相同支鸡。當(dāng)且僅當(dāng) TAG_NAME 和 TAG_CONTENT 都是合法的冬念，閉合標(biāo)簽才是合法的。
合法的 TAG_NAME 僅含有大寫字母牧挣，長(zhǎng)度在范圍 [1,9] 之間急前。否則，該 TAG_NAME 是不合法的瀑构。
合法的 TAG_CONTENT 可以包含其他合法的閉合標(biāo)簽裆针，cdata （請(qǐng)參考規(guī)則7）和任意字符（注意參考規(guī)則1）除了不匹配的<、不匹配的起始和結(jié)束標(biāo)簽寺晌、不匹配的或帶有不合法 TAG_NAME 的閉合標(biāo)簽世吨。否則，TAG_CONTENT 是不合法的呻征。
一個(gè)起始標(biāo)簽耘婚，如果沒(méi)有具有相同 TAG_NAME 的結(jié)束標(biāo)簽與之匹配，是不合法的怕犁。反之亦然。不過(guò)己莺，你也需要考慮標(biāo)簽嵌套的問(wèn)題奏甫。
一個(gè)<，如果你找不到一個(gè)后續(xù)的>與之匹配凌受，是不合法的阵子。并且當(dāng)你找到一個(gè)<或</時(shí)，所有直到下一個(gè)>的前的字符胜蛉，都應(yīng)當(dāng)被解析為 TAG_NAME（不一定合法）挠进。
cdata 有如下格式：<![CDATA[CDATA_CONTENT]]>。CDATA_CONTENT 的范圍被定義成 <![CDATA[ 和后續(xù)的第一個(gè) ]]>之間的字符誊册。
CDATA_CONTENT 可以包含任意字符领突。cdata 的功能是阻止驗(yàn)證器解析CDATA_CONTENT，所以即使其中有一些字符可以被解析為標(biāo)簽（無(wú)論合法還是不合法）案怯，也應(yīng)該將它們視為常規(guī)字符君旦。
合法代碼的例子:
輸入: "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
輸出: True
解釋:
代碼被包含在了閉合的標(biāo)簽內(nèi)： <DIV> 和 </DIV> 。
TAG_NAME 是合法的嘲碱，TAG_CONTENT 包含了一些字符和 cdata 金砍。
即使 CDATA_CONTENT 含有不匹配的起始標(biāo)簽和不合法的 TAG_NAME，它應(yīng)該被視為普通的文本麦锯，而不是標(biāo)簽恕稠。
所以 TAG_CONTENT 是合法的，因此代碼是合法的扶欣。最終返回True鹅巍。
輸入: "<DIV>>> ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>"
輸出: True
解釋:
我們首先將代碼分割為： start_tag|tag_content|end_tag 千扶。
start_tag -> "<DIV>"
end_tag -> "</DIV>"
tag_content 也可被分割為： text1|cdata|text2 。
text1 -> ">> ![cdata[]] "
cdata -> "<![CDATA[<div>]>]]>" 昆著，其中 CDATA_CONTENT 為 "<div>]>"
text2 -> "]]>>]"
start_tag 不是 "<DIV>>>" 的原因參照規(guī)則 6 县貌。
cdata 不是 "<![CDATA[<div>]>]]>]]>" 的原因參照規(guī)則 7 。
不合法代碼的例子:
輸入: "<A> <B> </A> </B>"
輸出: False
解釋: 不合法凑懂。如果 "<A>" 是閉合的煤痕，那么 "<B>" 一定是不匹配的，反之亦然接谨。
輸入: "<DIV> div tag is not closed <DIV>"
輸出: False
輸入: "<DIV> unmatched < </DIV>"
輸出: False
輸入: "<DIV> closed tags with invalid tag name <b>123</b> </DIV>"
輸出: False
輸入: "<DIV> unmatched tags with invalid tag name </1234567890> and <CDATA[[]]> </DIV>"
輸出: False
輸入: "<DIV> unmatched start tag <B> and unmatched end tag </C> </DIV>"
輸出: False
注意:
為簡(jiǎn)明起見(jiàn)摆碉，你可以假設(shè)輸入的代碼（包括提到的任意字符）只包含數(shù)字, 字母, '<','>','/','!','[',']'和' '。
# ##正則
class Solution:
def isValid(self, code: str) -> bool:
code = re.sub(r'<!\[CDATA\[.*?\]\]>|t', '-', code)
prev = None
while code != prev:
prev = code
code = re.sub(r'<([A-Z]{1,9})>[^<]*</\1>', 't', code)
return code == 't'
636脓豪、函數(shù)的獨(dú)占空間
給出一個(gè)非搶占單線程CPU的 n 個(gè)函數(shù)運(yùn)行日志巷帝，找到函數(shù)的獨(dú)占時(shí)間。
每個(gè)函數(shù)都有一個(gè)唯一的 Id扫夜，從 0 到 n-1楞泼，函數(shù)可能會(huì)遞歸調(diào)用或者被其他函數(shù)調(diào)用。
日志是具有以下格式的字符串：function_id：start_or_end：timestamp笤闯。例如："0:start:0" 表示函數(shù) 0 從 0 時(shí)刻開(kāi)始運(yùn)行堕阔。"0:end:0" 表示函數(shù) 0 在 0 時(shí)刻結(jié)束。
函數(shù)的獨(dú)占時(shí)間定義是在該方法中花費(fèi)的時(shí)間颗味，調(diào)用其他函數(shù)花費(fèi)的時(shí)間不算該函數(shù)的獨(dú)占時(shí)間超陆。你需要根據(jù)函數(shù)的 Id 有序地返回每個(gè)函數(shù)的獨(dú)占時(shí)間。
示例 1:
輸入:
n = 2
logs =
["0:start:0",
"1:start:2",
"1:end:5",
"0:end:6"]
輸出:[3, 4]
說(shuō)明：
函數(shù) 0 在時(shí)刻 0 開(kāi)始浦马，在執(zhí)行了 2個(gè)時(shí)間單位結(jié)束于時(shí)刻 1时呀。
現(xiàn)在函數(shù) 0 調(diào)用函數(shù) 1，函數(shù) 1 在時(shí)刻 2 開(kāi)始晶默，執(zhí)行 4 個(gè)時(shí)間單位后結(jié)束于時(shí)刻 5谨娜。
函數(shù) 0 再次在時(shí)刻 6 開(kāi)始執(zhí)行，并在時(shí)刻 6 結(jié)束運(yùn)行磺陡，從而執(zhí)行了 1 個(gè)時(shí)間單位瞧预。
所以函數(shù) 0 總共的執(zhí)行了 2 +1 =3 個(gè)時(shí)間單位，函數(shù) 1 總共執(zhí)行了 4 個(gè)時(shí)間單位仅政。
說(shuō)明：
輸入的日志會(huì)根據(jù)時(shí)間戳排序垢油，而不是根據(jù)日志Id排序。
你的輸出會(huì)根據(jù)函數(shù)Id排序圆丹，也就意味著你的輸出數(shù)組中序號(hào)為 0 的元素相當(dāng)于函數(shù) 0 的執(zhí)行時(shí)間滩愁。
兩個(gè)函數(shù)不會(huì)在同時(shí)開(kāi)始或結(jié)束。
函數(shù)允許被遞歸調(diào)用辫封，直到運(yùn)行結(jié)束硝枉。
1 <= n <= 100
#
class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
res = [0]*n
stack = []
for s in logs:
tmp=s.split(':')
if tmp[1]=='start':
stack.append([int(tmp[0]),int(tmp[2])])
else:
temp = stack.pop()
time = int(tmp[2])-temp[1]+1
res[temp[0]]+=time
if stack:
res[stack[-1][0]]-=time
return res
682廉丽、棒球比賽
你現(xiàn)在是棒球比賽記錄員。
給定一個(gè)字符串列表妻味，每個(gè)字符串可以是以下四種類型之一：
1.整數(shù)（一輪的得分）：直接表示您在本輪中獲得的積分?jǐn)?shù)正压。
- "+"（一輪的得分）：表示本輪獲得的得分是前兩輪有效 回合得分的總和。
- "D"（一輪的得分）：表示本輪獲得的得分是前一輪有效 回合得分的兩倍责球。
- "C"（一個(gè)操作焦履，這不是一個(gè)回合的分?jǐn)?shù)）：表示您獲得的最后一個(gè)有效 回合的分?jǐn)?shù)是無(wú)效的，應(yīng)該被移除雏逾。
每一輪的操作都是永久性的嘉裤，可能會(huì)對(duì)前一輪和后一輪產(chǎn)生影響。
你需要返回你在所有回合中得分的總和栖博。
示例 1:
輸入: ["5","2","C","D","+"]
輸出: 30
解釋:
第1輪：你可以得到5分屑宠。總和是：5仇让。
第2輪：你可以得到2分典奉。總和是：7丧叽。
操作1：第2輪的數(shù)據(jù)無(wú)效卫玖。總和是：5蠢正。
第3輪：你可以得到10分（第2輪的數(shù)據(jù)已被刪除）骇笔∈〉辏總數(shù)是：15嚣崭。
第4輪：你可以得到5 + 10 = 15分∨嘲總數(shù)是：30雹舀。
示例 2:
輸入: ["5","-2","4","C","D","9","+","+"]
輸出: 27
解釋:
第1輪：你可以得到5分〈志悖總和是：5说榆。
第2輪：你可以得到-2分〈缛希總數(shù)是：3签财。
第3輪：你可以得到4分∑總和是：7唱蒸。
操作1：第3輪的數(shù)據(jù)無(wú)效【牡穑總數(shù)是：3神汹。
第4輪：你可以得到-4分（第三輪的數(shù)據(jù)已被刪除）庆捺。總和是：-1屁魏。
第5輪：你可以得到9分滔以。總數(shù)是：8氓拼。
第6輪：你可以得到-4 + 9 = 5分你画。總數(shù)是13披诗。
第7輪：你可以得到9 + 5 = 14分撬即。總數(shù)是27呈队。
# 棧中只存儲(chǔ)有效得分
class Solution:
def calPoints(self, ops: List[str]) -> int:
stack=[]
for i in range(len(ops)):
if ops[i].isdigit():
stack.append(int(ops[i]))
elif ops[i]=="+":
stack.append(stack[-1]+stack[-2])
elif ops[i]=='D':
stack.append(stack[-1]*2)
elif ops[i]=='C':
stack.pop()
return sum(stack)
762剥槐、原子的數(shù)量
給定一個(gè)化學(xué)式formula（作為字符串），返回每種原子的數(shù)量宪摧。
原子總是以一個(gè)大寫字母開(kāi)始粒竖，接著跟隨0個(gè)或任意個(gè)小寫字母，表示原子的名字几于。
如果數(shù)量大于 1蕊苗，原子后會(huì)跟著數(shù)字表示原子的數(shù)量。如果數(shù)量等于 1 則不會(huì)跟數(shù)字沿彭。例如朽砰，H2O 和 H2O2 是可行的，但 H1O2 這個(gè)表達(dá)是不可行的喉刘。
兩個(gè)化學(xué)式連在一起是新的化學(xué)式瞧柔。例如 H2O2He3Mg4 也是化學(xué)式。
一個(gè)括號(hào)中的化學(xué)式和數(shù)字（可選擇性添加）也是化學(xué)式睦裳。例如 (H2O2) 和 (H2O2)3 是化學(xué)式造锅。
給定一個(gè)化學(xué)式，輸出所有原子的數(shù)量廉邑。格式為：第一個(gè)（按字典序）原子的名子哥蔚，跟著它的數(shù)量（如果數(shù)量大于 1），然后是第二個(gè)原子的名字（按字典序）蛛蒙，跟著它的數(shù)量（如果數(shù)量大于 1）糙箍，以此類推。
示例 1:
輸入:
formula = "H2O"
輸出: "H2O"
解釋:
原子的數(shù)量是 {'H': 2, 'O': 1}牵祟。
示例 2:
輸入:
formula = "Mg(OH)2"
輸出: "H2MgO2"
解釋:
原子的數(shù)量是 {'H': 2, 'Mg': 1, 'O': 2}深夯。
示例 3:
輸入:
formula = "K4(ON(SO3)2)2"
輸出: "K4N2O14S4"
解釋:
原子的數(shù)量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。
注意:
所有原子的第一個(gè)字母為大寫课舍，剩余字母都是小寫塌西。
formula的長(zhǎng)度在[1, 1000]之間他挎。
formula只包含字母、數(shù)字和圓括號(hào)捡需，并且題目中給定的是合法的化學(xué)式办桨。
# 判斷大小寫
# 判斷括號(hào)
class Solution:
def countOfAtoms(self, formula: str) -> str:
result_dict = {}
atom_name, tmp_time, cur_time, st = "", "", 1, []
for ch in formula[::-1]:
if ch.isdigit():
tmp_time = ch + tmp_time
elif ch == ")":
if tmp_time == "":
st.append(1)
else:
time = int(tmp_time)
tmp_time = ""
st.append(time)
cur_time *= time
elif ch == "(":
cur_time = cur_time // st.pop()
elif ch.islower():
atom_name = ch + atom_name
else:
atom_name = ch + atom_name
#update(atom_name, tmp_time, cur_time, result_dict)
time = 1 if tmp_time == "" else int(tmp_time)
result_dict[atom_name] = result_dict.setdefault(atom_name, 0) + time * cur_time
atom_name = ""
tmp_time = ""
result = [(atom + ("" if result_dict[atom] == 1 else str(result_dict[atom]))) for atom in sorted(result_dict.keys())]
return "".join(result)
735、行星碰撞???
給定一個(gè)整數(shù)數(shù)組 asteroids站辉，表示在同一行的行星呢撞。
對(duì)于數(shù)組中的每一個(gè)元素，其絕對(duì)值表示行星的大小饰剥，正負(fù)表示行星的移動(dòng)方向（正表示向右移動(dòng)殊霞，負(fù)表示向左移動(dòng)）。每一顆行星以相同的速度移動(dòng)汰蓉。
找出碰撞后剩下的所有行星绷蹲。碰撞規(guī)則：兩個(gè)行星相互碰撞，較小的行星會(huì)爆炸顾孽。如果兩顆行星大小相同祝钢，則兩顆行星都會(huì)爆炸。兩顆移動(dòng)方向相同的行星若厚，永遠(yuǎn)不會(huì)發(fā)生碰撞拦英。
示例 1:
輸入:
asteroids = [5, 10, -5]
輸出: [5, 10]
解釋:
10 和 -5 碰撞后只剩下 10。 5 和 10 永遠(yuǎn)不會(huì)發(fā)生碰撞测秸。
示例 2:
輸入:
asteroids = [8, -8]
輸出: []
解釋:
8 和 -8 碰撞后疤估，兩者都發(fā)生爆炸。
示例 3:
輸入:
asteroids = [10, 2, -5]
輸出: [10]
解釋:
2 和 -5 發(fā)生碰撞后剩下 -5霎冯。10 和 -5 發(fā)生碰撞后剩下 10铃拇。
示例 4:
輸入:
asteroids = [-2, -1, 1, 2]
輸出: [-2, -1, 1, 2]
解釋:
-2 和 -1 向左移動(dòng)，而 1 和 2 向右移動(dòng)肃晚。
由于移動(dòng)方向相同的行星不會(huì)發(fā)生碰撞锚贱，所以最終沒(méi)有行星發(fā)生碰撞仔戈。
說(shuō)明:
數(shù)組 asteroids 的長(zhǎng)度不超過(guò) 10000关串。
每一顆行星的大小都是非零整數(shù)，范圍是 [-1000, 1000] 监徘。
# + - 碰撞
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
if len(asteroids)==1:
return asteroids[0]
stack=[-1]
for i in range(len(asteroids)):
if asteroids[i]*stack[-1]<0: #異號(hào)
if asteroids[i]+stack[-1]>0:
if abs(stack[-1])<abs(asteroids[i]):
stack.pop()
stack.append(asteroids[i])
elif asteroids[i]+stack[-1]==0:
stack.pop()
elif asteroids[i]*stack[-1]>0: # 同號(hào)
stack.append(asteroids[i])
return stack
739晋修、每日溫度
根據(jù)每日 氣溫 列表，請(qǐng)重新生成一個(gè)列表凰盔，對(duì)應(yīng)位置的輸入是你需要再等待多久溫度才會(huì)升高超過(guò)該日的天數(shù)墓卦。如果之后都不會(huì)升高，請(qǐng)?jiān)谠撐恢糜?0 來(lái)代替户敬。
例如落剪，給定一個(gè)列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]睁本，你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：氣溫 列表長(zhǎng)度的范圍是 [1, 30000]忠怖。每個(gè)氣溫的值的均為華氏度呢堰，都是在 [30, 100] 范圍內(nèi)的整數(shù)。
#[73, 74, 75, 71, 69, 72, 76, 73]
# [1, 1, 4, 2, 1, 1, 0, 0]
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
ans = [0] * len(T)
stack = [] #indexes from hottest to coldest
for i in range(len(T) - 1, -1, -1):
while stack and T[i] >= T[stack[-1]]:
stack.pop()
if stack:
ans[i] = stack[-1] - i
stack.append(i)
return ans
770凡泣、基本計(jì)算器
給定一個(gè)表達(dá)式 expression 如 expression = "e + 8 - a + 5" 和一個(gè)求值映射枉疼，如 {"e": 1}（給定的形式為 evalvars = ["e"] 和 evalints = [1]），返回表示簡(jiǎn)化表達(dá)式的標(biāo)記列表鞋拟，例如 ["-1*a","14"]
表達(dá)式交替使用塊和符號(hào)骂维，每個(gè)塊和符號(hào)之間有一個(gè)空格。
塊要么是括號(hào)中的表達(dá)式贺纲，要么是變量航闺，要么是非負(fù)整數(shù)。
塊是括號(hào)中的表達(dá)式猴誊，變量或非負(fù)整數(shù)来颤。
變量是一個(gè)由小寫字母組成的字符串（不包括數(shù)字）。請(qǐng)注意稠肘，變量可以是多個(gè)字母福铅，并注意變量從不具有像 "2x" 或 "-x" 這樣的前導(dǎo)系數(shù)或一元運(yùn)算符 。
表達(dá)式按通常順序進(jìn)行求值：先是括號(hào)项阴，然后求乘法滑黔，再計(jì)算加法和減法。例如环揽，expression = "1 + 2 * 3" 的答案是 ["7"]略荡。
輸出格式如下：
對(duì)于系數(shù)非零的每個(gè)自變量項(xiàng)，我們按字典排序的順序?qū)⒆宰兞繉懺谝粋€(gè)項(xiàng)中歉胶。例如汛兜，我們永遠(yuǎn)不會(huì)寫像 “bac” 這樣的項(xiàng)，只寫 “abc”通今。
項(xiàng)的次數(shù)等于被乘的自變量的數(shù)目粥谬，并計(jì)算重復(fù)項(xiàng)。(例如辫塌，"aabc" 的次數(shù)為 4漏策。)。我們先寫出答案的最大次數(shù)項(xiàng)臼氨，用字典順序打破關(guān)系掺喻，此時(shí)忽略詞的前導(dǎo)系數(shù)。
項(xiàng)的前導(dǎo)系數(shù)直接放在左邊，用星號(hào)將它與變量分隔開(kāi)(如果存在的話)感耙。前導(dǎo)系數(shù) 1 仍然要打印出來(lái)褂乍。
格式良好的一個(gè)示例答案是 ["-2aaa", "3aab", "3bb", "4a", "5*c", "-6"] 。
系數(shù)為 0 的項(xiàng)（包括常數(shù)項(xiàng)）不包括在內(nèi)即硼。例如树叽，“0” 的表達(dá)式輸出為 []。
class Solution:
def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
class C(collections.Counter):
def __add__(self, other):
self.update(other)
return self
def __sub__(self, other):
self.subtract(other)
return self
def __mul__(self, other):
product = C()
for x in self:
for y in other:
xy = tuple(sorted(x + y))
product[xy] += self[x] * other[y]
return product
vals = dict(zip(evalvars, evalints))
def f(s):
s = str(vals.get(s, s))
return C({(s,): 1}) if s.isalpha() else C({(): int(s)})
c = eval(re.sub('(\w+)', r'f("\1")', expression))
return ['*'.join((str(c[x]),) + x)
for x in sorted(c, key=lambda x: (-len(x), x)) if c[x]]
844谦絮、 比較含退格的字符串
給定 S 和 T 兩個(gè)字符串题诵，當(dāng)它們分別被輸入到空白的文本編輯器后，判斷二者是否相等层皱，并返回結(jié)果性锭。 # 代表退格字符。
示例 1：
輸入：S = "ab#c", T = "ad#c"
輸出：true
解釋：S 和 T 都會(huì)變成 “ac”叫胖。
示例 2：
輸入：S = "ab##", T = "c#d#"
輸出：true
解釋：S 和 T 都會(huì)變成 “”草冈。
示例 3：
輸入：S = "a##c", T = "#a#c"
輸出：true
解釋：S 和 T 都會(huì)變成 “c”。
示例 4：
輸入：S = "a#c", T = "b"
輸出：false
解釋：S 會(huì)變成 “c”瓮增，但 T 仍然是 “b”怎棱。
提示：
1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小寫字母以及字符 '#'。
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
s = ""
t = ""
#將輸入S翻譯成s
for i in S:
if i == "#":
if s:
s = s[:-1]
else:
s = s + i
#將輸入T翻譯成t
for j in T:
if j == "#":
if t:
t = t[:-1]
else:
t = t + j
return s==t
856绷跑、括號(hào)的分?jǐn)?shù)
給定一個(gè)平衡括號(hào)字符串 S拳恋，按下述規(guī)則計(jì)算該字符串的分?jǐn)?shù)：
() 得 1 分。
AB 得 A + B 分砸捏，其中 A 和 B 是平衡括號(hào)字符串谬运。
(A) 得 2 * A 分，其中 A 是平衡括號(hào)字符串垦藏。
示例 1：
輸入： "()"
輸出： 1
示例 2：
輸入： "(())"
輸出： 2
示例 3：
輸入： "()()"
輸出： 2
示例 4：
輸入： "(()(()))"
輸出： 6
提示：
S 是平衡括號(hào)字符串梆暖，且只含有 ( 和 ) 。
2 <= S.length <= 50
class Solution:
def scoreOfParentheses(self, S: str) -> int:
num1 = S.replace('()', '+1')
num2 = num1.replace('(', '+2*(')
return eval(num2)
880掂骏、索引處的解碼字符串
給定一個(gè)編碼字符串 S假栓。為了找出解碼字符串并將其寫入磁帶蒿赢，從編碼字符串中每次讀取一個(gè)字符奕筐，并采取以下步驟：
如果所讀的字符是字母暇矫，則將該字母寫在磁帶上举娩。
如果所讀的字符是數(shù)字（例如 d）轻掩，則整個(gè)當(dāng)前磁帶總共會(huì)被重復(fù)寫 d-1 次炸裆。
現(xiàn)在娜搂，對(duì)于給定的編碼字符串 S 和索引 K薛闪，查找并返回解碼字符串中的第 K 個(gè)字母辛馆。
示例 1：
輸入：S = "leet2code3", K = 10
輸出："o"
解釋：
解碼后的字符串為 "leetleetcodeleetleetcodeleetleetcode"。
字符串中的第 10 個(gè)字母是 "o"。
示例 2：
輸入：S = "ha22", K = 5
輸出："h"
解釋：
解碼后的字符串為 "hahahaha"昙篙。第 5 個(gè)字母是 "h"腊状。
示例 3：
輸入：S = "a2345678999999999999999", K = 1
輸出："a"
解釋：
解碼后的字符串為 "a" 重復(fù) 8301530446056247680 次。第 1 個(gè)字母是 "a"苔可。
提示：
2 <= S.length <= 100
S 只包含小寫字母與數(shù)字 2 到 9 缴挖。
S 以字母開(kāi)頭。
1 <= K <= 10^9
解碼后的字符串保證少于 2^63 個(gè)字母焚辅。
class Solution:
def decodeAtIndex(self, S: str, K: int) -> str:
i = cnt = 0
c = ''
x = []
while i < len(S) and cnt < K:
if S[i].isdigit():
cnt *= int(S[i])
if S[i-1].isdigit(): x[-1][0] = cnt
else: x.append([cnt, len(c) - 1])
else:
c += S[i]
cnt += 1
x.append([cnt, len(c) - 1])
i += 1
ret = ''
while x:
t = x.pop()
K %= t[0]
if K == 0:
ret = c[t[1]]
break
return ret
895映屋、最大頻率棧
實(shí)現(xiàn) FreqStack，模擬類似棧的數(shù)據(jù)結(jié)構(gòu)的操作的一個(gè)類同蜻。
FreqStack 有兩個(gè)函數(shù)：
push(int x)棚点，將整數(shù) x 推入棧中。
pop()湾蔓，它移除并返回棧中出現(xiàn)最頻繁的元素瘫析。
如果最頻繁的元素不只一個(gè)，則移除并返回最接近棧頂?shù)脑亍?/p>
示例：
輸入：
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
輸出：[null,null,null,null,null,null,null,5,7,5,4]
解釋：
執(zhí)行六次 .push 操作后默责，棧自底向上為 [5,7,5,7,4,5]贬循。然后：
pop() -> 返回 5，因?yàn)?5 是出現(xiàn)頻率最高的桃序。
棧變成 [5,7,5,7,4]杖虾。
pop() -> 返回 7，因?yàn)?5 和 7 都是頻率最高的媒熊，但 7 最接近棧頂亏掀。
棧變成 [5,7,5,4]。
pop() -> 返回 5 泛释。
棧變成 [5,7,4]滤愕。
pop() -> 返回 4 。
棧變成 [5,7]怜校。
提示：
對(duì) FreqStack.push(int x) 的調(diào)用中 0 <= x <= 10^9间影。
如果棧的元素?cái)?shù)目為零，則保證不會(huì)調(diào)用 FreqStack.pop()茄茁。
單個(gè)測(cè)試樣例中魂贬，對(duì) FreqStack.push 的總調(diào)用次數(shù)不會(huì)超過(guò) 10000。
單個(gè)測(cè)試樣例中裙顽，對(duì) FreqStack.pop 的總調(diào)用次數(shù)不會(huì)超過(guò) 10000付燥。
所有測(cè)試樣例中，對(duì) FreqStack.push 和 FreqStack.pop 的總調(diào)用次數(shù)不會(huì)超過(guò) 150000愈犹。
class FreqStack:
def __init__(self):
self.freq = collections.Counter()
self.group = collections.defaultdict(list)
self.maxfreq = 0
def push(self, x):
f = self.freq[x] + 1
self.freq[x] = f
if f > self.maxfreq:
self.maxfreq = f
self.group[f].append(x)
def pop(self):
x = self.group[self.maxfreq].pop()
self.freq[x] -= 1
if not self.group[self.maxfreq]:
self.maxfreq -= 1
return x
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()
896键科、單調(diào)數(shù)列
如果數(shù)組是單調(diào)遞增或單調(diào)遞減的闻丑，那么它是單調(diào)的。
如果對(duì)于所有 i <= j勋颖，A[i] <= A[j]嗦嗡，那么數(shù)組 A 是單調(diào)遞增的。 如果對(duì)于所有 i <= j饭玲，A[i]> = A[j]侥祭，那么數(shù)組 A 是單調(diào)遞減的。
當(dāng)給定的數(shù)組 A 是單調(diào)數(shù)組時(shí)返回 true茄厘，否則返回 false矮冬。
示例 1：
輸入：[1,2,2,3]
輸出：true
示例 2：
輸入：[6,5,4,4]
輸出：true
示例 3：
輸入：[1,3,2]
輸出：false
示例 4：
輸入：[1,2,4,5]
輸出：true
示例 5：
輸入：[1,1,1]
輸出：true
提示：
1 <= A.length <= 50000
-100000 <= A[i] <= 100000
class Solution:
def isMonotonic(self, A: List[int]) -> bool:
return (all(A[i] <= A[i+1] for i in range(len(A) - 1)) or
all(A[i] >= A[i+1] for i in range(len(A) - 1)))
"""
class Solution:
def isMonotonic(self, A: List[int]) -> bool:
stack1=[A[0]]
stack2=[A[0]]
for i in range(1,len(A)):
if A[i]>stack1[-1]:
stack1.append(A[i])
elif A[i]<stack1[-1]:
stack2.append(A[i])
else:
stack1.append(A[i])
stack2.append(A[i])
return (len(stack1)==len(A) or len(stack2)==len(A))
"""
901、股票價(jià)格跨度
編寫一個(gè) StockSpanner 類次哈，它收集某些股票的每日?qǐng)?bào)價(jià)欢伏，并返回該股票當(dāng)日價(jià)格的跨度。
今天股票價(jià)格的跨度被定義為股票價(jià)格小于或等于今天價(jià)格的最大連續(xù)日數(shù)（從今天開(kāi)始往回?cái)?shù)亿乳，包括今天）硝拧。
例如，如果未來(lái)7天股票的價(jià)格是 [100, 80, 60, 70, 60, 75, 85]葛假，那么股票跨度將是 [1, 1, 1, 2, 1, 4, 6]障陶。
示例：
輸入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
輸出：[null,1,1,1,2,1,4,6]
解釋：
首先，初始化 S = StockSpanner()聊训，然后：
S.next(100) 被調(diào)用并返回 1抱究，
S.next(80) 被調(diào)用并返回 1，
S.next(60) 被調(diào)用并返回 1带斑，
S.next(70) 被調(diào)用并返回 2鼓寺，
S.next(60) 被調(diào)用并返回 1，
S.next(75) 被調(diào)用并返回 4勋磕，
S.next(85) 被調(diào)用并返回 6妈候。
注意 (例如) S.next(75) 返回 4，因?yàn)榻刂两裉斓淖詈?4 個(gè)價(jià)格
(包括今天的價(jià)格 75) 小于或等于今天的價(jià)格挂滓。
提示：
調(diào)用 StockSpanner.next(int price) 時(shí)苦银，將有 1 <= price <= 10^5。
每個(gè)測(cè)試用例最多可以調(diào)用 10000 次 StockSpanner.next赶站。
在所有測(cè)試用例中幔虏，最多調(diào)用 150000 次 StockSpanner.next。
此問(wèn)題的總時(shí)間限制減少了 50%贝椿。
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
d = 1
while len(self.stack) > 0 and price >= self.stack[-1][0]:
d += self.stack.pop()[1]
self.stack.append((price, d))
return d
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
907想括、子數(shù)組的最小值之和
給定一個(gè)整數(shù)數(shù)組 A，找到 min(B) 的總和烙博，其中 B 的范圍為 A 的每個(gè)（連續(xù)）子數(shù)組瑟蜈。
由于答案可能很大烟逊，因此返回答案模 10^9 + 7。
示例：
輸入：[3,1,2,4]
輸出：17
解釋：
子數(shù)組為 [3]踪栋，[1]焙格，[2]图毕，[4]夷都，[3,1]，[1,2]予颤，[2,4]囤官，[3,1,2]，[1,2,4]蛤虐，[3,1,2,4]党饮。
最小值為 3，1驳庭，2刑顺，4，1饲常，1蹲堂，2，1贝淤，1柒竞，1，和為 17播聪。
提示：
1 <= A <= 30000
1 <= A[i] <= 30000
class Solution:
def sumSubarrayMins(self, A: List[int]) -> int:
"""
:type A: List[int]
:rtype: int
"""
len_A = len(A)
if len_A == 0:
return 0
if len_A == 1:
return A[0]
ans = 0
left = [0] * len_A
right = [0] * len_A
stack = []
for i in range(len_A):
while stack and A[stack[-1]] > A[i]:
stack.pop()
if not stack:
left[i] = -1
else:
left[i] = stack[-1]
stack.append(i)
stack = []
for i in range(len_A - 1, -1, -1):
while stack and A[stack[-1]] >= A[i]:
stack.pop()
if not stack:
right[i] = len_A
else:
right[i] = stack[-1]
stack.append(i)
for i in range(len_A):
ans += (i - left[i]) * (right[i] - i) * A[i]
ans %= 1000000007
return ans
921朽基、使括號(hào)有效的最少添加
給定一個(gè)由 '(' 和 ')' 括號(hào)組成的字符串 S，我們需要添加最少的括號(hào)（ '(' 或是 ')'离陶，可以在任何位置）稼虎，以使得到的括號(hào)字符串有效。
從形式上講招刨，只有滿足下面幾點(diǎn)之一渡蜻，括號(hào)字符串才是有效的：
它是一個(gè)空字符串，或者
它可以被寫成 AB （A 與 B 連接）, 其中 A 和 B 都是有效字符串计济，或者
它可以被寫作 (A)茸苇，其中 A 是有效字符串。
給定一個(gè)括號(hào)字符串沦寂，返回為使結(jié)果字符串有效而必須添加的最少括號(hào)數(shù)学密。
示例 1：
輸入："())"
輸出：1
示例 2：
輸入："((("
輸出：3
示例 3：
輸入："()"
輸出：0
示例 4：
輸入："()))(("
輸出：4
提示：
S.length <= 1000
S 只包含 '(' 和 ')' 字符。
class Solution:
def minAddToMakeValid(self, S: str) -> int:
stack=[]
for i in range(len(S)):
if (len(stack)==0):
stack.append(S[i])
else:
if S[i]==stack[-1]:
stack.append(S[i])
else:
stack.pop()
return(len(stack))
946传藏、驗(yàn)證棧序列
給定 pushed 和 popped 兩個(gè)序列腻暮，每個(gè)序列中的 值都不重復(fù)彤守，只有當(dāng)它們可能是在最初空棧上進(jìn)行的推入 push 和彈出 pop 操作序列的結(jié)果時(shí)，返回 true哭靖；否則具垫，返回 false 。
示例 1：
輸入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
輸出：true
解釋：我們可以按以下順序執(zhí)行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
輸入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
輸出：false
解釋：1 不能在 2 之前彈出试幽。
提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列筝蚕。
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack=[pushed[0]]
for i in range(len(pushed)):
if len(stack)>0:
if popped[i]==stack[-1]:
stack.pop()
else:
stack.append(pushed[i])
return (len(stack)==0)
975、奇偶跳
給定一個(gè)整數(shù)數(shù)組 A铺坞，你可以從某一起始索引出發(fā)起宽，跳躍一定次數(shù)。在你跳躍的過(guò)程中济榨，第 1坯沪、3、5... 次跳躍稱為奇數(shù)跳躍擒滑，而第 2腐晾、4、6... 次跳躍稱為偶數(shù)跳躍丐一。
你可以按以下方式從索引 i 向后跳轉(zhuǎn)到索引 j（其中 i < j）：
在進(jìn)行奇數(shù)跳躍時(shí)（如藻糖，第 1，3钝诚，5... 次跳躍）颖御，你將會(huì)跳到索引 j，使得 A[i] <= A[j]凝颇，A[j] 是可能的最小值潘拱。如果存在多個(gè)這樣的索引 j，你只能跳到滿足要求的最小索引 j 上拧略。
在進(jìn)行偶數(shù)跳躍時(shí)（如芦岂，第 2，4垫蛆，6... 次跳躍）禽最，你將會(huì)跳到索引 j，使得 A[i] => A[j]袱饭，A[j] 是可能的最大值川无。如果存在多個(gè)這樣的索引 j，你只能跳到滿足要求的最小索引 j 上虑乖。
（對(duì)于某些索引 i懦趋，可能無(wú)法進(jìn)行合乎要求的跳躍。）
如果從某一索引開(kāi)始跳躍一定次數(shù)（可能是 0 次或多次）疹味，就可以到達(dá)數(shù)組的末尾（索引 A.length - 1）仅叫，那么該索引就會(huì)被認(rèn)為是好的起始索引帜篇。
返回好的起始索引的數(shù)量。
示例 1：
輸入：[10,13,12,14,15]
輸出：2
解釋：
從起始索引 i = 0 出發(fā)诫咱，我們可以跳到 i = 2笙隙，（因?yàn)?A[2] 是 A[1]，A[2]坎缭，A[3]竟痰，A[4] 中大于或等于 A[0] 的最小值），然后我們就無(wú)法繼續(xù)跳下去了幻锁。
從起始索引 i = 1 和 i = 2 出發(fā)凯亮，我們可以跳到 i = 3边臼，然后我們就無(wú)法繼續(xù)跳下去了哄尔。
從起始索引 i = 3 出發(fā)，我們可以跳到 i = 4柠并，到達(dá)數(shù)組末尾岭接。
從起始索引 i = 4 出發(fā)，我們已經(jīng)到達(dá)數(shù)組末尾臼予。
總之鸣戴，我們可以從 2 個(gè)不同的起始索引（i = 3, i = 4）出發(fā)，通過(guò)一定數(shù)量的跳躍到達(dá)數(shù)組末尾粘拾。
示例 2：
輸入：[2,3,1,1,4]
輸出：3
解釋：
從起始索引 i=0 出發(fā)窄锅，我們依次可以跳到 i = 1，i = 2缰雇，i = 3：
在我們的第一次跳躍（奇數(shù)）中入偷，我們先跳到 i = 1，因?yàn)?A[1] 是（A[1]械哟，A[2]疏之，A[3]，A[4]）中大于或等于 A[0] 的最小值暇咆。
在我們的第二次跳躍（偶數(shù)）中锋爪，我們從 i = 1 跳到 i = 2，因?yàn)?A[2] 是（A[2]爸业，A[3]其骄，A[4]）中小于或等于 A[1] 的最大值。A[3] 也是最大的值扯旷，但 2 是一個(gè)較小的索引拯爽，所以我們只能跳到 i = 2，而不能跳到 i = 3薄霜。
在我們的第三次跳躍（奇數(shù)）中某抓，我們從 i = 2 跳到 i = 3纸兔，因?yàn)?A[3] 是（A[3]，A[4]）中大于或等于 A[2] 的最小值否副。
我們不能從 i = 3 跳到 i = 4汉矿，所以起始索引 i = 0 不是好的起始索引。
類似地备禀，我們可以推斷：
從起始索引 i = 1 出發(fā)洲拇， 我們跳到 i = 4，這樣我們就到達(dá)數(shù)組末尾曲尸。
從起始索引 i = 2 出發(fā)赋续， 我們跳到 i = 3，然后我們就不能再跳了另患。
從起始索引 i = 3 出發(fā)纽乱， 我們跳到 i = 4，這樣我們就到達(dá)數(shù)組末尾昆箕。
從起始索引 i = 4 出發(fā)鸦列，我們已經(jīng)到達(dá)數(shù)組末尾。
總之鹏倘，我們可以從 3 個(gè)不同的起始索引（i = 1, i = 3, i = 4）出發(fā)薯嗤，通過(guò)一定數(shù)量的跳躍到達(dá)數(shù)組末尾。
示例 3：
輸入：[5,1,3,4,2]
輸出：3
解釋：
我們可以從起始索引 1纤泵，2骆姐，4 出發(fā)到達(dá)數(shù)組末尾。
提示：
1 <= A.length <= 20000
0 <= A[i] < 100000
class Solution:
def oddEvenJumps(self, A: List[int]) -> int:
n = len(A)
def st(data):
s, res = [], [0]*n
for i in data:
while s and s[-1] < i:
res[s.pop()] = i
s.append(i)
return res
d = sorted(range(n), key=lambda i: A[i])
n1, n2 = st(d), st(sorted(d, key=lambda i: -A[i]))
h, l = [0] * n, [0] * n
h[-1] = l[-1] = 1
for i in range(n - 2, -1, -1):
h[i] = l[n1[i]]
l[i] = h[n2[i]]
return sum(h)
1003捏题、檢查替換后的詞是否有效
給定有效字符串 "abc"玻褪。
對(duì)于任何有效的字符串 V，我們可以將 V 分成兩個(gè)部分 X 和 Y涉馅，使得 X + Y（X 與 Y 連接）等于 V归园。（X 或 Y 可以為空。）那么稚矿，X + "abc" + Y 也同樣是有效的庸诱。
例如，如果 S = "abc"晤揣，則有效字符串的示例是："abc"桥爽，"aabcbc"，"abcabc"昧识，"abcabcababcc"钠四。無(wú)效字符串的示例是："abccba"，"ab"，"cababc"缀去，"bac"侣灶。
如果給定字符串 S 有效，則返回 true缕碎；否則褥影，返回 false。
示例 1：
輸入："aabcbc"
輸出：true
解釋：
從有效字符串 "abc" 開(kāi)始咏雌。
然后我們可以在 "a" 和 "bc" 之間插入另一個(gè) "abc"凡怎，產(chǎn)生 "a" + "abc" + "bc"，即 "aabcbc"赊抖。
示例 2：
輸入："abcabcababcc"
輸出：true
解釋：
"abcabcabc" 是有效的统倒，它可以視作在原串后連續(xù)插入 "abc"。
然后我們可以在最后一個(gè)字母之前插入 "abc"氛雪，產(chǎn)生 "abcabcab" + "abc" + "c"房匆，即 "abcabcababcc"。
示例 3：
輸入："abccba"
輸出：false
示例 4：
輸入："cababc"
輸出：false
提示：
1 <= S.length <= 20000
S[i] 為 'a'注暗、'b'坛缕、或 'c'
class Solution:
def isValid(self, S: str) -> bool:
while 'abc' in S:
S = S.replace('abc', '')
return not S
1019墓猎、 鏈表中的下一個(gè)更大節(jié)點(diǎn)
給出一個(gè)以頭節(jié)點(diǎn) head 作為第一個(gè)節(jié)點(diǎn)的鏈表捆昏。鏈表中的節(jié)點(diǎn)分別編號(hào)為：node_1, node_2, node_3, ... 。
每個(gè)節(jié)點(diǎn)都可能有下一個(gè)更大值（next larger value）：對(duì)于 node_i毙沾，如果其 next_larger(node_i) 是 node_j.val骗卜，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的選項(xiàng)中最小的那個(gè)左胞。如果不存在這樣的 j寇仓，那么下一個(gè)更大值為 0 。
返回整數(shù)答案數(shù)組 answer烤宙，其中 answer[i] = next_larger(node_{i+1}) 遍烦。
注意：在下面的示例中，諸如 [2,1,5] 這樣的輸入（不是輸出）是鏈表的序列化表示躺枕，其頭節(jié)點(diǎn)的值為 2服猪，第二個(gè)節(jié)點(diǎn)值為 1，第三個(gè)節(jié)點(diǎn)值為 5 拐云。
示例 1：
輸入：[2,1,5]
輸出：[5,5,0]
示例 2：
輸入：[2,7,4,3,5]
輸出：[7,0,5,5,0]
示例 3：
輸入：[1,7,5,1,9,2,5,1]
輸出：[7,9,9,9,0,5,0,0]
提示：
對(duì)于鏈表中的每個(gè)節(jié)點(diǎn)罢猪，1 <= node.val <= 10^9
給定列表的長(zhǎng)度在 [0, 10000] 范圍內(nèi)
