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;
}  回复  更多评论