每日一题 861. 翻转矩阵后的得分
有一个二维矩阵 A 其中每个元素的值为 0 或 1 。
移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1都更改为 0。
在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。
返回尽可能高的分数。
示例：
输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：
转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
class Solution:
def matrixScore(self, A: List[List[int]]) -> int:
"""
矩阵仅仅变换行或者列，是的二进制最大。
则通过行的移动，可以让每一行的第一个数为1，这样在第一列（最高位）最大；
其余列保证1的个数大于0的个数，保证其余列（次高位）最大。这样之和为最大。
"""
if not A:
return 0
rows, columns = len(A), len(A[0])
# 保证第一列全为1, 这样二进制数最大
for x in A:
if x[0] == 0:
for i in range(columns):
x[i] = 0 if x[i] else 1
# 其余列之和大于长度的一半，则表示1多于0，这样保证在高位的数大
for j in range(1, columns):
sum_col = sum(A[i][j] for i in range(rows))
if sum_col < rows / 2:
for i in range(rows):
A[i][j] = 0 if A[i][j] else 1
# 求和
ref = 0
for i in range(rows):
ref_row = 0
for j in range(columns):
ref_row=(ref_row<<1)+A[i][j]
ref += ref_row
return ref
每日一题842. 将数组拆分成斐波那契序列
给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。
形式上，斐波那契式序列是一个非负整数列表 F，且满足：
-
0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）； -
F.length >= 3； - 对于所有的
0 <= i < F.length - 2，都有F[i] + F[i+1] = F[i+2]成立。
另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
示例 1：
输入："123456579"
输出：[123,456,579]
示例 2：
输入: "11235813"
输出: [1,1,2,3,5,8,13]
示例 3：
输入: "112358130"
输出: []
解释: 这项任务无法完成。
示例 4：
输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
示例 5：
输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。
class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
"""
官方解释
回溯加裁剪： 裁剪规则为不合法的数，超界或者出现0开头两位数
首先确定前两个数，存储到ref并查找之后的数
当出现ref 两个数以上，且ref后两个数之和为当前数，ref存储当前数，并继续下去，如果不是则跳出，并去掉存储的ref
并且重新确定前两个数。继续查找
"""
ref = []
m = 2**31 - 1
def backtrack(index):
if index == len(S):
return len(ref) >= 3
cur = 0
for i in range(index, len(S)):
if i > index and S[index] == '0':
return False
cur = cur * 10 + ord(S[i]) - ord('0')
if cur > m:
return False
if len(ref) < 2 or cur == ref[-1] + ref[-2]:
ref.append(cur)
if backtrack(i+1):
# 一直查找，如果满足则返回True
return True
# 如果不满足，跳出，这一条的数列不行，则pop存储的数
ref.pop()
elif len(ref) > 2 and cur > ref[-1] + ref[-2]:
return False
backtrack(0)
return ref
# https://blog.csdn.net/Changxing_J/article/details/108079585
# 感谢大神提供思路
def splitIntoFibonacci1(self, S: str) -> List[int]:
"""
暴力法， 双重遍历所有列表中的元素， 首先判断是否合法，然后判断
"""
N = len(S)
# 判断数字是否合法
def is_valid(n):
return not (int(n) > 0 and n[0] == "0") and int(n) <= (2 ** 31 - 1)
# 检查是否为斐波那契数列
def is_fibonacci(m, n):
if not is_valid(S[:m]) or not is_valid(S[m:n]):
return False
lst = [int(S[:m]), int(S[m:n])]
idx1 = n
while idx1 < N:
nn = lst[-1] + lst[-2] # 当前项
s1 = str(nn)
idx2 = idx1 + len(s1)
s2 = S[idx1:idx2]
if is_valid(s2) and s1 == s2:
lst.append(nn)
idx1 = idx2
else:
return False
return lst
# 筛选所有的斐波那契数列
for i in range(1, N):
for j in range(i + 1, N):
fibonacci_lst = is_fibonacci(i, j)
if fibonacci_lst:
return fibonacci_lst
return []
每日一题62. 不同路径
一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
"""
dp思路, dp[i][j] 表示从[0][0] 开始到[i][j] 的路径
最上面一行dp[0][i] = 1 , 最左边一列dp[i][0] = 1
"""
if m == 1 or n == 1:
return 1
dp = [[1] * n] * m
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
每日一题860. 柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
"""
保存5元, 10元, 20元的个数
如果遇到20元,优先找5元和10元. 没有则找3个5元.
"""
bill = {5: 0, 10:0, 20: 0}
for x in bills:
if x == 5:
bill[x] += 1
elif x == 10:
if bill[5] < 1:
return False
else:
bill[5] -= 1
bill[10] += 1
else:
if bill[10] > 0 and bill[5] > 0:
bill[5] -= 1
bill[10] -= 1
bill[20] += 1
continue
elif bill[5] > 2:
bill[5] -= 3
bill[20] +=1
else:
return False
return True
每日一题649. Dota2 参议院
Dota2 的世界里有两个阵营：Radiant(天辉)和 Dire(夜魇)
Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的**一**项：
-
禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。
-
宣布胜利：如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。
给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。
以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 Radiant 或 Dire。
class Solution:
def predictPartyVictory(self, senate: str) -> str:
"""
双队列, 分别记录R和D的顺序
R在前就会让最前面的D失效. 自己进入下一轮, 添加到R的最后面
"""
Radiant = [i for i, x in enumerate(senate) if x == 'R']
Dire = [i for i, x in enumerate(senate) if x == 'D']
while Radiant and Dire:
if Radiant[0] < Dire[0]:
Radiant.append(Radiant[0] + len(senate))
else:
Dire.append(Dire[0] + len(senate))
Radiant.pop(0)
Dire.pop(0)
return 'Radiant' if len(Radiant) else 'Dire'
每日一题376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如，[1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
'''
2个dp,
一个记录上扬摆动序列,一个记录下降摆动序列.
'''
if not nums:
return 0
down = [1 for _ in range(len(nums))]
up = [1 for _ in range(len(nums))]
for i in range(1, len(nums)):
for j in range(i):
# i和之前的数j 逐个比较,如果比他大,更新i的上扬序列,为j的上扬序列和j的下降序列+1之中的最大值。
if nums[i] > nums[j]:
up[i] = max(up[i], down[j] + 1)
elif nums[i] < nums[j]:
down[i] = max(down[i], up[j] + 1)
return max(max(down), max(up))
进阶算法
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
'''
记录每个数和前面的差值,
小于0表示比前面的小,大于0表示比前面的数大
出现连续正数或者连续负数对于最大摆动序列长度没有任何影响，
假如出现连续正数,则第一个正数记录最长上扬序列长度,后面的也是正数,只会影响上扬序列长度,
影响不了下降序列长度.
'''
n=len(nums)
if n<2:return n
a=[nums[i+1]-nums[i] for i in range(n-1)]
up=down=1
for i in a:
if i>0:
up=down+1
elif i<0:
down=up+1
return max(up,down)
每日一题217. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
'''
set 集合里的元素具有唯一性
如果有重复则输出True
一行代码
return len(nums) != len(set(nums))
'''
if not nums:
return False
x = set()
for num in nums:
if num in x:
return True
else:
x.add(num)
return False
因课题原因，前面一段时间未更新，会补更。
在飞的小猪
