当前位置： 首页 > article >正文

LeetCodeHot100_0x05

article 2025/3/4 22:46:00

LeetCodeHot100_0x05

32. 随机链表的复制（不熟）

求解思路： 这题还是由于对链表操作不熟，没能理解题目什么意思，再看了官方解释后才决定用哈希表解决该问题。具体思路：先用哈希存好数据，再分布创建val 和 next 、random。
【哈希法】

class Solution {
    public Node copyRandomList(Node head) {
        // 这题的难点在于如果按照常规遍历创建新节点，当前节点的random节点可能还没创建
        // 解决策略：分步创建，先创建好val和next，后面再补充random
        // 解决方法：哈希表存储当前节点和新节点键值对

        if(head == null) return null;

        Node curr = head;
        Map<Node,Node> hm =new HashMap<>();

        // 第一遍遍历：创建映射关系
        while(curr != null)  {
            hm.put(curr,new Node(curr.val));
            curr = curr.next;
        }

        // 第二遍遍历，根据映射关系补充next和random
        curr = head;
        while(curr != null) {
            hm.get(curr).next = hm.get(curr.next);  // 新节点的next节点为映射键节点的next
            hm.get(curr).random = hm.get(curr.random);  // 同理
            curr = curr.next;
        }
        return hm.get(head);    // 由于是new Node() 创建出来的，所以必然与原head地址值不同
    }
}

33. 排序链表

求解思路： 朴素做法是把值取出来排序再塞回去。进阶做法：限制O(NlogN)的排序无非两种，归并排序和快速排序。其中归并排序是稳定的排序，而且体现了分而治之的思想，所以我们尝试写个链表版的归并排序来解决这个问题。
【排值】把值取出来进行排序再塞回去

class Solution {
    public ListNode sortList(ListNode head) {
        // 取出来
        List<Integer> value = new ArrayList<>();
        ListNode curr = head;

        while(curr != null) {
            value.add(curr.val);
            curr = curr.next;
        }
        // 排序
        Collections.sort(value);
        // 填回
        curr = head;
        int i = 0;
        while(curr != null) {
            curr.val = value.get(i);
            i++;
            curr = curr.next;
        }
        return head;
    }
}

【归并排序】

class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }

    // 归并排序，链表版
    // 思想： 先分治，后合并 
    private ListNode mergeSort(ListNode head) {
        // 没有节点或只有一个节点无需排序，直接返回
        if(head == null || head.next == null) return head;
        
        //1. 利用快慢指针找到中间点作为基准
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        // 注意！这一步特别重要，断开链表！，这样左半部分就是head到slow了
        slow.next = null;

        //2. 对左半部分进行归并排序
        ListNode l = mergeSort(head);

        //3. 对右半部分进行归并排序
        ListNode r = mergeSort(mid);
        
        //4. 将左右链表进行合并
        return mergeList(l,r);
    }

    private ListNode mergeList(ListNode l,ListNode r) {
        ListNode newHead = new ListNode(-1);
        ListNode curr = newHead;

        while(l != null && r != null) {
            if(l.val < r.val) {
                curr.next = l;
                l = l.next;
            }else {
                curr.next = r;
                r = r.next;
            }
            curr = curr.next;
        }
        curr.next = (l != null) ? l : r;
        return newHead.next;
    }
}

34. 合并k个升序链表

求解思路：
【改值不改结构法】

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 朴素做法，改值不改结构
        if(lists.length == 0) return null;
        List<Integer> values = new ArrayList<>();
        for(int i = 0;i< lists.length;i++) {
            ListNode curr = lists[i];
            while(curr != null) {
                values.add(curr.val);
                curr = curr.next;
            }
        }
        Collections.sort(values);
        ListNode NewHead = new ListNode(-1);
        ListNode curr = NewHead;
        for(int i=0;i<values.size();i++) {
            curr.next = new ListNode(values.get(i));
            curr = curr.next;
        }
        return NewHead.next;
    }
}

【n指针遍历法】就是合并两个有序链表的升级版，给n条链表各一个指针进行遍历

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 指针做法，每个链表都有一个维护指针
        int n = lists.length;
        ListNode NewHead = new ListNode(-1);
        ListNode curr = NewHead;
        while(true) {
            ListNode curMinNode = null;   // 用于保存当轮最小值的节点信息
            int minidx = -1;              // 用来保存当前最小值位于哪条链表，同时用于判断遍历是否完成
            for(int i=0;i<n;i++) {
                // 判断当前链表是否已经遍历完
                if(lists[i] == null) continue;

                // 寻找当前位置的最小值
                if(curMinNode == null || curMinNode.val > lists[i].val) {
                    curMinNode = lists[i];
                    minidx = i;
                }
            }
                // 这里表明全部遍历完了
                if(minidx == -1) { 
                    break;
                }

                // 指针移动 
                curr.next = curMinNode;
                curr = curr.next;
                lists[minidx] = lists[minidx].next;
        }
        return NewHead.next;
    }
}

