力扣第 167 场双周赛

635
Contest
LeetCode
本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

3707. 相等子字符串分数 - 力扣（LeetCode） ​

题目类型 ​

#前缀和 #二分

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def scoreBalance(self, s: str) -> bool:
        pre = list(accumulate([ord(c) - 96 for c in s], initial=0))
        for i in range(1, len(s)):
            if pre[i] == pre[-1] - pre[i]:
                return True
        return False

3708. 最长斐波那契子数组 - 力扣（LeetCode） ​

题目类型 ​

#枚举 #分组循环

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        ans = 2
        while i < n:
            j = i + 1
            while j + 1 < n and nums[j + 1] == nums[j] + nums[j - 1]:
                j += 1
            ans = max(ans, j - i + 1)
            i = j
        return ans

3709. 设计考试分数记录器 - 力扣（LeetCode） ​

题目类型 ​

#前缀和 #离散化 #树状数组

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class ExamTracker:

    def __init__(self):
        self.tree = FenwickTree(10 ** 5 + 5)
        self.time = [0]
        self.cnt = 0

    def record(self, time: int, score: int) -> None:
        self.cnt += 1
        self.time.append(time)
        self.tree.update(self.cnt, score)

    def totalScore(self, startTime: int, endTime: int) -> int:
        lidx = bisect_left(self.time, startTime)
        ridx = bisect_left(self.time, endTime + 1)
        return self.tree.range_query(lidx, ridx - 1)


# Your ExamTracker object will be instantiated and called as such:
# obj = ExamTracker()
# obj.record(time,score)
# param_2 = obj.totalScore(startTime,endTime)
py
class Fenwick:
    __slots__ = ["n", "c"]

    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, delta: int):
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x > 0:
            s += self.c[x]
            x -= x & -x
        return s

3710. 最大划分因子 - 力扣（LeetCode） ​

题目类型 ​

#二分 #图论 #二分图 #并查集 #交替染色法

解题思路 ​

二分查找，二分图染色判断图是否能划分为两个连通块，或使用并查集。

参考：二分答案 + 判断二分图（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def maxPartitionFactor(self, points: List[List[int]]) -> int:
        n = len(points)
        if n == 2:
            return 0

        f = lambda a, b: abs(a[0] - b[0]) + abs(a[1] - b[1])
        d = [[0] * n for _ in range(n)]
        mx = 0
        for i in range(n):
            for j in range(i + 1, n):
                d[i][j] = d[j][i] = f(points[i], points[j])
                if d[i][j] > mx:
                    mx = d[i][j]

        def check(x):
            col = [-1] * n
            for i in range(n):
                if col[i] > -1:
                    continue
                col[i] = 0
                q = deque([i])
                while q:
                    i = q.popleft()
                    for j in range(n):
                        if i == j or d[i][j] >= x:
                            continue
                        if col[j] < 0:
                            col[j] = 1 ^ col[i]
                            q.append(j)
                        elif col[i] == col[j]:
                            return False
            return True

        left, right = 0, mx
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                left = mid + 1
            else:
                right = mid - 1
        return right
力扣第 168 场双周赛
力扣第 471 场周赛