铁岭免费移动网站建设,wordpress tooltipster,企业现在有必要做网站吗,网站建设需要什么样的内容记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 10/28 685. 冗余连接 II10/29 3211. 生成不含相邻零的二进制字符串10/30 3216. 交换后字典序最小的字符串10/31 3165. 不包含相邻元素的子序列的最大和11/1 3259. 超级饮料…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 10/28 685. 冗余连接 II10/29 3211. 生成不含相邻零的二进制字符串10/30 3216. 交换后字典序最小的字符串10/31 3165. 不包含相邻元素的子序列的最大和11/1 3259. 超级饮料的最大强化能量11/2 3226. 使两个整数相等的位更改次数11/3638. 大礼包 10/28 685. 冗余连接 II check用来检查是否满足 1.入度不能有大于1的 2.不能存在圈 先将所有点的父节点取出如果存在有两个父节点 那么说明这个节点需要取出一条边 遍历后check是否正确 若正确 将结果暂存ret 判断ret, 若ret内有多个 则取出位置最靠后的作为结果 若ret0: 所有节点入度都正常 说明存在圈 从后往前去除一个点 check是否正常 若正常则答案为这个点 def findRedundantDirectedConnection(edges)::type edges: List[List[int]]:rtype: List[int]def find(p,x):while p[x] ! x:p[x] p[p[x]]x p[x]return p[x]# 判断给定的图是不是有圈def cycle(graph):p {}for a, b in graph:p.setdefault(a, a)p.setdefault(b, b)pa, pb find(p, a), find(p, b)print([a,b],p,pa,pb)if pa pb: return(True)else:p[pa] p[pb]dic{}ans[]ret []def check(l):#入度不能大于1endpoint [y for x,y in l]if len(endpoint)!len(set(endpoint)):return Falsedef find(p,x):while p[x] ! x:p[x] p[p[x]]x p[x]return p[x]# 判断给定的图是不是有圈def cycle(graph):p {}for a, b in graph:p.setdefault(a, a)p.setdefault(b, b)pa, pb find(p, a), find(p, b)if pa pb: return(True)else:p[pa] p[pb]if cycle(l):return Falsereturn Truefor v in edges:top v[0]end v[1]dic.setdefault(end,[])dic[end].append(top)for k in dic.keys():if len(dic[k])1:for v in dic[k]:ori edges[:]tmp[v,k]ori.pop(ori.index(tmp))if check(ori):ret.append(tmp)if len(ret)0:for i in range(len(edges)-1,-1,-1):ori edges[:]ori.pop(i)if check(ori):ans edges[i]breakelse:pos -1for i in ret:if edges.index(i)pos:pos edges.index(i)ans i return ans 10/29 3211. 生成不含相邻零的二进制字符串 所有长度为2的子字符串至少有一个1 说明不存在连续的两个0 将二进制按位取反为x 判断不存在连续两个1 如果x(x1)0 说明x没有连续的两个1 def validStrings(n)::type n: int:rtype: List[str]ans []mask (1n)-1for i in range(1n):t mask^iif (t1 t)0:ans.append(f{i:0{n}b})return ans 10/30 3216. 交换后字典序最小的字符串 从前往后寻找 找到首次出现满足前面数字比后面大的就交换 def getSmallestString(s)::type s: str:rtype: strllist(s)nlen(s)for i in range(n-1):if int(l[i])%2int(l[i1])%2 and l[i]l[i1]:l[i],l[i1]l[i1],l[i]breakreturn .join(l) 10/31 3165. 不包含相邻元素的子序列的最大和 将数组分为两段 每一段的首尾都有不选 或 可选两种情况 一共就有四种情况 00:首不选 尾不选 01:首不选 尾可选 10:首可选 尾不选 11:首可选 尾可选 将某数组x分为前后a,b两段 分别讨论四种情况 f(x)为x数组不相邻子序列最大和 f00(x) max(f01(a)f00(b),f00(a)f10(b)) f01(x) max(f00(a)f11(b),f01(a)f01(b)) f10(x) max(f10(a)f10(b),f11(a)f00(b)) f11(x) max(f10(a)f11(b),f11(a)f01(b)) 用线段树来实现单点的修改 每个节点维护对应区间f(X) def maximumSumSubsequence(nums, queries)::type nums: List[int]:type queries: List[List[int]]:rtype: intMOD10**97nlen(nums)tr [[0]*4 for _ in range(2n.bit_length())]def maxv(a,b):return b if ba else adef merg(k):a,b tr[k*2],tr[k*21]tr[k][0] max(a[0]b[2],a[1]b[0])tr[k][1] max(a[0]b[3],a[1]b[1])tr[k][2] max(a[2]b[2],a[3]b[0])tr[k][3] max(a[2]b[3],a[3]b[1])def build(k,l,r):if lr:tr[k][3]maxv(nums[l],0)returnm(lr)//2build(k*2,l,m)build(k*21,m1,r)merg(k)def change(k,l,r,i,val):if lr:tr[k][3]max(val,0)returnm(lr)//2if im:change(k*2,l,m,i,val)else:change(k*21,m1,r,i,val)merg(k)build(1,0,n-1)ans 0for i,val in queries:change(1,0,n-1,i,val)ans (anstr[1][3])%MODreturn ans 11/1 3259. 超级饮料的最大强化能量 动态规划 f[i][0/1]代表第i步喝A/B获得的最大值 def maxEnergyBoost(energyDrinkA, energyDrinkB)::type energyDrinkA: List[int]:type energyDrinkB: List[int]:rtype: intnlen(energyDrinkA)f [[0,0] for _ in range(n1)]for i in range(1,n1):f[i][0] f[i-1][0]energyDrinkA[i-1]f[i][1] f[i-1][1]energyDrinkB[i-1]if i1:f[i][0] max(f[i][0],f[i-2][1]energyDrinkA[i-1])f[i][1] max(f[i][1],f[i-2][0]energyDrinkB[i-1])return max(f[n][0],f[n][1]) 11/2 3226. 使两个整数相等的位更改次数 按位判断 def minChanges(n, k)::type n: int:type k: int:rtype: intans 0while n0 or k0:if (n1)0 and (k1)1:return -1if (n1)1 and (k1)0:ans1n1k1return ans 11/3638. 大礼包 过滤掉不需要的套餐 保留有用套餐 dfs 遍历选取每一种套餐的情况 算出不买套餐的价格base 如果买套餐实惠则替换价格 def shoppingOffers(price, special, needs)::type price: List[int]:type special: List[List[int]]:type needs: List[int]:rtype: intn len(price)fsp []for sp in special:if sum(sp[i]*price[i] for i in range(n))sp[n]:fsp.append(sp)def dfs(curneed):base sum(curneed[i]*price[i] for i in range(n))for cursp in fsp:p cursp[n]netneed []for i in range(n):if cursp[i]curneed[i]:breaknetneed.append(curneed[i]-cursp[i])if len(netneed)n:base min(base,dfs(netneed)p)return basereturn dfs(needs)
