算法

算法面试题

本专栏的面试题来自于牛客网、一亩三分地、LeetCode、LintCode等网站,覆盖了一线互联网如BAT、TMD、微软、亚马逊等巨头,在校招或者社招的时候最容易出的算法面试题。

美团

快手

猿辅导

  • [3.1 旋转数组]
  • [3.2 整数转换英文表示]

拼多多

  • [4.1 二叉树的层次遍历]

头条

滴滴

  • 1.1 算法题,最近最少访问,看起来我们得需要维护一个次数,而实际上 LRU 算法中的 Recenctly 是不统计的单个 key 的次数的,比如过去访问了 3 次 keyA,然后接着访问了 1 次 keyB,下次淘汰的依然是 keyA,只是因为 keyA 更加的 Recently。因此我们可以使用双向链表来维护一个淘汰的顺序即可,比如头部永远都是最近访问的,尾部永远都是很长时间没有访问的 key,每次 getput 的时候都需要将相应的 key 移动到头部即可。Java 自带的 LinkedList 没有带 capacity 的构造函数LinkedList 的底层是双向循环链表,因为 LinkedListremove 方法的复杂度是 O(n),因此我们得需要自己实现这个双向链表,才能达到一个 getput 都是 O(1) 复杂度的算法。在具体实现细节上,维护双向链表的删除,headtail (tail 指针必须进行维护,否则无法达到 O(1) 查找到要删除的 Key 的复杂度要求) 的维护更新最好也是需要 DUMMY 节点的,这样的话就无须额外维护 headtail 的边界点。如果不使用 DUMMY,那么删除 node 的算法大致如下,显得非常的小心翼翼,极易出错。另外,维护节点访问的顺序,可以分为两个步骤:先删除该节点,然后插入到头部,通过分为两个函数,也可以简化算法的实现。该题的示例写法参考
// 删除 p
if (p.prev !=  null && p.next != null) {
    p.prev.next = p.next;
    p.next.prev = p.prev;
} else if (p.prev == null && p.next != null) {
    head = null;
} else if (p.next == null && p.prev != null) {
    p.prev.next = null;
}

另外牛客网上这道题,返回的是多次 get 的值存放到一个 int[] 数组里面的这个数组序列,那么我们会用 List<Integer> 来存储,并转为 int[]

int[] arr = list.stream().mapToInt(i -> i).toArray();

另外还有一个需要注意的点就是,到达最大容量 k,需要删除尾巴节点的代码,千万不要像下面这样写:

// 这一步之后,TAIL.prev 指向的指针已经变化了,所以应该先把 TAIL.prev 这个使用 tmp 保存下来
deleteNode(TAIL.prev);
map.remove(TAIL.prev.key);
  • 1.3 这道题目,看了官方的很多实现,感觉中心扩展法的做法还是较为容易理解的。动态规划法的公式也比较容易理解,定义 dp[i][j] 表示字符串 s[i...j] 是否是回文字符串,一个回文字符串,两头肯定一样:dp[i] == dp[j],并且去掉两头以后,里面也同样得需要是回文字符串:dp[i + 1][j - 1] == true,那么有边界条件:i + 1 < j - 1,问题是填充二维数组的顺序不是很好理解,可能记不住。中心扩展法从左到右依次选则 1 到 2 个字符,然后以这两个字符为中心,向左向右进行扩展,记录最大的回文字符串的长度。

  • 5.1 这道题,我们需要维护一个 Map,这个 Map 记录了遇到的各个最新字符的位置和字符的映射关系,同时我们还需要一个 left 来标识当前在 map 中维护的字符串的最左侧开端的索引,当遇见重复字符的时候,我们需要left 到这个字符存在 map 中的旧的索引位置 oldPosition 的这段字符,从 map 中都给移除掉 (最新刷了一遍,结果写成了将 oldPosition -> i 之间的给删除了,写错了),以便放进来新的字符,开始新的字符串,并更新 left 的值为 oldPosition + 1

  • 8.1 这道题,为了能容纳更多的数字到一个递增序列中,那么对于固定长度的递增序列,其末尾的数字越小越好,比如长度为两位的递增序列 [2, 101],假设下一个数字遇到的是 3,那么应该用 3 来代替 101,来构成一个长度为 2 的递增序列,以便后续能够容纳更多的元素进来。还有一个地方是如何处理这种情况,比如 [7, 8, 1, 2, 3, 4], 我们记录了 [7, 8],但是下一个是 1,1 可能是一个新的递增序列的开始,因为它比 7 更适合作为一个序列的开始,所以遇到 1 的时候要更新一维数组的最小的值,由 7 变为 1,所以我们需要维护一个动态的递增数组,第一位记录的是长度为 1 的数组的末尾的最小值,第二位记录的是长度为 2 的数组的末尾的最小值……。这道题为了实现 O(nlogn) 的解法,需要实现一个在递增数组中,查找第一个大于 num 的这个索引,这就涉及到二分搜索的算法。

