算法面试准备

理论部分

一、如何正确回答一个算法问题

  1. 算法答案只是一个方面,很多时候面试官更关注的是思考问题的方式,因此要尝试着去与面试官探讨自己的思路
  2. 讨论题目的一些条件
  3. 注意代码的优化、规范性、容错性

二、算法面试不意味着技术面试优秀

  1. 项目经历和项目中遇到的实际问题
  2. 遇到印象最深的bug
  3. 面向对象的思想
  4. 设计模式
  5. 网络相关;安全相关;内存相关;并发相关
  6. 系统设计

三、技术面试优秀不意味着能够拿到Offer

项目经历

  1. 项目经历也非常重要,是面试官了解个人过去的重要点
  2. 实习
  3. 参与实战课程学习
    1. 慕课网
    2. Coursera
  4. 创建自己的项目

通过过去了解你的思考行为方式(结合项目)

  1. 遇到的最大的挑战?
  2. 犯过的错误?
  3. 遭遇的失败?
  4. 最享受的工作内容?
  5. 遇到冲突的处理方式?
  6. 做的最与众不同的事儿?

准备好合适的问题问面试官

  1. 小组的运行模式
  2. 了解了项目,询问项目的后续规划是如何的
  3. 这个产品中的某个问题是如何解决的
  4. 产品为什么选择某些技术?采用的标准是什么?

四、算法面试准备

高级数据结构和算法面试提及的概率较低

  1. 红黑树
  2. B-tree
  3. 数论
  4. FFT(傅里叶几何变换)
  5. 斐波那契堆

不要轻视基础算法和数据结构,仅关注“有意思的”题目

  1. 各种排序算法
  2. 基础数据结构和算法的实现:如堆、二叉树、图…
  3. 基础数据结构的使用:如链表、栈、队列、哈希表、图、Trie、 并查集…
  4. 基础算法:深度优先、广度优先、二分查找、递归…
  5. 基本算法思想:递归、分治、回溯搜索、贪心、动态规划…

要将学习与实践相结合

  1. 要将理论与实践相结合
  2. 不要陷入刷题的误区中,学会举一反三

五、解决算法面试问题的整体思路

注意题目中的条件

  1. 给定一个有序的数组
    1. 二分法
  2. 有一些题目中的条件本质暗示:
    1. 设计一个nlogn的算法(通过搜索树/排序/归并)
    2. 无需考虑额外的空间(开辟空间换取时间优化)
    3. 数据规模(设计n^2算法 )

没有思路的时候

  1. 给自己简单的测试用例,试验一下
  2. 不要忽视暴力解法。暴力解法通常是思考的解题

优化算法

  1. 遍历场景的算法思路
  2. 遍历常见的数据结构
  3. 空间和时间的交换(哈希表)
  4. 预处理信息(排序)

实际编写问题

  1. 极端条件判断
    1. 数组为空?字符串为空?数量为0?指针为null?
  2. 变量名(语义)
  3. 模块化、复用性

实践部分

时间复杂度

计算:O(f(n))=指令数*数据量(往往省略指令数,因为它是常量)

O(f(n))表示一个上界,因此归并排序的时间复杂度说是O(n^2)也没错;在实际的时间复杂度计算中,我们往往取一个数的上界,比如处理n个字符串,我们默认内部的字符串长度都为最长的长度s;

一个时间复杂度的问题
有一个字符串数组,将数组中的每一一个字符串按照字母序排序;之后
再将整个字符串数组按照字典序排序。整个操作的时间复杂度?
O(nslog(s)) + 0(snlog(n)) = 0( nslogs + snlogn )
= O( n
s
(logs+logn) )

数据规模

在一条常规操作指令的前提下,如果如果要想在1s之内解决问题:
O(n^2)的算法可以处理大约10^4级别 的数据;
O(n)的算法可以处理大约10^8级别的数据;
O(nlogn)的算法可以处理大约10^7级别的数据

验证时间复杂度

对于自己的算法,通过迭代控制输入的数据量,每次迭代增加2倍的数据量,然后比较前后两次时间的变化,判断时间复杂度

递归时间复杂度

递归中进行一次递归调用的复杂度分析(看递归的深度)

递归中进行多次递归调用的复杂度分析(观察递归深度+每层时间复杂度)

空间复杂度

数组

常见问题

  1. 排序:选择排序;插入排序;归并排序;快速排序
  2. 查找:二分查找法
  3. 数据结构:栈;队列;堆

二分查找

