LeetCode笔记：Biweekly Contest 75
LeetCode笔记：Biweekly Contest 75
codename_cys
发布于 2022-04-13 16:29:26
发布于 2022-04-13 16:29:26
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题思路倒是简单，逐位进行二进制比特比较就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def minBitFlips(self, start: int, goal: int) -> int:
res = 0
while start != 0 or goal != 0:
res = res if start % 2 == goal % 2 else res + 1
start = start // 2
goal = goal // 2
return res提交代码评测得到：耗时56ms，占用内存14MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题应该是有比较巧妙的方法的，不过这里我们的思路十分的暴力，直接一个二重循环搞定了……
2. 代码实现
给出python代码实现如下：
class Solution:
def triangularSum(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n-1, 0, -1):
for j in range(i):
nums[j] = (nums[j] + nums[j+1]) % 10
return nums[0] 提交代码评测得到：耗时3334ms，占用内存13.7MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题我们的思路还是比较直接的，就是考察每一个0之后的10序列个数以及每一个1之后的01序列个数。
但是，我们对于其计数的实现却是多少有点繁琐的，用了两个累积数组进行求解。
2. 代码实现
给出python代码实现如下：
class Solution:
def numberOfWays(self, s: str) -> int:
n = len(s)
post0 = [0 for _ in range(n)]
post1 = [0 for _ in range(n)]
for i in range(n-2, -1, -1):
if s[i+1] == "0":
post0[i] = post0[i+1] + 1
post1[i] = post1[i+1]
else:
post0[i] = post0[i+1]
post1[i] = post1[i+1] + 1
post01 = [0 for _ in range(n)]
post10 = [0 for _ in range(n)]
for i in range(n-3, -1, -1):
if s[i+1] == "0":
post01[i] = post01[i+1] + post1[i+1]
post10[i] = post10[i+1]
else:
post01[i] = post01[i+1]
post10[i] = post10[i+1] + post0[i+1]
res = 0
for i in range(n-2):
if s[i] == "0":
res += post10[i]
else:
res += post01[i]
return res提交代码评测得到：耗时2938ms，占用内存24.6MB。
3. 算法优化
这一题看了一下别人的解法，发现思路基本还是一样，但是求解的方式变成了计算前后0或者1的乘积，这样的话同样都可以统计010或者101的序列，但是实现上明显更加优雅了。
给出别人的code如下：
class Solution:
def numberOfWays(self, s: str) -> int:
count1=0
for i in s:
if i=="1":
count1+=1
count0=len(s)-count1
n0,n1=0,0
ans=0
for i in s:
if i=="1":
ans+=n0*count0
n1+=1
count1-=1
else:
ans+=n1*count1
n0+=1
count0-=1
return ans4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题我自己没有搞定，不过看别人的乘积发现基本都是只用了一两分钟就搞定了，简直惊呆了我。
后来才知道，原来这个是有标准算法的，就是一个字符串匹配的z algorithm，因此这里我们就不对其进行具体的解释了，具体可以看我另外整理的z algorithm的介绍（经典算法：Z算法（z algorithm））。
2. 代码实现
给出python代码实现如下：
class Solution:
def sumScores(self, s: str) -> int:
def z_algorithm(s):
n = len(s)
z = [0 for _ in range(n)]
l, r = -1, -1
for i in range(1, n):
if i > r:
l, r = i, i
while r < n and s[r-l] == s[r]:
r += 1
z[i] = r-l
r -= 1
else:
k = i - l
if z[k] < r - i + 1:
z[i] = z[k]
else:
l = i
while r < n and s[r-l] == s[r]:
r += 1
z[i] = r-l
r -= 1
z[0] = n
return z
z = z_algorithm(s)
return sum(z)提交代码评测得到：耗时553ms，占用内存18.9MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022/04/05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