而最关键的查找合适的替换位置的算法,因为二分搜索算法不好写,容易写错,所以面试的时候可以先写一个 O(n) 的查找算法 (注意此处可以写作 arr[hi] 大于等于 i,也就是等于的时候 hi 也往后退一下,这样下一步可以直接写 arr[hi + 1] = nums[i]):

// len 是辅助数组 arr 的长度
int hi = len - 1;
// 注意此处可以写作 arr[hi] 大于等于 i
while (hi >= 0 && arr[hi] >= i) {
    hi--;
}

arr[hi + 1] = nums[i];

而我们在面试过程中,还需要将上述算法改为如下的二分搜索。其中有几点需要注意,(1) 使用 lo + ((hi - lo) >> 1) 计算 lohi 的中间索引。(2) 对于 arr[mid]nums[i] 的对比关系,我们首先问一下,假设 nums[i] 大于 arr[mid],那么这个 mid 有没有可能成为我们要寻找的目标索引?很明显,是不可能的,因为我们是要用小的 nums[i] 替换大 arr[mid] 的,而非大值替换小值,而大值位于 mid 索引的右侧,所以当 nums[i] 大于 arr[mid] 的时候,我们应该将 lo 调整为 mid + 1。参考上面 O(n) 的思路,此处等于的时候,我们也归为大于的情况,让其走 else 分支。在 else 分支中,此时 mid 这个索引有可能刚好满足需要查找的位置,那么怎么算刚好?这里刚好指的是 arr[mid - 1] < nums[i] < arr[mid],此时 nums[i] 替换 arr[mid] 是我们想要的结果,这里因为涉及到了 mid - 1,因此判断 mid 是否为 0 的特殊情况,也是情理之中的时候。如果不满足这两个条件,那么说明当前 mid 的值还是太大,因此我们尝试向 mid 的左侧,即值相对来说稍微小一点的地方挪动一下,hi = mid - 1,来继续查找。

int hi = currentArrLength - 1;
int lo = 0;

while (lo <= hi) {
    int mid = lo + ((hi - lo) >> 1);
    
    if (nums[i] >= arr[mid]) {
        lo = mid + 1;
    } else {
        if (mid == 0 || arr[mid - 1] < nums[i]) {
            arr[mid] = nums[i];
            break;
        } else {
            hi = mid - 1;
        }
    }
}
  • 8.2 算法题,nextp 指针相同的时候,这个时候 p 不要往后移动;不相同的时候,p 才向后移动。如果相同的时候也移动,会漏掉节点。

  • 8.3 是牛客网根据网友发布的帖子里面的算法题,整理出来的一些高频算法题。能链接到 LeetCode 上的题目,都链接到了上面,不能链接的,也链接到了 NowCoder 上面。下面着重讲述做题心得。

