首页 > 编程语言 >力扣大厂热门面试算法题 24-26

力扣大厂热门面试算法题 24-26

时间:2024-03-14 20:01:33浏览次数:28  
标签:24 链表 26 ListNode nums head next 力扣 节点

        24. 两两交换链表中的节点,25. K 个一组翻转链表,26. 删除有序数组中的重复项,每题做详细思路梳理,配套Python&Java双语代码, 2024.03.14 可通过leetcode所有测试用例

目录

24. 两两交换链表中的节点

解题思路

递归思路

迭代思路

完整代码

Python

Java

25. K 个一组翻转链表

解题思路

完整代码

Python

Java

26. 删除有序数组中的重复项

解题思路

完整代码

Python

Java


24. 两两交换链表中的节点

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:

输入:head = [1,2,3,4]
输出:[2,1,4,3]

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1]

解题思路

两种方式。

递归思路
  1. 终止条件:当前节点为空或者下一个节点为空,说明没有更多的节点需要交换,直接返回当前节点。
  2. 递归单元内需要做什么:交换当前节点和下一个节点的位置。
  3. 如何进入下一层递归:将当前节点的指针指向递归后返回的头节点。
迭代思路
  1. 创建一个哑节点(dummy node),它的下一个节点指向头节点。
  2. 初始化两个指针prevcurr,其中prev指向哑节点,curr指向头节点。
  3. 遍历链表,当curr及其下一个节点不为空时,执行以下操作: a. 记录curr的下一个节点为next。 b. 使curr的下一个节点指向next的下一个节点。 c. 使next的下一个节点指向prev的下一个节点。 d. 使prev的下一个节点指向next。 e. 更新prevcurr指针,准备下一对节点的交换。

完整代码

Python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        next_node = head.next
        head.next = self.swapPairs(next_node.next)
        next_node.next = head
        return next_node
