前言
想去甲方的话，就得会算法才能过笔试。。
反正刷一刷也没坏处，将就着学学吧
哈希
两数之和
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]目前的思路是直接暴力遍历数组求和，在 python 中就是遍历列表
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1,len(nums)):
res=nums[i]+nums[j]
if (res==target):
return [i,j]https://leetcode.cn/problems/two-sum/solutions/1463966/jian-dan-python-by-chanemo-muld/
由于题目保证仅存在一个答案，故遍历过程中只要存在一个解，即可返回结果
同时，可以注意到，上例的遍历过程存在一定的重复，如遍历了元素 2 之后，结果为 2+7=9，但若再遍历下一个元素 7 时，结果为 7+2=9，二者返回的是相同的数字组合，只不过顺序不同。因此，遍历当前元素时无需从该元素前面的元素中找答案。
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: in
:rtype: List[int]
"""
# 遍历列表
for i in range(len(nums)):
# 计算需要找到的下一个目标数字
res = target-nums[i]
# 遍历剩下的元素，查找是否存在该数字
if res in nums[i+1:]:
# 若存在，返回答案。这里由于是两数之和，可采用.index()方法
# 获得目标元素在nums[i+1:]这个子数组中的索引后，还需加上i+1才是该元素在nums中的索引
return [i, nums[i+1:].index(res)+i+1]数据结构
栈
【模板】栈
思路上就是先实现栈的数据结构，然后根据对应的操作做判断
num = int(input())
class Stack:
def __init__(self) -> None:
self.data = []
def push(self, e):
self.data.append(e)
def pop(self):
return self.data.pop()
def isEmpty(self):
if len(self.data) == 0:
return True
def top(self):
return self.data[-1]
s = Stack()
for i in range(num):
oper = input()
if oper[0:4] == "push":
e = oper.split(" ")
s.push(int(e[1]))
elif oper == "pop":
if s.isEmpty():
print("error")
else:
print(s.pop())
elif oper == "top":
if s.isEmpty():
print("error")
else:
print(s.top())栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
那很有数据结构了
模拟栈思路
首先我们需要模拟一个栈，然后入栈序列里的元素每次入栈前都检测一次栈顶元素能否符合当前出栈序列的元素，由于栈先进后出的特性，一旦匹配到下一步就必须立刻出栈
输入：[1,2,3,4,5],[4,5,3,2,1]
流程：push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()判断是否入栈：模拟栈为空或模拟栈栈顶与出栈序列不匹配
判断是否出栈：模拟栈栈顶与出栈序列匹配
先遍历出栈序列，再遍历入栈序列往模拟栈入栈直到匹配到出栈序列当前指向的元素，此时模拟栈出栈，如果入栈结束没匹配到则返回 False；否则在全部遍历成功结束后返回 True
注意：遍历入栈序列时需要检测当前下标是否超过数组长度，输入样例：[1] [2]
class Solution:
def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
l = len(pushV)
temp = []
j = 0
for i in range(l):
while j<l and (len(temp)==0 or temp[-1]!=popV[i]):
temp.append(pushV[j])
j+=1
if temp[-1] == popV[i]:
temp.pop()
else:
return False
return True原地栈思路
- step 1：用下标n表示栈空间，用j表示出栈序列的下标。
- step 2：遍历每一个待入栈的元素，加入栈顶，即push数组中n的位置，同时增加栈空间的大小，即n的大小。
- step 3：当栈不为空即栈顶n大于等于0，且栈顶等于当前出栈序列，就出栈，同时缩小栈的空间，即减小n。
- step 4：最后若是栈空间大小n为0，代表全部出栈完成，否则不匹配。
class Solution:
def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
#表示栈空间的大小，初始化为0
n = 0
#出栈序列的下标
j = 0
#对于每个待入栈的元素
for num in pushV:
#加入栈顶
pushV[n] = num
#当栈不为空且栈顶等于当前出栈序列
while n >= 0 and pushV[n] == popV[j]:
#出栈，缩小栈空间
j += 1
n -= 1
n += 1
#最后的栈是否为空
return True if n == 0 else False有效括号序列
给出一个仅包含字符’(‘,’)’,’{‘,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，”()”和”()[]{}”都是合法的括号序列，但”(]”和”([)]”不合法。
思路是利用栈结构，每出现一个 (，{，[ 就入栈，每出现一个 ), }, ] 就出栈，如果最后不是空栈就判定为不合法
一开始想用三个栈来判，但是发现([)]是不合法的，那怎么办，写个特判居然过了（
class Stack:
def __init__(self) -> None:
self.data = []
def push(self, e):
self.data.append(e)
def pop(self):
return self.data.pop()
def isEmpty(self):
if len(self.data) == 0:
return True
def top(self):
return self.data[-1]
class Solution:
def isValid(self , s: str) -> bool:
s1 = Stack()
s2 = Stack()
s3 = Stack()
for i in range(len(s)):
if s[i]=="(":
s1.push(s[i])
if s[i]==")":
if not s1.isEmpty():
s1.pop()
else:
return False
if s[i]=="{":
s2.push(s[i])
if s[i]=="}":
if not s2.isEmpty():
s2.pop()
else:
return False
if s[i]=="[":
s3.push(s[i])
if s[i]=="]":
if not s3.isEmpty():
s3.pop()
else:
return False
if s=="([)]":
return False
if s1.isEmpty() and s2.isEmpty() and s3.isEmpty():
return True
else:
return False正解
class Solution:
def isValid(self , s: str) -> bool:
#辅助栈
st = []
#遍历字符串
for i, char in enumerate(s):
#遇到左小括号
if char == '(':
#期待遇到右小括号
st.append(')')
#遇到左中括号
elif char == '[':
#期待遇到右中括号
st.append(']')
#遇到左大括号
elif char == '{':
#期待遇到右大括号
st.append('}')
#必须有左括号的情况下才能遇到右括号
elif(len(st) == 0):
return False
#右括号匹配则弹出
elif(st[-1] == char):
st.pop()
#栈中是否还有元素
return len(st) == 0 逆波兰表达式求值
给定一个逆波兰表达式，求表达式的值。
逆波兰表达式：https://zhuanlan.zhihu.com/p/357982040
对于逆波兰表达式1 2 3 4 * - 5 / + 6 +，先找到第一个符号，抽出符号前的两个数字并计算
- 找到符号
*, 进行计算3 * 4 = 12, 当前表达式为1 2 12 - 5 / + 6 + - 找到符号
-, 进行计算2 - 12 = -10, 当前表达式为1 -10 5 / + 6 + - 找到符号
/, 进行计算-10 / 5 = -2, 当前表达式为1 -2 + 6 + - 找到符号
+, 进行计算1 + -2 = -1, 当前表达式为-1 6 + - 找到符号
+, 进行计算-1 + 6 = 5, 得到结果为5
思路：
将数值元素依次加入栈中，如果遇到符号，则将栈中的最后两个数值出栈，注意先后顺序，先出栈的在计算时处于符号之后，后出栈的数值在计算时处于符号之前。计算完成后将得到的数值入栈。最后，数值栈中仅保留一个数值元素，这个就是计算结果。
注意字符串与整型的转换
class Solution:
def evalRPN(self , tokens: List[str]) -> int:
s = []
for token in tokens:
if token not in "+-*/":
s.append(int(token))
else:
b = int(s.pop())
a = int(s.pop())
if token == "+":
s.append(a+b)
elif token == "-":
s.append(a-b)
elif token == "*":
s.append(a*b)
elif token == "/":
s.append(a/b)
return s[0]点击消除
牛牛拿到了一个字符串。
他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串”abbc”点击后可以生成”ac”。
但相同而不相邻、不相同的相邻字母都是不可以被消除的。
牛牛想把字符串变得尽可能短。他想知道，当他点击了足够多次之后，字符串的最终形态是什么？
思路：
创建一个模拟栈，把字符串依次入栈，如果将要入栈的字母与栈顶字母相同，那么就把栈顶字母出栈
判断最后的结果，如果是空栈则返回0，否则把列表转换为字符串
st = input()
s = []
for char in st:
if len(s)==0:
s.append(char)
elif s[-1]==char:
s.pop()
else:
s.append(char)
if len(s)==0:
print(0)
else:
print("".join(s))表达式求值
请写一个整数计算器，支持加减乘三种运算和括号。
输入是一个字符串🤔
eval 秒了😋
class Solution:
def solve(self , s: str) -> int:
return eval(s)目前的思路是开两个栈，一个存放数字，另一个存放运算符
遇到 ) 时运算符栈依次弹出，直到遇到 (
每弹出一个运算符，数字栈就弹出两个数字，运算的结果入栈
于是目前写出来的代码只能只能支持加减法和括号，遇到乘法优先级就没法处理。。
def solve(s):
stack1 = []
stack2 = []
num = 0
for i in range(len(s)):
if s[i] in "0123456789":
num = num * 10 + int(s[i])
if s[i] not in "0123456789" or i == len(s) - 1:
if num != 0 or s[i - 1] == '0':
if s[i-2]=="-":
stack2.append(-1*num)
else:
stack2.append(num)
num = 0
if s[i] in "+-*()":
stack1.append(s[i])
if s[i] == ")":
while stack1[-1] != "(":
sign = stack1.pop()
if sign == "+" or sign == "-":
temp2 = stack2.pop()
temp1 = stack2.pop()
stack2.append(temp1 + temp2)
if sign == "*":
temp2 = stack2.pop()
temp1 = stack2.pop()
stack2.append(temp1 * temp2)
stack1.pop()
while len(stack1) and len(stack2):
sign = stack1.pop()
if sign == "+" or sign == "-":
temp2 = stack2.pop()
temp1 = stack2.pop()
stack2.append(temp1 + temp2)
if sign == "*":
temp2 = stack2.pop()
temp1 = stack2.pop()
stack2.append(temp1 * temp2)
print(stack2)
solve("3-2+1*(2+(33+4)*3)+8")逆波兰表达式解
还有一种办法，直接把字符串转换成逆波兰表达式，然后照前面题目的方法求值即可
def solve(s):
'''假设 s 是一个仅有数字和运算符号(包含括号)的有效中缀表达式'''
stack1, stack2, prev = [], [], ''
# 符号优先级(栈中最后一位与当前符号进行比较)
symbol_table = {
"+": {"+": '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>'},
"-": {"+": '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>'},
"*": {"+": '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>'},
"/": {"+": '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>'},
"(": {"+": '<', '-': '<', '*': '<', '/': '<', '(': '<', ')': '='},
")": {"+": ' ', '-': ' ', '*': '', '/': '', '(': ' ', ')': ' '},
}
for value in s:
if value not in '+-*/()': # 是数字
if prev not in '+-*/()': # 是连续的数字
stack2.append(stack2.pop() * 10 + int(value))
else:
stack2.append(int(value))
else:
while True: # 在栈中可能有多个优先级更高的符号, 需要遍历
if len(stack1) == 0 or symbol_table[stack1[-1]][value] == '<': # 当前符号优先级更高, 加入栈
stack1.append(value)
break
elif stack1[symbol_table[-1]][value] == '=': # 结束符遇到了结束符
stack1.pop()
break
elif stack1[stack1[-1]][value] == '>': # 栈中优先级更高, 可计算
stack2.append(stack1.pop())
prev = value
for sign in stack1: # 符号栈中可能会剩余一个符号, 直接加入
stack2.append(stack1.pop())
for token in tokens:
if token not in "+-*/":
stack2.append(int(token))
else:
b = int(stack2.pop())
a = int(stack2.pop())
if token == "+":
stack2.append(a+b)
elif token == "-":
stack2.append(a-b)
elif token == "*":
stack2.append(a*b)
elif token == "/":
stack2.append(a/b)
return stack2[0]
if __name__ == "__main__":
print(solve('1+(2-3*4)/5+6'))官方解
需要处理的问题：
运算优先级：减法可视为加一个相反数；那么就剩乘法和加法，优先处理乘法，把前一个数和后一个相乘；加法就把这些数字存起来，等乘法处理完再相加
括号：看作一个新的表达式（子问题），递归求解
遇到左括号进入递归，遇到右括号退出这个递归，返回括号内部的计算结果
方法：
step 1：使用栈辅助处理优先级，默认符号为加号。
step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为 int 型数字。
s = "1324-1+32+1" num = 0 stack = [] i = 0 while i < len(s): if s[i] == " ": i += 1 continue if s[i] in "0123456789": num = num * 10 + int(s[i]) if s[i] not in "0123456789" or i == len(s) - 1: stack.append(num) num = 0 i += 1 print(stack)step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
step 4：当遇到符号的时候如果是 +，得到的数字正常入栈，如果是 -，则将其相反数入栈，如果是 *，则将栈中内容弹出与后一个元素相乘再入栈。
step 5：最后将栈中剩余的所有元素，进行一次全部相加。
开一个栈是为了处理优先级
class Solution:
def solve(self , s ):
s = s.strip()
stack = []
res = 0
num = 0
sign = '+'
index = 0
while index < len(s):
if s[index] == ' ':
index += 1
continue
# 遇到左括号
if s[index] == '(':
end = index + 1
lens = 1
while lens > 0:
if s[end] == '(':
lens += 1
if s[end] == ')':
lens -= 1
end += 1
#将括号视为子问题进入递归
num = self.solve(s[index + 1: end - 1])
index = end - 1
continue
#字符数字转换成int数字
if '0' <= s[index] <= '9':
num = num * 10 + int(s[index])
#根据符号运算
if not '0' <= s[index] <= '9' or index == len(s) - 1:
#加
if sign == '+':
stack.append(num)
#减，加相反数
elif sign == '-':
stack.append(-1 * num)
#乘优先计算
elif sign == '*':
stack.append(stack.pop() * num)
num = 0
sign = s[index]
index += 1
#栈中元素相加
while stack:
res += stack.pop()
return res没看懂这里的优先级处理
队列
【模板】队列
请你实现一个队列。
操作：
push x：将 x 加入队尾，保证 x 为 int 型整数。
pop：输出队首，并让队首出队
front：输出队首：队首不出队
先进先出
仿照栈，写一个队列的数据结构，python 的 pop 可以指定索引移出列表
class Queue:
def __init__(self) -> None:
self.data = []
def push(self, e):
self.data.append(e)
def pop(self):
return self.data.pop(0)
def front(self):
return self.data[0]
def isEmpty(self):
if len(self.data) == 0:
return True
q = Queue()
num = int(input())
for _ in range(num):
oper = input()
if oper[0:4]=="push":
e = oper.split(" ")
q.push(int(e[1]))
elif oper == "pop":
if q.isEmpty():
print("error")
else:
print(q.pop())
elif oper == "front":
if q.isEmpty():
print("error")
else:
print(q.front())然后会惊讶地发现在 10w 次操作那里 TLE 了，优化了半天
class Queue:
def __init__(self):
self.data = []
def push(self, e):
self.data.append(int(e))
def pop(self):
return self.data.pop(0)
def front(self):
return self.data[0]
def size(self):
return len(self.data)
q = Queue()
num = input()
for _ in range(int(num)):
o = input()
if o.split()[0] == "push":
e = o.split()[1]
q.push(e)
if o == "pop":
if q.size() == 0:
print("error")
else:
print(q.pop())
if o == "front":
if q.size() == 0:
print("error")
else:
print(q.front())有概率过，但是不多
不如 pypy3 交掉
【模板】循环队列
请你实现一个循环队列，该循环队列可利用的空间大小等于 n 个int型变量的大小。
在上面的基础上，返回队列长度做一个判断即可
class Cirque:
def __init__(self) -> None:
self.data = []
def push(self, e):
self.data.append(e)
def pop(self):
return self.data.pop(0)
def front(self):
return self.data[0]
def size(self):
return len(self.data)
q = Cirque()
m = input().split()
length = int(m[0])
num = int(m[1])
for _ in range(num):
oper = input()
if oper[0:4] == "push":
e = oper.split(" ")
if q.size() == length:
print("full")
else:
q.push(int(e[1]))
elif oper == "pop":
if q.size() == 0:
print("empty")
else:
print(q.pop())
elif oper == "front":
if q.size() == 0:
print("empty")
else:
print(q.front())链表
【模板】链表
请你实现一个链表。
insert x y：将y加入链表，插入在第一个值x的结点之前。若链表中不存在值为x的结点，则插入在链表末尾。保证x,y为int型整数。
delete x：删除链表中第一个值为x的结点。若不存在值为x的结点，则不删除。
num = int(input())
class linklist:
def __init__(self):
self.items = []
def insert(self,x,y):
if x in self.items:
loc = self.items.index(x)
self.items.insert(loc,y)
else:
self.items.append(y)
def delete(self,x):
if x in self.items:
loc = self.items.index(x)
self.items.pop(loc)
def size(self):
return len(self.items)
def output(self):
for i in range(self.size()):
print(self.items[i],end=' ')
s = linklist()
for i in range(num):
o = input()
case = o.split()[0]
if case == "insert":
x = int(o.split()[1])
y = int(o.split()[2])
s.insert(x,y)
elif case == "delete" and not s.size() == 0:
x = int(o.split()[1])
s.delete(x)
if s.size() == 0:
print("NULL")
else:
s.output()没用到指针也叫链表么。。