華為面試題(8分鐘寫(xiě)出代碼)

icylord

沒(méi)經(jīng)過(guò)ACM訓(xùn)練的，就算了吧。 8分鐘寫(xiě)動(dòng)態(tài)規(guī)劃。

davetys

1.設(shè)一個(gè)數(shù)組C，把數(shù)組A和B都包含到里面，對(duì)C進(jìn)行排序
2.讓SUMA=A[0]=C[2n-1]，SUMB=B[0]=C[2n-2], SUMA和SUMB分別是A和B的當(dāng)前和
3.C倒序輪流給A和B賦值，如果SUMA大于等于SUMB，把C中較大的那個(gè)賦給B，然后接下來(lái)的就符給A，如果SUMA小于SUMB，則相反，然后SUMA和SUMB加上當(dāng)前的A和B
4.如此往復(fù)，應(yīng)該是最小的差距了

此算法是C倒序賦值給A和B，不是順序賦值

偽代碼：

sort（C, 2n）;
SUMA=A[0]=C[2n-1];
SUMB=B[0]=C[2n-2];
for(i=1,i<n;i++)
{
    if(SUMA<SUMB)
    {
        A[ i ] = C[2(n-i)-1];
        B[ i ] = C[2(n-i)-2];
        SUMA += A[ i ];
        SUMB += B[ i ];
    }
    else
    {
        A[ i ] = C[2(n-i)-2];
        B[ i ] = C[2(n-i)-1];
        SUMA += A[ i ];
        SUMB += B[ i ];
    }
}

xyl5565

終于搞定 bug害人

//不知道n
//條件
import console
數(shù)組1={}
數(shù)組2={}
n=console.getNumber( "請(qǐng)輸入每個(gè)數(shù)組元素個(gè)數(shù): " )
for(i=1;n;1)
{
        table.push(數(shù)組1,console.getNumber( "請(qǐng)輸入數(shù)組1的第"+i+"個(gè)元素:" ))
}
for(i=1;n;1)
{
        table.push(數(shù)組2,console.getNumber( "請(qǐng)輸入數(shù)組2的第"+i+"個(gè)元素:" ))
}


//功能函數(shù)
getsum=function(ts)
{
if(not #ts)
{
        return 0;
}
        sum=0
        for(k,v in ts)
        {
                sum+=v       
        }
        return sum;
}

s3=table.concat(數(shù)組1,數(shù)組2)
table.sort(s3)
數(shù)組1={}
數(shù)組2={}
while(#s3>0)//有數(shù)字就繼續(xù)取
{
sum2=getsum(數(shù)組2)
sum1=getsum(數(shù)組1)
t1=數(shù)組1
t2=數(shù)組2
        if(sum2>sum1)
        {
                t1=數(shù)組2
                t2=數(shù)組1
        }
        n=table.pop(s3,1)
        table.push(t2,n)
        sum2=getsum(t2)
        sum1=getsum(t1)
        for(i=1;#s3;1)
        {
                if((sum1+s3)>=sum2)
                {
                                l=i
                                break ;
                }
                l=i
        }
                table.push(t1,s3[l])
                table.remove(s3,l)               
}

console.log('數(shù)組:')
console.log(table.tostring(數(shù)組1))
console.log(table.tostring(數(shù)組2))
console.log('和為:')
console.log(getsum(數(shù)組1))
console.log(',')
console.log(getsum(數(shù)組2))
execute("pause")

xyl5565

程序 計(jì)算.rar (283.51 KB, 下載次數(shù): 1)

2015-09-14 18:24 上傳

點(diǎn)擊文件名下載附件

wangyifei2012

確實(shí)挺容易進(jìn)誤區(qū)的

amduroncn

有點(diǎn)難了.

cgd0282

開(kāi)第三個(gè)數(shù)組，a,和b 放進(jìn)去，排序，大端的全放b，小端全放a. a的和 - b的和就是最大負(fù)數(shù)。不就是最小值嗎？討論那么久

haoruixiang

//偽代碼：
    int a[]={1,23,,3435,354,67,};
    int b[]={3,342,123,1,5412,123,};
    int c[] = a+b;
    sort(c);
    for(int i =0; i< len(c); i++)
    {
        if (i%2==0)
        {
            a[i/2] =c[i];
        }else{
            b[i/2] =c[i];
        }
    }

undiedphoenix

感覺(jué)挺簡(jiǎn)單啊，這么長(zhǎng)時(shí)間還有回復(fù)。1算出倆個(gè)數(shù)組和 的差值 2.將差值除以2（每次交換差值會(huì)縮小2倍）3.找到小于差值的最近的交換。
例如 a {1 2 3 4 } b{6 7 8 9}
一、suma =10 sumb=30   (sumb-suma)/2 =10
9 -1 =8 <10 交換 a{9 2 3 4} b{6 7 8 1}
二、suma =18 sumb=22   (sumb-suma)/2 =2
8 最小差4 ；7最小差3 ；6最小差2
正好交換6 和4 即可
a{9 2 3 6} b{4 7 8 1}
三、 suma = sumb =20