头像

acw_lyl


访客:4461

离线:3天前



acw_lyl
3天前

题目描述

使用字符串哈希的方式,时间复杂度为O(NlgN)

#include<iostream>
#include<string.h>
#include<algorithm>

using namespace std;

typedef unsigned long long ULL;
const int N=2000010,base=131;
ULL hl[N],hr[N],p[N];

char str[N];

ULL get_hash(ULL h[],int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}


int main(){
    int t=1;
    while(scanf("%s",str+1),strcmp(str+1,"END")){
        int n=strlen(str+1);
        //先将"#"插入原数组
        for(int i=2*n;i;i-=2){
            str[i]=str[i/2];
            str[i-1]='#';
        }
        n=2*n;
        p[0]=1;
        //字符串哈希过程
        for(int i=1,j=n;i<=n;i++,j--){
            hl[i]=hl[i-1]*base+str[i]-'a'+1;//正序
            hr[i]=hr[i-1]*base+str[j]-'a'+1;//逆序
            p[i]=p[i-1]*base;
        }

        //以每个点为中心,二分查找最大的相等的两端
        int ans=0;
        for(int i=1;i<=n;i++){
            int l=0,r=min(i-1,n-i);
            while(l<r){
                int mid=l+r+1>>1;
                if(get_hash(hl,i-mid,i-1)!=get_hash(hr,n+1-(i+mid),n+1-(i+1))) r=mid-1;
                else l=mid;
            }

            if(str[i-l]<='z'&&str[i-l]>='a') ans=max(ans,l+1);//如果查到的回文串的两端不是 # 的话,说明字符要多一个
            else ans=max(ans,l);
        }
        printf("Case %d: %d\n",t++,ans);

    }
    return 0;
}


活动打卡代码 LeetCode 1478. 安排邮筒

acw_lyl
4天前
class Solution {
public:
    int minDistance(vector<int>& h, int m) {
        //最简单的版本:如果只放一个油桶,那么我们将其放在中位数即可。
        //那么我们要是放置k个邮筒,那么可以采用dp的方式,将数组划分成k端,然后在每一个段上放一个邮筒
        //状态设计:f[i][j]:表示将1-i划分成j段,最小的距离总和
        //转移,枚举最后一段位置,f[i][j]=min(f[i][j],f[t-1][j-1]+cost(t,i))
        //cost(t,i)表示从t~i这段的最短距离和,是可以预处理出来的
        //时间复杂度,最外层循环i,j  --》O(NK)
        //内层循环最后一段的位置,   --->O(N)
        //总的时间复杂度为O(N^2*K)

        sort(h.begin(),h.end());
        int n=h.size();
        //首先预处理出来  每个区间段  的距离总和cost[i,j]
        vector<vector<int>>cost(n,vector<int>(n));
        for(int i=0;i<n;i++)
            for(int j=i;j<n;j++)
                for(int k=i;k<=j;k++)
                    cost[i][j]+=abs(h[k]-h[(j-i+1)/2+i]);

        //
        const int INF=0x3f3f3f3f;
        vector<vector<int>>f(n,vector<int>(m+1,INF));
        //初始化f[0][i]=0;
        for(int i=1;i<=m;i++) f[0][i]=0;

        for(int i=1;i<n;i++)
            for(int j=1;j<=m;j++){
                for(int k=0;k<=i;k++)
                {
                    if(!k) f[i][j]=min(f[i][j],cost[k][i]);
                    else
                        f[i][j]=min(f[i][j],f[k-1][j-1]+cost[k][i]);
                }

            }
        return f[n-1][m];
    }
};



acw_lyl
5天前

暴力解法,O(n3),遍历每一个位置,然后,从每一个位置向左遍历,比较当前高度的最小值

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int ans=0;
        int n=mat.size(),m=mat[0].size();
        vector<vector<int>>h(n,vector<int>(m,0));
        //预处理出来每个点往上查能有多少个1
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                if(mat[i][j]==0) h[i][j]=0;
                else{
                    h[i][j]=1;
                    if(i)h[i][j]+=h[i-1][j];
                    int max_h=n;
                    for(int k=0;j-k>=0&&mat[i][j-k];k++){
                        max_h=min(max_h,h[i][j-k]);
                        ans+=max_h;
                    }
                }
            }
        return ans;
    }
};