(1) 翻转单链表: 这道题,可以换一个描述,将原链表的每一个节点,从头部开始全部拆下来,以头插法逐次插入到另外一个新的链表的头部,而这个新的链表一开始只是一个空指针 anotherHead = null

(2) 数组排序:对于这道题,我觉得至少应该掌握堆排序快速排序归并排序,三种排序算法的写法。其中快速排序,首先需要进行 partition,然后递归调用 sort 函数,以便将 left ~ index - 1,以及 index + 1 ~ right 都排好序,对于 partition 算法,一种较为简单的写法是,定义 i 指针指向左侧小于 pivot 的数字序列的最后一个索引,然后 j 负责在前面探路,只要遇到小于等于(只小于也是可以的) pivot 的值,那么 i 指针就加 1,否则不变,这样当 i 不等于 j 的时候,就可以交换 ij 的值。对于归并排序,首先从中间切割,然后递归对 begin ~ middlemiddle + 1 ~ end 进行排序,最后进行 merge,在 merge 阶段,一般会创建一个长度为 end - begin + 1 的数组,将合并的结果临时存放到这个数组里面,最后再将数字从这个数组中拷贝到原数组中。对于堆排序,首先第一步建立最大堆,这个建立过程索引 i 的取值范围 n/2 -> 0,为什么是一半?因为堆是树状的,堆建立好以后,每一节点都会与自己的孩子进行对比,进行一个下调或者上升,确保每一个节点的值都大于或者等于孩子的值,而 n/2 + 1 ~ n 都是叶子节点,这部分节点无须进行堆的调整。另外一个问题,为什么堆需要倒着建立堆?这是为了,每一次对于堆节点的调整后,都保证该节点的子树是满足堆的定义的,以如下树为例,假设从堆顶 5 开始调整,那么调整完,34 将会放到堆顶,这很明显是不正确的。建堆结束之后,数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶,也就是最大的元素。我们把它跟最后一个元素交换,那最大元素就放到了下标为 n 的位置。当堆顶元素移除之后,我们把下标为 n 的元素放到堆顶,然后再通过堆化的方法,将剩下的 n−1 个元素重新构建成堆。

     5
   /   \
  12   34
  / \  / \
100 43 6  7

(3) 含有重复数字的二分查找:这道题的坑的地方在于可能会出现重复数字,那么,当遇见重复数字的时候,需要 O(n)mid 往索引 0 的地方去查找看是否都等于:

if (nums[mid] == target) {
    if (mid == 0 || nums[mid - 1] != target) {
        return mid;
    }
    
    int i = mid - 1;
    while (i >= 0 && nums[i] == target) {
        i--;
    }
    return i + 1;
}

一开始采用的是这种 for 的方式去写的,一旦 i == 0 的时候,那么还是会走到最后的一行,即返回的是 mid 而非 0

if (nums[mid] == target) {
    if (mid != 0 && nums[mid - 1] == target) {
        for (int i = mid - 1; i >= 0; i--) {
            if (nums[i] != target) {
                return mid;
            }
        }
    }

    return mid;
}

(4) 数组中最小的 K 个数。这道题可以用快速排序中的 partition 算法来做,经过一次 partition 算法,返回的是 pivot 所在的索引 i 的位置,所有小于 pivot 的都在数组左边,大于 pivot 的都在数组右边;除了这一点,还有就是 pivot 在这个数组里面所处的位置也确定了,如果排序这个数组,那么 pivot 现在已经放到了正确的位置上,那就是处在第 i + 1 的位置。所以可以依托二分排序的结构,每一趟 partition,可以对比 pivotIndexk - 1 是否相等,相等则返回前 K 个即可,不相等,则相应的调整 lohi 的值即可,这个算法的复杂度平均 O(n) 最坏 O(n^2)。平均时间复杂度为:

n + n/2 + n/4 + ... + 8 + 4 + 2 + 1 = 2n

如果每次选取的 pivot 不合适,复杂度退化为:

