前言

大家好，这里收集了腾讯常考的十道算法题（真题）。在金三银四，希望对大家有帮助呀。

  1. 重排链表
  2. 最长递增子序列
  3. 环形链表
  4. 反转链表
  5. 最长回文子串
  6. 全排列
  7. LRU 缓存
  8. 合并K个升序链表
  9. 无重复字符的最长子串
  10. 删除链表的倒数第 N 个结点

1. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln复制代码

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …复制代码

输入：

head = [1,2,3,4]复制代码

输出：

[1,4,2,3]复制代码

思路：

如果是数组就好了，哈哈，因为数组可以直接通过下标访问，很容易就可以解答这道题了。但是这是链表。链表不支持下标访问，我们没办法随机访问到链表任意位置的元素，怎么办呢？

我们可以先遍历一下，用数组把链表的元素按顺序存储起来呀，然后就可以把它当做数组这么访问来用了对吧，最后重建下链表即可啦。

ArrayList的底层就是数组，我们先用它存储链表就好，如下：

 List list = new ArrayList(); ListNode node = head; while (node != null) {list.add(node);node = node.next;}复制代码

有了一个数组结构的链表后，如何重建链表呢？ 回头多看示例两眼，很容易就发小规律啦：先排第1个，再排倒数第1个，接着排第2个，紧接着倒数第2个。显然这个规律很明显，代码也比较好实现：

int i = 0;int j = list.size()-1;while(i<j){list.get(i).next = list.get(j);i++;if(i==j){break; } list.get(j).next = list.get(i); j--;}//大家画个图就很清晰知道为什么需要这行了，哈哈 list.get(i).next = null;复制代码

完整实现代码如下：

class Solution {public void reorderList(ListNode head) {if (head == null) {return;}List list = new ArrayList();ListNode node = head;while (node != null) {list.add(node);node = node.next;}int i = 0, j = list.size() - 1;while (i < j) {list.get(i).next = list.get(j);i++;if (i == j) {break;}list.get(j).next = list.get(i);j--;}list.get(i).next = null;}}复制代码

2. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

实例1：

输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。复制代码

实例2：

输入：nums = [0,1,0,3,2,3]输出：4复制代码

思路：

这道题是求最值问题，可以使用动态规划解决。动态规划的解题整体思路就是：

  1. 穷举分析
  2. 分析找规律，拆分子问题
  3. 确定边界
  4. 确定最优子结构
  5. 写出状态转移方程

2.1 穷举分析

动态规划的核心思想包括拆分子问题，记住过往，减少重复计算。 所以我们在思考原问题：数组num[i]的最长递增子序列长度时，可以思考下相关子问题，比如原问题是否跟子问题num[i-1]的最长递增子序列长度有关呢？

自底向上的穷举过程：

  • 当nums只有一个元素10时，最长递增子序列是[10],长度是1.
  • 当nums需要加入一个元素9时，最长递增子序列是[10]或者[9],长度是1。
  • 当nums再加入一个元素2时，最长递增子序列是[10]或者[9]或者[2],长度是1。
  • 当nums再加入一个元素5时，最长递增子序列是[2,5],长度是2。
  • 当nums再加入一个元素3时，最长递增子序列是[2,5]或者[2,3],长度是2。
  • 当nums再加入一个元素7时，,最长递增子序列是[2,5,7]或者[2,3,7],长度是3。
  • 当nums再加入一个元素101时，最长递增子序列是[2,5,7,101]或者[2,3,7,101],长度是4。
  • 当nums再加入一个元素18时，最长递增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],长度是4。
  • 当nums再加入一个元素7时,最长递增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],长度是4.

2.2 分析找规律，拆分子问题

通过上面分析，我们可以发现一个规律：

如果新加入一个元素nums[i], 最长递增子序列要么是以nums[i]结尾的递增子序列，要么就是nums[i-1]的最长递增子序列。看到这个，是不是很开心，nums[i]的最长递增子序列已经跟子问题 nums[i-1]的最长递增子序列有关联了。

原问题数组nums[i]的最长递增子序列 = 子问题数组nums[i-1]的最长递增子序列/nums[i]结尾的最长递增子序列

是不是感觉成功了一半呢？但是如何把nums[i]结尾的递增子序列也转化为对应的子问题呢？要是nums[i]结尾的递增子序列也跟nums[i-1]的最长递增子序列有关就好了。又或者nums[i]结尾的最长递增子序列，跟前面子问题num[j]（0=<j<i）结尾的最长递增子序列有关就好了，带着这个想法，我们又回头看看穷举的过程：