【迭代法】也是合并两个有序链表的升级版，只需要逐条逐条的迭代合并

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        int n = lists.length;
        ListNode res = lists[0];
        for(int i=1;i<n;i++) {
            res = merge2List(res,lists[i]);
        }
        return res;
        
    }
    
    private ListNode merge2List(ListNode l1, ListNode l2) {
        // 创建一个哑节点，以便于处理头节点
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // 合并两个有序链表
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // 连接剩余节点
        if (l1 != null) {
            current.next = l1;
        } else if (l2 != null) {
            current.next = l2;
        }

        // 返回合并后的链表（跳过哑节点）
        return dummy.next;
    } 
}

35. LRU缓存（重点手撕面经题）

说明： 这一题是很重要的面试题，需要实现一个最近最少使用缓存结构，
难点在于思考底层数据结构的选择。由于get、put函数的要求是O(1),且要求能O(1)删除最远古的元素。这提示我们设计数据结构时考虑哈希表 和 双向链表。我一开始想着用Map+LinkedList的结构去实现，发现LinkedList的get方法和remove方法底层都是要遍历链表的（因为虽然LinkedList底层也是双向链表结构，但是是基于索引的，每个节点之间是无法直接找到的，需要遍历，不符合）。

难点2在于数据结构的设计，题解在设计双向链表时，引入了虚拟头和虚拟尾，减少了很多越界特判的情况发生，从而简化了代码书写，思维特别巧妙。

最后，对于这一题来说，多理解，多写，多背。如果面试真的遇到了，希望你不仅能写的出来，还能阐述实现的思路。

class LRUCache {
    
    class DLinkedNode {
        int key;            // 键
        int value;          // 值
        DLinkedNode prev;   // 存储前驱节点
        DLinkedNode next;   // 存储后继节点
        public DLinkedNode() {} // 无参构造
        public DLinkedNode(int key, int value) { // 有参构造
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;   // 当前大小
    private int capacity; // 需要的初始容量
    private DLinkedNode head,tail;  // 虚拟头节点和虚拟尾节点
    
    /**
     * 初始化函数
     */
    public LRUCache(int capacity) {
        // 以正整数作为容量capacity初始化LRU缓存
        this.capacity = capacity;
        this.size = 0;
        // 创建虚拟头尾节点,构造双向链表闭环
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    /**
     * 获取值函数
     */
    public int get(int key) {
        // 如果key存在于缓存中，返回关键字的值，否则返回-1
        // O(1)
        DLinkedNode node = cache.get(key);  // 利用哈希表快速判断有没有该节点
        if(node == null) return -1;         // 没有返回-1

        // 如果存在，需要将它移动到头部（先删后加）
        moveToHead(node);
        return node.value;
    }
    
    /**
     * 添加值函数
     */
    public void put(int key, int value) {
        // 如果key已存在，变更为value
        // 如果不存在，插入key-value
        // 如果key数量超过capacity，逐出最久未使用关键字
        // O(1)

        DLinkedNode node = cache.get(key);
        if(node != null) {  // 存在的情况，替换 + 移动头部
            node.value = value;
            moveToHead(node);
        }else {            // 不存在的情况 判断容量 + 触发删除 + 头部添加
            // 创建元素
            DLinkedNode newNode = new DLinkedNode(key,value); 
            // 添加哈希表
            cache.put(key,newNode);
            // 头部添加
            addToHead(newNode);
            // 判断容量
            ++size;
            if(size > capacity) {
                // 触发删除尾部元素
                DLinkedNode tail = removeTail();
                // 将尾部元素移除哈希表
                cache.remove(tail.key);
                --size;
            }
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;   // 前驱节点是虚拟头节点
        node.next = head.next;  // 后继节点是原虚拟头节点的后继节点
        head.next.prev = node;  // 原虚拟头节点的后继节点的前驱节点变为node
        head.next = node;       // 虚拟头节点的后继节点改为node
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;  // 当前节点的前驱节点的后继节点改为当前节点的后继节点
        node.next.prev = node.prev;  // 当前节点的后继节点的前驱节点改为当前节点的前驱节点
    }

    private void moveToHead(DLinkedNode node) {
        // 先移除后添加
        removeNode(node);
        addToHead(node);
    }

    // 移除尾节点，返回节点
    private DLinkedNode removeTail() {
        DLinkedNode targetNode = tail.prev;    // 要移除的节点在虚拟尾节点的前面
        removeNode(targetNode); // 删除目标节点
        return targetNode;  // 返回
    }
}

36. 二叉树的中序遍历

求解思路： 涉及到二叉树的题目，基本上都是递归和迭代两种解法。递归类似深度搜索，一条路走到黑，而迭代法像是一层一层去做，通常会使用队列数据结构。
【递归法】

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        LDR(root,res); // 从根开始中序遍历
        return res;
    }

    private void LDR(TreeNode root,List<Integer> res) {
        if(root == null) return;
        LDR(root.left,res);  // 左
        res.add(root.val);   // 中
        LDR(root.right,res); // 右
    }
}

【迭代法】

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 迭代写法，借助栈结构
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()) {
            // 迭代处理左子树(一直深入到子节点)
            while(root!=null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();// 弹出左子树节点并检查当前节点有没有右子树，有的话继续重复操作 
            res.add(root.val);
            root = root.right;
        } 
        return res;
    }
}

