力扣刷题记录10.13

k

2024/10/13

（1）最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

1、动态规划法

维护一个dp数组，dp[i]表示以nums[i]做结尾的最长连续递增子序列长度。

外循环遍历数组的所有元素，内循环遍历在这个元素之前的元素，如果此元素大于之前的元素，则说明可以形成一个递增子序列。于是就可以做max比较确定dp[i]的大小。

最后遍历dp数组找到最长的长度。

时间复杂度：O（n^2）

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        if(n==0) return 0;
        vector<int> dp(n,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
    return *max_element(dp.begin(),dp.end());
    }
};

2、贪心＋二分查找

维护一个向量数组vec。这个数组的特点是：里面的元素保持严格递增，并且vec的长度是到nums[i]时，前面的最长递增子序列的长度。但是vec中的元素不一定是正确的子序列。

令len=1；vec[len]=nums[0];

怎么贪心呢？就是直接遍历数组，有两种情况：

• 如果nums[i]大于vec中最大的元素vec[len]，那么就直接把它放置入vec中，同时增加len的大小，即vec[++len]=nums[i];

• 否则的话，就找到vec中第一个大于它的元素，并将它的值替换过去。这样既没有改变vec的长度（没有错误），也可以使得维护了一个能容纳更大元素的序列。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size(),len=1;
        if(n==0) return 0;
        vector<int> vec(n+1);
        vec[1]=nums[0];
        for(int i=1;i<n;i++){
            if(nums[i]>vec[len]){
                vec[++len]=nums[i];
            }else{
                int l=1,r=len,pos=0;
                while(l<=r){
                    int mid=(l+r)>>1;
                    if(vec[mid]<nums[i]){
                        
                        l=mid+1;
                    }
                    else{
                        pos=mid;
                        r=mid-1;
                    }
                }
                vec[pos]=nums[i];
            }
        }
        return len;
    }
};

（2）动态规划

1、 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。

重点：不仅要维护最大值，还要维护最小值，因为有负数。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int minF=nums[0], maxF=nums[0], n=nums.size(),ans=nums[0];
        for(int i=1;i<n;i++){
            int mi=minF,mx=maxF;
            minF=min(mi*nums[i],min(mx*nums[i],nums[i]));
            maxF=max(mi*nums[i],max(mx*nums[i],nums[i]));
            ans=max(ans,maxF);
        }
        return ans;
    }
};

（3）图论

1、无向图的连通数

依次删除无向图中的点，依次返回其中的连通数。

#include "bits/stdc++.h"

using namespace std;
//dfs: 依次访问此节点连接的节点，并继续dfs。
void dfs(unordered_map <int ,vector<int> > ball,int j,vector<bool>& num){
    num[j]=true;  //注意一开始要赋值true！！！！
    for(int i=0;i<ball[j].size();i++){ 
        if(num[ball[j][i]]==false)   //注意这里只遍历未访问过的点！！！！！！！
            dfs(ball,ball[j][i],num);   //节点下标要搞清楚
    }
}

int main() {
    int n,m;
    cin>>n>>m;
    unordered_map <int ,vector<int> >  ball(n+1
    while(m){
        int u,v;
        cin>>u>>v;
        ball[u].push_back(v);
        ball[v].push_back(u);
        m--;
    }
    int i=1;
    while(i<=n){
        ball[i]={};  //不用删除含有它的节点的向量中的它
        int cnt=0;
        vector<bool> num(n+1,false);  //起始值
        for(int j=i+1;j<=n;j++){
            if(num[j]==false){
                cnt++;  //更新个数
                dfs(ball,j,num);
            }
        }
        cout<<cnt<<endl;
        i++;
    }
    return 0;
}

（4）数组

1、

给定一个数组，每次操作可以将相邻的两个值正负翻转，可以做无限次操作，问数组中所有元素累加起来的最大值。

这道题理清思路好简单，就是看负数是不是奇数个，如果是偶数个，就是返回所有值加在一起（也就是一定能够每个值都变成正的），如果是奇数个,那么一定会留下负数。所以直接用绝对值相加后的值减去所有数最小的绝对值*2。

int maxSum(vector<int> nums){
   int n=nums.size();
   int cnt=0,mx=INT_MAX,ans=0;
   for(int i=0;i<n;i++){
      ans+=abs(nums[i]);
      mi=min(mi,abs(nums[i]));
      if(nums[i]<0){
         cnt++;
      }
   }
   return cnt%2==0?ans:ans-mi*2;
}