当前位置: 首页 >> 面试题 >> 技术 >> 后端开发 >> 算法 >>

算法面试题记录

1,在无序数组中查找满足条件之和为target的两个数

从头开始扫描数组,将扫描过的元素加入hash_map,对于正在扫描的元素a[i]在哈希表中查找值为target-a[i]的元素,如果有就返回两个数,整个时间复杂度为O(n)。

2,反转一个语句

首先按每个字符翻转整个字符串,然后从头开始扫描,使用一个标记记录扫描过程中遇到的单词开头位置,遇到空格或者到达末尾,就翻转从标记位置开始的这个单词。直到结束,

 

3,一个数组先降序后升序,如何找到中间最小的那个元素

使用二分法,是二分查找的变形。二分查找是比较a[mid]和target,这个是比较a[mid]和其左右侧元素。

while( low <= high ) {

mid = (low + high)/2;

if(a[mid] <a[mid-1] && a[mid] <a[mid+1]) return mid;

if(a[mid] < a[mid-1]) {low = mid;}

else{high = mid;} //这个时候元素只剩下a[mid] > a[mid+1]这一种情况;

}

 

基础面试题

对于超大数据集的问题,上来就先看看hash+分治能不能行:

1. 选一个hash函数,能将数据集范围的整数分到若干个桶中,每个桶中落入的数的个数能够内存处理即可

2. 每个桶内进行操作

3,归并各个桶

Loading