记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 11/25 743. 网络延迟时间
- 11/26 3206. 交替组 I
- 11/27 3208. 交替组 II
- 11/28 3250. 单调数组对的数目 I
- 11/29 3251. 单调数组对的数目 II
- 11/30 3232. 判断是否可以赢得数字游戏
- 12/1 51. N 皇后
11/25 743. 网络延迟时间
BFS 当前节点k 遍历k联通的所有节点to 如果能够更新节点to的时间
那么讲节点to加入队列 后续考虑
def networkDelayTime(times, n, k):""":type times: List[List[int]]:type n: int:type k: int:rtype: int"""from collections import defaultdictcost = {}time = defaultdict(list)for i in range(1,n+1):cost[i] = float('inf')cost[k] = 0for fro,to,t in times:time[fro].append((to,t))l = [k]while l:k = l.pop(0)for to,t in time[k]:if cost[k]+t<cost[to]:l.append(to)cost[to] = cost[k]+tans = max(cost.values())if ans == float('inf'):return -1return ans11/26 3206. 交替组 I
遍历每个位置i 判断其与i-1 i+1是否不同
def numberOfAlternatingGroups(colors):""":type colors: List[int]:rtype: int"""n=len(colors)ans=0for i in range(n):if colors[i]^colors[(i+1)%n] and colors[i]^colors[(i-1)%n]:ans+=1return ans11/27 3208. 交替组 II
将k-1个长度的数组接到原数组后
定位起点l 将右侧位置r不断右移 直至colors[r]!=colors[r-1]
找到尽可能长的交替区间[l,r-1]
如果区间内个数大于等于k个
那么可以得到(r-1-l+1)-k+1个交替组
从下一个起点l=r重新开始查找
def numberOfAlternatingGroups(colors, k):""":type colors: List[int]:type k: int:rtype: int"""n=len(colors)colors = colors+colors[:k-1]ans=0l = 0r = 1while l<n:while r<n+k-1 and colors[r]!=colors[r-1]:r+=1print(l,r)if r-l>=k:ans+=r-l-k+1l=rr+=1return ans11/28 3250. 单调数组对的数目 I
dp
定义dp[i][j]表示arr1[i]=j时 前i+1个元素组成的单调数组数目
dp[i][v2]=sum(dp[i-1][v1]) 需要v2>=v1 且 nums[i-1]-v1>=nums[i]-v2>=0
v2>=nums[i]-nums[i-1]+v1 => v2>=v1+d d=max(0,nums[i]-nums[i-1])
状态转移 dp[i][j]=dp[i][j-1]+dp[i-1][j-d]
def countOfPairs(nums):""":type nums: List[int]:rtype: int"""MOD=10**9+7n,m=len(nums),max(nums)dp = [[0]*(m+1) for _ in range(n)]for v in range(nums[0]+1):dp[0][v]=1for i in range(1,n):d = max(0,nums[i]-nums[i-1])for j in range(d,nums[i]+1):if j==0:dp[i][j]=dp[i-1][j-d]else:dp[i][j]=(dp[i][j-1]+dp[i-1][j-d])%MODreturn sum(dp[n-1])%MOD11/29 3251. 单调数组对的数目 II
dp
定义dp[i][j]表示arr1[i]=j时 前i+1个元素组成的单调数组数目
dp[i][v2]=sum(dp[i-1][v1]) 需要v2>=v1 且 nums[i-1]-v1>=nums[i]-v2>=0
v2>=nums[i]-nums[i-1]+v1 => v2>=v1+d d=max(0,nums[i]-nums[i-1])
状态转移 dp[i][j]=dp[i][j-1]+dp[i-1][j-d]
def countOfPairs(nums):""":type nums: List[int]:rtype: int"""MOD=10**9+7n,m=len(nums),max(nums)dp = [[0]*(m+1) for _ in range(n)]for v in range(nums[0]+1):dp[0][v]=1for i in range(1,n):d = max(0,nums[i]-nums[i-1])for j in range(d,nums[i]+1):if j==0:dp[i][j]=dp[i-1][j-d]else:dp[i][j]=(dp[i][j-1]+dp[i-1][j-d])%MODreturn sum(dp[n-1])%MOD11/30 3232. 判断是否可以赢得数字游戏
除非个位数和两位数的和相同 否则Alice必定获胜
def canAliceWin(nums):""":type nums: List[int]:rtype: bool"""s=sum(nums)one = 0 for num in nums:if num//10==0:one+=numreturn False if 2*one==s else True12/1 51. N 皇后
1.遍历每一层的位置
确定一个位置后 将后面不能填的位置标记
2.遍历每一层
使用三个set记录已有皇后的位置
列，左到右的斜线，右到左的斜线
y, x+y, x-y
如果当前位置可以放 那么将这三个值放入 并记录当前x层的列位置y
查看下一层x+1
如果已到了最后一层则保存当前其情况
否则将刚才的状态清空 查看下一个位置
def solveNQueens(n):""":type n: int:rtype: List[List[str]]"""import copyres=[]m = [["."]*n for _ in range(n)]def dfs(i,prem):for loc in range(n):tmpm = copy.deepcopy(prem)if tmpm[i][loc]==".":for x in range(loc+1,n):tmpm[i][x]="x"for x in range(i+1,n):tmpm[x][loc]="x"if loc+x-i<n:tmpm[x][loc+x-i]="x"if loc-(x-i)>=0:tmpm[x][loc-(x-i)]="x"tmpm[i][loc]="Q"if i==n-1:res.append(tmpm)else:dfs(i+1,tmpm)dfs(0,m)ret = []for r in res:ans=[]for line in r:st = ""for s in line:if s=='Q':st+='Q'else:st+='.'ans.append(st)ret.append(ans)return retdef solveNQueens2(n):""":type n: int:rtype: List[List[str]]"""col,ltr,rtl = set(),set(),set()ans=[]pos=[]def dfs(y):for x in range(n):if (x not in col) and ((x+y) not in ltr) and ((x-y) not in rtl):col.add(x)ltr.add(x+y)rtl.add(x-y)pos.append(x)if y+1==n:tmp = pos[:]ans.append(tmp)else:dfs(y+1)col.remove(x)ltr.remove(x+y)rtl.remove(x-y)pos.pop()dfs(0)ret=[]for p in ans:tmp=[]for i in p:row = ['.']*nrow[i]='Q'tmp.append(''.join(row))ret.append(tmp)return ret
