深圳网站建设设,大连金州旅游景点有哪些,兰州市做网站的,莱芜都市网人才招聘文章目录1.删除最外层的括号信息要求答案2.棒球比赛信息示例答案3. 用栈实现队列要求说明:答案4.用队列模拟栈描述注意答案5.下一个更大的元素#xff08;未解#xff09;信息#xff1a;示例#xff1a;注意:答案#xff1a;6.删除字符串中的所有相邻重复项信息示例…
文章目录1.删除最外层的括号信息要求答案2.棒球比赛信息示例答案3. 用栈实现队列要求说明:答案4.用队列模拟栈描述注意答案5.下一个更大的元素未解信息示例注意:答案6.删除字符串中的所有相邻重复项信息示例答案7. 获取栈中的最小元素 (时间复杂度较大)信息示例:答案8.比较包含退格的两个字符串(复杂度都比较低)信息示例答案9.判断是否是有效的括号很巧妙信息示例答案10.二叉树的中序遍历左跟右信息答案11.二叉树的前序遍历根左右信息答案12.二叉树的后序排列顺序是左右根信息答案13.使括号有效的最少添加巧妙信息示例答案14.二叉搜索树迭代器二叉搜索树信息答案15.扁平化嵌套列表迭代器信息示例答案1.删除最外层的括号
信息
有效括号字符串为空 ()、( A “)” 或 A B其中 A 和 B 都是有效的括号字符串 代表字符串的连接。例如()(())() 和 “(()(()))” 都是有效的括号字符串。
如果有效字符串 S 非空且不存在将其拆分为 S AB 的方法我们称其为原语primitive其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S考虑将其进行原语化分解使得S P_1 P_2 … P_k其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解删除分解中每个原语字符串的最外层括号返回 S 。
要求
示例 1
输入(()())(())
输出()()()
解释
输入字符串为 (()())(())原语化分解得到 (()()) (())
删除每个部分中的最外层括号后得到 ()() () ()()()。示例 2
输入(()())(())(()(()))
输出()()()()(())
解释
输入字符串为 (()())(())(()(()))原语化分解得到 (()()) (()) (()(()))
删除每隔部分中的最外层括号后得到 ()() () ()(()) ()()()()(())。示例 3
输入()()
输出
解释
输入字符串为 ()()原语化分解得到 () ()
删除每个部分中的最外层括号后得到 。答案
class Solution(object):def removeOuterParentheses(self, S)::type S: str:rtype: strlast, cur_len 0, 0result []for i, each in enumerate(S):if each (:cur_len 1if each ):cur_len - 1if cur_len 0:result.append(S[last 1:i])last i 1return .join(result)solution Solution()
print(solution.removeOuterParentheses(()()))2.棒球比赛
信息
你现在是棒球比赛记录员。 给定一个字符串列表每个字符串可以是以下四种类型之一 1.整数一轮的得分直接表示您在本轮中获得的积分数。 2. “”一轮的得分表示本轮获得的得分是前两轮有效 回合得分的总和。 3. “D”一轮的得分表示本轮获得的得分是前一轮有效 回合得分的两倍。 4. “C”一个操作这不是一个回合的分数表示您获得的最后一个有效 回合的分数是无效的应该被移除。
每一轮的操作都是永久性的可能会对前一轮和后一轮产生影响。 你需要返回你在所有回合中得分的总和。
示例
示例 1:
输入: [“5”,“2”,“C”,“D”,] 输出: 30 解释: 第1轮你可以得到5分。总和是5。 第2轮你可以得到2分。总和是7。 操作1第2轮的数据无效。总和是5。 第3轮你可以得到10分第2轮的数据已被删除。总数是15。 第4轮你可以得到5 10 15分。总数是30。 示例 2:
输入: [“5”,-2,“4”,“C”,“D”,“9”,,] 输出: 27 解释: 第1轮你可以得到5分。总和是5。 第2轮你可以得到-2分。总数是3。 第3轮你可以得到4分。总和是7。 操作1第3轮的数据无效。总数是3。 第4轮你可以得到-4分第三轮的数据已被删除。总和是-1。 第5轮你可以得到9分。总数是8。 第6轮你可以得到-4 9 5分。总数是13。 第7轮你可以得到9 5 14分。总数是27。 注意
输入列表的大小将介于1和1000之间。 列表中的每个整数都将介于-30000和30000之间。
答案
class Solution:def calPoints(self, ops)::type ops: List[str]:rtype: intres []for i in range(len(ops)):if ops[i] C:res.pop()elif ops[i] D:res.append(res[-1] * 2)elif ops[i] :res.append(res[-1] res[-2])else:res.append(int(ops[i]))return sum(res)3. 用栈实现队列
要求
使用栈实现队列的下列操作
push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。 示例:
MyQueue queue new MyQueue();
queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false
说明:
你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。 假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作。
答案
from collections import deque
class MyQueue:def __init__(self):Initialize your data structure here.self.Myqueue deque()def push(self, x: int) - None:Push element x to the back of queue.self.Myqueue.append(x)def pop(self) - int:Removes the element from in front of queue and returns that element.if len(self.Myqueue) 0:return self.Myqueue.popleft()else:return Nonedef peek(self) - int:Get the front element.if len(self.Myqueue) 0:return self.Myqueue[0]else:return Nonedef empty(self) - bool:Returns whether the queue is empty.return len(self.Myqueue) 04.用队列模拟栈
描述
使用队列实现栈的下列操作
push(x) – 元素 x 入栈pop() – 移除栈顶元素top() – 获取栈顶元素empty() – 返回栈是否为空
注意
你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。 你可以假设所有操作都是有效的例如, 对一个空的栈不会调用 pop 或者 top 操作。
答案
class MyStack(object):def __init__(self):Initialize your data structure here.self.stack []self.length 0def push(self, x):Push element x onto stack.:type x: int:rtype: Noneself.stack.append(x)self.length 1def pop(self):Removes the element on top of the stack and returns that element.:rtype: intif self.empty() is False:self.length - 1return self.stack.pop()def top(self):Get the top element.:rtype: intif self.empty() is False:return self.stack[self.length - 1]def empty(self):Returns whether the stack is empty.:rtype: boolif len(self.stack) 0:return Truereturn False5.下一个更大的元素未解
信息
给定两个没有重复元素的数组 nums1 和 nums2 其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在对应位置输出-1。
示例
示例 1:
输入: nums1 [4,1,2], nums2 [1,3,4,2]. 输出: [-1,3,-1] 解释: 对于num1中的数字4你无法在第二个数组中找到下一个更大的数字因此输出 -1。 对于num1中的数字1第二个数组中数字1右边的下一个较大数字是 3。 对于num1中的数字2第二个数组中没有下一个更大的数字因此输出 -1。 示例 2:
输入: nums1 [2,4], nums2 [1,2,3,4]. 输出: [3,-1] 解释: 对于num1中的数字2第二个数组中的下一个较大数字是3。 对于num1中的数字4第二个数组中没有下一个更大的数字因此输出 -1。
注意:
nums1和nums2中所有元素是唯一的。 nums1和nums2 的数组大小都不超过1000。
答案
未解
6.删除字符串中的所有相邻重复项
信息
给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。
在 S 上反复执行重复项删除操作直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例
输入“abbaca” 输出“ca” 解释 例如在 “abbaca” 中我们可以删除 “bb” 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”其中又只有 “aa” 可以执行重复项删除操作所以最后的字符串为 “ca”。
提示1 S.length 20000
S 仅由小写英文字母组成。答案
class Solution:def removeDuplicates(self, S: str) - str:stack[] # 定义一个栈for i in S:if not stack: # 如果当前栈为空stack.append(i)elif i stack[-1]: # 如果当前元素与栈顶元素相等stack.pop()else:stack.append(i)return .join(stack)7. 获取栈中的最小元素 (时间复杂度较大)
信息
设计一个支持 pushpoptop 操作并能在常数时间内检索到最小元素的栈。
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.
答案
class MinStack:def __init__(self):initialize your data structure here.self.stack []self.flag0def push(self, x: int) - None:self.stack.append(x)def pop(self) - None:if self.stack:self.stack.pop()def top(self) - int:if self.stack:return self.stack[-1]def getMin(self) - int:self.flag self.stack[0]for i in self.stack:if self.flag i:self.flag ireturn self.flag执行结果
执行用时 : 2828 ms, 在所有 Python3 提交中击败了5.02%的用户 内存消耗 : 16 MB, 在所有 Python3 提交中击败了99.88%的用户
8.比较包含退格的两个字符串(复杂度都比较低)
信息
给定 S 和 T 两个字符串当它们分别被输入到空白的文本编辑器后判断二者是否相等并返回结果。 # 代表退格字符。
示例
示例 1
输入S “ab#c”, T “ad#c” 输出true 解释S 和 T 都会变成 “ac”。 示例 2
输入S “ab##”, T “c#d#” 输出true 解释S 和 T 都会变成 “”。 示例 3
输入S “a##c”, T “#a#c” 输出true 解释S 和 T 都会变成 “c”。 示例 4
输入S “a#c”, T “b” 输出false 解释S 会变成 “c”但 T 仍然是 “b”。
答案
class Solution:def backspaceCompare(self, S: str, T: str) - bool:# 新建两个栈stack_a []stack_b [] for i in S:if i ! #:stack_a.append(i)elif i # and stack_a:stack_a.pop()for i in T:if i ! #:stack_b.append(i)elif i # and stack_b:stack_b.pop()return stack_a stack_b执行结果 执行用时 :44 ms, 在所有 Python3 提交中击败了96.89%的用户 内存消耗 :13 MB, 在所有 Python3 提交中击败了98.24%的用户
9.判断是否是有效的括号很巧妙
信息
给定一个只包括 ‘(’’)’’{’’}’’[’’]’ 的字符串判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例
示例 1:
输入: “()” 输出: true 示例 2:
输入: “()[]{}” 输出: true 示例 3:
输入: “(]” 输出: false 示例 4:
输入: “([)]” 输出: false 示例 5:
输入: “{[]}” 输出: true
答案
class Solution:def isValid(self, s: str) - bool:while {} in s or () in s or [] in s:s s.replace({}, )s s.replace([], )s s.replace((), )return s 10.二叉树的中序遍历左跟右
信息
给定一个二叉树返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1 2 / 3
输出: [1,3,2] 进阶: 递归算法很简单你可以通过迭代算法完成吗
答案 class TreeNode:def __init__(self, x):self.val xself.left Noneself.right Noneclass Solution:def __init__(self):self.stack []def inorderTraversal(self, root: TreeNode) - List[int]:if root is None:return self.stackif root.left:self.inorderTraversal(root.left)self.stack.append(root.val)if root.right:self.inorderTraversal(root.right)return self.stack11.二叉树的前序遍历根左右
信息
给定一个二叉树返回它的 前序 遍历。
示例:
输入: [1,null,2,3] 1 2 / 3
输出: [1,2,3] 进阶: 递归算法很简单你可以通过迭代算法完成吗
答案
class TreeNode:def __init__(self, x):self.val xself.left Noneself.right Noneclass Solution:def __init__(self):self.stack []def preorderTraversal(self, root: TreeNode) - List[int]:if root is None:return self.stackself.stack.append(root.val)if root.left:self.preorderTraversal(root.left)if root.right:self.preorderTraversal(root.right)return self.stack12.二叉树的后序排列顺序是左右根
信息
给定一个二叉树返回它的 后序 遍历。
示例:
输入: [1,null,2,3] 1 2 / 3
输出: [3,2,1] 进阶: 递归算法很简单你可以通过迭代算法完成吗
答案
class TreeNode:def __init__(self, x):self.val xself.left Noneself.right Noneclass Solution:def __init__(self):self.stack []def postorderTraversal(self, root: TreeNode) - List[int]:if root is None:return self.stackif root.left:self.postorderTraversal(root.left)if root.right:self.postorderTraversal(root.right)self.stack.append(root.val)return self.stack13.使括号有效的最少添加巧妙
信息
给定一个由 ‘(’ 和 ‘)’ 括号组成的字符串 S我们需要添加最少的括号 ‘(’ 或是 ‘)’可以在任何位置以使得到的括号字符串有效。
从形式上讲只有满足下面几点之一括号字符串才是有效的
它是一个空字符串或者 它可以被写成 AB A 与 B 连接, 其中 A 和 B 都是有效字符串或者 它可以被写作 (A)其中 A 是有效字符串。 给定一个括号字符串返回为使结果字符串有效而必须添加的最少括号数。
示例
示例 1
输入()) 输出1 示例 2
输入((( 输出3 示例 3
输入() 输出0 示例 4
输入()))(( 输出4
提示S.length 1000
S 只包含 ( 和 ) 字符。答案
class Solution:def minAddToMakeValid(self, S: str) - int:while () in S:S S.replace((),)return len(S)14.二叉搜索树迭代器
二叉搜索树
二叉查找树Binary Search Tree又二叉搜索树二叉排序树它或者是一棵空树或者是具有下列性质的二叉树 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 它的左、右子树也分别为二叉排序树。
信息
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。 示例 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
提示
next() 和 hasNext() 操作的时间复杂度是 O(1)并使用 O(h) 内存其中 h 是树的高度。 你可以假设 next() 调用总是有效的也就是说当调用 next() 时BST 中至少存在一个下一个最小的数。
答案
class TreeNode:def __init__(self, x):self.val xself.left Noneself.right Noneclass BSTIterator:def __init__(self, root: TreeNode):self.stack []while root:self.stack.append(root)root root.leftdef next(self) - int:return the next smallest numbertemp self.stack.pop()res temp.valtemp temp.rightwhile temp:self.stack.append(temp)temp temp.leftreturn resdef hasNext(self) - bool:return whether we have a next smallest numberreturn self.stack ! []15.扁平化嵌套列表迭代器
信息
给定一个嵌套的整型列表。设计一个迭代器使其能够遍历这个整型列表中的所有整数。
列表中的项或者为一个整数或者是另一个列表。
示例
示例 1:
输入: [[1,1],2,[1,1]] 输出: [1,1,2,1,1] 解释: 通过重复调用 next 直到 hasNext 返回falsenext 返回的元素的顺序应该是: [1,1,2,1,1]。 示例 2:
输入: [1,[4,[6]]] 输出: [1,4,6] 解释: 通过重复调用 next 直到 hasNext 返回falsenext 返回的元素的顺序应该是: [1,4,6]。
答案
