十道必知必会算法面试题
01翻转链表
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
力扣题目链接
题解
image.png
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。
python实现
#双指针
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur != None: # 这里必须得判断cur != None而不是cur.next != None，否则在cur为None是会报错
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
java实现
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null)//如果节点为NULL或者单个节点直接返回
return head;
ListNode pre=head;//前驱节点
ListNode cur=head.next;//当前节点用来枚举
while (cur!=null)
{
ListNode next=cur.next;
//改变指向
cur.next=pre;
pre=cur;
cur=next;
}
head.next=null;//将原先的head节点next置null防止最后成环
return pre;
}
}
02设计LRU
题意：请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
力扣题目链接
光看这个题就想放弃
题解
方法：哈希表 + 双向链表
算法
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1)O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：
对于 get 操作，首先判断 key 是否存在：
如果 key 不存在，则返回 -1−1；
如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
对于 put 操作，首先判断 key 是否存在：
如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。
上述各项操作中，访问哈希表的时间复杂度为 O(1)O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1)O(1) 时间内完成。
python实现
class DLinkedNode:
def __init__(self,key=0,value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self,capacity:int):
self.cache = dict()
# 使用伪头部和伪尾部节点作为标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.next = self.head
self.capacity = capacity
self.size = 0
def get(self,key:int):
if key not in self.cache:
return -1
# 如果 key 存在，先通过哈希表定位，再移到头部
node = self.cache[key]
self.moveToHead(node)
return node.value
def put(self,key:int,value:int):
if key not in self.cache:
# 如果 key 不存在，创建一个新的节点
node = DLinkedNode(key,value)
# 添加进哈希表
self.cache[key] = node
#添加至双向链表头部
self.addToHead(node)
self.size += 1
if self.size > self.capacity:
# 如果超出容量，删除双向链表的尾部节点
removed = self.removeTail()
# 删除哈希表中对应的项
self.cache.pop(removed.key)
self.size -= 1
else:
# 如果key存在，先通过哈希表定位，再修改value，并移到头部
node = self.cache[key]
node.value = value
self.moveToHead(node)
def addToHead(self,node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node # 记住这一步和下一步的顺序不能反
self.head.next = node
def removeNode(self,node):
node.prev.next = node.next
node.next.prev = node.prev
def moveToHead(self,node):
self.removeNode(node)
self.addToHead(node)
def removeTail(self):
node = self.tail.prev
self.removeNode(node)
return node
java实现
class LRUCache {
class Node {
int key;
int value;
Node pre;
Node next;
public Node() {
}
public Node( int key,int value) {
this.key = key;
this.value=value;
}
}
class DoubleList{
private Node head;// 头节点
private Node tail;// 尾节点
private int length;
public DoubleList() {
head = new Node(-1,-1);
tail = head;
length = 0;
}
void add(Node teamNode)// 默认尾节点插入
{
tail.next = teamNode;
teamNode.pre=tail;
tail = teamNode;
length++;
}
void deleteFirst(){
if(head.next==null)
return;
if(head.next==tail)//如果删除的那个刚好是tail 注意啦 tail指针前面移动
tail=head;
head.next=head.next.next;
if(head.next!=null)
head.next.pre=head;
length--;
}
void deleteNode(Node team){
team.pre.next=team.next;
if(team.next!=null)
team.next.pre=team.pre;
if(team==tail)
tail=tail.pre;
team.pre=null;
team.next=null;
length--;
}
}
Map<Integer,Node> map=new HashMap<>();
DoubleList doubleList;//存储顺序
int maxSize;
LinkedList<Integer>list2=new LinkedList<>();
public LRUCache(int capacity) {
doubleList=new DoubleList();
maxSize=capacity;
}
public int get(int key) {
int val;
if(!map.containsKey(key))
return -1;
val=map.get(key).value;
Node team=map.get(key);
doubleList.deleteNode(team);
doubleList.add(team);
return val;
}
public void put(int key, int value) {
if(map.containsKey(key)){// 已经有这个key 不考虑长短直接删除然后更新
Node deleteNode=map.get(key);
doubleList.deleteNode(deleteNode);
}
else if(doubleList.length==maxSize){//不包含并且长度小于
Node first=doubleList.head.next;
map.remove(first.key);
doubleList.deleteFirst();
}
Node node=new Node(key,value);
doubleList.add(node);
map.put(key,node);
}
}
03环形链表
题目：给定一个链表，判断链表中是否有环，用O(1)内存解决。
力扣题目链接
题解：这个问题利用快慢双指针比较高效，快指针fast每次走2步，slow每次走1步，慢指针走n步到尾时候快指针走了2n步，而环的大小一定小于等于n所以一定会相遇，如果相遇那么说明有环，如果不相遇fast先为null说明无环。
python实现
class Solution:
def hasCycle(self, head):
fast,slow = head,head
while fast != None and fast.next != None : # fast.next != None 这里必须得判断fast.next是因为下面fast每次走两步
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False
java实现
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast=head;
ListNode slow=fast;
while (fast!=null&&fast.next!=null) {
slow=slow.next;
fast=fast.next.next;
if(fast==slow)
return true;
}
return false;
}
}
扩展：如有有环，返回入环的那个节点
力扣题目链接
题解：交汇时候fast走2x步，slow走x步，环长为y。并且快指针和慢指针交汇时候，多走的步数刚好是换长y的整数倍（它两此刻在同一个位置，快指针刚好多绕整数倍圈数才能在同一个位置相聚），可以得到2x=x+ny(x=ny)。所以说慢指针走的x和快指针多走的x是圈长y的整数倍。从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是环形入口的节点
python实现
class Solution:
def hasCycle(self, head):
slow,fast = head,head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
p = head
q = slow
while p != q:
p = p.next
q = q.next
return p
return None
java实现
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
if (slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2; // 返回环的入口
}
}
return NULL;
}
};
04两个栈实现队列
题目：两个栈实现队列，题意为：
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
力扣题目链接
题解：使用两个栈，一个用来插入，一个用来删除，删除的栈stack2空了添加所有stack1中的数据继续操作。
python实现
class Myqueue:
def __init__(self):
self.stack_in = []
self.stack_out = []
def push(self,x):
self.stack_in.append(x)
def pop(self):
if len(self.stack_out) == 0: # 输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入）
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
if len(self.stack_out) == 0: # 这里的判断条件其实是stack_out和stack_in都为0，走到这个判断时in栈必空
return -1
return self.stack_out.pop()
java实现
class CQueue {
Deque<Integer> stack1;
Deque<Integer> stack2;
public CQueue() {
stack1 = new LinkedList<Integer>();
stack2 = new LinkedList<Integer>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
// 如果第二个栈为空 将stack1数据加入stack2
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
} //如果stack2依然为空 说明没有数据
if (stack2.isEmpty()) {
return -1;
} else {//否则删除
int deleteItem = stack2.pop();
return deleteItem;
}
}
}
05二叉树层序(锯齿)遍历
题目：给你二叉树的根节点 root ，返回其节点值的层序遍历 。 （即逐层地，从左到右访问所有节点）。
力扣题目链接
题解：需要借用一个辅助数据结构即队列来实现，队列先进先出，我们首先记录枚举前队列大小len，然后根据这个大小len去枚举遍历就可以得到完整的该层数据了，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
python实现
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self,root):
# 存储每层的节点列表
results = []
if not root:
return results
# 辅助队列
queue = [root]
while queue:
# 获取当前层的节点数
length = len(queue)
alist = []
for i in range(length):
node = queue.pop(0)
# 存储当前节点
alist.append(node.val)
# 把当前节点所有的左右节点全部加入队列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
results.append(alist)
return results
java实现
class Solution {
public List<List<Integer>> resList = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
checkFun(root);
return resList;
}
//BFS--迭代方式--借助队列
public void checkFun(TreeNode node) {
if (node == null) return;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
while (!que.isEmpty()) {
List<Integer> itemList = new ArrayList<Integer>();
int len = que.size();
while (len > 0) {
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if (tmpNode.left != null) que.offer(tmpNode.left);
if (tmpNode.right != null) que.offer(tmpNode.right);
len--;
}
resList.add(itemList);
}
}
}
06 二叉树前中后序遍历(非递归)
题解前序：前序遍历是中左右，非递归与递归实现区别在于的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来。
python实现
class Solution: # 递归
def preorderTraversal(self, root: TreeNode) -> List[int]:
def preorder(root: TreeNode):
if not root:
return
res.append(root.val)
preorder(root.left)
preorder(root.right)
res = list()
preorder(root)
return res
---------------------------------------------------
class Solution: # 非递归
def preorderTraversal(self,root):
if not root:
return []
res = []
stack = []
node = root
while stack or node:
while node:
res.append(node.val)
stack.append(node)
node = node.left
node = stack.pop()
node = node.right
return res
java实现
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
return result;
}
}
中序题解：对于二叉树的中序遍历，其实就是正常情况第二次访问该节点的时候才抛出输出(第一次数前序)，这样我们枚举每个节点第一次不能删除，需要先将它存到栈中，当左子节点处理完成的时候在抛出访问该节点。
核心也就两步，叶子节点左右都为null，也可满足下列条件：
1.枚举当前节点(不存储输出)并用栈存储，节点指向左节点，直到左孩子为null。
2.抛出栈顶访问。如果有右节点，访问其右节点重复步骤1，如有没右节点，继续重复步骤2抛出。
python实现
# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
def traversal(root: TreeNode):
if root == None:
return
traversal(root.left) # 左
result.append(root.val) # 中序
traversal(root.right) # 右
traversal(root)
return result
--------------------------------------------------
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
java实现
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer>value=new ArrayList<Integer>();
Stack<TreeNode> q1 = new Stack();
while(!q1.isEmpty()||root!=null)
{
while (root!=null) {
q1.push(root);
root=root.left;
}
root=q1.pop();//抛出
value.add(root.val);
root=root.right;//准备访问其右节点
}
return value;
}
}
后序题解：而后序遍历按照递归的思路其实一般是第三次访问该节点是从右子节点回来才抛出输出，这个实现起来确实有难度。但是具体的实现，我们使用一个pre节点记录上一次被抛出访问的点，如果当前被抛出的右孩子是pre或者当前节点右为null，那么就将这个点抛出，否则说明它的右侧还未被访问需要将它"回炉重造"，后面再用！
python实现
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
def traversal(root: TreeNode):
if root == None:
return
traversal(root.left) # 左
traversal(root.right) # 右
result.append(root.val) # 中序
traversal(root)
return result
----------------------------------------------------------
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
# 中结点先处理
result.append(node.val)
# 左孩子先入栈
if node.left:
stack.append(node.left)
# 右孩子后入栈
if node.right:
stack.append(node.right)
# 将最终的数组翻转
return result[::-1]
java实现
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
TreeNode temp=root;//枚举的临时节点
List<Integer>value=new ArrayList<>();
TreeNode pre=null;//前置节点
Stack<TreeNode>stack=new Stack<>();
while (!stack.isEmpty()||temp!=null){
while(temp!=null){
stack.push(temp);
temp=temp.left;
}
temp=stack.pop();
if(temp.right==pre||temp.right==null)//需要弹出
{
value.add(temp.val);
pre=temp;
temp=null;//需要重新从栈中抛出
}else{
stack.push(temp);
temp=temp.right;
}
}
return value;
}
}
07跳台阶(斐波那契、爬楼梯)
题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
题解：这个问题入门级别dp，分析当前第k阶的结果，每个人可以爬1个或者2个台阶，那么说明它可能是由k-1或者k-2来的，所以就是两个子情况的叠加(需要特殊考虑一下初始情况)，这个思路有人会想到递归，没错用递归确实可以解决但是用递归效率较低(因为这个是个发散的递归一个拆成两个)，使用记忆化搜索会稍微好一些。
但是dp是比较好的方法，核心状态转移方程为：dp[i]=dp[i-1]+dp[i-2]，有些空间优化的那就更好了，因为只用到前两个值，所以完全可以用三个值重复使用节省空间。
python实现
# 空间复杂度为O(n)版本
class Solution:
def climbStairs(self, n: int) -> int:
# dp[i] 为第 i 阶楼梯有多少种方法爬到楼顶
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
# 空间复杂度为O(1)版本
class Solution:
def climbStairs(self, n: int) -> int:
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
tmp=dp[0]+dp[1]
dp[0]=dp[1]
dp[1]=tmp
return dp[1]
java实现
class Solution {
public int climbStairs(int n) {
if(n<3)return n;
int dp[]=new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i=3;i<n+1;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
public int climbStairs(int n) {
int a = 0, b = 0, c = 1;
for (int i = 1; i <= n; i++) {
a = b;
b = c;
c = a + b;
}
return c;
}
}
08 TOPK问题
通常问的有最小的K个数，寻找第K大都是TOPK这种问题，这里就用力扣215寻找数组第K大元素作为例子。
题目：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
题解：其实就是考察排序
python实现
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
if len(nums) == 1: return nums[0]
mid = int(len(nums) // 2)
left, right, mids = [], [], []
for i in range(len(nums)):
if nums[i] > nums[mid]:
left.append(nums[i])
elif nums[i] < nums[mid]:
right.append(nums[i])
else:
mids.append(nums[i])
if len(left) >= k:
return self.findKthLargest(left, k)
elif len(mids) >= k - len(left):
return nums[mid]
else:
return self.findKthLargest(right, k - len(left) - len(mids))
java实现
class Solution {
public int findKthLargest(int[] nums, int k) {
quickSort(nums,0,nums.length-1,k);
return nums[nums.length-k];
}
private void quickSort(int[] nums,int start,int end,int k) {
if(start>end)
return;
int left=start;
int right=end;
int number=nums[start];
while (left<right){
while (number<=nums[right]&&left<right){
right--;
}
nums[left]=nums[right];
while (number>=nums[left]&&left<right){
left++;
}
nums[right]=nums[left];
}
nums[left]=number;
int num=end-left+1;
if(num==k)//找到k就终止
return;
if(num>k){
quickSort(nums,left+1,end,k);
}else {
quickSort(nums,start,left-1,k-num);
}
}
}
09 无重复的最长子串(数组)
题目：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
题解：先区分两个概念，子串：是连续的，可以看成原串的一部分截取。
子序列：不一定是连续的，但是要保证各个元素之间相对位置不变。
这里选择的思路是滑动窗口，滑动窗口，就是用一个区间从左往右，右侧先进行试探，找到区间无重复最大值，当有重复时左侧再往右侧移动一直到没重复，然后重复进行到最后。在整个过程中找到最大子串即可。
python实现
class Solution:
def lengthOfLongestSubstring(s):
occ = set()
n = len(s)
right = -1
ans = 0
for i in range(n):
if i != 0:
occ.remove(s[i-1])
while right + 1 < n and s[right+1] not in occ:
occ.add(s[right+1])
right += 1
ans = max(ans,right-i+1)
return ans
java实现
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}
10 排序
此处可查看排序算法-python实现