单调栈:遍历每一行,每一行维护一个单调栈,单调栈单调上升,里面存的是下标和总数。

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int ans=0;
        int n=mat.size(),m=mat[0].size();
        vector<vector<int>>h(n,vector<int>(m,0));
        //预处理出来每个点往上查能有多少个1
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mat[i][j]){
                    h[i][j]=1;
                    if(i) h[i][j]+=h[i-1][j];
                }
            }
        }
        for(int i=0;i<n;i++){
            stack<pair<int,int>>stk;
            for(int j=0;j<m;j++)
            {
                while(stk.size()&&h[i][stk.top().first]>=h[i][j]) stk.pop();
                int s=0;
                if(stk.size()){
                    s+=stk.top().second;
                    s+=(j-stk.top().first)*h[i][j];
                }else s+=(j+1)*h[i][j];

                ans+=s;
                stk.push({j,s});
            }
        }    
        return ans;
    }
};



acw_lyl
5天前
class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int ans=0;
        for(int i=0;i<left.size();i++){
            ans=max(ans,left[i]);
        }
        for(int i=0;i<right.size();i++)
            ans=max(ans,n-right[i]);
        return ans;
    }
};



acw_lyl
5天前
class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(),arr.end());
        for(int i=0;i<arr.size()-2;i++){
            if(arr[i]-arr[i+1]!=arr[i+1]-arr[i+2]) 
                return false;
        }
        return true;
    }
};



acw_lyl
5天前
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& p, int k) {
        deque<pair<int,int>>q;
        int n=p.size();
        int ans=INT_MIN;
        for(int i=0;i<n;i++){
            while(q.size()&&p[i][0]-q.front().first>k) q.pop_front();

            if(!q.empty()) {
                ans=max(ans,p[i][0]+p[i][1]+q.front().second-q.front().first);
                while(q.size()&&p[i][1]-p[i][0]>=q.back().second-q.back().first) q.pop_back();
            } 
            q.push_back({p[i][0],p[i][1]});
        }

        return ans;
    }
};



acw_lyl
5天前
class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int n=nums.size(),mod=1e9+7;
        vector<int>p(n);
        p[0]=1;
        for(int i=1;i<n;i++) p[i]=p[i-1]*2%mod;//预处理2的多少次方

        int ans=0;
        for(int i=0,j=n-1;i<=j;i++){
            while(j>=i&&nums[j]+nums[i]>target) j--;
            if(j>=i&&nums[j]+nums[i]<=target)   
                ans=(ans+p[j-i])%mod;
        }
        return ans;
    }
};



acw_lyl
13天前
class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        //这个题看时间复杂度大概就是个O(N),或者O(lg(N))。
        //思路:双指针算法,但是由于要求两端,所以需要使用记忆话,提前将走过的路,记忆下来
        //f[i]表示,前i个节点中综合为target的最短距离
        //那么更新ans=min(ans,i-j+1+f[j-1])
        //更新f[i]=min(i-j+1,f[i-1]),划分为选第i个节点还是不选第i个节点。
        int n=arr.size();
        vector<int>f(n,1e6);

        int sum=0;
        int ans=INT_MAX;
        for(int i=0,j=0;i<n;i++){
            sum+=arr[i];
            while(sum>target) sum-=arr[j++];
            if(sum==target){
                if(j) ans=min(ans,i-j+1+f[j-1]);
                f[i]=i-j+1;
            }
            if(i)f[i]=min(f[i],f[i-1]);
        }
        if(ans>1e6) return -1;
        return ans;
    }
};


活动打卡代码 LeetCode 1476. 子矩形查询

acw_lyl
13天前
public:
    vector<vector<int>>nums;
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        nums=rectangle;
    }

    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for(int i=row1;i<=row2;i++){
            for(int j=col1;j<=col2;j++){
                nums[i][j]=newValue;
            }
        }
    }

    int getValue(int row, int col) {
        return nums[row][col];
    }
};



acw_lyl
13天前
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        vector<int>ans;
        stack<int>stk;

        int n=prices.size();
        for(int i=n-1;~i;i--){
            while(stk.size()&&prices[i]<prices[stk.top()]) stk.pop();
            if(stk.empty())     ans.push_back(prices[i]);
            else{
                ans.push_back(prices[i]-prices[stk.top()]);
            }
            stk.push(i);
        }
        return vector<int>(ans.rbegin(),ans.rend());
    }
};