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

【我想找一份实习】算法篇

news 来源：原创 2024/4/19 23:54:31

笔者注：之前为了准备蓝桥杯等系列算法比赛写了很多算法博客，也真的让自己在算法方面提升很大，收获了很多奖项。现在，目标变成了【我想找一份实习】，所以，这一系列文章，将会以实习为导向，完成算法、八股文等多方面维度的学习和准备，希望能在最后拿到一份自己想要的实习。

本文为“算法篇”，学习路径源自大佬labuladong：https://labuladong.github.io/algo/

数据结构

链表

21 合并两个有序链表（简单）

基本操作，注意使用虚拟头结点，方便结果处理

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 虚拟头结点
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                p.next = list2;
                list2 = list2.next;
            } else {
                p.next = list1;
                list1 = list1.next;
            }
            // 新链表的节点继续往下走
            p = p.next;
        }
        if (list1 == null) {
            // 说明list2可能还有剩
            p.next = list2;
        }
        if (list2 == null) {
            // 说明list1可能还有剩
            p.next = list1;
        }
        return dummy.next;
    }
}

86 分隔链表（中等）

具体来说，我们可以把原链表分成两个小链表，一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x，最后再把这两条链表接到一起，就得到了题目想要的结果。

注意合并时，要将p2.next置为null，否则当最后一个节点值小于x时，合并后会成环，可以画图试试

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode();
        ListNode dummy2 = new ListNode();
        ListNode p1 = dummy1;
        ListNode p2 = dummy2;
        while (head != null) {
            if (head.val < x) {
                // 放p1中
                p1.next = head;
                p1 = p1.next;
            } else {
                // 放p2中
                p2.next = head;
                p2 = p2.next;
            }
            head = head.next;
        }
        // 连接两个链表，注意要让更大的链表的next=null否则当最后一个节点值小于x时，会成环
        p2.next = null;
        p1.next = dummy2.next;
        return dummy1.next;
    }
}

※23 合并K个升序链表（困难）

合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？

这里我们就要用到 优先级队列（二叉堆） 这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<>(){
            @Override
            public int compare(ListNode a, ListNode b) {
                return a.val - b.val;  // 降序排列
            }
        });
        for (ListNode node : lists) {
            if (node != null) {
                // 先只添加k个链表的头结点，后面在遍历时把头结点之后的结点加入
                pq.add(node);
            }
        }
        // 和前面合并有序链表一样
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        while (!pq.isEmpty()) {
            // 获取所有链表的当前最小节点放入新链表中
            ListNode tmp = pq.poll();
            p.next = tmp;
            // 对于当前拿走了一个结点的链表，还需要把剩余节点加入pq队列
            if (tmp.next != null) {
                pq.add(tmp.next);
            } 
            // 新链表的节点继续往前走
            p = p.next;
        }
        return dummy.next;
    }
}

※19 删除链表的倒数第 N 个结点（中等）

这道题涉及一个问题：如何快速找到倒数第N个节点？

画图解决：
1、先让一个节点p1，从头结点开始先走N步
2、引入一个新的节点p2，指向头结点
3、p1、p2同时走，当p1 == null时，p2所在位置即为倒数第N个节点

ListNode p1 = head;
// 先走k步
for (int i = 0; i < k; i++) {
	p1 = p1.next;
}
ListNode p2 = head;
// 再同时走
while (p1 != null) {
	p2 = p2.next;
	p1 = p1.next;
}
// 最后p2所指即为所需节点
return p2;

但是本题要删除倒数第N个节点，那我们就得找到倒数第N+1个节点，但是为了避免需要删除头结点而找不到第N+1个节点的情况，可以给原始链表加上一个虚拟头结点：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头结点，给head再增加一个节点，避免删除头结点时出错
        // 如果链表长度=4，n=4，我们现在要去找第n+1个节点，找不到呀？
        ListNode dummy = new ListNode();
        dummy.next = head;
        // 有了虚拟头结点就可以处理删除头结点的问题
        ListNode p1 = dummy;
        // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
        n += 1;
        for (int i = 0; i < n; i++) {p1 = p1.next;}
        // 再来个p2 和 p1一起走
        ListNode p2 = dummy;
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        // 现在p2所处位置就是要删除节点的前一个节点
        // 删掉倒数第 n 个节点
        p2.next = p2.next.next;
        return dummy.next;
    }
}

