LeetCode Hot100

2025-11-11 2025-11-13 数据结构 leetcode leetcode 算法技术 1

滑动窗口

3.无重复字符的最大子串

题目：

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

思路：

滑动窗口思想，左右指针一直移动，遇到重复的就更新左边界(移除左边的元素)，数据结构方面用HashMap存储**<当前字符,出现的位置+1>**

步骤：

定义数据结构
遍历字符串
1. 遇到重复的就更新左边界（左指针）
2. 更新最大长度
3. 存当前字符对应的左边界
返回结果

代码

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)

这样做的好处有两点：第一避免空指针判断，第二统一了头部插入和尾部删除操作

步骤：
1. 定义数据结构Node类和LRUCache 类成员
2. 初始化（哑节点）
3. 完成get方法：判断node是否为空？返回-1：把node移到链表最前，返回node的value
4. 完成put方法：判断node是否为空？不为空更新，然后将node移到链表最前；为空的话则创建新节点，把新节点移到链表最前，然后检查容量，如果超过链表容量，移除链表末尾的，并删除哈希表中的key
5. 以上步骤需要四个方法完成：
  1. addToHead(node) - 头部插入；插入的是新节点
  2. removeNode(node) - 删除节点；
  3. moveToHead(node) - 移到头部；把已有节点移到头部（调用2+1方法）
  4. 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 ，请你反转链表，并返回反转后的链表。
思路：
1. 迭代法
  1. 首先，原本初始化之后是这样的。 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节点？
    
    出处，十分清晰：我要弄懂每一个困难题
  2. 递归法
    假设链表是：
    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;
    }
}

LeetCode Hot100

https://xancel.top/archives/leetcodehot100

作者

我不是Administrator

发布于

2025-11-11

更新于

2025-11-13

许可

数据结构 leetcode leetcode 算法技术