N + (N-1) + (N-2) + (N-3) .... = O(N^2)

那么应该如何进行优化,使用 randomhi 进行一个交换:

int partition(int nums, int lo, int hi) {
    int random = new Random().nextInt(hi - lo + 1) + lo;
    swap(nums, random, hi);

    // 此时才开始我们以前的写法
    int pivot = nums[hi];
    // ...
}

另外这道题还可以使用堆来做,不过这个堆应该是自己构造的,算法复杂度 O(NlogK)

(4) 寻找第 K 大。这道题注意的是,这里的第 K 大,指的是从大到小排序的第 K 个数字,所以第 K 大,相当于从小到大的第 N - K + 1 小,所以在查找之前一定要对 K 做上述公式的转换。

(5) 两数之和。这道题注意的是,看最终返回的是这两个数,还是两个数的索引,如果是两个数的索引,那么可能采用排序然后二分搜索目标值的方法不太合适。应该采用哈希的方式来尝试,边遍历边判断即可,题目只是要求 index1 要小于 index2,如果含有重复数字的话,那么用第一小的数字,还是用第二小的数字,并未做要求。

for (int i = 0; i < numbers.length; i++) {
    Integer index = map.get(target - numbers[i]);
    
    if (index != null) {
        // target - numbers[i] 在之前出现过
        return new int[]{ index + 1, i + 1 };
    } else {
        map.put(numbers[i], i);
    }
}

(6) 链表中的节点每 K 个一组翻转。① 注意有多少 group 这个 group 不要求错了 ② 写一个 findKthNode(curHead) 的方法来找第 k 个节点 ③ 用一个新的节点作为最后的节点 head,一组翻转后,然后挂到这个新节点的末尾,然后进行下一组。

(7) 求链表环的入口。① 探测 meetNode ② 根据 meetNode 求出环的节点个数 cycleLenfasterhead 移动 cycleLenslowerfaster 一起移动,直到相遇 ⑤ 最后返回 slower

(8) sqrt 这道题。① x 小于等于 1 的时候,直接返回 x 即可。② 下限 lo = 1,上限,hi = x / 2。③ 使用 mid * midx 来对比大小关系,会溢出,即使使用 long 来存储也不行,因为 int * int = int

(9) 两个链表的第一个公共节点。① 不能通过翻转链表,然后尾巴变成头部,从头部开始遍历的做法,因为两个链表是共用尾巴的,一个翻转了,另外一个跟着也翻转了,它们共用内存。② 思路:找到长度 diff,然后一起向后走,直到遇到相同节点。

(10) 二叉树前序遍历。① 设置一个指针 curr 沿着左树一直往左走,边走边放到栈里面,同时添加到 result 列表中。② 走到头,只要右树一直为空,就一直从栈里面 pop。③ 直到 curr 指针可以转到右树。

(11) 二叉树中序遍历。① 设置一个指针 curr 沿着左树一直往左走,边走边放到栈里面。② 走到头,只要右树一直为空,就一直从栈里面开始 pop,边 pop 边放入 res。③ 直到 curr 指针可以转到右树。

(12) 二叉树后序遍历。① 设置一个指针 curr 沿着左树一直往右走,边走边放到栈里面,同时通过 add(0, node) 头插到 result 列表中。② 走到头,只要左树一直为空,就一直从栈里面 pop。③ 直到 curr 指针可以转到左树。

(13) 最长公共子串。① dp[i][j] 表示以 A[i] 结尾和以 B[j] 结尾的最长连续字符串长度。② dp[i][j] = dp[i - 1][j - 1] + 1i - 1j - 1 必须大于等于 0。

(14) 螺旋矩阵。① while 循环条件是 rowBegin <= rowEnd && colBegin <= colEnd。② 每次走一行或一列,都需要 rowBegin++colEnd--rowEnd--colBegin++。③ 因为 rowBegin++ 可能会导致 rowBegin > rowEnd,因此第三次从右往左走的时候,需要加上 rowBegin <= rowEnd 这个条件;第四次从下往上走的时候,需要加上 colEnd >= colBegin 这个条件。

