1CM

評論

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

用STL是不是很簡單？  回復  更多評論   

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

你的函數開頭寫得不好。
參數正不正確，應該是調用者保證的事。
比如：
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);
}
你調用一次f3()就要重復判斷p三次，嚴重浪費。
去掉各函數內的“if(0==p) {...}”，在調用f3()前判斷一下參數的有效性，就可以節省兩次判斷。這就是有調用者保證。

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

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

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

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

粗粗寫了一個，未詳加考慮，權當拋磚引玉吧。

#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;
}

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

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

使用一個循環的,
供大家參考吧
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;
}  回復  更多評論   

# re: 微軟電話面試總結 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;
}

  回復  更多評論   

# re: 微軟電話面試總結 2008-09-27 03:18 玄機逸士

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

為了可讀性，程序寫得有點啰嗦。還有很大的改善空間。:)

#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;
}  回復  更多評論   

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

題目給的是個單調不減數列,刪除單調序列的重復項可以這么做

#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;
}

  回復  更多評論   

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

都是庸才啊.  回復  更多評論   

# re: 微軟電話面試總結 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 無故多執行好多步
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;
}  回復  更多評論   

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

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

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

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

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

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

# re: 微軟電話面試總結 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;
}
}  回復  更多評論   

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

正解如下：一次循環，用兩個下標就行，0~i的元素都是沒有重復的，i為最后一個沒有重復的元素，j從1開始，一旦發現一個元素與a[i]不一樣，就將a[j]和
a[i]交換。思路源自算法導論快排的寫法。
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;
}  回復  更多評論