本文主要是介绍Dayx6:剑指offer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
队列
- 滑动窗口的最大值 牛客网
给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值.
e.g:输入数组[2, 3, 4, 2, 6, 2, 5, 1]及滑动窗口的大小3,那么一共存在6个滑动窗口，它们的最大值分别为[4, 4, 6, 6, 6, 5]。
分析
(多 practice)–deque()
#两端开口队列
def maxInWindows_2(nums, k):from collections import dequeif len(nums)<k or k<=0: return []res=[]q=deque() #!!!Initialization#1for i in range(len(nums)):if q and i-q[0]+1>k: q.popleft()while q and nums[q[-1]]<=nums[i]: q.pop() #弹出最后进入ele #2q.append(i) #i一定是要插入的 #3#4if i+1>=k: #为了最开始i=0,1,2<k时的处理res.append(nums[q[0]])return res
#基本解法
class Solution:def maxInWindows(self, num, size):count=len(num)-size+1 #滑动窗口个数if len(num)<size or size==0: return [] #!!!特殊conditionres=[]for i in range(count):res.append(max(num[i:i+size]))return res
- n个骰子的点数 AcWing
n个骰子投掷1次，获得的总点数为s.掷出n~6n点分别有多少种掷法?
分析
DP
def numberOfDice(self, n):# 每个地方索引+1都是因为方便计算。因为是从骰子个数和一个骰子的范围都是从 1 开始的。dp=[[0]*(6*n+1) for _ in range(n+1)]dp[0][0]=1for i in range(1,n+1): #i:骰子个数for j in range(i,6*i+1):for k in range(1,min(j,6)+1): #s.t 下面[j-k]>=0 #j:i个总和 k:(i-1)th结果dp[i][j]+=dp[i-1][j-k]return [dp[n][j] for j in range(n,6*n+1)]
#递归--core part
缺点：大量重复运算
ans=0
for i in range(1,7):ans+=self.dfs(n-1.sum-i)- 扑克牌中的顺子 牛客网
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。
2～10为数字本身，A为1，J为11，Q为12，K为13，大小王可以看做任意数字。
假设这副牌中大小王均有两张。
思路清晰最重要
0. 大小王：=0
1 . 将5个数sort()
2… 找到第一个非零值得索引，判断其后是否有对子
3 . 若无对子，再判断是否 最大值-最小值<=4
def isContinuous_2(self, nums):if not nums: return Falsenums.sort()k=0while nums[k]==0: #等价while not nums[k]: ## 找到第一个不为0的元素的索引!!!记忆经典code片段k+=1for i in range(k,len(nums)-1):if nums[i]==nums[i+1]: return Falsereturn nums[-1]-nums[k]<=4- 圆圈中最后剩下的数字 AcWing
0, 1, …, n-1这n个数字(n>0)排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。
求出这个圆圈里剩下的最后一个数字。
分析
def lastRemaining_2(self, n, m):'''递推，最优解 Time:O(n) Space:O(1)'''if n<=0 or m<=0: return -1last =0 # 表示：=1时，只剩一个人那么0就活了for i in range(2,n+1):last =(last+m)% ireturn lastdef lastRemaining_1(self, n, m):"""递归, 可能会爆栈"""if n==1: return 0return (self.lastRemaining(n-1,m)+m) %n
- 股票的最大利润 leetcode 121
一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），计算你所能获取的最大利润。
分析
def maxProfit(self, nums: List[int]) -> int:if not nums: return 0f=0minValue=nums[0]for i in range(1,len(nums)):f=max(f, nums[i]-minValue) #!!!取max~minValue=min(minValue, nums[i])return f
这篇关于Dayx6:剑指offer的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
