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