常见算法笔试题
常见算法
算法与数据结构是⾯试考察的重中之重，也是⽇后刷题时需要着重训练的部分。
简单的总结⼀下，⼤约有这些内容：
算法 - Algorithms
1、排序算法：快速排序、归并排序、计数排序
2、搜索算法：回溯、递归、剪枝技巧
3、图论：最短路、最⼩⽣成树、⽹络流建模
4、动态规划：背包问题、最长⼦序列、计数问题
5、基础技巧：分治、倍增、⼆分、贪⼼
数据结构 - Data Structures
1、数组与链表：单/双向链表、跳舞链
2、栈与对列
3、树与图：最近公共祖先、并查集
4、哈希表
5、堆：⼤/⼩根堆、可并堆
6、字符串：字典树、后缀树
递归与迭代的区别
递归（recursion）：递归常被⽤来描述以⾃相似⽅法重复事物的过程，在数学和计算机科学中，指的是在函数定义中使⽤函数⾃⾝的⽅法。（A调⽤A ）
迭代（iteration）：重复反馈过程的活动，每⼀次迭代的结果会作为下⼀次迭代的初始值。（A重复调⽤B）
递归是⼀个树结构，从字⾯可以其理解为重复“递推”和“回归”的过程，当“递推”到达底部时就会开始“回
归”，其过程相当于树的深度优先遍历。
迭代是⼀个环结构，从初始状态开始，每次迭代都遍历这个环，并更新状态，多次迭代直到到达结束状态。
# 理论上递归和迭代时间复杂度⽅⾯是⼀样的，但实际应⽤中（函数调⽤和函数调⽤堆栈的开销）递归⽐迭代效率要低。
链接：www.jianshu/p/32bcc45efd32
来源：简书
算法的时间复杂度和空间复杂度
时间复杂度和空间复杂度是⽤来评价算法效率⾼低的2个标准。
时间复杂度：就是说执⾏算法需要消耗的时间长短，越快越好。⽐如你在电脑上打开计算器，如果⼀个普通的运算要消耗1分钟时间，那谁还会⽤它呢，还不如⾃⼰⼝算呢。
空间复杂度：就是说执⾏当前算法需要消耗的存储空间⼤⼩，也是越少越好。本来计算机的存储资源就是有限的，如果你的算法总是需要耗费很⼤的存储空间，这样也会给机器带来很⼤的负担。
时间复杂度的计算
表⽰⽅法
我们⼀般⽤“⼤O符号表⽰法”来表⽰时间复杂度：T(n) = O(f(n)) n是影响复杂度变化的因⼦，f(n)是复杂度具体的算法。
常见的时间复杂度量级
常数阶O(1)
线性阶O(n)
对数阶O(logN)
线性对数阶O(nlogN)
平⽅阶O(n²)
⽴⽅阶O(n³)
K次⽅阶O(n^k)
指数阶(2^n)
常见的时间复杂度（按效率排序） O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
接下来再看⼀下不同的复杂度所对应的算法类型。
常数阶O(1)
int a = 1;
int b = 2;
int c = 3;
线性阶O(n)
for(i = 1; i <= n; i++) {
j = i;
j++;
}
对数阶O(logN)
int i = 1;
while(i < n) {
i = i * 2;
}
线性对数阶O(nlogN)
for(m = 1; m < n; m++) {
i = 1;
while(i < n) {
i = i * 2;
}
}
平⽅阶O(n²)
for(x = 1; i <= n; x++){
for(i = 1; i <= n; i++) {
j = i;
j++;
}
}
空间复杂度计算
空间复杂度 O(1)
如果算法执⾏所需要的临时空间不随着某个变量n的⼤⼩⽽变化，即此算法空间复杂度为⼀个常量，可表⽰为 O(1)。
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。
空间复杂度 O(n)
int[] m = new int[n]
笔试题for(i = 1; i <= n; ++i) {
j = i;
j++;
}
这段代码中，第⼀⾏new了⼀个数组出来，这个数据占⽤的⼤⼩为n，后⾯虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第⼀⾏即可，即 S(n) = O(n)。⼗⼤经典排序算法
# 冒泡排序
⽐较相邻的元素。如果第⼀个⽐第⼆个⼤，就交换他们两个。
对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对。这步做完后，最后的元素会是最⼤的数。
针对所有的元素重复以上的步骤，除了最后⼀个。
持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。
import sys
sys.setrecursionlimit(1000000)
## 冒泡排序  (******)
### 时间复杂度：O(n^2)
def Bubble_sort(li):
for i in range(len(li)-1):
for j in range(len(li)-1-i):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
## 选择排序
⾸先在未排序序列中到最⼩（⼤）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻最⼩（⼤）元素，然后放到已排序序列的末尾。
重复第⼆步，直到所有元素均排序完毕。
#### 时间复杂度：O(n^2)
def select_sort(li):
for i in range(len(li)):
minLoc = i ###i = 0
for j in range(i+1, len(li)):
if li[j] < li[minLoc]:
li[j], li[minLoc] = li[minLoc], li[j]
> 插⼊排序（打扑克牌）
将第⼀待排序序列第⼀个元素看做⼀个有序序列，把第⼆个元素到最后⼀个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插⼊有序序列的适当位置。（如果待插⼊的元素与有序序列中的某个元素相等，则将待插⼊元素插⼊到相等元素的后⾯。）
#### 时间复杂度： O(n^2)
def insert_sort(li):
for i in range(1, len(li)):
tmp = li[i]
j = i - 1
while j >=0 and li[j] > tmp:
li[j+1] = li[j]
j = j - 1
li[j+1] = tmp
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp:
right = right - 1
li[left] = li[right]
while left < right and li[left] <= tmp:
left = left + 1
li[right] = li[left]
li[left] = tmp
return left
## 快速排序
1、从数列中挑出⼀个元素，称为 "基准"（pivot）;
2、重新排序数列，所有元素⽐基准值⼩的摆放在基准前⾯，所有元素⽐基准值⼤的摆在基准的后⾯（相同的数可以到任⼀边）。在这个分区退出之后
，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3、递归地（recursive）把⼩于基准值元素的⼦数列和⼤于基准值元素的⼦数列排序；
## 时间复杂度：O(nlogn)
def quick_sort(li, left, right):
if left < right:
mid = partition(li, left, right)
quick_sort(li, left, mid-1)
quick_sort(li, mid+1, right)
# 计算时间复杂度
import time,random
li = [random.randint(1,100) for _ in range(100000)]
start = time.time()
quick_sort(li, 0, len(li)-1)
cost = time.time() - start
print('quick_sort:%s' % (cost))
import time,random
li = [random.randint(1,100) for _ in range(100000)]
start = time.time()
Bubble_sort(li)
cost = time.time() - start
print('bubble_sort:%s' % (cost))
import time,random
li = [random.randint(1,100) for _ in range(100000)]
start = time.time()
insert_sort(li)
cost = time.time() - start
print('insert_sort:%s' % (cost))
算法-⼒扣（LeetCode）
链表反转
反转⼀个单链表：
输⼊: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否⽤两种⽅法解决这道题？
# 双向指针迭代
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 申请两个节点，pre和 cur，pre指向None
pre = None
cur = head
# 遍历链表，while循环⾥⾯的内容其实可以写成⼀⾏
# 这⾥只做演⽰，就不搞那么骚⽓的写法了
while cur:
# 记录当前节点的下⼀个节点
tmp =
# 然后将当前节点指向pre
< = pre
# pre和cur节点都前进⼀位
pre = cur
cur = tmp
return pre
# 2、递归解法
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 递归终⽌条件是当前为空，或者下⼀个节点为空
if(head==None ==None):
return head
# 这⾥的cur就是最后⼀个节点
cur = )
# 这⾥请配合动画演⽰理解
# 如果链表是 1->2->3->4->5，那么此时的cur就是5
# ⽽head是4，head的下⼀个是5，下下⼀个是空
# 所以 就是5->4
# 防⽌链表循环，需要将设置为空
< = None
# 每层递归函数都返回cur，也就是最后⼀个节点
return cur
来源：⼒扣（LeetCode）
反转字符串
编写⼀个函数，其作⽤是将输⼊的字符串反转过来。输⼊字符串以字符数组 char[] 的形式给出。⽰例
输⼊：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
简单实现
class Solution:
def reverseString(self, s):
# 1、递归实现
class Solution:
def reverseString(self, s):
def helper(left, right):
if left < right:
s[left], s[right] = s[right], s[left]
helper(left + 1, right - 1)
helper(0, len(s) - 1)
# 2、⼀部实现
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
# one step by python
s[:] = s[::-1]
来源：⼒扣（LeetCode）
⼆叉树的最⼤深度
给定⼀个⼆叉树，出其最⼤深度。
⼆叉树的深度为根节点到最远叶⼦节点的最长路径上的节点数。
说明: 叶⼦节点是指没有⼦节点的节点。
⽰例： 给定⼆叉树 [3,9,20,null,null,15,7]
3
/ \
9  20
/
  \
