百度面试题总结—01(算法)

查看原题

1.用C语言实现一个revert函数,它的功能是将输入的字符串在原串上倒序后返回。

思路:重新定义一个字符串,反向取出原字符串的值

1
2
3
4
5
6
7
8
9
10
11
12
char *revert(char *str)
{

int lenght = strlen(str);
char *ret = new char(lenght);
int left = 0, right = lenght - 1;
for (int i = lenght - 1; i >= 0; i--)
{
ret[lenght - i - 1] = str[i];
}
ret[lenght] = '\0';
return ret;
}

2.用C语言实现函数void memmove(void dest, const void *src, size_t n),memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。

思路:主要解决内存重叠的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void *memmove(void *dest, const void *src, size_t n)
{

if (NULL == dest || NULL == src)
{
cerr << "NULL pointers";
return NULL;
}
int step;
char *p, *q;
if ((char *)src == (char *)dest)
return dest;
else if ((char *)src > (char *)dest)
{
step = 1;
p = (char *)src;
q = (char *)dest;
}
else
{
step = -1;
p = (char *)src + n - 1;
q = (char *)dest + n - 1;
}
for (int i = 0; i != n; i++)
{
*q = *p;
p += step;
q += step;
}
return dest;
}

3.蚂蚁与木杆

描述:有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
思路:蚂蚁相遇掉头,可以看作蚂蚁还在继续往各自的前方走。

4.给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。

思路:取左右两个指针,分别从头部和尾部遍历,交换不和谐元素。

5.在一维坐标轴上有n个区间段,求重合区间最长的两个区间段。

思路:根据每个区段左坐标排序,每次记录最大重合距离和最远有坐标。
备注:贪心问题,类似不同时间段任务安排。

6.现在有1千万个随机数,随机数的范围在1到1亿之间。现在要求写出一种算法,将1到1亿之间没有在随机数中的数求出来。

思路:利用位图,即开一个1亿位的bitset,内存为100m/8== 12.5m, 然后如果一个数有出现,对应的bitset上标记为1,最后统计bitset上为0的即可。

7.循环有序数组的二分查找。

对已排好序的数组A,一般来说可用二分查找可以很快找到。现有一特殊数组A[],它是循环递增的,如A[]={ 17 19 20 25 1 4 7 9},试在这样的数组中找一元素x,看看是否存在。
LeetCode原题,查看请点击LeetCode-num033

8.如何解决Hash冲突等问题

(1)哈希函数的构造方法:数字分析方法,平方取中法,分段叠加法,除留取余法,伪随机数法
(2)处理冲突的方法:开放定址法,再哈希法,链地址法,建立公共溢出区。

9.判断一个数的所有因数的个数是偶数还是奇数

开始每太理解,仔细看一下答案,才理解题意。答案是这样的,如果这个数是平方数,那么结果为奇数,否则为偶数。
那么顺着这个思路可以继续思考,如果这个数所有质因数都是偶数个,那么这个数就是平方数,结果为奇;否则只要有质因数个数是一个,结果就是偶。

10.

问题描述:写一个C的函数,输入整数N,输出整数M,M满足:M是2的n次方,且是不大于N中最大的2的n次方。例如,输入4,5,6,7,都是输出4。
思路:平均时间复杂度可以达到O(logN),遍历从一到给定数之间所有的2的倍数。找到最大不大于给定数的值。
但是这是最好的答案了吗?我觉得不是,可以寻找更好的办法。
优化:我们都知道位运算,2的次方数的二进制有个特点,就是首位为1,而其他所有的位都是0。那么从这个角度出发。那么我们只要得到最二进制中最高位的值就可以了。那么我们可以直接通过位运算求得输入数字的二进制最高位就可以了。
那么问题又来了,怎么获得最高位的值呢,可以不断移位,计数数位数,但这样做的其实和最开始的方法效率是一样的。
优化:其实再想一下的话,我们可以先获得除了二进制首位剩余位的值,然后与原数异或运算,就可以直接得到结果。时间复杂度降到O(1)。