評論

# re: 微軟電話面試總結(jié) 2007-12-18 11:55 tip

用STL是不是很簡單？  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié) 2007-12-18 16:19 func

你的函數(shù)開頭寫得不好。
參數(shù)正不正確，應(yīng)該是調(diào)用者保證的事。
比如：
void f1(int* p) {
if(0==p) {...}
...
}
void f2(int* p) {
if(0==p) {...}
f1(p);
}
void f3(int* p) {
if(0==p) {...}
f2(p);
}
你調(diào)用一次f3()就要重復(fù)判斷p三次，嚴(yán)重浪費。
去掉各函數(shù)內(nèi)的“if(0==p) {...}”，在調(diào)用f3()前判斷一下參數(shù)的有效性，就可以節(jié)省兩次判斷。這就是有調(diào)用者保證。

作為函數(shù)的實現(xiàn)者，你要做的是用斷言assert保證參數(shù)正確性，因為它只在debug版本有效，release版本中不起作用。即能報錯，又不影響效率。  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié) 2007-12-19 11:30 南龍

@func
是的，有道理。不過第二個是對size進(jìn)行判斷，~~
if(p == NULL) return -1;
if(size <= 0) return 0;
if(size == 1) return 1;  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié)[未登錄] 2007-12-19 11:54 goodname

粗粗寫了一個，未詳加考慮，權(quán)當(dāng)拋磚引玉吧。

#include <stdio.h>
#include <assert.h>

int compact(int arr[],int size)
{
int i,j;
int count = 0;

for(i = 0;i<size;i++)
{
for(j=0;j<i && arr[j] != arr[i];j++) ;

if(j == i)
{
arr[count++] = arr[i];
}
}

return count;
}

int main()
{
int i;
int arr[] = {1,1,2,3,3,5};
int size;
int count;

size = sizeof(arr)/sizeof(arr[0]);
count = compact(arr,size);

assert(count <= size);

printf("count = %d\n",count);

for(i = 0;i<count;i++)
printf("arr[%d] = %d\n",i,arr[i]);

return 0;
}

應(yīng)該還有更好點的解法,也許可以使用goto效率還高些?
  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié)[未登錄] 2007-12-19 12:48 goodname

使用一個循環(huán)的,
供大家參考吧
int compact(int arr[],int size)
{
int i = 0;
int count = 0;
int current = 0;

while(i<=count)
{
if(i == count)
{
i=0;
arr[count++] = arr[current++];
if(current >= size)
return count;
}
else if(arr[i] == arr[current])
{
i = 0;
current++;
if(current >= size)
return count;
}
else
{
i++;
}
}

return count;
}  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié) 2007-12-19 15:32 南龍

@goodname 寫的太好了，100分 ^_^
這樣如何？

int compact(int arr[],int size)
{
    int i;
    static int count = 0;
    static int curren =0;
    if(curren>=size) return count;
    for(i=0;i< curren && arr[i] != arr[curren];i++);
    if(i == curren)
        arr[count++] = arr[curren];
    curren++;
    compact(arr,size);
    return count;
}

  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié) 2008-09-27 03:18 玄機(jī)逸士

我的程序如下，供參考。
說明：經(jīng)過InitialCompact運算后，最多只有兩個數(shù)重復(fù)的情況，比如{1, 1, 1, 2, 3, 3, 5, 5, 5, 5, 5, 5, 10} 會變成{1, 1, 2, 3, 5, 5, 10}，即肯定不會出現(xiàn)有三個數(shù)重復(fù)的情況，再運行一次InitialCompact就不會再出現(xiàn)重復(fù)數(shù)字了。

為了可讀性，程序?qū)懙糜悬c啰嗦。還有很大的改善空間。:)

#include "stdio.h"
#include "stdlib.h"
#include "assert.h"

int initialcompact(int*, int);
int compact(int*, int);