37. 二叉树的最大深度

【递归法】

class Solution {
    int res = 0;
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        res = Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
        return res;
    }
}

38. 翻转二叉树

【递归法】
在这里插入图片描述
拿这张图理解，假设1，3节点就是简单节点，那就直接交换1，3就行了。但是现实是1，3节点可能也是一个二叉树。那就递归处理，先把1，3节点的子树给翻转完毕，最后轮到1，3节点就行了。

在实现上，只需要在交换1，3节点的时候，套上一个invertTree() 函数就可以实现递归处理。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 整体法，将二叉树退化成两层最简单的二叉树，那么我们要做的就是
        // 左叶子节点与右叶子节点交换
        // 然后扩展到普通多层二层树:
        // 只要当前节点不是最简二层二叉树，那就用invertTree把它底下的结构先改变了
        // 这里右用到了递归的思想
        if(root == null) return null;
        TreeNode left = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(left);
        return root;
    }
}

39. 总结

0x05遇到的题目主要是链表和树结构。通过前面两天刷链表题的经验，0x05遇到的题目即使有些不熟也是能写出来的。树方面的题目暂时也没有遇到比较难的题目，全部都是考察递归和对树形结构的基本了解吧。总结以下每一题：

  • 随机链表的复制 哈希
    • 由于随机链表的结构特性，这题先创建好普通链表的复制，最后将random指针填回去就行
  • 排序链表 归并排序
    • 朴素做法对值进行快排，进阶做法锻炼归并排序的链表版
  • 合并K个升序链表 n指针、递归
    • 这题是合并两个升序列表的进阶，所以解法也一样。n指针维护、递归逐条合并等
  • LRU缓存
    • 这题根据题目的意思，需要我们自己实现一个 哈希 + 双向链表的数据结构
  • 二叉树中序遍历 递归
    • 递归 左 值 右即可
  • 二叉树最大深度 递归
    • 递归 （左，右）Max + 1 即可
  • 二叉树翻转 递归
    • 递归 （左 ，右）Swap 即可

http://www.kler.cn/a/570724.html

相关文章：

  • IT安全运维指南：手册、工具与资源速览
  • 私有云基础架构
  • C++核心编程之STL_string容器
  • Python网络爬虫技术：现代应用、对抗策略与伦理边界
  • 【开源项目】好用的开源项目记录（持续更新）
  • 深度学习-自监督学习总结
  • 微服务概览与治理
  • realsenseD455相机录制bag转为TUM数据集
  • 【Python 3.12.1 颠覆性升级：GIL 解锁与性能飞跃，开启多线程新时代】
  • 几种详细的最大公约数的求法
  • Windows环境下Maven的配置
  • Linux驱动开发之串口驱动移植
  • 【Elasticsearch】索引生命周期管理相关的操作（Index Lifecycle Actions）
  • Spark核心之06：知识点梳理
  • Self-Pro: A Self-Prompt and Tuning Framework for Graph Neural Networks
  • 力扣hot100——二分查找
  • 养老小程序方案详解居家养老小程序系统
  • BIO、NIO、AIO、Netty从简单理解到使用
  • 2.数据结构：1.Tire 字符串统计
  • 【蓝桥杯单片机】第十二届省赛