LeetCode笔记：Biweekly Contest 56（补发）
LeetCode笔记：Biweekly Contest 56（补发）
codename_cys
发布于 2021-07-20 11:31:41
发布于 2021-07-20 11:31:41
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题的思路很清晰，就是找三个数，然后看一下是否满足勾股定理。
最暴力的解法就是三重循环，这里我们是使用二重循环然后看一下其求和结果是否是范围内的数的平方。
2. 代码实现
给出python代码实现如下：
class Solution:
def countTriples(self, n: int) -> int:
res = 0
for i in range(1, n+1):
for j in range(1, n+1):
s = i*i + j*j
k = int(math.sqrt(s))
if k > n:
break
if k*k == s:
res += 1
return res提交代码评测得到：耗时408ms，占用内存14.1MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题用一个广度遍历算法即可快速地给出答案。
我们用广度优先遍历的方式不断地延展可访问空间，直至到达边界。
2. 代码实现
给出python代码实现如下：
class Solution:
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
n, m = len(maze), len(maze[0])
seen = {tuple(entrance)}
q = [[entrance[0], entrance[1], 0]]
while q:
x, y, s = q.pop(0)
if s != 0 and (x == n-1 or y == m-1 or x == 0 or y == 0):
return s
if x-1 >= 0 and (x-1, y) not in seen and maze[x-1][y] == ".":
q.append((x-1, y, s+1))
seen.add((x-1, y))
if x+1 < n and (x+1, y) not in seen and maze[x+1][y] == ".":
q.append((x+1, y, s+1))
seen.add((x+1, y))
if y-1 >= 0 and (x, y-1) not in seen and maze[x][y-1] == ".":
q.append((x, y-1, s+1))
seen.add((x, y-1))
if y+1 < m and (x, y+1) not in seen and maze[x][y+1] == ".":
q.append((x, y+1, s+1))
seen.add((x, y+1))
return -1提交代码评测得到：耗时968ms，占用内存15.9MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题事实上就是一个分类讨论的题目，我们总可以将游戏分为如下几种情况：
- 左右侧原始的数值之和相同，那么Alice的目的就是令左侧总和不等于右侧总和，此时只要问号数左右侧不平衡，那么Alice就是必胜的；
- 左侧原始数值之和大于右侧，此时Bob要赢，他就必须要尽可能地令右侧的问号取的数大于左侧问号取的数，且差值恰好为原始的差值；
- 左侧原始数值之和小于右侧，此时Bob要赢，他就必须要尽可能地令右侧的问号取的数小于左侧问号取的数，且差值恰好为原始的差值；
无论如何，显而易见的就是我们只需要考虑左右侧原始的数据之和的差值以及问号数目的差值即可，因为Alice和Bob对于左右侧数值之和的需求总是相悖的，因此最优策略下如果两侧各有一个元素，那么必然他们的取值是相同的。
那么，我们就可以进一步进行分类讨论，当左侧原始数值之和大于右侧时，又可以分为以下几种情况：
- 左右侧问号数相同，此时Alice必胜；
- 左侧问号比较多，此时Alice同样必胜；
- 右侧问号数比较多，此时当且仅当问号数为偶数（此时Bob处于后操作位），且差值之和恰好满足 n = 9 × k 2 n = 9 \times \frac{k}{2} n=9×2k时，Bob才可以赢。
同样，我们可以得到左侧原始数值之和小于右侧时的情况。
最终，我们将其转换为代码即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def sumGame(self, num: str) -> bool:
delta_num = 0
delta_mark = 0
n = len(num) // 2
for i in range(n):
if num[i] == "?":
delta_mark += 1
else:
delta_num += int(num[i])
if num[n+i] == "?":
delta_mark -= 1
else:
delta_num -= int(num[n+i])
def f(n, k):
if k == 0:
return n != 0
elif n == 0:
return k > 0 or k < -1
elif n * k > 0:
return True
n, k = abs(n), abs(k)
return k % 2 == 1 or n != 9 * (k //2)
return f(delta_num, delta_mark)提交代码评测得到：耗时212ms，占用内存15.3MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
放弃了，参考官方解答吧……
官方解答：规定时间内到达终点的最小花费
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-07-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录