C++博客-021742

一道算法面试题，大家讨论看看

猪头饼 — Thu, 22 Mar 2007 15:14:00 GMT

题目：

从1到N(100000)中任意拿掉两个数，把剩下的99998个数顺序打乱，并且放入数组A中。要求只扫描一遍数组，把这两个数找出来。可以使用最到不超过5个局部变量，不能用数组变量，并且不能改变原数组的值。

思路：

遍历一次数组，求出这两个数的和a+b 与积a*b
a+b = 1+2+3+4+...+N- sum(A[]);    (1)
a*b = 1*2*3*4*...*N / multi(A[]);   (2)

主要解决sum与multi的溢出问题

(1) 可化为 (N-A[0]) + (N-1-A[1]) + ...+ (3-A[N-3]) + 2 + 1

(2) 可以用对数来代替原数进行求积的等价运算,避免溢出的问题，但是这种方法会产生一些精度上的问题，不知道大家有什么更好的方法！
先求出log(a*b) :
                         = log(1*2*3*4*....*N)/log(A[0]*A[1]*A[2]*...*A[N-3])
                         = log(N)-log(A[0]) + log(N-1)-log(A[1]) + ... +log(3)-log(A[N-3]) + log(2) + log(1)

知道了两数的和与积,由此就可以计算出a跟b的值来.

代码如下：

#include <iostream>
#include <Ctime>
#include <Cmath>
using namespace std;

#define N 100000

//生成不同的随机数的数组
void GetDiffRandomNum(int A[], int n)
{
    srand(unsigned(time(NULL)));
    int i=0;

    for(int index = n-1; index > 0; index--)
    {
        i = rand() % index;
        swap(A[i], A[index]);
    }

}

int main()
{

    int A[N]={0};
    for(int i=0; i<N; i++)
    {
        A[i] = i+1;
    }
    GetDiffRandomNum(A, N);
    //DISPLAY(A, N);

    unsigned int sum = 0;
    double logSum = 0;

    for(i=0; i<N-2; i++)
    {
        sum += N-i-A[i];
        logSum += log(N-i)-log(A[i]);
    }
    sum += 2 + 1;
    logSum += log(2)+log(1);

    double multi = exp(logSum);

    //两数的和与积
    cout<<int(sum)<<'\t'<<int(multi)<<endl;

    //求出两数
    for(i=1; i<=N; i++)
    {
        double temp = i*(sum-i);
        if(multi-0.5<=temp && temp <= multi+0.5)
            cout<<i<<'\t'<<int(sum-i)<<endl;
    }

    return 0;
}

PS（谢谢枝~的帮助）请大家指导

//................................
通过大家的帮助：
得到另一个写法，不会产生精度问题

(1+N)*N /2 - S = a + b
1/6 * n*(n + 1)*(2n + 1) - X = a*a + b*b

注：
1/6 * n*(n + 1)*(2n + 1)=1*1 + 2*2 + 3*3 +...+N*N
X = A[0]*A[0] + A[1]*A[1] +...A[N-3]*A[N-3]

==>
a + b = m
a*a + b*b = n

由于可解出a,b

    unsigned int sum = 0;
    unsigned int sqrSum = 0;

    for(i=0; i<N-2; i++)
    {
        sum += N-i-A[i];
        sqrSum += ((N-i)*(N-i)) - ((A[i])*A[i]);

    }
    sum += 2 + 1;
    sqrSum += 2*2 + 1*1;

猪头饼 2007-03-22 23:14 发表评论

KMP算法资料

猪头饼 — Thu, 09 Nov 2006 17:51:00 GMT

看了两三天的KMP算法,一直看的迷迷糊糊的.现在把这些资料贴在这里...以备日后之需

1.串的模式匹配的改进算法(这个网站对我的理解帮助很大,特别是右边的那块说明部分,以前自己脑筋老是转不过来) http://cist.dhu.edu.cn/kejian/%CA%FD%BE%DD%BD%E1%B9%B9%BE%AB%C6%B7%BF%CE%B3%CC/%D4%DA%CF%DF%D1%A7%CF%B0/text/chapter04/section3/c5.htm