※876 链表的中间结点（简单）

经典问题了，之前也刷过几遍，就是快慢指针

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;  // 如果是偶数个节点，返回的是中间靠后的节点
        }
        return slow;
    }
}

环形链表三连问： 1. 是否有环(141) 2. 找出环的入口(142) 3. 环中节点个数

※141 环形链表（简单）

同上，依旧使用快慢指针，如果有环，则快指针必然会和慢指针相遇：

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

※142 环形链表Ⅱ（中等）

在上一题基础上需要找到入环结点，也是模板题：

关键是让slow指针最后要重新指向头结点，然后再让slow、fast指针一起走，最后相遇的地方就是入环结点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 先判断有无环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 成环了
                break;
            }
        }
        // 若无环则直接null
        if (fast == null || fast.next == null) {
            return null;
        }
        // 让slow指针指向头结点，再和fast指针一起走，直到两者相遇点就是入环点
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

环中结点个数

slow与fast相遇在环的入口, 让fast或者slow单独在环里再走一圈, 并进行计数, 当fast.next = slow时, 返回count+1，就是环中节点的个数。

160 相交链表（简单）

如果两个链表的长度一致的话还好处理，直接从head开始往后遍历，判断有相同的结点[==]，就说明是相交的，关键是长度不相同，但注意：相交点之后的两条链表合为一条链，那我们就让长的链表先把多的结点数走掉，再让两个链表一起走，如果相交，走到后面总会有结点一致；如果不相交，到最后都为null，也一样了。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        int lenA = 0;
        int lenB = 0;
        while (pA != null) {
            lenA++;
            pA = pA.next;
        }
        while (pB != null) {
            lenB++;
            pB = pB.next;
        }
        // 让长的链表先走一段
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                headA = headA.next;
            }        
        } else {
            for (int i = 0; i < lenB - lenA; i++) {
                headB = headB.next;
            }
        }
        // 最后再判断是否相交，不相交也能正确返回null
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
}

206 反转链表（简单）

用递归可以写得很简洁明了，因为递归的重点在于函数含义的理解，而不用真正搞懂内部递归调用的过程。

递归函数定义为：输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

那么，就可以画图进行分析：

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
关键是最后这里，head.next = null，一方面是断开head正向的连接，另一方面也让反转后的最后一个节点的next=null。

同时要注意base基础条件，没有结点、或只有一个结点，反转就是自身，直接返回即可。

// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

迭代解法：

/**
     * 迭代方法
     * 1 -> 2 -> 3 -> 4 -> null
     * null <- 1 <- 2 <- 3 <- 4
     *
     * @param head
     * @return
     */
    public static ListNode reverseListIterative(ListNode head) {
        ListNode prev = null; //前指针节点
        ListNode curr = head; //当前指针节点
        //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
        while (curr != null) {
            ListNode nextTemp = curr.next; //临时节点，暂存当前节点的下一节点，用于后移
            curr.next = prev; //将当前节点指向它前面的节点
            prev = curr; //前指针后移
            curr = nextTemp; //当前指针后移
        }
        return prev;
    }

反转链表前N个结点

// 将链表的前 n 个节点反转（n <= 链表长度）
ListNode reverseN(ListNode head, int n)

在这里插入图片描述
之前反转是让头结点的next直接等于null，但是这里需要将头结点的next连接到后驱结点（第n+1个结点），因为只需要反转一部分。

class Solution {
    ListNode postNode;
    public ListNode reverseList(ListNode head, int n) {
        if (n == 1) {  // 到达了需要反转的最后一个结点
            postNode = head.next;  // 记录n+1后驱结点
            return head;  // 避免只有单个结点的情况
        }
        // 下面和反转整个链表的过程差不多，区别就是最后还需要连接到后驱节点上
        ListNode last = reverseList(head.next, n - 1);
        head.next.next = head;
        // 这里下一个结点要连接到后驱节点上
        head.next = postNode;
        return last;
    }
}