对于有序数列,才能使用二分查找法(排序的作用)

1
2
3
4
5
6
7
8
9
10
11
12
int binarySearch( T arr[], int n, T target ){
int 1 = 0,r= n- 1; // 在[l... r]的范围里寻找target
while( l <= r ){ //当l == r时,区间[l...r]依然是有效的
int mid = l+(r-l)/2; //这样可以避免整数溢出,(l+r)/2当数极大的时候,会溢出
if( arr [mid] == target )
return mid;
if( target > arr [mid] )
l = mid + 1; // target在[mid+1...r]中
else // target < arr[mid]
r = mid - 1; // target在[l...mid-1]中
}
return -1;

283. 移动零

利用双指针,指针i遍历不为0的数字,将其保留到[0,k)的数组中,k指针始终落后或同步于i指针,因此i指针所扫描的非零数字都可以被[0,K)中

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public void moveZeroes(int[] nums) {
int k=0;
for(int i=0;i<nums.length;i++){
if(nums[i] != 0){
nums[k++] = nums[i];
}
}
for(int j=k;j<nums.length;j++){
nums[j] = 0;
}
}
}

27. 移除元素

给定一个数组nums和一个数值val,将数组中所有等于val的元素删除,并返回剩余的元素个数。

  • 如何定义删除?从数组中去除?还是放在数组末尾?
  • 剩余元素的排列是否要保证原有的相对顺序?
  • 是否有空间复杂度的要求? 0(1)

解题思路:与283类似,只不过是将0替换成了目标值

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int removeElement(int[] nums, int val) {
int k=0;
for(int i=0;i<nums.length;i++){
if(nums[i] != val){
nums[k++] = nums[i];
}
}
return k--;
}
}

26. 删除排序数组中的重复项

给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

解题思路:与前面删除元素题目相似,同样是将满足条件的数保存在[0,k]中,只不过要删除的元素是动态变化,当前元素比k大时,则++k后再互换,因为需要保留一个k的元素在数组中

1
2
3
4
5
6
7
8
9
10
class Solution {
public int removeDuplicates(int[] nums) {
int k=0;
for(int i=0;i<nums.length;i++){
if(nums[i] > nums[k])
nums[++k] = nums[i];
}
return ++k;
}
}

80. 删除排序数组中的重复项 II

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

解题思路:与26类似,只不过需要保留两个元素,因此需要加一个条件判断,判断当前元素与之前是否相同,且是否为第二个,是的话则将将k移动到第二个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int removeDuplicates(int[] nums) {
int k=0;
int count = 1;
for(int i=1;i<nums.length;i++){
if(nums[i] == nums[i-1] && count <2){
nums[++k] = nums[i];
count++;
}else if(nums[i] > nums[k]){
nums[++k] = nums[i];
count=1;
}
}
return ++k;
}
}

综上:

删除某个元素,就是要将有效的元素保留在[0,k]/[0,k)中,比对要删除的元素,可能是某个固定的值/也可能是动态变化的值,当与其不同时,则进行交换/覆盖

排序思想

75. 颜色分类

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

解题思路:三路排序思想,分别设置三个区间[0,zero]、(zero,i)、[two,n-1]

初始条件:由于0区间和2区间无数,所以分别设置为-1和n,当与2进行交换时,two–,再交换,i不做变换,进行下次判断;当与0进行交换时,由于i有可能和zero同步,因此每当zero++时,i也++确保区间满足[0,zero]、(zero,i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public void sortColors(int[] nums) {
int zero = -1;
int two = nums.length;
for(int i=0;i<two;){//结束条件
if(nums[i]==0){//当为0时,与zero++进行交换,同时i++
zero++;
swap(nums,i++,zero);
}else if(nums[i]==2){//为2时,与two--进行交换,进行下一轮判断
two--;
swap(nums,i,two);
}else//当为1时,则直接i++
i++;
}
}

public void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j]= temp;
}
}

88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

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
public void merge(int[] nums1, int m, int[] nums2, int n) {
//时间换空间,需要再复制
// int len1 = m - 1;
// int len2 = n - 1;
// int len = m + n -1;
// while(len1 >= 0 && len2 >= 0){
// nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
// }
// System.arraycopy(nums2,0,nums1,0,len2+1);

//复制数组先,避免数组1的值被覆盖
int k=0;
int i=0;
int j=0;
int[] clone = nums1.clone();
while(k<m+n){
if(i>=m){
nums1[k++] = nums2[j++];
}else if(j>=n){
nums1[k++] = clone[i++];
}else if(clone[i] < nums2[j]){
nums1[k++] = clone[i++];
}else
nums1[k++] = nums2[j++];
}
}

