LeetCode 第十二天 huawei测试准备 python
以下题目来源LeetCode
1094. 拼车
车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
class Solution:def carPooling(self, trips: List[List[int]], capacity: int) -> bool:res=[0]*1000for i in range(len(trips)):numPassengers, from_, to=trips[i]for j in range(from_,to):res[j]=res[j]+numPassengersif res[j]>capacity:return Falsereturn True
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
class Solution:def maxProfit(self, prices: List[int]) -> int:#dp[i][0]表示第i天持有股票的最大现金 dp[i][0]表示第i天不持有股票的现金#递推关系 dp[i][0]=max(dp[i-1][0],-price[i]dp=[[0]*2 for _ in range(len(prices))]dp[0][0]=-prices[0]dp[0][1]=0for i in range(1,len(prices)):dp[i][0]=max(dp[i-1][0],-prices[i])dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])return dp[-1][1]122. 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
class Solution:def maxProfit(self, prices: List[int]) -> int:#dp[i][0]表示第i天持有股票的最大现金 dp[i][0]表示第i天不持有股票的现金#递推关系 dp[i][0]=max(dp[i-1][0],dp[i-1][1]-price[i])#dp[i][1]=max(dp[i-1][1],dp[i-1][0]+price[i])#初始化dp[0][0]=-price dp[0][1]=0dp=[[0]*2 for _ in range(len(prices))]dp[0][0]=-prices[0]dp[0][1]=0for i in range(1,len(prices)):dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])return dp[-1][1]
拓扑排序
210. 课程表 II
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
一个队列辅助实现拓扑排序
class Solution:def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:edges = collections.defaultdict(list) # 存储每个节点的入度indeg = [0] * numCoursesres=[]for after,pre in prerequisites:edges[pre].append(after)indeg[after]=indeg[after]+1q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])while q:temp=q.popleft()res.append(temp)for i in edges[temp]:indeg[i]=indeg[i]-1if indeg[i]==0:q.append(i)if len(res)!=numCourses:res= []return res5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
class Solution:def longestPalindrome(self, s: str) -> str:#dp[i][j] i到j是回文字# 递推公式 if s[i-1]==s[j+1]： dp[i-1][j+1]=dp[i][j] && True#if s[i-1]==s[j+1] : 判断只加左边或者只加右边是不是回文字dp=[[False]*(len(s)+1) for _ in range(len(s)+1)]max_len=0res=''for i in range (len(s)-1,-1,-1):for j in range(i,len(s)):if s[i]==s[j]:if j-i<2:dp[i][j]=Trueelse:dp[i][j]=dp[i+1][j-1]if dp[i][j]:if j+1-i>max_len:max_len=j+1-i res=s[i:j+1]return res
20. 有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
class Solution:def isValid(self, s: str) -> bool:stack=[-1]kuohao={')':'(','}':'{',']':'['}for i in s:if i in ['[','{','(']:stack.append(i)else:left_true=kuohao[i]if stack[-1]==left_true:stack.pop()else:stack.append(i)if len(stack)==1:return True else:return False
43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
class Solution:def multiply(self, num1: str, num2: str) -> str:def str_to_num(s):count=0num_=0for i in range(len(s)-1,-1,-1):num_ =num_+ int(s[i])*(10count) count=count+1return num_# print(str_to_num(num1),str_to_num(num2))return str(str_to_num(num1)*str_to_num(num2))
93. 复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
我要去跑步了 明天再写吧
