讨论/题目交流/ 🏆 第 165 场力扣周赛/
🏆 第 165 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 找出井字棋的获胜者
4 分 - 不浪费原料的汉堡制作方案
5 分 - 统计全为 1 的正方形子矩阵
6 分 - 分割回文串 III

展开讨论
力扣 (LeetCode)发起于 2019-12-01
最近编辑于 2019-12-01

出题人绝对玩过小学奥数。。。
第二题和第三题,让我回想起了被鸡兔同笼和数正方形支配的恐惧。。。
复杂度分别为O(1), O(N)

class Solution:
    # 第二题:
    def numOfBurgers(self, tomato: int, cheese: int) -> List[int]:
        # 4x+2y=tomato
        # x+y=cheese
        x = (tomato-2*cheese)/2
        y = (4*cheese-tomato)/2
        if x%1 or y%1 or x<0 or y<0:
            return []
        else:
            return [int(x),int(y)]

    # 第三题:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp = {(r,c) for r,row in enumerate(matrix) for c,pt in enumerate(row) if pt}
        ans = 0
        while(dp):
            ans+= len(dp)
            dp = {(r,c) for (r,c) in dp if (r,c+1) in dp and (r+1,c+1) in dp and (r+1,c) in dp}
        return ans

第四题还是dp,不过要分成两次:先统计子串,再对前缀串dp。复杂度O(N**3)
top-down邪教:

from functools import lru_cache
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        @lru_cache(None)
        def diff(i,j):
            if i>=j:
                return 0
            return diff(i+1,j-1)+(s[i]!=s[j])

        @lru_cache(None)
        def split(j,k):
            if k==1:return diff(0,j)
            return min(split(i,k-1)+diff(i+1,j) for i in range(k-2,j))
        return split(len(s)-1, k)
1
展开全部 11 讨论