lintcode 子数组问题(最全的面试子数组问题)

前言

2017年的六月份到九月份,陆陆续续在leetcode上面刷了130道题目。

眼瞅着明年开年就要开始求职找实习。于是重新开始了一波刷题。

现在的选择是使用lintcode,相比leetcode,我认为lintcode更好的是:

1.有中文版的,用起来比较熟悉。
2.记笔记比较方便。
3.题目比leetcode一些,题不在多,在于精。
4.可以创建群组,一起刷题,看到群里刷题动态(包括代码和笔记)。
5.有倒计时功能。(一般简单15min,中等30min,困难45min),这个比较能模拟真实面试场景。

正题

这次参与刷题的一共有四人(嘟嘟、琼琼、东东、博主 )。

41.最大子数组
dp[i] = max(dp[i-1],0)+a[i] (空间可用O(1))
42.最大子数组2
找两个不重叠的子数组,让和最大。
双向DP。(前向后向分别找最大)
43.最大子数组3
给一个k,找出k个不重叠的子数组,让和最大。
local[i][m]表示到第i个位置,分为m个子数组的局部最大和(最后一个子数组包含第i个元素)
global[i][m]表示到第i个位置,分为m个子数组的全局最大和(最后一个子数组不一定包含第i个元素)
要这样去分,是因为状态转移的时候需要用到。比如第i+1个位置的元素能不能拼到最后一个子数组里,还是另开一个子数组。
状态转移方程为:
local[i][m] = max(global[i-1][m-1],local[i-1][m])+nums[i] (需要包含第i个元素,max里面第一项表示新开一个子数组,第二项表示把第i个元素拼到最后一个子数组上)
global[i][m] = max(local[i][m],global[i-1][m])(从当前局部最大和之前的全局最大中找)
AC代码:
class Solution {
public:
    /*
     * @param nums: A list of integers
     * @param k: An integer denote to find k non-overlapping subarrays
     * @return: An integer denote the sum of max k non-overlapping subarrays
     */
    int maxSubArray(vector<int> &nums, int k) {
        // write your code here
        //到第i个位置在内,分为m个不重叠的子数组
        //要看包含第i-1个位置(分为m个),到第i-1个位置、不一定包含第i-1个位置(分为m-1个)
        
        int len = nums.size();
        vector<vector<int> > local(len,vector<int>(k)); //一定包含第i位置
        vector<vector<int> > global(len,vector<int>(k)); //不一定包含第i个位置
        
        for(int i=0;i<len;++i){
            for(int m=0;m<k;++m){
                if(m>i) break;
                if(m==0){
                    local[i][m] = i==0?nums[i]:max(local[i-1][m],0)+nums[i];
                    global[i][m] = i==0?nums[i]:max(local[i][m],global[i-1][m]);
                }
                else{
                    local[i][m] = i-1>=m?max(global[i-1][m-1],local[i-1][m])+nums[i]:global[i-1][m-1]+nums[i];
                    global[i][m] = i-1>=m?max(local[i][m],global[i-1][m]):local[i][m];
                }
            }
        }
        return global[len-1][k-1];
    }
};

44.最小子数组
和41最大子数组类似

45.最大子数组差
和42最大子数组2类似。
双向DP。(前向最大 后向最小)和(前向最小 后向最大)

138.子数组之和
找到和为0的子数组,返回起始位置和结束位置。
sum[i]记录到0位置到i位置的和,O(n^2)方法会超时。【python的O(n^2)可以过,面试估计就GG了。。】
类似2 sum的题目,使用map,把之前的和都存到map中。
存在的话,说明已经找到了。
初始化map[0]=-1;
AC代码:
class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    vector<int> subarraySum(vector<int> &nums) {
        // write your code here
        int len=nums.size(), sum=0;
        vector<int> res(2);
        map<int,int> mp;
        mp[0]=-1;
        
        for(int i=0;i<len;++i){
            sum+=nums[i];
            if(mp.find(sum)!=mp.end()){
                res[0]=mp[sum]+1,res[1]=i;
                return res;
            }
            mp[sum]=i;
        }
    }
};

139.最接近零的子数组和
sum[i]表示0到i位置的和,那么求sum[j]-sum[i]就可以求得子数组和,然后再选择最小的。这样时间是O(n^2),我们只需要找最接近0的,那么我们何不将这些sum数组排序,然后挨着的两个找呢。
191.乘积最大子序列
比较笨拙的办法是我之前使用的:
由于要求最大乘积,而且都是整数。那么我们只用考虑负数的个数即可,如果是偶数,全部连乘即可。如果是奇数个,那么只用考虑最左边的负数(左右两边分别单独连乘)和最右边的负数(左右两边分别单独连乘)。然后需要用0来做边界。
后来和同学讨论,发现这题其实很简单。。。
由于是连乘最大。我们只用保留之前的最大和最小即可。(最小的乘以负数变为最大)
两种方法都可以过,但是第二种写起来会简单许多:乘积最大子序列
402.连续子数组求和
类似41,只是需要返回边界。可以使用双指针,或者先得到右边界再算左边界
617.最大平均子数组(好题!!)
长度大于等于K的子数组平均值最大。
拿到这题首先是没有思路,想到的方法只能是O(n^2),但是提示我会超时,n的个数达到10^4。