2.KMP 算法的注记 http://www.cublog.cn/u/20/showart_136705.html

3.KMP算法中推导next[],nextval[]--手记 http://jiasimon040510.t8log.ccut.cn/blog-htm-do-showone-tid-6983.html

4.算法原理：

在匹配过和中，当主串中第i个字符与模式串中第j个字符“失配”时（s[i]!=t[j])，将模式串尽量向右移动，让模式串中第k（k

要让这个条件成立，那么在k之前的k个t字符[0 到 k-1]必须在i之前的k个s字符[i-k 到 i-1]相匹配即：

t[0, 1, 2...k-1] == s[i-k, i-k+1, i-k+2...i-1] ---(1)

而由之前的部分匹配成功的结果可知：

   t[0, 1, 2...j-1] == s[i-j, i-j+1, i-j+2...i-1]     ---(2)
==>
   t[j-k, j-k+1, j-k+2...j-1] == s[i-k, i-k+1, i-k+2...i-1]   --(3)

由(1)与(3)可得：

t[0, 1, 2...k-1] == t[j-k, j-k+1, j-k+2...j-1] ---(4)

求出k值,就是next[j]的值了

总之,相对我来说,算法不是很好懂.但是大家看到我这么笨的人到最后都能明白一二.大家就更没有理由看不懂了,祝大家成功附上我的测试源码:

#include < iostream >

using namespace std;

void GetNext( char t[], int next[])
{
     int j = 0 ;
     int k = - 1 ;
    next[j] = k;
     int tlen = strlen(t);

     while (j < tlen)
     {
         if (k == - 1 || t[j] == t[k])
         {
            j ++ ;
            k ++ ;
             if (t[j] == t[k])
             {
                next[j] = next[k];
            }
             else
                next[j] = k;
        }
         else
         {
            k = next[k];
        }
    }
}

int KMP( char s[], char t[], int pos, int next[])
{
     int slen = strlen(s);
     int tlen = strlen(t);
     int i = 0 ;
     int j = 0 ;

     while (i < slen && j < tlen)
     {
         if (j == - 1 || s[i] == t[j])
         {
            i ++ ;
            j ++ ;
        }
         else
         {
            j = next[j];
        }
    }

     if (j == tlen)
     {
         return i - tlen;
    }
     else
         return - 1 ;
}

int main ( int argc, char ** argv)
{

     char s[] = " aaaabaabaaabaaabaaaaabaaabaaabaaabaaabaaabaaabaaabaaabaaabacb " ;

     char t[] = " aabaaa " ;

     int next[ 20 ] = { 0 } ;
    GetNext(t, next);
     for ( int i = 0 ; i < 20 ; i ++ )
        cout << " next[ " << i << " ]:   " << next[i] << endl;

    cout << KMP(s, t, 0 , next) << endl;
}

猪头饼 2006-11-10 01:51 发表评论

[讨论]临时对象有地址么？

猪头饼 — Sun, 12 Feb 2006 14:12:00 GMT

class A
{

private :
     int i;
public :
    A( int ii):i(ii) {} // cout<
    A():i( 0 ) {}

     ~ A() {cout << " ~A( " << i << " ) " << endl;}

     const A operator + ( const A & r) const
     {
         return A(i + r.i);

    }
} ;

int main()
{
     int i = 10 ,j = 20 ;
     // cout<<&(i+j)< // 这里为什么会出错呢？
    A a1( 10 ),a2( 20 ),a3( 30 ),a4( 40 );
    cout <<& (a1 + a2) << endl;        // 这里就应该是临时变量的地址了吧
    system( " pause " );
     return 0 ;
}

既然这样可以运行，那为什么内置的类型如：int float之类的不能取临时对象的值呢？
我重载的+号运算符应该没有写错吧、、
请大家指教。。谢谢我还只是一个初学者

猪头饼 2006-02-12 22:12 发表评论