(15) 合并 K 个有序链表。介绍一下 PriorityQueue 的几个构造器和重要方法

// 默认 capacity 11,顺序按照元素的自然顺序
PriorityQueue();
// 按照指定的 capacity,以及指定的 Comparator 来创建堆
PriorityQueue(int initialCapacity, Comparator<? super E> comparator);

// 插入 e 到优先级队列中
boolean offer(E e);
// 从堆顶获取,但是不移除
E peek();
// 从堆顶获取并移除
E poll();

另外就是 Integer 实现大小排序的原来:

class Integer implements Comparable<Integer> {

    @Override
    public int compareTo(Integer anotherInteger) {
        return compare(this.value, anotherInteger.value);
    }

    // 小于返回 -1, 大于返回 1
    public static int compare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }

}

另外就是 Comparator<T> 的定义:

public interface Comparator<T> {

    int compare(T o1, T o2);
    
}

(16) 三个数字和等于0。① 这道题整体思路,首先排序,使用 i 指针指向第一个数字,然后使用 lohi,一个从低处,一个从高处,从两端向中间聚拢。② 如果 i + 1i 指向的数字是重复的,则跳过。③ lo++hi-- 的时候,也需要判断 lo + 1hi - 1 位置的数字是否和 lohi 有重复。

(17) 在转动(旋转)过的有序数组中寻找 target: 重要的是确定 A[mid] 位于哪一半,而非 target 位于哪一半。① 如果 lo < hi,那么可以使用两个指针 lo 永远指向前半段,hi 永远指向后半段,当 lo + 1 == hi 的时候,那么说明 lo 指向的恰好是前半段的结尾,hi 恰好是后半段的开头,这个时候返回 hi 即可。如果 lo >= hi,那么直接返回 0 即可。② 如果 A[mid] 大于等于 A[0], 那么证明 mid 在前半段,所以可以 lo = mid。③ 反之,hi = mid


LeetCode-Cn 遇到的情况:

Integer[] numArr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
// 是否是奇数
nums[i] & 1 == 1
// 是否是偶数
nums[i] % 1 == 0
  • 每日温度,这道题最关键的就是如何高效的在数组中寻找排列在后面的、并且比自己数值大的值。而这个需要借助一个数据结构,单调栈,栈里面存放的是索引,只要栈里面的数组比当前数字小,那么栈里面的数字就一直 pop()

  • 两个有序数组的中位数。TODO

  • 字符串的排列

上述算法题来自:


数组
环形数组微软 最大子数组之和为 K微软 下一个排列微软
两个有序数组合并后的中位数微软 买卖股票微软 生成螺旋矩阵微软
两个有序数组第 K 大的数微软
二叉搜索树中删除一个节点微软 二叉搜索树中新增一个节点微软 二叉树的直径微软、头条
中序遍历的下一个节点 二叉树最大路径和微软 二叉树非递归中序遍历微软
二叉树最近公共祖先微软 一颗二叉树是否是另外一颗的子树微软 二叉树右视图微软
DFS
WordLadder微软、阿里 二维数组寻找最长的单调递增序列微软
写一个计算器(逆波兰表达式)微软 MinStack微软
排序
PancakeSorting微软 颜色排序网易阿里 堆排序微软
链表归并排序 快排序 归并排序
栈排序美团 磁盘归并排序微软
字符串
找出最多 K 个不同字符的最长子串微软 两个字符串整数相加微软
动态规划
二维矩阵数值和最小的路径微软 最小火车票费用亚马逊 最长递增子序列 LIS微软
链表
链表是否有环微软 找出链表环的入口节点微软
回溯
组合总和 为运算表达式设计优先级头条
数学
开根号微软
读写:5 个线程读 1 个线程写微软