我们的目标是求这个平均值,那这个值的范围在哪里呢?
令数组中最小元素为min,最大值为max。那么平均值的范围必须是[min,max]

我们设平均值为x,如果有一个O(n)的方法能判断长度大于等于K的子数组平均值大于x或者小于等于x,这样时间复杂度就变成了O(n*log2(max-min))。因为我们将left=min,right=max,mid=(left+right)/2,如果最大平均值大于mid,直接让left=mid;如果最大平均值小于等于mid,让right=mid。

我们使用sum[i]表示0位置到i位置的元素之和。 由于之前是平均值不确定,数组的长度不确定,i到j的平均值为(sum[j]-sum[i])/(j-i)。这样的计算必须是O(n^2)。
而现在我们只需要判断最大平均值是不是大于mid。我们将每个元素都减去mid,我们现在只需要判断最大平均值是不是大于0。而(sum[j]-sum[i])/(j-i)是不是大于0,直接等价为sum[j]-sum[i]是不是大于0

而算sum[j]-sum[i]里的最大值不需要枚举每个i和j。我们在遍历数组的时候只需要记录和位置j 距离为k以上的最小值即可。而这个最小值是可以很轻易的得到的。

AC代码:
class Solution {
public:
    /*
     * @param nums: an array with positive and negative numbers
     * @param k: an integer
     * @return: the maximum average
     */
    double maxAverage(vector<int> &nums, int k) {
        int len = nums.size();
        double l=nums[0],r=nums[0],mid,eps=1e-6;
        vector<double> sum(len+1);
        for(int i=1;i<len;++i){
            l = min(l,double(nums[i]));
            r = max(r,double(nums[i]));
        }
        
        while(r-l>eps){
            mid = (r+l)/2;
            double pre=0;
            bool flag=false;
            
            sum[0]=0;
            for(int i=1;i<=len;++i)
                sum[i]=sum[i-1]+nums[i-1]-mid;
            
            for(int i=k;i<=len;++i){
                if(sum[i]-pre>eps){
                    flag=true;
                    break;
                }
                pre = min(pre,sum[i-k+1]);
            }
            if(flag) l=mid;
            else r=mid;
        }
        return r;
    }
};


番外
想到了最近今日头条实习生面试的一道题目。
题意是让求一个子数组,让子数组里的最小元素乘以子数组的和最大。(最小数字*区间和 最大)
这个题目的来源是POJ 2796

当然O(n^2)的方法面试官当然是不满意的。
现在最主要的问题是确定每个数字的边界,在左边找一个比它大的第一个元素位置,在右边找一个比它大的第一个元素的边界。然后计算每个数字乘以对应的区间和即可。

如何找每个数字的边界,一般的做法是维护一个单调递增栈。遍历数组,如果比栈顶大,就入栈,如果比栈顶小,说明边界找到了。(如果比栈顶小,那么栈顶元素的左边界是次顶元素的位置,右边界是当前元素的位置)
AC代码:(nums[i]用cin的话会超时,scanf有输入优化)
#include<iostream>
#include<stack>
#include<cstdio>
#define maxn 100005
using namespace  std;

long long nums[maxn];
long long sum[maxn]; //记录和

int main(){
    int n,i;
    int l,r; //结果的左边界,右边界。
    long long ans,tmp; //最后的结果

    while(cin>>n){
        ans = l = r =  0;
        stack<int> stac; //单调递增栈
        for(i=0;i<n;++i){
            scanf("%lld",&nums[i]);
            sum[i]=i==0?nums[i]:sum[i-1]+nums[i];
        }
        nums[n]=0;

        for(i=0;i<=n;++i){
            while(!stac.empty()&&nums[stac.top()]>nums[i]){
                long long cur = nums[stac.top()];
                stac.pop();
                if(stac.empty()) tmp = sum[i-1]*cur;
                else tmp = (sum[i-1]-sum[stac.top()])*cur;
                if(tmp>ans) ans=tmp,r=i-1,l=stac.empty()?0:stac.top()+1;
            }
            stac.push(i);
        }
        cout<<ans<<endl;
        cout<<l+1<<" "<<r+1<<endl;
    }
    return 0;
}

同样的类型还有leetcode 84
给一个数组,让求数组构成的图里面的最大矩形。


问题来了,在左边找一个比它大的第一个元素位置,在右边找一个比它大的第一个元素的边界。然后计算每个数字乘以对应的区间长度即可。
是不是和上面的题目特别相似啊。。。
AC代码:
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size(),res=0;
        heights.push_back(0);
        
        stack<int> stac;
        for(int i=0;i<=len;++i){
            while(!stac.empty()&&heights[stac.top()]>heights[i]){
                int tmp = heights[stac.top()];
                stac.pop();
                tmp = stac.empty()?tmp*i:tmp*(i-1-stac.top());
                res = max(res,tmp);
            }
            stac.push(i);
        }
        return res;
    }
};
相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院