滑动窗口
3.无重复字符的最大子串
题目：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
思路：
滑动窗口思想，左右指针一直移动，遇到重复的就更新左边界(移除左边的元素)，数据结构方面用HashMap存储**<当前字符,出现 的位置+1>**
步骤：
-
定义数据结构
-
遍历字符串
- 遇到重复的就更新左边界（左指针）
- 更新最大长度
- 存当前字符对应的左边界
-
返回结果
代码
class Solution {
public int lengthOfLongestSubstring(String s) {
//滑动窗口 hashmap存储字符 以及字符对应的左边界
HashMap<Character,Integer> map = new HashMap<>();
int res = 0;
int last_next = 0;
//i右指针 j左指针
for(int i = 0,j = 0;i < s.length();i++){
//如果当前右指针的字符是出现过的
if(map.containsKey(s.charAt(i))){
//取一下这个字符的下一个字符下标 也就是左边界的起始位置
last_next = map.get(s.charAt(i));
//更新一下左指针
j = Math.max(j,last_next);
}
//更新一下最大长度
res = Math.max(res,i-j+1);
//存一下当前字符对应的下一次左边界的下标
map.put(s.charAt(i),i+1);
}
return res;
}
}
链表
146.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) 的平均时间复杂度运行。
- 思路：
首先我们需要一种数据结构来满足这道题的需求：遍历是O(1)复杂度，还能够记录使用顺序。
单是数组/链表/哈希表一种无法满足，使用LinkedHashMap又违反了这道题的初心，所以在选择数据结构上选择好了也就事半功倍了，我们选择的是双向链表（记录使用的顺序）+哈希表（查找O1），哈希表的key是Node的key，value是Node
然后在设计双向链表的时候有一点就是要使用哑节点，也就是真实的链表数据是在不变的head和tail之间的：
head (dummy) ↔ 实际节点1 ↔ 实际节点2 ↔ ... ↔ tail (dummy)
这样做的好处有两点：第一避免空指针判断，第二统一了头部插入和尾部删除操作
-
步骤：
-
定义数据结构Node类和LRUCache 类成员
-
初始化（哑节点）
-
完成get方法：判断node是否为空？返回-1：把node移到链表最前，返回node的value
-
完成put方法：判断node是否为空？不为空更新，然后将node移到链表最前；为空的话则创建新节点，把新节点移到链表最前，然后检查容量，如果超过链表容量，移除链表末尾的，并删除哈希表中的key
-
以上步骤需要四个方法完成：
- addToHead(node) - 头部插入；插入的是新节点
- removeNode(node) - 删除节点；
- moveToHead(node) - 移到头部；把已有节点移到头部（调用2+1方法）
- removeTail() - 删除尾部；获取尾部的节点，调用2方法
-
代码
class LRUCache {
//定义一个节点数据结构 双向链表+哈希表
class Node{
int key;
int value;
Node prev;
Node next;
Node(int key,int value){
this.key = key;
this.value = value;
}
}
private Map<Integer,Node> cache;
private int capacity;
private Node head,tail;
//双向链表技巧：哑节点
//head (dummy) ↔ 实际节点1 ↔ 实际节点2 ↔ ... ↔ tail (dummy)
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new HashMap<>();
head = new Node(0,0);
tail = new Node(0,0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if(node == null){
return -1;
}
//使用后移动到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
//如果节点非null 更新值 然后移动到头部
if(node != null){
node.value = value;
moveToHead(node);
}else{
//如果节点是null 新建一个节点
Node newNode = new Node(key,value);
cache.put(key,newNode);
addToHead(newNode);
//检查容量
if(cache.size() > capacity){
Node tailNode = removeTail();
cache.remove(tailNode.key); //map自带remove方法
}
}
}
//将当前新来的节点移到最前
private void addToHead(Node node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
//移除节点
private void removeNode(Node node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
//将当前已有节点移动到最前
private void moveToHead(Node node){
removeNode(node);
addToHead(node);
}
//删除并返回尾部的节点
private Node removeTail(){
Node res = tail.prev;
removeNode(res);
return res;
}
}
206.反转链表
-
题目：
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
-
思路：
-
迭代法
-
首先，原本初始化之后是这样的。 pre 指向 NULL， cur 指向head。 我们要明确一点，我们交换的对象只有两个 pre 和 cur。
第一步，我们定义好nxt节点，我们不会对nxt节点有任何操作，它就像一个锚点，帮助我们进入下一次循环而已
第二步， 我们执行最核心的反转步骤，
cur.next = pre，改变当前节点(cur节点)的next指针指向的位置，我们让他去指向pre节点
第三步，这里我们必须先移动 pre 再移动 cur。 不然会丢失节点位置，具体情况我会在最后的部分展示一张图
第四步，让cur节点去接替nxt节点的位置，方便下一次反转的操作
到此我们第一次循环已经结束了，我知道第一次循环没看明白，这里还有第二次第五步，我们定义好 nxt 节点并且进行反转操作
第六步，我们改变pre指针和cur指针为下一次遍历做好准备
最后，为什么要先移动 pre 再移动 cur， 我们可以试试先移动 cur 再移动 pre 来反证。先移动cur:
再移动pre:
这样我们下一次循环是不是就丢失了pre节点？
出处，十分清晰：我要弄懂每一个困难题
-
递归法
假设链表是：
1 -> 2 -> 3 -> 4 -> 5 -> null
1.1 递归到底
递归函数一直调用 reverseList(head.next)，直到 head == null或 head.next == null（即最后一个节点）。
这时返回最后一个节点 5作为新链表的头。
此时递归栈情况（从底向上）：reverseList(5) 返回 5 reverseList(4) 等待处理 reverseList(3) 等待处理 reverseList(2) 等待处理 reverseList(1) 等待处理1.2 回溯过程修改指针
回溯时，head是当前层的节点，newHead是已经反转好的部分的头节点（即原链表的尾节点 5）。关键操作：
head.next.next = head; // 把下一个节点指向自己（反转箭头） head.next = null; // 断开原来指向下一个节点的指针，防止成环以 head = 4为例： 此时 newHead = 5（已经反转好的部分的头） head.next是 5 head.next.next = head即 5.next = 4，形成 5 -> 4 head.next = null即 4.next = null（后面回溯到 3 时会改成指向 3）
-
-
代码：
class Solution {
public ListNode reverseList(ListNode head) {
//迭代法
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex;
}
return pre;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
//递归法
if(head == null || head.next == null){
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
25.K个一组翻转链表
-
题目：
给你链表的头节点
head，每k个节点一组进行翻转，请你返回修改后的链表。k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
代码：
-
思路
-
获取链表长度，计算能翻转的次数
-
循环n轮，每次翻转k个节点
- 一个指针记录上一组的尾部
- 一个指针记录这一组的开头
- 翻转当前的k个节点
- 将上一次尾部和翻转后的新头进行连接
- 更新上一组的尾部
-
解释一下这段代码：
// 连接上一组和当前组 prevGroupTail.next = prev; // 上一组尾部接新头 groupStart.next = curr; // 当前组尾部接下一组开头 prevGroupTail = groupStart; // 更新上一组尾部假设我们在翻转第2组（k=2）：
初始链表: dummy -> 2 -> 1 -> 3 -> 4 -> 5 -> 6 ↑ ↑ prevGroupTail curr (第2组开头)翻转第2组（3和4）后：
翻转后: 3 -> 4 变成 4 -> 3 但此时链表是断开的： dummy -> 2 -> 1 4 -> 3 5 -> 6 ↑ ↑ ↑ prevGroupTail prev curr (下一组开头)我们需要把这三段连接起来。
翻转完成后：
prev：当前翻转组的新头节点（比如4）
curr：下一组的开头节点（比如5）groupStart：当前翻转组翻转前的头（翻转后变成尾）（比如3）prevGroupTail：上一组的尾节点（比如1）
这题一定要画图画指针理解一下
-
-
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) return head;
// 1. 获取链表长度
int length = 0;
ListNode temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
// 2. 计算需要翻转的组数
int n = length / k;
if (n == 0) return head; // 如果不够一组，直接返回
// 3. 创建哑结点方便操作
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prevGroupTail = dummy; // 上一组的尾部
ListNode curr = head;
// 4. 循环 n 轮
for (int i = 0; i < n; i++) {
// 记录当前组的开头（翻转后变成尾部）
ListNode groupStart = curr;
ListNode prev = null;
// 翻转当前组的 k 个节点
for (int j = 0; j < k; j++) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// 连接上一组和当前组
prevGroupTail.next = prev; // 上一组尾部接新头
groupStart.next = curr; // 当前组尾部接下一组开头
prevGroupTail = groupStart; // 更新上一组尾部
}
return dummy.next;
}
}
双指针
15.三数之和
-
题目：给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。注意： 答案中不可以包含重复的三元组。 -
思路：
-
首先将数组排序，这样：
- 便于跳过重复元素
- 便于使用双指针技巧
-
固定一个数，转化为两数之和
对于每个nums[i]，在[i+1, n-1]范围内寻找两个数，使得它们的和等于-nums[i]。 -
双指针寻找
- 左指针
l = i + 1 - 右指针
r = n - 1 - 根据
nums[l] + nums[r]与target的比较移动指针
- 左指针
-
去重处理（关键）
- 固定数的去重
if (i > 0 && nums[i] == nums[i-1]) continue;
如果当前数与前一个数相同，跳过以避免重复解。 - 找到解后的去重
找到一组解后，需要跳过左右指针的重复元素:while (l < r && nums[l] == nums[l+1]) l++; while (l < r && nums[r] == nums[r-1]) r--; l++; r--; // 移动到下一个不同的元素
- 固定数的去重
-
-
代码：
class Solution { public List<List<Integer>> threeSum(int[] nums) { //初始化 先排序 便于遍历和比较 Arrays.sort(nums); List<List<Integer>> list = new ArrayList<>(); // -4 -1 -1 0 1 2 //后面两个，就不用遍历了 for (int i = 0; i < nums.length - 2; i++) { //如果当前数和前一个数相同，跳过避免重复解 if (i > 0 && nums[i] == nums[i - 1]) continue; //遍历到正的，就不用再遍历了 if (nums[i] > 0) break; int target = 0 - nums[i]; int l = i + 1; int r = nums.length - 1; //遍历条件 while(l < r){ if (nums[l] + nums[r] == target) { list.add(Arrays.asList(nums[i], nums[l], nums[r])); //去重 while (l < r && nums[l] == nums[l + 1]) l++; while (l < r && nums[r] == nums[r - 1]) r--; l++; r--; } else if (nums[l] + nums[r] < target) { l++; } else { r--; } } } return list; } }