二次遍历,先来看看0x3f大佬的真·二行解法👇(推荐)
class Solution:
def countHillValley(self, nums: List[int]) -> int:
nums = [x for x, _ in groupby(nums)]
return sum((a < b) == (c < b) for a, b, c in zip(nums, nums[1:], nums[2:]))
然后是我用JS写的假·一行解法👇(不推荐)
var countHillValley = (nums) => {let res=0,i=0,n=nums.length; while(i<n){ let start = i, v=nums[i];while (i < n && nums[i] == v) {i++;} if (start > 0 && i < n && nums[start-1] < v == (nums[i] < v)) { res++; } } return res;};
灵神一行解法👇(原来是脑筋急转弯,看完表示震惊了!!!)
class Solution:
def countCollisions(self, s: str) -> int:
return len(s.lstrip('L').rstrip('R')) - s.count('S')
递归+搜索,可可一行解法👇(不推荐,虽然是一行但是非常不pythonic,大家不要学)
class Solution:
def maximumBobPoints(self, numArrows: int, alice: List[int]) -> List[int]:
return (res:=(solve:=lambda idx,num:(0, []) if idx==12 else (res1[0], [0]+res1[1]) if (res2:=solve(idx+1, num-alice[idx]-1))[0]+idx<=(res1:=solve(idx+1, num))[0] or num <= alice[idx] else (res2[0]+idx, [alice[idx]+1]+res2[1]))(0,numArrows)[1])[:-1]+[res[-1]+numArrows-sum(res)]
二进制枚举,六弦爷六行解法👇(推荐!)
d = {mask: sum(i for i in range(12) if (mask >> i) & 1 == 1) for mask in range(1 << 12)}
order = sorted(d, key=d.__getitem__, reverse=True)
class Solution:
def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
mask = next(mask for mask in order if sum(aliceArrows[i] + 1 for i in range(12) if (mask >> i) & 1 == 1) <= numArrows)
res = [aliceArrows[i] + 1 if ((mask >> i) & 1 == 1) else 0 for i in range(12)]
res[0] += numArrows - sum(res)
return res
灵剑大佬的板子,比较清新脱俗的写法👇
class Node:
def __init__(self):
self.left = None
self.right = None
self.lmost = None
self.lchar = None
self.rmost = None
self.rchar = None
self.most = None
self.i = None
self.j = None
def update_stats(self):
if self.left is None:
return
if self.left.lmost == self.left.j - self.left.i and self.left.lchar == self.right.lchar:
self.lchar = self.left.lchar
self.lmost = self.left.lmost + self.right.lmost
else:
self.lchar = self.left.lchar
self.lmost = self.left.lmost
if self.right.rmost == self.right.j - self.right.i and self.right.rchar == self.left.rchar:
self.rchar = self.right.rchar
self.rmost = self.right.rmost + self.left.rmost
else:
self.rchar = self.right.rchar
self.rmost = self.right.rmost
self.most = max(self.left.most, self.right.most)
if self.left.rchar == self.right.lchar:
most2 = self.left.rmost + self.right.lmost
self.most = max(self.most, most2)
@classmethod
def create(cls, s, i, j):
node = cls()
if i + 1 == j:
node.lmost = 1
node.rmost = 1
node.lchar = s[i]
node.rchar = s[i]
node.most = 1
node.i = i
node.j = j
else:
m = (i + j) // 2
node.left = cls.create(s, i, m)
node.right = cls.create(s, m, j)
node.i = i
node.j = j
node.update_stats()
return node
def update(self, pos, char):
if self.left is None:
self.lchar = self.rchar = char
elif pos < self.left.j:
self.left.update(pos, char)
else:
self.right.update(pos, char)
self.update_stats()
class Solution:
def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
tree,ans = Node.create(s, 0, len(s)),[]
for i, c in zip(queryIndices, queryCharacters):
tree.update(i, c)
ans.append(tree.most)
return ans
总结
除开第四题没法做最短解法,前三题顺利完成【5行完成周赛三题】的小目标!
|