王道408DS算法总结
顺序存储结构
一种较为万能的方法：空间换时间
P.18-10 逆置算法 O(2/n) O(1)
P.18-11 二分查找 O(log2n) O(1) 类比力扣非等长序列
P.18-12 寻找众数，摩尔投票，遍历计数法 O(n) O(1)
P.18-13 空间换时间，统计法 O(n) O(n) 力扣原题：缺失的第一个正数
P.18-14 三元组找最短距离，轮流遍历法（三指针） O(n) O(1)
链式存储结构
P.40-1/2 对于不带头结点的删除指定值，指针的引用或二级指针的删除只需要操作两个结点，可以用于递归方法（每次传入局部变量）；循环方法只能先让首个元素不是删除的元素，再用操作三结点法
P.40-3 利用递归特性实现栈的思想，为了判空加了额外的判断
P.40-4 删除带头结点最小值，操作三结点法，存储好最小值结点和其前驱即可，最后判断完最小后释放
P.40-5 头结点逆置，O(1)空间，可以用头插法在首部后面每次插入值，也可以操作三结点法（要保留后继结点的信息）
P.40-6 带头结点直接插入法排序链表（或者用空间换时间，再排序）：在左边有序链表中找到第一个比p大的结点的前驱，操作三结点指向，继续找下一个元素
栈、队列和数组
P70-3-2 遍历计数法 O(n) O(1)
P70-4 与力扣回文数判断中转字符的算法类似。
思想：加入栈的思想，全部压入栈再输出，看输出序列和原序列是否一致，当然这样需要扫描两次。
改进：压入一半，再从栈顶输出元素和剩下一半比较。
细节处理：奇数个数直接跳过中间数，然后开始扫描另一半，如果相等就继续出栈，不相等不出栈，这样最后栈空就是对称的。
P70-5 注意栈满条件，入栈看栈满，出栈看栈空
Leetcode算法总结
1.两数之和 哈希表；利用结构体存储原位置的方法进行快排，操作双指针 O(log2n) O(n)
2.盛水最多的容器 双指针法 O(n) O(1)
3.下一个排列 找规律，从后向前找升序，逆置法 O(n) O(1)
4.搜索旋转数组 二分法查找 O(log2n) O(1)
5.查找非降序数组指定元素范围 难点：查找第一个大于等于target 的下标 O(log2n) O(1)
6.搜索插入位置 难点：二分法查找失败时找到插入的位置
7.课程表问题 优先队列+贪心O(nlogn) O(n) hard
这里有n门不同的在线课程，按从1到n编号。给你一个数组courses ，其中courses[i] = [durationi, lastDayi]表示第i门课将会持续上 durationi天课，并且必须在不晚于lastDayi的时候完成。
你的学期从第1天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。
简单的数学证明得到先做后面一定也可以先做前面，先做前面不一定能先做后面，所以将先做前面设为最优解。
根据最晚期限排序后，依次添加新的课程，如果加进去时间够新课程的时限就添加进队列，如果不行就找之前最大耗时的课程和新课程耗时对比，如果新课程更小则会替换，相当于整体向前。
class Solution:
def scheduleCourse(self, courses: List[List[int]]) -> int:# 返回整型
courses.sort(key=lambda c:c[1])# 创建简单的、不需要命名的小型函数。它通常用于函数式编程，sort期望返回一个key，这里传递参数c返回c[1]
q = list()# 创建空列表
total = 0
for ti,di in courses:
if total + ti <= di:# 增加一门课程不会超过它的限时
total += ti
# Python 默认是小根堆
# 堆中的每个节点的值都小于或等于其子节点的值。
# 堆是一棵完全二叉树，通常使用数组或列表来表示。
# 升序排列，因为小根堆会将较小的值放在顶部
heapq.heappush(q, -ti)
elif q and -q[0]>ti:# 如果最大的那个时长超过所添加的课程的时长则会被替换
total -= -q[0] - ti
heapq.heappop(q)
heapq.heappush(q, -ti)
return len(q)8.检查骑士巡视方案 空间换时间O(n2) O(n2) easy
骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。
给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。
如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。
注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。
class Solution:
def checkValidGrid(self, grid: List[List[int]]) -> bool:
if grid[0][0] != 0:
return False
rows, cols = len(grid), len(grid[0]) # 获取行数和列数
q = [0] * (rows * cols)
for a in range(rows):
for b in range(cols):
q[grid[a][b]]=a*rows+b # 这里存放行列坐标也可以
for i in q:
if i>0:
x = abs(q[i-1]//rows-q[i]//rows)
y = abs(q[i]%rows-q[i-1]%rows)
if not ((x ==1 and y==2) or(x ==2 and y==1)):
return False
return True9.可以攻击国王的往后 哈希映射O(n) O(1) easy
在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。
给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。
class Solution:
def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
# 站在国王视角，匹配每一个王后，建立国王8个方向的哈希映射，每个方向只保留最近的那个王后
hashmap = defaultdict(lambda: (None, inf))
for qx,qy in queens:
kx, ky = king
# 用来判断方向
qdx = 0
qdy = 0
if qx - kx > 0:
qdx = 1
if qx - kx < 0:
qdx = -1
if qy - ky > 0:
qdy = 1
if qy - ky < 0:
qdy = -1
if qx == kx or qy == ky or abs(qx-kx) == abs(qy-ky):
if hashmap[(qdx,qdy)][1] > abs(qx-kx)+abs(qy-ky):
# 只判断符合条件的最小距离，坐标存储在hashmap[(qdx,qdy)][0]
hashmap[(qdx,qdy)] = ([qx,qy],abs(qx-kx)+abs(qy-ky))
return [ans[0] for ans in hashmap.values()] # 返回的是队列10.宝石补给 O(m+n) O(1) 练习python遍历语法 easy
欢迎各位勇者来到力扣新手村，在开始试炼之前，请各位勇者先进行「宝石补给」。
每位勇者初始都拥有一些能量宝石， gem[i] 表示第 i 位勇者的宝石数量。现在这些勇者们进行了一系列的赠送，operations[j] = [x, y] 表示在第 j 次的赠送中 第 x 位勇者将自己一半的宝石（需向下取整）赠送给第 y 位勇者。
在完成所有的赠送后，请找到拥有最多宝石的勇者和拥有最少宝石的勇者，并返回他们二者的宝石数量之差。
class Solution:
def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:
for i in range(len(operations)):
change = gem[operations[i][0]]//2
gem[operations[i][0]] -= change
gem[operations[i][1]] += change
max = 0
min = inf
for i in gem:
if i > max:
max = i
if i < min:
min = i
return max -min11.打家劫舍3 动态规划 O(n) O(n) hard
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 *在不触动警报的情况下 ，小偷能够盗取的最高金额* 。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
@cache
def do(node):
if not node:
return 0
ans = node.val
ans += dont(node.left)
ans += dont(node.right)
return ans
@cache
def dont(node):
if not node:
return 0
ans = 0
ans += max(do(node.left),dont(node.left))
ans += max(do(node.right),dont(node.right))
return ans
return max(do(root),dont(root))12.打家劫舍4 O(nlogT) O(1) T 是数组 nums 最大值与最小值之差，二分查找的次数为 O(logT) particularly hard
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。
# 找到k个间隔开的数之和与数组最小值的差的最小值
# 用二分查找去找这个值，这个值一定在min-max之间，每次去试mid索引，然后去匹配k个数出来，计算count值和k比较，符合小于等于k则向左找，说明mid索引大了，大于k向右找
# 相当于限制小偷所能偷得的最小金额，然后二分查找最小金额组合里的最大值，
# 如果找到了这个最大值，小于等于这个值是刚好能凑够k个数的，即count=k，
# 而最后找到的是这个值在range(min,max)里的索引，而因为最小金额组合里的大值和小值之差
# 刚好可以用这个索引来表示（起始就是小值），所以最后的总结果只要用这个索引加上小值就可以了
from bisect import bisect_left
from typing import List
class Solution:
def minCapability(self, nums: List[int], k: int) -> int:
def keyq(y:int)->int:
visited = False
count = 0
for i in nums:
if i<=y and not visited:
visited = True
count += 1
else:
visited = False
return count
return bisect_left(range(min(nums),max(nums)),k,key=keyq) + min(nums)附python3.10新标准库bisect_left的含key用法：
from bisect import bisect_left
def q(y : int) -> int:
print("y=",y)
return y
num0=[4,4,4,5,6,7,9,14]
bisect_left(range(min(num0),max(num0)), 10, key = q)
# 二分查找，key的作用就是给q传入mid索引位置上的值，然后用返回的值和k=10比较
# range只保留num0里4(0)-13(9)的部分，但是初始min=0，max=10
# 相当于如下的伪代码：
# while left<right:
# mid=(left+right)//2
# k>key left=mid+1向右
# k<=key right=mid向左
# 返回第一个大于等于k位置的索引13.股票价格跨度 hard O(n)，其中 n 为调用 next 函数的次数 O(n) 单调栈
from math import inf
class StockSpanner:
def __init__(self):
self.stack=[(0,inf)] # 记录权重和价格
def next(self, price: int) -> int:
weight=1
while price>=self.stack[-1][1]: # -1表示栈顶
weight+=self.stack[-1][0] # 把删掉的权重全加起来再加上自己的1
self.stack.pop()
self.stack.append((weight,price))
return weight
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)14.股票价格波动 hard O(logn) O(n)
给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的 价格 。
不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录 更正 前一条错误的记录。
请你设计一个算法，实现：
- 更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将 更正 之前的错误价格。
- 找到当前记录里 最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
- 找到当前记录里股票的 最高价格 。
- 找到当前记录里股票的 最低价格 。
from sortedcontainers import SortedList
class StockPrice:
def __init__(self):
# 初始化一个有序股价列表，用来寻找最大和最小值，因为一旦替换了最大股价，就很难找到次小值
self.sortlist = SortedList()
# 初始化一个时间股价隐射字典
self.timePriceMap = {}
# 初始化一个当前股价所在时间
self.currenttime = 0
def update(self, timestamp: int, price: int) -> None:
self.currenttime = max(timestamp,self.currenttime)
# 将股价进有序列表
self.sortlist.add(price)
# 将当前的股票信息存入哈希表
if timestamp in self.timePriceMap:
self.sortlist.discard(self.timePriceMap[timestamp])
self.timePriceMap[timestamp] = price
def current(self) -> int:
# 将当前最新的股票价格输出
return self.timePriceMap[self.currenttime]
def maximum(self) -> int:
return self.sortlist[-1]
def minimum(self) -> int:
return self.sortlist[0]
# Your StockPrice object will be instantiated and called as such:
# obj = StockPrice()
# obj.update(timestamp,price)
# param_2 = obj.current()
# param_3 = obj.maximum()
# param_4 = obj.minimum()15.最小和分割 easy O(lognum⋅loglognum) O(lognum)
给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：
num1和num2直接连起来，得到num各数位的一个排列。换句话说，num1和num2中所有数字出现的次数之和等于num中所有数字出现的次数。num1和num2可以包含前导 0 。
请你返回 num1 和 num2 可以得到的和的 最小 值。
class Solution:
def splitNum(self, num: int) -> int:
# 先转为字符串，然后排序，每隔一个取一个数。这样取两个数出来
stringnum = str(num)
sortstrnumlist = sorted(stringnum) # 得到字符列表['1', '2', '3', '4', '5']
sortstrnum = "".join(sortstrnumlist) # 使用空分隔符连接
num1 = int(sortstrnum[::2]) # 起始位置:结束位置:步长
num2 = int(sortstrnum[1::2])
return num1+num216.移动机器人 hard O(logn) O(1)
有一些机器人分布在一条无限长的数轴上，他们初始坐标用一个下标从 0 开始的整数数组 nums 表示。当你给机器人下达命令时，它们以每秒钟一单位的速度开始移动。
给你一个字符串 s ，每个字符按顺序分别表示每个机器人移动的方向。'L' 表示机器人往左或者数轴的负方向移动，'R' 表示机器人往右或者数轴的正方向移动。
当两个机器人相撞时，它们开始沿着原本相反的方向移动。
请你返回指令重复执行 d 秒后，所有机器人之间两两距离之和。由于答案可能很大，请你将答案对 $10^9 + 7$ 取余后返回。
解答：针对排序后的数组进行求和，公式为$(n-i-1)x_i-(i+1)x_{i+1},i\in [0,n-2]$
class Solution:
def sumDistance(self, nums: List[int], s: str, d: int) -> int:
# 由于碰撞相当于两个机器人交换位置，所以可以忽略碰撞，让机器人正常行进，然后在最后排序整个位置数组即可
mod = 10**9 + 7
for i,_ in enumerate(nums): # 使用zip进行一起遍历，enumerate可以获取索引与值
if s[i] == "L":
nums[i]-=d
else:
nums[i]+=d
nums = sorted(nums)
length = 0
for i,_ in enumerate(nums):
#$(n-i)x_i-ix_{i+1}$
if i<len(nums)-1:
length += (len(nums)-i-1)*nums[i]-(i+1)*nums[i+1]
return abs(length) % mod17.奖励最顶尖的K名学生 easy O(logn) O(n)
给你两个字符串数组 positive_feedback 和 negative_feedback ，分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。
一开始，每位学生分数为 0 。每个正面的单词会给学生的分数 **加 **3 分，每个负面的词会给学生的分数 **减 ** 1 分。
给你 n 个学生的评语，用一个下标从 0 开始的字符串数组 report 和一个下标从 0 开始的整数数组 student_id 表示，其中 student_id[i] 表示这名学生的 ID ，这名学生的评语是 report[i] 。每名学生的 ID 互不相同 。
给你一个整数 k ，请你返回按照得分 从高到低 最顶尖的 k 名学生。如果有多名学生分数相同，ID 越小排名越前。
class Solution:
def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:
# 空间换时间，存储正负面词汇的字典映射为一个分数
# 这样只需要遍历一次report，查询是否在字典里以及映射的分数
# 最后将ID与得分存储在二元组中，再根据不同ID的得分进行排序
words = {}
for s in positive_feedback:
words[s] = 3
for s in negative_feedback:
words[s] = -1
top = []
score = 0
for s,i in zip(report,student_id):
# text.split(", ", 2) # 用逗号和空格分割，最多分成3部分
for w in s.split(): # 默认空格
if w in words:
score += words[w]
top.append([-score,i])
score = 0
top.sort() # 针对第一个元素递增排序
result = []
count = 0
for _,i in top:
result.append(i)
count += 1
if count == k:
break
return result18.找出数组的串联值 easy O(nlogN) O(logN) n表示nums长度，N表示nums里最大值，logN表示最大值的位数（由于要转成字符串，相当于字符串长度）
给你一个下标从 0 开始的整数数组 nums 。
现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。
- 例如，
15和49的串联是1549。
nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：
- 如果
nums中存在不止一个数字，分别选中nums中的第一个元素和最后一个元素，将二者串联得到的值加到nums的 串联值 上，然后从nums中删除第一个和最后一个元素。 - 如果仅存在一个元素，则将该元素的值加到
nums的串联值上，然后删除这个元素。
返回执行完所有操作后 nums 的串联值。
class Solution:
def findTheArrayConcVal(self, nums: List[int]) -> int:
# 首尾同时向中间遍历
l = len(nums)
i = 0
j = l-1
r = 0
while i < j and i < l and j >= 0:
string = str(nums[i]) + str(nums[j])
r += int(string)
i += 1
j -= 1
if i == j:
r += nums[i]
return r19.避免洪水泛滥 hard O(nlogn) O(n)
你的国家有无数个湖泊，所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的，那么它就会装满水。如果第 n 个湖泊下雨前是 满的 ，这个湖泊会发生 洪水 。你的目标是避免任意一个湖泊发生洪水。
给你一个整数数组 rains ，其中：
rains[i] > 0表示第i天时，第rains[i]个湖泊会下雨。rains[i] == 0表示第i天没有湖泊会下雨，你可以选择 一个 湖泊并 抽干 这个湖泊的水。
请返回一个数组 ans ，满足：
ans.length == rains.length- 如果
rains[i] > 0，那么ans[i] == -1。 - 如果
rains[i] == 0，ans[i]是你第i天选择抽干的湖泊。
如果有多种可行解，请返回它们中的 任意一个 。如果没办法阻止洪水，请返回一个 空的数组 。
请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊，那么将无事发生。
from sortedcontainers import SortedList
class Solution:
def avoidFlood(self, rains: List[int]) -> List[int]:
# 记录雨天，扫描湖泊雨天信息，定位抽水的日子，找到之前同一个湖泊的下雨天，二分查找最接近这个下雨天的晴天，找不到返回空，找到记录ans
# 初始化湖泊雨天信息
lake_day = {}
sunday = SortedList()
ans = [1] * len(rains)
for day,lake in enumerate(rains):
if lake == 0:
sunday.add(day)
else:
if lake not in lake_day:
lake_day[lake] = day
else:# 二分查找
r = sunday.bisect(lake_day[lake])# 有序列表才可以二分查找
if r == len(sunday):
return []
else:
ans[sunday[r]] = lake
sunday.discard(sunday[r])
# 泄洪后要将lake_day信息更新
lake_day[lake] = day
ans[day] = -1
return ans20.只出现一次的数字 hard O(n) O(1) 学习位运算（异或）
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 做所有元素的二进制位运算，或者是异或运算，最终相同的部分会抵消为0，只保留唯一的一个
ans = 0
for i in nums:
ans = ans ^ i
return ans21.只出现一次的数字2 particularly hard O(n) O(1)
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。 请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 核心思想：按位运算，将所有位求和除以3，余数是1就出1，余数是0就出0
# 由于是除以3，所以只会存在余数1余数2余数3的三种状态，其中余数2必不可能是数组结束的位置，只是一个中间态所以不需要出东西，而且什么时候出不用我们管，我们只管算。
# 采用时序逻辑电路的设计思想，记录00，01，10三种余数状态，刚好00和01的第二位可以表示出0还是1，所以基于此设计真值表：
# 余0得0之后是余0，如果刚好可以出的话就出0
# 余0得1之后是余1，如果刚好可以出的话就出1
# 余1得0之后是余1，如果刚好可以出的话就出1
# 余1得1之后是余2，中间态
# 余2得0之后是余2，中间态
# 余2得1之后是余0，如果刚好可以出的话就出0
# 构造卡诺图，得出计算公式
a = 0
b = 0
for num in nums:
na = (~a&b&num)|(a&~b&~num)
nb = (~a&~b&num)|(~a&b&~num)
a = na
b = nb
return b22.只出现一次的数字3 hard O(n) O(1)
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
# 首先只要找到第一个会出现异或为1的二进制位，两个结果数在这个位上必然会出现不一样，按照这个位是0和1分为两个类别，然后单独对每个类别进行异或
# 负数的二进制是补码，反码加一
# 反码和原码做与运算只保留原码从右往左第一次出现1的位
ans = 0
result1 = 0
result2 = 0
for a in nums:
ans ^= a
l = ans & -ans
for a in nums:
if l & a:
result1 ^= a
else:
result2 ^= a
return [result1, result2]23.统计无向图中无法互相到达点对数 hard O(m+n)，其中 m 是边数 O(m+n)
给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 $edges[i] = [a_i, b_i]$ 表示节点 $a_i$ 和 $b_i$ 之间有一条 无向 边。
请你返回 无法互相到达 的不同 点对数目 。
/**
* @param {number} n
* @param {number[][]} edges
* @return {number}
*/
// 事先将边存储在矩阵里，一条边存储两次。然后使用深读优先遍历对矩阵进行遍历，记录没有的遍历的边数
var countPairs = function(n, edges) {
//写一个带记录各个顶点最大深读的深读遍历，记录连通的顶点数
const graph = new Array(n).fill(0).map(() => new Array());//用映射来表示邻接表
for (let i = 0; i < edges.length; i++) {
let r = edges[i];
graph[r[0]].push(r[1]);
graph[r[1]].push(r[0]);
}
const visited = new Array(n).fill(false);
const dfs = function(x) {
let count = 1;
visited[x] = true;
for(const i of graph[x]){
if(!visited[i]){
count += dfs(i);
}
}
return count;
}
re = 0;
for(const i in graph){
sum = 0;
if(!visited[i]){
sum = dfs(i);
re += sum*(sum-1)/2
}
}
//用所有结点最大可能的连通数-已有的连通数
return n*(n-1)/2-re;
};24.掷骰子等于目标和的方法数 hard O(n*k*target) O(n*target)
这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n , k 和 target ，返回可能的方式(从总共 $k^n$ 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。
答案可能很大，你需要对 $10^9 + 7$ 取模 。
//复习c++二维vector创建
//对于这种题，最好采用递推的动态规划进行处理，先确定最后一个骰子取1-k的哪个数，取一个数就会让前面n-1个骰子的方案的和发生变化，所以一共要计算k次和，然后每次和再各自计算
//其次处理好边界条件即可
class Solution {
private:
static constexpr int mod = 1000000007;
public:
int numRollsToTarget(int n, int k, int target) {
vector<vector<int>>f(n+1, vector<int>(target+1));
f[0][0]=1;
for(int a=1;a<=n;a++)
for(int b=0;b<=target;b++)
for(int x=1;x<=k;x++)
{
if(b-x>=0)
f[a][b]=(f[a][b]+f[a-1][b-x])%mod;//f表示第a个骰子的和为b的方案数，最后一次选了x，第a-1个骰子的和就要变成b-x
}
return f[n][target];
}
};25.参加会议的最多员工数 particularly hard O(n) O(n) 基环内向树、拓扑排序、双端队列
一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。
员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。
给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
Solution.
class Solution:
def maximumInvitations(self, favorite: List[int]) -> int:
n = len(favorite)
# 统计入度，便于进行拓扑排序
indeg = [0] * n
for i in range(n):
indeg[favorite[i]] += 1
used = [False] * n
f = [1] * n
# 创建一个双端队列（deque），其中包含了那些入度为零的节点的索引
q = deque(i for i in range(n) if indeg[i] == 0)
while q:
# 左端出队
u = q.popleft()
used[u] = True
# v代表下u指向的节点
v = favorite[u]
# 状态转移
# 更新到v节点经过的点数，一般是加1
f[v] = max(f[v], f[u] + 1)
# v的入度减1
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
# 最终会记录和环连接的点，包括环上的那个连接处的点的f值，但环上的点不会被访问
# ring 表示最大的环的大小
# total 表示所有环大小为 2 的「基环内向树」上的最长的「双向游走」路径之和
ring = total = 0
for i in range(n):
if not used[i]:# 只有环上的点会被访问
j = favorite[i]
# favorite[favorite[i]] = i 说明环的大小为 2，环为2的两个节点一定和外面可能有关连，也就是计算好了f值的
if favorite[j] == i:
total += f[i] + f[j]
used[i] = used[j] = True
# 否则环的大小至少为 3，我们需要找出环
else:# 记录环的长度
u = i
cnt = 0
while True:
cnt += 1
u = favorite[u]
used[u] = True
if u == i:
break
ring = max(ring, cnt)
return max(ring, total)学习python有向图写法（与本题无关）
# python采用字典存储这种数据结构，一个字典graph["A"].append("B")代表添加顶点
# graph = {
# 'A': ['B', 'C'],
# 'B': ['D'],
# 'C': ['E'],
# 'D': ['F'],
# 'E': [],
# 'F': []
# }
# graph["A"]=[] # 或者从0开始添加
# graph["A"].append(("D"))
# node = "A"
# 获得邻居节点：graph.get(node, [])
# 前提是每个员工都有喜欢的员工26.故障键盘 easy O(n) O(n) 双端队列
你的笔记本键盘存在故障，每当你在上面输入字符 'i' 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。
返回最终笔记本屏幕上输出的字符串。
输入s =”poiinter”
输出”ponter”
预期结果”ponter”
解答：遇到一次i更换一次队头，每次输入都是队尾进
class Solution {
public:
string finalString(string s) {
deque<char> q;
bool head = false;
for(int i=0;i<s.length();i++){
if(s[i]=='i'){
head =!head;
continue;
}
if(!head){
q.push_back(s[i]);
}else{
q.push_front(s[i]);
}
}
string a;
if(!head){
while(!q.empty()){
a.push_back(q.front());
q.pop_front();
}
}else{
while(!q.empty()){
a.push_back(q.back());
q.pop_back();
}
}
return a;
}
};企业算法
1.神策
//给定一个数组arr，表示连续n天的股价，数组下标表示第几天
//指标X：任意两天股价之和-两天的间隔
//如：第3天，价格是10；第4天，价格是30，X=10+30-(4-3)
//要求：返回arr的最大指标X，O(n)
int maxX(int a*,int n)
{
if(a==null||n<2)return -1;
int prebest=a[0];
int ans=0;
for(int i=1;i<n;i++)
{
ans=max(ans,prebest+a[i]-i);
prebest=max(prebest,a[i]+i)
}
return ans;
}
//分成两部分看，因为+永远在-左边，所以保证a(i)+i一直最大，-往前留一个合计值就行，如果还能大就替换掉2.美团
//两个数组AB，长度为n和m，目标是让两个数组变得一样
//操作1：将数组中的某一数a改成b，代价是|b-a|时间
//操作2：将数组中的某一数a删掉，代价是|a|时间
//要求：以最少时间将两个数组变得相同，求出这个代价；1<=n,m<=2000; |Ai|,|Bi|<=10000
//方法：利用左递归，列出所有变动的可能性，最终计算出几种可能性最中小的代价值
//改进：暴力递归变动态规划
int zuo(int a*,int b*,int m,int n,int ai,int bi)
{
if(ai==m&&bi==n)
return 0;//同时走到终点
if(ai!=m&&bi==n)//A还没走完，剩下全删
return a[ai]+zuo(a,b,m,n,ai+1,bi);
if(ai==m&&bi!=n)//B还没走完，剩下全删
return a[ai]+zuo(a,b,m,n,ai,bi+1);
//A和B都没走完
//删ai
int p1=a[ai]+zuo(a,b,m,n,ai+1,bi);
//删bi
int p2=b[bi]+zuo(a,b,m,n,ai,bi+1);
//同时删，因为代价还不如替换所以被忽略
//替换
int p4=abs(a[ai]-b[bi])+zuo(a,b,m,n,ai+1,bi+1);
//ai==bi这种情况不用管，可以包含在p4
return min(p1,min(p2,p4));
}3.美团
//给出三个点的坐标，给出未知点到三个点的曼哈顿距离，求未知点的坐标
//数据值范围是1到50000
//方法选择最小曼哈顿距离的已知点构圆，未知点肯定在圆内，直接遍历
#include <limits.h>
int *find(int a*,int b*,int c*,int ad,int bd,int cd,int n)//给的是所有的数范围1-n
{
int *x1=NULL;
iny r1=INT_MAX;
int *x2=NULL;
}