215. 数组中的第K个最大元素(Medium)

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

解题思路:

求第K大的数,则在排序后的索引为length-k

利用快排求得索引为length-k得元素

partition可以做到O(n)

时间复杂度分析:每次扫描剩下一半得元素,则n+n/2+n/4+…..1=2n-1

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
32
33
34
35
class Solution {
public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int l = 0;
int h = nums.length - 1;
while(l < h){
int ans = partition(nums,l,h);
if(ans == k)
break;
else if(ans < k){
l = ans + 1;
}else{
h = ans - 1;
}
}
return nums[k];
}

public int partition(int[] nums,int low,int high){
int i,j;
for( i=low,j=low;j<high;j++){
if(nums[j]<nums[high]){//i,j利用滑动窗口,确保[i,j)得元素都是大于nums[high],然后最后置换i,j,则将数据分为两半
swap(nums,i++,j);
}
}
swap(nums,i,j);
return i;
}

public void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

对撞指针

167. 两数之和 II - 输入有序数组(Easy)

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

解题思路:

由于数组有序,可以遍历数组,target-nums[i],通过二分搜索来搜索下个数得索引,时间复杂度为nlogn

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
public int[] twoSum(int[] numbers, int target) {
int[] res = new int[2];
for(int i=0;i<numbers.length;i++){
int val = target - numbers[i];
int index = binarySearch(numbers,val,i+1,numbers.length-1);
if(index > 0){
res[0] = i+1;
res[1] = index + 1;
break;
}
}
return res;
}

public int binarySearch(int[] nums,int val,int l,int h){
int ans = -1;
while(l <= h){
int mid = l + (h-l)/2;
if(nums[mid] < val)
l = mid+1;
else if(nums[mid] > val)
h = mid-1;
else {
ans = mid;
break;
}
}
return ans;
}

125. 验证回文串(Easy)

使用Character.isLetterOrDigit() 来判断是否是数字和字母
使用toCharArray()来将字符串转化成char数组
char类型不能用==来比较,需要转换成int

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
public class Palindrome {
public boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
char[] charArray = s.toCharArray();

while (i < j) {
// 将i和j指向第一个是字母和数字的位置
while (!Character.isLetterOrDigit(charArray[i]) && i < j) {
i++;
}
while (!Character.isLetterOrDigit(charArray[j]) && i < j) {
j--;
}

// 如果不相等,就返回false
if ((int) Character.toLowerCase(charArray[i]) != (int) Character.toLowerCase(charArray[j])) {
return false;
}

// 将i和j向中间移动
i++; j--;
}

return true;
}
}

344. 反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

1
2
3
4
5
6
7
8
9
10
11
12
public void reverseString(char[] s) {

int l = 0;
int h = s.length-1;
while(l<h){
char temp = s[l];
s[l] = s[h];
s[h] =temp;
l++;
h--;
}
}

11. 盛最多水的容器Medium

img

解题思路:

求解最大的面积,那么要求我们往一个容器面积可能变大的方向进行迭代,从而记录最大值;

通过双指针,利用一个数学思维,将边比较短的一变缩进,则面积可能变大,消态法:

  • 消态法:若h[i]<h[j],则i++,计算s(h[i+1],h[j]),则相当于消去了 {S(i, j - 1), S(i, j - 2), … , S(i, i + 1)}S(i,j−1),S(i,j−2),…,S(i,i+1) 状态集合。而所有消去状态的面积一定<=S(i,j):短板高度:相比 S(i, j)S(i,j) 相同或更短(<= h[i]<=h[i]);

  • 底边宽度:相比 S(i, j)S(i,j) 更短。

  • 因此所有消去的状态的面积都 < S(i, j)<S(i,j)。通俗的讲,我们每次向内移动短板,所有的消去状态都不会导致丢失面积最大值 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    public int maxArea(int[] height) {
int ans = 0;
int l=0;
int r=height.length-1;
while(l<r){
int hL = height[l];
int hR = height[r];
ans = Math.max(ans,Math.min(hL,hR)*(r-l));
if(hL < hR)
l++;
else
r--;
}
return ans;
}

滑动窗口

209. 长度最小的子数组(Medium)

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组,并返回其长度如果不存在符合条件的连续子数组,返回 0。

示例:

1
2
3
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
0%