结果
这里是式酱(∠・ω< )⌒☆
大家新年快乐！T3 WA麻了，一开始看岔题目了，以为是i<j,甚至想用模拟的做法去做，后来仔细一想才发现是脑筋急转弯，新年掉大分。T4数据很小，直接记忆化暴力即可。
6296. 交替数字和
模拟即可
class Solution:
def alternateDigitSum(self, n: int) -> int:
flag = 1 if len(str(n))%2 else -1
res = 0
while n:
res += flag*(n%10)
n //= 10
flag *= -1
return res6297. 根据第 K 场考试的分数排序
不明意义的题目
class Solution:
def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
return sorted(score,key = lambda x:-x[k])6298. 执行逐位运算使字符串相等
先思考转换关系：11变10/01 10/01变11 00变00
i,j任意选取的情况下，1在有另外一个1结合的情况下可以变为0，0在有任意1结合的情况下可以变成1，而且10和01可以互换(相当于移位)，与顺序无关。
class Solution:
def makeStringsEqual(self, s: str, target: str) -> bool:
c = Counter(s)
t = Counter(target)
# 直接移位完成
if c['1'] == t['1']:
return True
# 1变0 最终状态起码要有一个1才能转换 10 无法变 00
# 110可以变100
if c['1'] > t['1'] and t['1'] >= 1:
return True
# 0变1 此时初始状态c中起码要有一个1才能转换
if c['1'] < t['1'] and c['1'] >= 1:
return True
return False简化一下代码
class Solution:
def makeStringsEqual(self, s: str, target: str) -> bool:
return (s == target) or ('1' in s and '1' in target)6299. 拆分数组的最小代价
数据范围很小，记忆化暴力搜，据说有nlogn的解法，赛后再去学习一手。
定义每个子数组起始坐标作为状态，总状态个数O(n)，转移也是O（n），时间复杂度O（n^2）
class Solution:
def minCost(self, nums: List[int], k: int) -> int:
n = len(nums)
@cache
def dfs(i):
if i == n:
return 0
c = Counter()
count = 0
ans = 10**18
for j in range(i,n):
c[nums[j]] += 1
if c[nums[j]] == 2:
count += 2
elif c[nums[j]] >= 3:
count += 1
ans = min(ans,k + count + dfs(j + 1))
return ans
return dfs(0)写在最后
评论 (8)
