5275. 找出井字棋的获胜者
A 和 B 在一个 3 x 3 的网格上玩井字棋。
井字棋游戏的规则如下：
玩家轮流将棋子放在空方格 (" ") 上。
第一个玩家 A 总是用 "X" 作为棋子，而第二个玩家 B 总是用 "O" 作为棋子。
"X" 和 "O" 只能放在空方格中，而不能放在已经被占用的方格上。
只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。
如果所有方块都放满棋子（不为空），游戏也会结束。
游戏结束后，棋子无法再进行任何移动。
给你一个数组 moves，其中每个元素是大小为 2 的另一个数组（元素分别对应网格的行和列），它按照 A 和 B 的行动顺序（先 A 后 B）记录了两人各自的棋子位置。
如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。
你可以假设 moves 都 有效（遵循井字棋规则），网格最初是空的，A 将先行动。
暴力统计moves所在线的个数，一共有8条线，如果有一条线个数首先达到3，则胜利
class Solution(object):
def tictactoe(self, moves):
"""
:type moves: List[List[int]]
:rtype: str
"""
ans = "Pending"
if len(moves) == 9:
ans = "Draw"
cnt = []
cnt.append([0]*8)# 横向 0 1 2 纵向3 4 5 斜线 6 7
cnt.append([0]*8)
mark = 0
ans_str = ["A","B"]
for arr in moves:
x,y = arr[0],arr[1]
cnt[mark][x]+=1
cnt[mark][y+3]+=1
if x==y:
cnt[mark][6]+=1
if abs(x-y)==2 or (x==y and x==1):
cnt[mark][7]+=1
for i in cnt[mark]:
if i == 3:
return ans_str[mark]
mark = mark^1
return ans
5276. 不浪费原料的汉堡制作方案
圣诞活动预热开始啦，汉堡店推出了全新的汉堡套餐。为了避免浪费原料，请你帮他们制定合适的制作计划。
给你两个整数 tomatoSlices 和 cheeseSlices，分别表示番茄片和奶酪片的数目。不同汉堡的原料搭配如下：
巨无霸汉堡：4 片番茄和 1 片奶酪
小皇堡：2 片番茄和 1 片奶酪
请你以 [total_jumbo, total_small]（[巨无霸汉堡总数，小皇堡总数]）的格式返回恰当的制作方案，使得剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量都是 0。
如果无法使剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量为 0，就请返回 []。
本质上就是求方程的解，简化一下就好
方程本质在代码注释中
class Solution(object):
def numOfBurgers(self, tomatoSlices, cheeseSlices):
"""
:type tomatoSlices: int
:type cheeseSlices: int
:rtype: List[int]
"""
if tomatoSlices < 2*cheeseSlices or tomatoSlices > 4*cheeseSlices or (tomatoSlices & 1):
return []
# x*2 + y*4 = tomatoSlices => 2*(x+y)+2*y = tomatoSlices
# x+y = cheeseSlices
# tomatoSlices - 2*cheeseSlices = 2*y
y = (tomatoSlices - 2*cheeseSlices)//2
x = cheeseSlices - y
if x*2 + y*4 == tomatoSlices:
return [y,x]
return []
5277. 统计全为 1 的正方形子矩阵
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
正方形子矩阵，选一个代表点作为统计，方便起见选为左上角的点。从边长为1开始逐步扩大，如果符合就继续，每次只需要遍历扩张的边是否点全为1，不符合就淘汰。
class Solution(object):
def countSquares(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
m = len(matrix)
n = len(matrix[0])
limit = min(m,n)
def check(x,y,edge):
tmpx,tmpy = x,y
x = x+edge-1
y = y+edge-1
if x>=m or y>=n:
return False
for i in range(tmpy,y):
if not matrix[x][i]:
return False
for i in range(tmpx,x):
if not matrix[i][y]:
return False
return matrix[x][y] == 1
now = []
for i in range(m):
for j in range(n):
if matrix[i][j]:
now.append([i,j])
ans = len(now)
for i in range(2,limit+1):
if not now:
break
tmp = []
for pos in now:
if check(pos[0],pos[1],i):
print(pos)
tmp.append(pos)
ans+=1
now = tmp
return ans
5278. 分割回文串 III
给你一个由小写字母组成的字符串 s，和一个整数 k。
请你按下面的要求分割字符串：
首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
请返回以这种方式分割字符串所需修改的最少字符数。
动态规划，dp作为转移复杂度len(s)*len(s)*k
dp(i,j)代表统计到第i个字符时，分隔j次需要修改的次数，我们可以遍历(0-i)为起点的字符串进行转移，起点记为pos,则用 dp(pos,j-1)+edit(pos,i)可以更新dp(i,j)的结果
class Solution(object):
def palindromePartition(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
dp = [ [-1]*(k+1) for i in range(len(s)+1) ]
dp[0][0] = 0
def check(x,y):
l,r = x,y-1
edit = 0
while l<r:
edit += s[l]!=s[r]
l+=1
r-=1
return edit
def update(x,y):
if x== -1:
return y
if y==-1:
return x
return min(x,y)
for i in range(1,len(s)+1):
for j in range(i):
edit = check(j,i)
for status in range(k):
if dp[j][status]!=-1:
dp[i][status+1] = update(edit+dp[j][status],dp[i][status+1])
return dp[len(s)][k]