92 反转链表 II（中等）

现在需要按照题目需求，反转一个范围内[m, n]的链表，链表的索引从1开始，当m==1时，就相当于上一题反转前N个结点，当m != 1时，怎么办？

如果我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head.next.next 呢……

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            // 就相当于是反转前right个结点
            return reverseN(head, right);
        }
        // 如果不是从第一个结点开始，那就把下一个结点当作第一个结点
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    // 反转前N个结点的函数，别忘了记录后驱结点
    ListNode postNode = null;
    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            postNode = head.next;  // 找到n+1结点作为后去节点
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        // 这里要连接到后驱结点
        head.next = postNode;
        return last;
    }
}

迭代写法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode();
        dummy.next = head;  // 避免边界情况

        // 走left-1到达leftNode的preNode
        ListNode leftPrev = dummy;
        for (int i = 0; i < left - 1; i++) {
            leftPrev = leftPrev.next;
        }

        // 在leftPrev的基础上再走right - left + 1到达rightEnd结点
        ListNode rightEnd = leftPrev;
        for (int i = 0; i < right - left + 1; i++) {
            rightEnd = rightEnd.next;
        }

        // 再记录下leftNext、rightNext结点，用于最后反转后的连接
        ListNode leftNext = leftPrev.next;
        ListNode rightNext = rightEnd.next;

        // 断开左右结点的连接
        leftPrev.next = null;
        rightEnd.next = null;
        
        // 从leftNode开始反转
        ListNode newHead = reverse(leftNext);

        // 再连接起来
        leftPrev.next = newHead;
        leftNext.next = rightNext;
        return dummy.next;
    }

    // 简单的链表反转函数
    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;  // pre指针往后移动
            cur = tmp;
        }
        return pre;
    }
}

值得一提的是，递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)

相关文章：

  • python入门之简洁安装VS保姆版安装（含虚拟环境）
  • Tomcat漏洞利用工具-TomcatVuln
  • 【MySQL探索之旅】多表查询
  • NLP vs. LLMs: 理解它们之间的区别
  • 深入解析Apache Hadoop YARN：工作原理与核心组件
  • 优先编码器电路①
  • 图论（算法竞赛、蓝桥杯）--Dijkstra算法最短路
  • xss.haozi.me靶场练习
  • 09-认证-自研微服务框架
  • 请求包的大小会影响Redis每秒处理请求数量
  • 【Docker 的安装：centos】
  • 打开 Camera app 出图，前几帧图像偏暗、偏色该怎样去避免？
  • uniapp 微信小程序和H5的弹窗滚动穿透解决
  • linux安装tomcat、mysql、redis、宝塔，rpm命令
  • Linux命令老是记不住？一篇文章帮你解决。Linux常用命令汇总
  • 接口测试用例生成工具介绍及应用
  • 【axios】二次封装——避免重复发送请求
  • Maven 高级 5 多环境配置与应用 5.1 多环境开发
  • [ vulhub漏洞复现篇 ] Apache APISIX 默认密钥漏洞 CVE-2020-13945
  • 【图像分割】基于电磁算法优化多级阈值实现图像分割附matlab代码
  • SushiSwap历任“主厨”史
  • 【数据结构与算法】用队列实现栈用栈实现队列设计循环队列
  • 【模型训练】YOLOv7吸烟行为检测
  • stm32f4xx-ADC
  • 吃透Jmeter，5小时搞定5天工作量
  • Unreal4.27 houdini niagara粒子无法导入问题笔记
  • 使用Docker搭建Apache Kafka环境
  • 【Linux】权限管理
  • 【学生管理系统】用户管理之用户登录
  • 操作系统八股文03-内存管理
  • DRL经典文献阅读（一）：策略梯度理论（Policy Gradient, PG）
  • 第26章 物联网软件系统测试