暑期练习
0705
494. 目标和
首先考虑了使用dfs但是结果超时
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
def dfs(nums,target,index,n):
if n==index:
if target==0:
return 1
else :
return 0
return dfs(nums,target-nums[index],index+1,n)+dfs(nums,target+nums[index],index+1,n)
return dfs(nums,target,0,len(nums))
接着使用dp得到结果
遍历[-1000,1000]的所有可能性
j + 1000是为了变量的映射
dp[i-1][j + 1000]可以直接跳到dp[i][j + nums[i] + 1000]和dp[i][j - nums[i] + 1000]，理由是i-1 \(\rightarrow\) i只需要\(\pm\) nums[i]+1000,原因是dp[i][j]是i个数组成数字j的方案数。
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
dp = [[0] * 2001 for _ in range(n)]
dp[0][nums[0] + 1000] += 1
dp[0][-nums[0] + 1000] += 1
for i in range(1, n):
for j in range(-1000, 1001):
if dp[i-1][j + 1000] > 0:
dp[i][j + nums[i] + 1000] += dp[i-1][j + 1000]
dp[i][j - nums[i] + 1000] += dp[i-1][j + 1000]
return dp[n-1][target + 1000]
3115. 质数的最大距离
"""
简单的判断，双指针左右同时搜索，遇到第一个质数就停下，如果两个指针都停下就结束返回结果
需要注意的重点是continue不要忘记，遇到了质数之后指针不需要继续向前，以及while f or r:，应该是两个指针都查找到才停止，只要有一个没有找到就应该继续，所以需要使用or而不是and。
"""
class Solution:
def maximumPrimeDifference(self, nums: List[int]) -> int:
def is_prime(num):
if num <= 1:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True
n=len(nums)
left=0
right=n-1
f,r=True,True
while f or r:
if f:
if is_prime(nums[left]):
f=False
continue
left+=1
if r:
if is_prime(nums[right]):
r=False
continue
right-=1
return right-left
//Java
class Solution {
public int maximumPrimeDifference(int[] nums) {
int n=nums.length;
int left=0;
int right=n-1;
boolean f = true;
boolean r = true;
while (f || r) {
if (f) {
if (isPrime(nums[left])) {
f = false;
continue;
}
left++;
}
if (r) {
if (isPrime(nums[right])) {
r = false;
continue;
}
right--;
}
}
return right - left;
}
private boolean isPrime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}
3099. 哈沙德数
#非常基础
class Solution {
public int sumOfTheDigitsOfHarshadNumber(int x) {
int sum=0;
int temp=x;
while (temp>0){
sum += temp % 10;
temp /= 10;
}
if (x%sum==0){
return sum;
}
else{
return -1;
}
}
}
3033. 修改矩阵
#基础题
class Solution:
def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
m=len(matrix)
n=len(matrix[0])
record=[]
ma=[0]*n
for i in range(n):
for j in range(m):
if matrix[j][i]==-1:
record.append([j,i])
ma[i]=max(ma[i],matrix[j][i])
for j,i in record:
matrix[j][i]=ma[i]
return matrix
0706
3101. 交替子数组计数
"""
本题重点是理解，dp[i]的状态，我这里假设的是以nums[i]为结尾的子数组为交替子数组的数量，所以结尾需要sum(dp)
装填转移方程为1.
$$
dp[i]=dp[i-1]+1 if nums[i] != nums[i-1]
dp[i]=1 if nums[i] = nums[i-1]
$$
举[1,2,2,1]作为例子
i=0时显然dp[0]=1,i=1的时候dp[1]=1+1=2{[2],[1,2]两种[1]不算在内，因为假设的是以nums[i]为结尾的子数组为交替子数组的数量)}
dp[2]=1,dp[3]=2
return 1+2+2+1=6
"""
class Solution:
def countAlternatingSubarrays(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 1
dp= [1] * n
dp[1]= 2 if nums[0] != nums[1] else 1
for i in range(2,n):
if nums[i] != nums[i-1]:
dp[i] = dp[i-1]+1
else:
dp[i] = 1
return sum(dp)
接下来是用时和内存的改进，使用滚动数组,因为我们注意到状态只和前一个状态有关也就是dp[i]只会和dp[i-1]有关，因此我们只需要一个参数last记录前一状态即可
class Solution:
def countAlternatingSubarrays(self, nums: List[int]) -> int:
n = len(nums)
res=1
if n == 1:
return res
last=2 if nums[0]!=nums[1] else 1
res+=last
for i in range(2,n):
if nums[i] != nums[i-1]:
last = last+1
else:
last = 1
res+=last
return res
0707
1958. 检查操作是否合法
#纯纯折磨人，枚举
class Solution:
def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
# 判断每个方向是否存在以操作位置为起点的好线段
def check(dx: int, dy: int) -> bool:
x, y = rMove + dx, cMove + dy
step = 1 # 当前遍历到的节点序号
while 0 <= x < 8 and 0 <= y < 8:
if step == 1:
# 第一个点必须为相反颜色
if board[x][y] == "." or board[x][y] == color:
return False
else:
# 好线段中不应存在空格子
if board[x][y] == ".":
return False
# 遍历到好线段的终点，返回 true
if board[x][y] == color:
return True
step += 1
x += dx
y += dy
# 不存在符合要求的好线段
return False
# 从 x 轴正方向开始逆时针枚举 8 个方向
dx = [1, 1, 0, -1, -1, -1, 0, 1] # 行改变量
dy = [0, 1, 1, 1, 0, -1, -1, -1] # 列改变量
for k in range(8):
if check(dx[k], dy[k]):
return True
return False
100339. 找出加密后的字符串
class Solution:
def getEncryptedString(self, s: str, k: int) -> str:
n = len(s)
ret = ""
for i in range(n):
tmp = (i+k)%n
ret += s[tmp]
return ret
100328. 生成不含相邻零的二进制字符串
class Solution:
def validStrings(self, n: int) -> List[str]:
if n == 1:
return ["0", "1"]
queue = deque([["0", "0"]])
queue.append(["1", "1"])
res = []
while queue:
q = queue.popleft()
if len(q[1]) == n:
res.append(q[1])
else:
if q[0] == "0":
queue.append(["1", q[1] + "1"])
if q[0] == "1":
queue.append(["0", q[1] + "0"])
queue.append(["1", q[1] + "1"])
return res
100359. 统计 X 和 Y 频数相等的子矩阵数量
class Solution:
"""
使用prefix_x_count[i][j]记录[0][0] &\rightarrow& [i][j]位置的前缀和x的总数，使用prefix[i][j]记录 [0][0] &\rightarrow& [i][j]位置的 x - y的差值
"""
def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
prefix = [[0] * n for _ in range(m)]
prefix_x_count = [[0] * n for _ in range(m)]
res = 0
for i in range(m):
for j in range(n):
x = 1 if grid[i][j] == 'X' else 0
if i > 0:
x += prefix_x_count[i - 1][j]
if j > 0:
x += prefix_x_count[i][j - 1]
if i > 0 and j > 0:
x -= prefix_x_count[i - 1][j - 1]
prefix_x_count[i][j] = x
for i in range(m):
for j in range(n):
x = 1 if grid[i][j] == 'X' else 0
y = 1 if grid[i][j] == 'Y' else 0
if i > 0:
x += prefix[i - 1][j]
if j > 0:
x += prefix[i][j - 1]
if i>0 and j>0:
x -= prefix[i - 1][j - 1]
prefix[i][j] = x - y
if prefix[i][j] == 0 and prefix_x_count[i][j] >0:
res += 1
return res