编程之美 数字中的技巧2

快速寻找满足条件的两个数

解法1

hashmap存数据,先遍历数组,查找hashmap中是否存在给定和-a[i]的值,时间复杂度O(n)

解法2

1.排序,2. 设定收尾指针,a[start]+a[end] < num,则star++,>,则end–,=,则return

子数组的最大乘积

给定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合中乘积最大的一组,并写出算法的时间复杂度

解法

s[i-1] i t[i+1]

如上图,array[]为初始数组

s[i]表示前i个元素的乘积,1<=i<=N,s[0] = 1,s[i] = s[i-1]*array[i-1]

t[i]表示数组后(N-i)个元素的乘积,1<=i<=N,t[N+1]=1, t[i] = t[i+1]*array[i]

p[] = s[i-1]*t[i+1]

方法:先分别从头到尾和从尾到头扫描数组两次,可得到s[]和t[],在遍历一次数组即可得到p[],时间复杂度为O(N)

求数组的子数组之和的最大值

所给数组A[0]…A[n-1]

解法1

动态规划思路:分治(大问题转换为小问题) + 元素和除该元素结果的关系

可以考虑数组的第一个元素A[0],以及最大的一段数组(A[i],…,A[j])和A[0]的关系:

  1. 当 0=i=j时,元素A[0]本身构成和最大的一段
  2. 当 0=i<j时,子数组之和由A[0]开始
  3. 当 0<i时,元素A[0]和子数组之和没有关系

All[0]=max{A[0],A[0]+start[1],All[1]},其中,start[1]表示子数组之和包含A[0],从A[1]开始的最大子数组之和,All[1]表示A[1]…A[j]的最大子数组之和。从尾开始遍历

int max(int[] A){
    int[] start = new int[A.length()];
    int[] All = new int[A.length()];
    for(int i = n-2; i >=0 ; i--){
        all[i] = Math.max(A[i],Math.max(A[i]+start[i+1],all[i+1]));
    }
    return all[0];
}

解法2

public int FindGreatestSumOfSubArray(int[] array) {
        int max = Integer.MIN_VALUE;
        int res = 0;
        for(int i = 0; i < array.length; i++){
            if(res >= 0){
                res = res + array[i];
            }else{
                res = array[i];
            }
            if(res > max){
                max = res;
            }
        }
        return max;
    }

若A[n-1]和A[0]收尾相邻,找和最大,把题目分为两种情况

  1. 解没有跨过A[n-1]到A[0](原问题)
  2. 解跨过A[n-1]到A[0]

对于第二种情况,只要找到从A[0]开始和最大的一段0…j(0 <= j < n),以及以A[n-1]结尾的和最大的一段i…n-1(0 <= i < n),和最大值M_2

M_2 = A[i]+...+A[n-1]+A[0]+...+A[j]

如果 i<=j

M_2 = A[0]+...+A[n-1]

否则

M_2 = A[0]+...+A[j]+A[i]+...+A[n-1]

求数组的子数组之和的最大值(二维)

二维数组求解最大值

解法1

首先计算区域和,然后排序比较,ps[i][j]表示区域0-i,0-j的所有元素之和

for(int i = 0; i <= n; i++)
    ps[i][0] = 0;
for(int j = 0; j <= m; j++)
    ps[0][j] = 0;
for(int i=1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        ps[i][j] = ps[i-1][j] + ps[i][j-1]-ps[i-1][j-1] + B[i][j]

时间复杂度O(N^2*M^2)

解法2

二维转一维

int MaxSum(int[] A, int n, int m){
    maximun = Integer.MIN_VALUE;
    for(int a = 0; a < n; a++){
        for(int c = a; c < n; c++){
            start = BC(a,c,m);
            All = BC(a,c,m);
            //一维数组的解法
        }
    }
}

其中 BC(a,c,i)表示在第a行和第c行之间的第i列的所有元素之和,即总体可看成一个一维数组。

数组分割???

  1. 有一个无序,元素个数为2n的正整数数组,要求:如何能把这个数组分割为元素个数为n的两个数组,并使两个子数组的和最接近

解法

假设数组A[1…2n]所有元素的和是SUM,模仿动态规划解0-1背包问题,令S(k,i)表示前k个元素中任意i个元素的和的集合,即S(k.i)={S1,S2…}.

  1. S(k, 1) = {A[i] | 1<= i <= k}
  2. S(k, k) = {A[1]+A[2]+…+A[k]}
  3. S(k, i) = S(k-1, i) U {A[k] + x | x属于S(k-1, i-1) }

按照这个递推公式来计算,最后找出集合S(2N, N)中与SUM/2最接近的那个和,这便是答案,这个算法的时间复杂度是O(2^N).

因为这个过程中只关注和不大于SUM/2的那个子数组的和。所以集合中重复的和以及大于SUM/2的和都是没有意义的,有意义的和的个数最多就是SUM/2个。所以,我们不需要记录S(2N,N)中都有哪些和,只需要从SUM/2到1遍历一次,逐个询问这个值是不是在S(2N,N)中出现,第一个出现的值就是答案。这个是网上C++版本的答案,本人实际上还不是太理解,如果有更好的解释方式,也请大牛们赐教

int arr[] = {0,1,5,7,8,9,6,3,11,20,17};
const int N=5;
const int SUM = 87;

// 模仿动态规划解0-1背包问题的策略
int solve1()
{
    int i , j , s;
    int dp[2*N+1][N+1][SUM/2+2];

    /*
    用dp(i,j,c)来表示从前i个元素中取j个、且这j个元素之和不超过c的最佳(大)方案,在这里i>=j,c<=S
    状态转移方程:   
    限第i个物品不取  
    dp(i,j,c)=max{dp(i-1,j-1,c-a[i])+a[i],dp(i-1,j,c)}
    dp(2N,N,SUM/2+1)就是题目的解。
    */
    //初始化
    memset(dp,0,sizeof(dp));

    for(i = 1 ; i <= 2*N ; ++i)
    {
        for(j = 1 ; j <= min(i,N) ; ++j)
        {
            for(s = SUM/2+1 ; s >= arr[i] ; --s)
            {
                dp[i][j][s] = max(dp[i-1][j-1][s-arr[i]]+arr[i] , dp[i-1][j][s]);
            }
        }
    }

    //因为这为最终答案 dp[2*N][N][SUM/2+1];
    i=2*N , j=N , s=SUM/2+1;
    while(i > 0)
    {
        if(dp[i][j][s] == dp[i-1][j-1][s-arr[i]]+arr[i])   //判定这个状态是由哪个状态推导出来的
        {
            cout<<arr[i]<<" ";    //取中arr[i]
            j--;
            s -= arr[i];
        }    
        i--;
    }
    cout<<endl;
    return dp[2*N][N][SUM/2+1];
}
Share