二分查找 寻找重复数 给定一个包含 n + 1 个整数的数组 nums,其数字都在 [1, n] 范围内,包括 1 和 n。 可知至少存在一个重复的整数。 假设 nums 只有一个重复的整数,返回这个重复的数。 你设计的解决方案必须不修改数组 nums,并且只使用常量级 O(1) 的额外空间。 示例 1: 输入:nums = [1,3,4,2,2] 输出:2 示例 2: 输入:nums = [3,1,3,4,2] 输出:3 示例 3: 输入:nums
链表 删除链表的倒数第 N 个结点 给你一个链表的头节点 head,删除链表的倒数第 n 个结点,并且返回链表的头节点。 示例 1: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2: 输入:head = [1], n = 1 输出:[] 示例 3: 输入:head = [1,2], n = 1 输出:[1] 提示: * 链表中结点的数目为 sz * 1 <= sz <= 30 * 0 <
链表 环形链表 II 给定一个链表的头节点 head,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置,索引从 0 开始。 如果 pos 是 -1,则在该链表中没有环。 注意: * pos 不作为参数进行传递。 * pos 仅仅是为了标识链表的实际情况。 * 不允许修改链表。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:返回索引为 1 的链表节点 解释:链表中有一个环,其尾部连接到第二个节点。 示例 2: 输入:head
链表 环形链表 给你一个链表的头节点 head,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置,索引从 0 开始。 注意: * pos 不作为参数进行传递。 * pos 仅仅是为了标识链表的实际情况。 如果链表中存在环,则返回 true。 否则,返回 false。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。 示例 2: 输入:head = [1,2], pos = 0 输出:
链表 回文链表 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 示例 1: 输入:head = [1,2,2,1] 输出:true 示例 2: 输入:head = [1,2] 输出:false 提示: 链表中节点数目在范围[1, 105] 内 0 <= Node.val <= 9 进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? 解法一(数组 + 双指针): /** * Definition
链表 相交链表 给你两个单链表的头节点 headA 和 headB。 请你找出并返回两个单链表相交的起始节点。 如果两个链表不存在相交节点,返回 null。 题目数据保证整个链式结构中不存在环。 注意: * 函数返回结果后,链表必须保持其原始结构。 * 链表相交指的是两个链表从某个节点开始,后续节点在内存中是同一批节点。 * 不能只比较节点值是否相等,必须比较节点本身是否相同。 自定义评测中会使用: * intersectVal:相交的起始节点的值。如果不存在相交节点,这一值为 0 * listA:第一个链表 * listB:第二个链表 * skipA:在 listA 中从头节点开始跳到交叉节点的节点数 * skipB:在 listB 中从头节点开始跳到交叉节点的节点数 评测系统会根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给程序。 示例 1: 输入:intersectVal = 8, listA = [4,1,8,4,
双指针 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height = [4,
算法 三数之和 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 **注意:**答案中不可以包含重复的三元组。 示例 1: 输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]] 解释: nums[0]
双指针 盛最多水的容器 盛最多水的容器 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 **说明:**你不能倾斜容器。 示例 1: 输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,
算法 移动零 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。 示例 1: 输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2: 输入: nums = [0] 输出: [0] 提示: * 1 <= nums.length <= 104 * -231 <= nums[i] <= 231 - 1 解法(快慢指针法): class Solution { public: void