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

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

image.png

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

展开讨论
  • 找出井字棋的获胜者
    首先模拟走的情况,得到最终的棋盘局面,然后模拟判断谁赢或者draw以及pending就可以了。时间复杂度 O(n2)O(n^2),当然 n=3n=3
class Solution(object):
    def tictactoe(self, moves):
        """
        :type moves: List[List[int]]
        :rtype: str
        """
        def check_win(grid):
            for i in range(3):
                if grid[i][0] == grid[i][1] and grid[i][0] == grid[i][2]:
                    if grid[i][0] != 0:
                        return grid[i][0]
                    
            for i in range(3):
                if grid[0][i] == grid[1][i] and grid[0][i] == grid[2][i]:
                    if grid[0][i] != 0:
                        return grid[0][i]
            
            if grid[0][0] == grid[1][1] and grid[0][0] == grid[2][2]:
                if grid[0][0] != 0:
                    return grid[0][0]
                
            if grid[2][0] == grid[1][1] and grid[2][0] == grid[0][2]:
                if grid[2][0] != 0:
                    return grid[2][0]
            return None
        import numpy as np
        grid = np.zeros((3,3),dtype=np.int)
        cnt = 1
        for x,y in moves:
            grid[x,y] = cnt
            cnt = 3 - cnt
        res = check_win(grid)
        if not res is None:
            return chr(ord('A')+res-1)
        if len(moves) == 9: return 'Draw'
        return 'Pending'
  • 不浪费原料的汉堡制作方案
    这道题有两种思路,第一种思路是贪心,我们先假设全部做小汉堡,这样会导致两种情况:

    1. 番茄不够:无解
    2. 番茄剩余:由于大汉堡只比小汉堡多2个番茄,所以我们可以对每个小汉堡加上两个番茄变成大汉堡。

    对于第二种情况,还需要判断番茄奇偶数量以及是不是全做大汉堡都有多余等无解情况。

    而第二种思路更简单,我们可以直接列一个二元一次方程组,直接求解数量,然后判断数量是不是正整数来判断无解就可以了。

class Solution(object):
    def numOfBurgers(self, tomatoSlices, cheeseSlices):
        """
        :type tomatoSlices: int
        :type cheeseSlices: int
        :rtype: List[int]
        """
        if tomatoSlices == 0 and cheeseSlices == 0:
            return [0,0]
        if tomatoSlices == 0 or cheeseSlices == 0:
            return []
        tomatoSlices -= cheeseSlices * 2
        if tomatoSlices < 0 or tomatoSlices % 2 != 0:
            return []
        
        if tomatoSlices > cheeseSlices * 2:
            return []
        return [tomatoSlices/2, cheeseSlices-tomatoSlices/2]
  • 统计全为 1 的正方形子矩阵

  • 首先预处理出每行每列从第0个格子到第i个格子的和,这样我们可以在 O(1)O(1) 的时间内判断该行或者列某一部分是否全为1,这是非常常见的预处理技巧。

    然后我们暴力正方形起点和边长判断就可以了。如果我们已知(i,i)到(i+k,j+k)为全1正方形,那么我们要判断(i,i)到(i+k+1,i+k+1)的时候,只需要判断(i+k+1,i..i+k+1)以及(i..i+k+1,i+k+1)是否全为1就可以了,可以用上述的预处理结果快速计算出来。时间复杂度 O(n3)O(n^3)

class Solution(object):
    def countSquares(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        import numpy as np
        row_sum = np.cumsum(matrix,axis=0)
        col_sum = np.cumsum(matrix,axis=1)
        n = len(matrix)
        m = len(matrix[0])
        def get_row_sum(i, ti, tj):
            if i == 0:
                return row_sum[ti,tj]
            else:
                return row_sum[ti,tj] - row_sum[i-1,tj]
        def get_col_sum(j, tj, ti):
            if j == 0:
                return col_sum[ti,tj]
            else:
                return col_sum[ti,tj] - col_sum[ti,j-1]
        def get_ans(i,j):
                
            ans = 0
            ti = i; tj = j
            if matrix[ti][tj] == 1: ans += 1
            else: return ans
            
            ti += 1
            tj += 1
            while ti < n and tj < m:
                if not get_row_sum(i, ti, tj) == ti - i + 1:
                    break
                if not get_col_sum(j, tj, ti) == tj - j + 1:
                    break
                ans += 1
                ti += 1; tj += 1
            return ans
        ans = 0
        for i in range(n):
            for j in range(m):
                ans += get_ans(i,j)
        return ans

  • 分割回文串 III

  • DP,首先暴力计算把 [i..j][i..j] 变成回文串的最小代价,计算方式也很简单,直接看第一个和最后一个,第二个和倒数第二个...是否一样,不一样则代价加1。

    有了预处理数组 cost 以后,令状态为 dp[i][j]dp[i][j] 表示把前 ii 个字符变为 jj 个回文串的最小代价,那么 dp[i][j]=min(dp[x][j1]+cost[x+1,i]),x[0..i1]dp[i][j] = min(dp[x][j-1] + cost[x+1,i]), x∈[0..i-1]

    最后结果为 dp[n1][k]dp[n-1][k] 即把前n个字符变为k段的最小代价。时间复杂度为 O(n3)O(n^3)

class Solution(object):
    def palindromePartition(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        import numpy as np
        def get_cost(s):
            n = len(s)
            cost = 0
            for i in range(n//2):
                if s[i] != s[n-i-1]:
                    cost += 1
            return cost
        n = len(s)
        cost = np.ones((n,n),dtype=np.int)*1000
        for i in range(n):
            for j in range(i,n):
                cost[i,j] = get_cost(s[i:j+1])
        #print(cost)
        dp = np.ones((n, k+3),dtype=np.int)*1000
        dp[0][1] = 0
        for i in range(1,n):
            dp[i][1] = cost[0,i]
            for mk in range(2,min(k+1,i+2)):
                for j in range(i):
                    dp[i][mk] = min(dp[i][mk], dp[j][mk-1] + cost[j+1,i])
        #print(dp)
        return dp[n-1][k]
9
展开全部 11 讨论