为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 274554
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

t
有一个数组长度为N,里面的N个数的范围是[1, N-1],因此必有数是重复出现的。求一个算法找出这个数,要求时间复杂度为O(n),空间复杂度为O(1)。
#include<iostream>
#include
<algorithm>
using namespace std;
int main()
{
 
int a[]={1,2,4,3,6,3,4};
 
int tmp,tmp2;
 tmp
=a[0];
 
while(1)
 {
  
if(a[tmp]!=-1)
  {
   tmp2
=a[tmp];
   a[tmp]
=-1;
   tmp
=tmp2;
  }
  
else break;
 }
 printf(
"%d\n",tmp);
}




用两个栈实现队列
#include
<iostream>
#include
<stack>
using namespace std;
stack
<int>stackA,stackB;
void enqueue(int x)
{
 stackA.push(x);
}
int dequeue()
{
 
if(stackB.empty())
 {
  
while(!stackA.empty())
  {
   stackB.push(stackA.top());
   stackA.pop();
  }
 }
 
if(stackB.empty())
  
return -1;
 
int val=stackB.top();
 stackB.pop();
 
return val;
}
int main()
{
 
char ch;
 
int i=0;
 
while(cin>>ch)
 {
  
if(ch=='e')
  {
   enqueue(i
++);
  }
  
else cout<<dequeue()<<endl;
 }
}




题目概述:有一个没有排序,元素个数为2N的正整数数组。要求把它分割为元素个数为N的两个数组,并使两个子数组的和最接近。
假设数组A[1..2N]所有元素的和是SUM。模仿动态规划解0-1背包问题的策略,令S(k, i)表示前k个元素中任意i个元素的和的集合。显然:
S(k, 1) = {A[i] | 1<= i <= k}
S(k, k) = {A[1]+A[2]+…+A[k]}
S(k, i) = S(k-1, i) U {A[k] + x | x属于S(k-1, i-1) }
按照这个递推公式来计算,最后找出集合S(2N, N)中与SUM最接近的那个和,这便是答案。这个算法的时间复杂度是O(22N).
因 为这个过程中只关注和不大于SUM/2的那个子数组的和。所以集合中重复的和以及大于SUM/2的和都是没有意义的。把这些没有意义的和剔除掉,剩下的有 意义的和的个数最多就是SUM/2个。所以,我们不需要记录S(2N,N)中都有哪些和,只需要从SUM/2到1遍历一次,逐个询问这个值是不是在 S(2N,N)中出现,第一个出现的值就是答案。我们的程序不需要按照上述递推公式计算每个集合,只需要为每个集合设一个标志数组,标记SUM/2到1这 个区间中的哪些值可以被计算出来。关键代码如下:

for(i = 0; i < N+1; i++)  
    for(j = 0; j < sum/2+1; j++)  
        flag[i][j] = false;  
flag[0][0] = true;  
for(int k = 1; k <= 2*N; k++) {  
    for(i = k > N ? N : k; i >= 1; i--) {  
        //两层外循环是遍历集合S(k,i)  
        for(j = 0; j <= sum/2; j++) {  
            if(j >= A[k] && flag[i-1][j-A[k]])  
                flag[i][j] = true;  
        }  
    }  
}  
for(i = sum/2; i >= 0; i--) {  
    if(flag[N][i]) {  
        cout << "minimum delta is " << abs(2*i - sum) << endl;  
        break;  
    }  

posted on 2010-08-04 07:52 baby-fly 阅读(158) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理