这周的两个比赛也是有点伤,都是大佬们只需要7、8分钟就能搞定的题目,我硬是两个第四题都没有想到好的思路,最后都是看了其他大佬们的解答才搞定的,然后发现这两题都只需要几行,就很伤……
感觉最近状态真心不太好,唉……
给出题目一的试题链接如下:
这一题就是rule based翻译一下题中给出的4个情况即可。
给出python代码实现如下:
class Solution:
def bestHand(self, ranks: List[int], suits: List[str]) -> str:
if len(set(suits)) == 1:
return "Flush"
cnt = Counter(ranks).values()
if max(cnt) >= 3:
return "Three of a Kind"
elif max(cnt) == 2:
return "Pair"
else:
return "High Card"
提交代码评测得到:耗时34ms,占用内存13.9MB。
给出题目二的试题链接如下:
这一题其实就是找到原序列当中所有的连续的0的子序列,然后计算一下他们能够构成的子序列的数目,最后把这些数全部相加即可。
给出python代码实现如下:
class Solution:
def zeroFilledSubarray(self, nums: List[int]) -> int:
res, cnt = 0, 0
for x in nums:
if x == 0:
cnt += 1
else:
res += cnt * (cnt+1) // 2
cnt = 0
res += cnt * (cnt+1) // 2
return res
提交代码评测得到:耗时1895ms,占用内存24.7MB。
给出题目三的试题链接如下:
这道题的主要难点就在于说需要对每一个数快速地找到其最小的index,因此我们需要额外地对每一个数建立一个有序的index的数组,然后一直维护这个数组即可。
给出python代码实现如下:
class NumberContainers:
def __init__(self):
self.nums = []
self.index = defaultdict(list)
def change(self, index: int, number: int) -> None:
idx = bisect.bisect_left(self.nums, (index, -1))
if idx >= len(self.nums) or self.nums[idx][0] != index:
bisect.insort(self.nums, (index, number))
bisect.insort(self.index[number], index)
else:
x = self.nums[idx][1]
self.nums[idx] = (index, number)
bisect.insort(self.index[number], index)
self.index[x].pop(bisect.bisect_left(self.index[x], index))
return
def find(self, number: int) -> int:
return -1 if self.index[number] == [] else self.index[number][0]
提交代码评测得到:耗时2350ms,占用内存58.5MB。
给出题目四的试题链接如下:
这一题其实我一开始没想到,但是看了答案之后发现其实还是挺简单的,其实就是一个简单的构造问题。
我们给出一种构造方式,当所有的数字第一次出现一轮之后,那么对于长度为1的子序列,我们总能够对这个序列实现构造。
假设我们现在已经可以完成长度为
的序列,如果我们在其之后又能够出现一轮所有
的数字,那么我们就能够构造出任意一个长度为
的子序列。
反之,如果有一个数没有存在,那么我们总能够找到一个子序列,使得这个序列无法被成功构造。
给出python代码实现如下:
class Solution:
def shortestSequence(self, rolls: List[int], k: int) -> int:
seen = set()
res = 1
for x in rolls:
seen.add(x)
if len(seen) == k:
res += 1
seen = set()
return res
提交代码评测得到:耗时1503ms,占用内存28.3MB。