目录
- 283. 移动零
- 153. 寻找旋转排序数组中的最小值
- 468. 验证IP地址
- 224. 基本计算器
- 739. 每日温度
- 138. 随机链表的复制
- 47. 全排列 II
- 207. 课程表
- LCR 125. 图书整理 II
283. 移动零
题目链接
Python
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n=len(nums)
i=0
for j in range(n):
if nums[j]!=0:
nums[i],nums[j]=nums[j],nums[i]
i+=1 # i指向0，因为当前数字不为0才前进
153. 寻找旋转排序数组中的最小值
题目链接
Python
class Solution:
def findMin(self, nums: List[int]) -> int:
low,high=0,len(nums)-1
while low<high:
mid=(low+high)//2
# 元素值互不相同
if nums[mid]<nums[high]:
high=mid
else: # nums[mid]>nums[high]:
low=mid+1
return nums[low]
类似题目 33. 搜索旋转排序数组
468. 验证IP地址
题目链接
Python
class Solution:
def validIPAddress(self, queryIP: str) -> str:
def validIPv6(IP_string):
IP_lst = IP_string.split(':')
if len(IP_lst) != 8: # IPv6必须由8个子串组成
return False
for IP in IP_lst:
if not 1 <= len(IP) <= 4: # 每个子串必须小于4个字符
return False
for char in IP:
if not ('0' <= char <= '9' or 'a' <= char <= 'f' or 'A' <= char <= 'F'):
return False
return True
def validIPv4(IP_string):
IP_lst = IP_string.split('.')
if len(IP_lst) != 4: # IPv4必须由4个子串组成
return False
for IP in IP_lst:
if not IP.isdigit() or not 0 <= int(IP) <= 255:
return False
if str(int(IP)) != IP: # 不能有前导0
return False
return True
if queryIP.find(".") != -1:
return 'IPv4' if validIPv4(queryIP) else 'Neither'
else:
return 'IPv6' if validIPv6(queryIP) else 'Neither'
return 'Neither'
224. 基本计算器
题目链接
Python
class Solution:
def calculate(self, s: str) -> int:
ops=[1] # 栈顶元素记录了当前位置所处的每个括号所「共同形成」的符号
sign=1 # 代表「当前」的符号
res=0
n=len(s)
i=0
while i<n:
if s[i]==" ":
i+=1
elif s[i]=="+":
sign=ops[-1]
i+=1
elif s[i]=="-":
sign=-ops[-1]
i+=1
elif s[i]=="(":
ops.append(sign)
i+=1
elif s[i]==")":
ops.pop()
i+=1
else:
num=0
while i<n and s[i].isdigit():
num=num*10+ord(s[i])-ord("0")
i+=1
res+=num*sign
return res
进阶版 227. 基本计算器 II
739. 每日温度
题目链接
Python
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
res=[0]*len(temperatures)
stack=[0]
for i in range(1,len(temperatures)):
if temperatures[stack[-1]]>=temperatures[i]:
stack.append(i)
else:
while stack and temperatures[stack[-1]]<temperatures[i]:
res[stack[-1]]=i-stack[-1]
stack.pop()
stack.append(i)
return res
138. 随机链表的复制
题目链接
Python
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
# 在每个原节点后面创建一个新节点
# 1->1'->2->2'->3->3'
cur=head
while cur:
new_node=Node(cur.val)
new_node.next=cur.next
cur.next=new_node
cur=new_node.next
# 设置新节点的随机结点
cur=head
while cur:
if cur.random:
cur.next.random=cur.random.next
cur=cur.next.next
# 将两个链表分开
dummy=Node(0)
cur=head
pre=dummy
while cur:
pre.next=cur.next
pre=pre.next
cur.next=pre.next
cur=cur.next
return dummy.next
47. 全排列 II
题目链接
建议先做 46. 全排列
Python
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
path=[]
res = []
def backtrack(nums, used):
if len(path)==len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if i>0 and nums[i] == nums[i-1] and used[i-1]==False:
continue
if not used[i]:
path.append(nums[i])
used[i] = True
backtrack(nums, used)
path.pop()
used[i] = False
nums.sort()
used=[False]*len(nums)
backtrack(nums,used)
return res
207. 课程表
题目链接
Python
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# 初始化邻接表
adjacency=[[] for _ in range(numCourses)]
# 初始化每个点的入度
indegrees=[0 for _ in range(numCourses)]
# 遍历prerequisites为邻接表、每个点的入度赋值
for cur,pre in prerequisites:
adjacency[pre].append(cur)
indegrees[cur]+=1
# 将所有入度为0的节点入队
from collections import deque
queue=deque()
for i in range(numCourses):
if indegrees[i]==0:
queue.append(i)
# 使用拓扑排序（依次将队列中入度为0的节点出队）
while queue:
pre=queue.popleft()
numCourses-=1
# 将pre后面的节点cur的入度统统-1
for cur in adjacency[pre]:
indegrees[cur]-=1
if indegrees[cur]==0:
queue.append(cur)
return not numCourses # 有环numCourses非0返回False
# 无环numCourses为0返回True
进阶版 210. 课程表 II
LCR 125. 图书整理 II
题目链接
类似题目 232. 用栈实现队列
Python
class CQueue:
def __init__(self):
self.stack1=[]
self.stack2=[]
def appendTail(self, value: int) -> None:
self.stack1.append(value)
def deleteHead(self) -> int:
if self.stack2:
return self.stack2.pop()
if not self.stack1:
return -1
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()