Java
/**
 * 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; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        while (head != null && head.next != null) {
            ListNode first = head;
            ListNode second = head.next;

            prev.next = second;
            first.next = second.next;
            second.next = first;

            prev = first;
            head = first.next;
        }
        return dummy.next;
    }
}

25. K 个一组翻转链表

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

提示:
  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

进阶:你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?

解题思路

  1. 找到k个一组的链表节点: 遍历链表,每次移动k步来定位到每个组的最后一个节点。如果剩余节点不足k个,则保持这部分不变。
  2. 反转每组节点: 对于每个分组,进行链表反转操作。这里需要注意的是,反转操作不仅需要反转内部的节点,还要连接好每组的头尾。
  3. 连接各组: 反转完一组后,需要将反转后的子链表重新连接起来。这涉及到更新前一组的尾节点指向当前组反转后的头节点。

完整代码

Python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 创建一个哑节点,便于处理头节点前的操作
        dummy = ListNode(0)
        dummy.next = head
        pre, end = dummy, dummy

        while end.next:
            # 尝试移动end指针,找到当前组的最后一个节点
            for _ in range(k):
                end = end.next
                if not end:  # 如果节点数不足k个,不进行翻转
                    return dummy.next
            # 记录下一组的起始节点
            start, next = pre.next, end.next
            # 断开当前组与下一组的连接,以便单独翻转当前组
            end.next = None
            # 翻转当前组,并将翻转后的子链表接回原链表
            pre.next = self.reverse(start)
            # 重新连接翻转后的子链表与下一组的起始节点
            start.next = next
            # 移动pre和end指针到下一组的起始位置
            pre = start
            end = pre

        return dummy.next

    def reverse(self, head: ListNode) -> ListNode:
        # 辅助函数:翻转链表
        prev = None
        while head:
            next_temp = head.next  # 临时存储下一个节点
            head.next = prev  # 将当前节点指向前一个节点,实现翻转
            prev = head  # 移动prev指针
            head = next_temp  # 移动head指针
        return prev
Java
/**
 * 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; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode end = dummy;

        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) end = end.next;
            if (end == null) break;
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = next;
            pre = start;
            end = pre;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

26. 删除有序数组中的重复项

        给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

        考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

        更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}
如果所有断言都通过,那么您的题解将被 通过。

示例 1:

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

解题思路

        要解决这个问题,我们可以采用双指针技术。思路是用两个指针ij遍历数组,i是慢指针,j是快指针。当nums[i]nums[j]相等时,增加j以跳过重复项。当遇到nums[i]nums[j]不相等时,则将nums[j]的值复制到nums[i + 1],然后递增i,接着递增j。重复这一过程,直到j遍历完整个数组。数组的前i + 1个元素就是不含重复元素的数组。最后返回的i + 1就是数组中不同元素的个数。

完整代码

Python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]

        return i + 1
Java
public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
}

标签:24,链表,26,ListNode,nums,head,next,力扣,节点
From: https://blog.csdn.net/qq_52213943/article/details/136719923

相关文章

  • 2024.3.12 软工日报
    学习时间:下午四节课代码量:200packagecom.example.myapplication;importandroid.os.AsyncTask;importjava.sql.Connection;importjava.sql.DriverManager;importjava.sql.PreparedStatement;importjava.sql.SQLException;publicclassMysqlHelp{publicstaticvoidi......
  • 2024年最新腾讯云优惠券获得方法整理
    腾讯云作为国内领先的云服务提供商,其优质的产品和服务深受用户喜爱。而腾讯云优惠券则是用户在使用腾讯云服务时能够享受到的一项福利,可以有效降低上云成本。那么,2024年如何获得腾讯云优惠券呢?本文将为大家详细整理最新腾讯云优惠券获得方法。方法一:腾讯云官网活动页面腾讯......
  • LeetCodeHot100 73. 矩阵置零 54. 螺旋矩阵 48. 旋转图像 240. 搜索二维矩阵 II
    73.矩阵置零https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-100-likedpublicvoidsetZeroes(int[][]matrix){inttop=0,bottom=matrix.length,left=0,right=matrix[0].length;int[][]flag......
  • 洛谷 P3261 [JLOI2015] 城池攻占 题解
    题目分析其他人要么倍增,要么左偏树,那我就来讲讲朴实无华的dfs序加上线段树的做法。首先发现题目中明确指出了作乘法的时候一定是乘上一个大于零的数,这是为什么呢?首先把可以占领当前城池的战斗力的不等式列出来:\[h_j\le\left\{\begin{array}{c}s_i\timesv_j&&{a_j=......
  • 2024-03-14
    2024-03-14Riddle继续做上次没做出来的题2-SAT限制是如果一个点不选,那么与它相连的所有点都必须选如果一个点选了,那么和他在同一个部分的所有点都不能选对于边的限制直接建但是“部分”的限制直接建图是\(O(n^2)\)的优化方法是前缀优化建图对于每一个部分,用\(a_i......
  • 2024年最新港区Apple ID注册教程
    大家都知道,许多海外应用在国内并不能直接下载,例如,TikTok在国内用不了,对跨境电商和海外社媒营销人员来说,如何有效地接触和利用各个国家或地区的在线资源,尤其是对于海外应用程序的接入是很重要的。不过许多做TikTok跨境电商的卖家会将Apple ID切换到港区,下载香港地区可用的TikT......
  • 2024最新华为OD机试,题库清单(按算法分类),高效刷题,举一反三,玩转OD
    目录专栏导读华为OD机试算法题太多了,知识点繁杂,如何刷题更有效率呢?一、逻辑分析二、数据结构1、线性表①数组②双指针2、map与list3、优先队列4、滑动窗口5、二叉树6、并查集7、栈三、算法1、基础算法①贪心算法②二分查找③分治递归④搜索算法⑤排序算法2、......
  • MYSQL学习笔记26: 多表查询|子查询
    多表查询|子查询行子查询查询与张无忌工资相同,且直属领导相同的员工#写法1select*fromempwheresalary=(selectsalaryfromempwherename='张无忌')andmanagerId=(selectmanagerIdfromempwherename='张无忌');#可以合并起来,写入一个集合selec......
  • 百度网盘(百度云)SVIP超级会员共享账号每日更新(2024.03.14)
    一、百度网盘SVIP超级会员共享账号可能很多人不懂这个共享账号是什么意思,小编在这里给大家做一下解答。我们多知道百度网盘很大的用处就是类似U盘,不同的人把文件上传到百度网盘,别人可以直接下载,避免了U盘的物理载体,直接在网上就实现文件传输。百度网盘SVIP会员可以让自己百度账......
  • 计算机类主题会议推荐之——ICETIS 2024
    ​第九届电子技术和信息科学国际学术会议(ICETIS2024)大会官网:www.icetis.org大会时间:2024年5月17-19日大会地点:中国-杭州收录检索:EICompendex,Scopus​大会简介       ICETIS会议始于2016年,先后吸引众多来自国内外高等院校、科学研究所、企事业单位的专家、教授......