3502. 到达每个位置的最小费用
问题:
给你一个长度为 n 的整数数组 cost 。当前你位于位置 n（队伍的末尾），队伍中共有 n + 1 人，编号从 0 到 n 。
你希望在队伍中向前移动，但队伍中每个人都会收取一定的费用才能与你 交换位置。与编号 i 的人交换位置的费用为 cost[i] 。
你可以按照以下规则与他人交换位置：
- 如果对方在你前面，你 必须 支付
cost[i]费用与他们交换位置。 - 如果对方在你后面，他们可以免费与你交换位置。
返回一个大小为 n 的数组 answer，其中 answer[i] 表示到达队伍中每个位置 i 所需的 最小 总费用。
思路:
到达每个位置的最小费用就是在包含了自身的前缀中取最小值,所以只需维护当前最小值逐位存储即可
复杂度:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)
代码:
class Solution {
public int[] minCosts(int[] cost) {
int min = cost[0];
int[] res = new int[cost.length];
res[0] = min;
for(int i=1;i<cost.length;i++){
if(cost[i]<min){
min = cost[i];
}
res[i] = min;
}
return res;
}
}
718. 最长重复子数组
跳转: 718. 最长重复子数组
问题:
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
思路:
动态规划.
比较容易理解的一种递推方式是增加前缀,前缀能匹配就是后一个的最大前缀数+1,不匹配就归零.
或者也可以顺着思考,拿一个和另一个做比较,只记连续的数量,断开就要清零.
复杂度:
- 时间复杂度: O ( n ∗ m ) O(n*m) O(n∗m)
- 空间复杂度: O ( m i n ( m , n ) ) O(min(m,n)) O(min(m,n))
代码:
class Solution {
public int findLength(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int n = nums1.length;
int m = nums2.length;
int ans = 0;
int[] fn = new int[m+1];
for(int i=0;i<n;i++){
for(int j=m-1;j>=0;j--){
fn[j+1] = nums1[i]==nums2[j]?fn[j]+1:0;
ans = Math.max(ans,fn[j+1]);
}
}
return ans;
}
}
3507. 移除最小数对使数组有序 I
问题:
给你一个数组 nums，你可以执行以下操作任意次数：
- 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
- 用它们的和替换这对元素。
返回将数组变为 非递减 所需的 最小操作次数 。
如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。
思路:
暴力模拟,在判断时记录最小位置,方便合并操作.
min不能开太小,太小了有可能多数合并超过min
复杂度:
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( n ) O(n) O(n)
代码:
class Solution {
int min = 50001;
int start=0;
public int minimumPairRemoval(int[] nums) {
int count = 0;
while(!isNonDecreasing(nums)){
count+=1;
nums = getMerge(nums);
// System.out.println(Arrays.toString(nums));
}
return count;
}
boolean isNonDecreasing(int[] nums){
boolean res = true;
for(int i=1;i<nums.length;i++){
if(nums[i]<nums[i-1]) res = false;
int tmp = nums[i]+nums[i-1];
if(tmp<min){
min = tmp;
start = i-1;
}
}
return res;
}
int[] getMerge(int[]nums){
int[] res = new int[nums.length-1];
int j = 0;
for(int i=0;i<nums.length&&j<nums.length-1;i++){
if(i==start){
res[j++] = min;
min = 50001;
i++;
}
else res[j++] = nums[i];
}
return res;
}
}
368. 最大整除子集(每日一题)
跳转: 368. 最大整除子集
问题:
给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
answer[i] % answer[j] == 0，或answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。
思路:
先排序,方便判断余数
状态变量的含义为以当前元素结尾的整除子集的数量
记录好最大状态,然后遍历状态数组求出一个有效子集即可
复杂度:
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( n ) O(n) O(n)
代码:
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int[] fn = new int[n];
Arrays.fill(fn, 1);
int max = 1;
int maxValue=0;
for (int i = 1; i < n; i++) {
for (int k = i - 1; k >= 0; k--) {
if (nums[i] % nums[k] == 0) {
fn[i] = Math.max(fn[i], fn[k] + 1);
}
}
if (fn[i] > max) {
max = Math.max(max, fn[i]);
maxValue = nums[i];
}
}
// System.out.println(max);
List<Integer> res = new ArrayList<>();
for(int i=n-1;i>=0&&max>0;i--){
if(fn[i]==max&&maxValue%nums[i]==0){
maxValue = nums[i];
res.add(nums[i]);
max--;
}
}
return res;
}
}
5. 最长回文子串
跳转: 5. 最长回文子串
问题
给你一个字符串 s，找到 s 中最长的 回文 子串。
思路:
遍历字符串长度和初值,并特判长度为3以内的情况,记录最大值的长度和初值直接返回子串
复杂度:
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( n ) O(n) O(n)
代码:
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n+1][n];
int max = 1;
int begin = 0;
Arrays.fill(dp[1],true);
for(int i=2;i<=n;i++){
for(int j=0;j<=n-i;j++){
int e = j+i-1;
if(s.charAt(j)==s.charAt(e))
if(i<3){
dp[i][j] = true;
}else{
dp[i][j] = dp[i-2][j+1];
}
else dp[i][j] = false;
if(dp[i][j]&&i>max){
max = i;
begin = j;
}
}
}
return s.substring(begin,begin+max);
}
}
总结
今天去试了一下周赛,就做出了一个,第二题用哈希加遍历统计就直接超时了
做了一些动态规划的题目,感觉对动态规划的题目不够熟练