15  7
⽅法：递归
直观的⽅法是通过递归来解决问题。在这⾥，我们演⽰了 DFS（深度优先搜索）策略的⽰例。
class Solution:
def maxDepth(self,root): # root⼦节点
if root is None:
return 0
else:
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height,right_height)+1  #左右对⽐基于⼦节点+1
整数反转
给出⼀个 32 位的有符号整数，你需要将这个整数中每位上的数字进⾏反转。
⽰例：
输⼊: 123
输出: 321
⽅法：字符串的反转，记录符号位。
class Solution:
def reverse(self, x: int) -> int:
flag = -1 if x < 0  else 1
res = flag * int(str(abs(x))[::-1])
return res if (-2**31)<=res<=(2**31-1) else 0
作者：powcai
删除排序中数组中的重复项
给定⼀个排序数组，你需要在 删除重复出现的元素，使得每个元素只出现⼀次，返回移除后数组的新长度。
不要使⽤额外的数组空间，你必须在 修改输⼊数组 并在使⽤ O(1) 额外空间的条件下完成。
⽰例：
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后⾯的元素。
思路：
⽤两个指针，指向第⼀个和第⼆个元素，如果他们相等，删除第⼆个元素。指针还指向原来的位置，继续⽐较。不等的话，两个指针位置都加⼀。遍历结束即可。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
pre,cur=0,1 # 指针初始指向数
while cur<len(nums):
if nums[pre]==nums[cur]:
nums.pop(cur) # 取出重复数
else:
pre,cur=pre+1,cur+1  # 交换并加⼀往后
return len(nums)# 数组的长度