int main(int argc, char* argv[])
{
int i;
int a[] = {1, 1, 2, 3, 3, 5, 5, 5, 5, 5, 5, 10};
int b = compact(a, 12);
printf("the number of compacted array element is: %d\n", b);
printf("the compacted array elements are: \n");
for(i = 0; i < b; i++)
printf("%d\n", a[i]);
return 0;
}

int initialcompact(int* p, int size)
{
assert(p != NULL);
for(int i=0; i < size; i++)
{
for(int j=1; j < size-1; j++)
{
if(p[i] == p[i+j])
{
for(int k = 0; k < size-i-j; k++)
{
p[i+j+k] = p[i+j+k+1];
}
size--;
}
}
}
return size;
}

int compact(int* p, int size)
{
assert(p != NULL);
size = initialcompact(p, size);
size = initialcompact(p, size);
return size;
}  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié) 2008-10-23 22:44 aimfaraway

題目給的是個單調(diào)不減數(shù)列,刪除單調(diào)序列的重復(fù)項可以這么做

#include <iostream.h>
int delete_d(int *A,int n)
{
int i=0;
for(int j=1;j<n;)
{
if(A[i]!=A[j])
{
A[++i]=A[j];
}

j++;
}

return i+1;
}
//test
int main()
{
int A[]={1,1,2,3,3,5,6,6,6,6};
int n =delete_d(A,10);
for(int i=0;i<n;i++)
cout<<A[i]<<" ";
return 0;
}

  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié) 2008-12-17 12:07 guest

都是庸才啊.  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié) 2009-01-07 16:06 baolei

#include <stdio.h>
#include <assert.h>

int compact(int arr[],int size)
{
int i,j;
int count = 0;

for(i = 0;i<size;i++)
{
for(j=0;j<count && arr[j] != arr[i];j++)
{;}

if(j == count)
{//用 j < i, j == i 無故多執(zhí)行好多步
arr[count++] = arr[i];
}
}

return count;
}

int main()
{
int i;
int arr[] = {1,1,2,3,3,5};
int size;
int count;

size = sizeof(arr)/sizeof(arr[0]);
count = compact(arr,size);

assert(count <= size);

printf("count = %d\n",count);

for(i = 0;i<count;i++)
printf("arr[%d] = %d\n",i,arr[i]);

return 0;
}  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié) 2009-04-18 23:59 yinyueyouge

用hash表啊~~遍歷數(shù)組里面的每一個整數(shù)，插入hash表里面。這樣復(fù)雜度只是O（n)

或者用一個二元樹，遍歷數(shù)組里面每一個整數(shù)，插入二元樹里面。這樣復(fù)雜度是O(log n)  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié) 2009-04-19 00:02 yinyueyouge

若是單調(diào)不減數(shù)列, 那更簡單了，可以用時間復(fù)雜度O（n）和空間O(1) 完成。

遍歷數(shù)組里面的每一個元素，和前一個值比較。若是相等，咔嚓掉。若是大，繼續(xù)。
  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié) 2010-04-23 23:52 supernavy

大家看這樣行嗎？

int compact(int[] array, int size) {
int i,j,count=0;
for(int i=0;i<size;i++) {
for(j=i+1;j<size&&array[j]==array[i];j++);
array[count++]=array[i];
i=j;
}
}  回復(fù)  更多評論   

# re: 微軟電話面試總結(jié)[未登錄] 2011-04-29 00:03 jason

正解如下：一次循環(huán)，用兩個下標(biāo)就行，0~i的元素都是沒有重復(fù)的，i為最后一個沒有重復(fù)的元素，j從1開始，一旦發(fā)現(xiàn)一個元素與a[i]不一樣，就將a[j]和
a[i]交換。思路源自算法導(dǎo)論快排的寫法。
int unique(int *a, int size)
{
if (NULL == a)
return -1;
if (size <= 0)
return 0;
if (1 == size)
return 1;

int i,j;
int temp;

i = 0;
for (j=1; j<size; j++)
{
if (a[j] != a[i])
{
i++;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
return i+1;
}  回復(fù)  更多評論