双指针

问题地址 LeetCode每日一题/2020-10-23 LeetCode234. 回文链表 问题描述 规则 请判断一个链表是否为回文链表。 示例 示例1 输入: 1->2 输出: false 示例2 输入: 1->2->2->1 输出: true 进阶 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 思路分析 判断一个链表是否为回文链表，只需要使用两个指针，一个正向移动，一个从后往前移动，移动的过程中比较两个指针所指向节点的值即可。因为题目给定的是单向链表，只能从前往后访问链表元素，所以我们可以使用如下方法： 方法一：使用线性表存储链表元素，遍历线性…

问题地址 LeetCode每日一题/2020-10-22 LeetCode763. 划分字母区间 问题描述 规则 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。 示例 示例1 输入：S = "ababcbacadefegdehijhklij" 输出： 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。 提示 S的长度在之间…

问题地址 LeetCode每日一题/2020-10-21 LeetCode925. 长按键入 问题描述 规则 你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。 你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。 示例 示例1 输入：name = "alex", typed = "aaleex" 输出：true 解释：'alex' 中的 'a' 和 'e' 被长按。 示例2 输入：name = "saeed", typed = "ssaaedd" 输出：f…

问题地址 LeetCode每日一题/2020-10-20 LeetCode143. 重排链表 问题描述 规则 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例 示例1 给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例2 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3. 解析 解题思路 最直观的想法是使用线性表存…

问题地址 LeetCode每日一题/2020-10-19 LeetCode844. 比较含退格的字符串 问题描述 规则 给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。 注意： 如果对空文本输入退格字符，文本继续为空。 示例 示例1 输入：S = "ab#c", T = "ad#c" 输出：true 解释：S 和 T 都会变成 “ac”。 示例2 输入：S = "ab##", T = "c#d#" 输出：true 解释：S 和 T 都会变成 “”。 示例3 输入：S = "a##c", T = "#a#c" 输出：true …

问题地址 LeetCode每日一题/2020-10-18 LeetCode19. 删除链表的倒数第N个节点 问题描述 规则 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明 给定的 n 保证是有效的。 进阶 你能尝试使用一趟扫描实现吗？ 解析 解题思路 定义两个指针p1和p2，同时指向head，p2先移动n个指针； 如果p2不为null，则同时移动p1、p2； 如果p2为空，则返回p1.next 数据…

问题地址 LeetCode每日一题/2020-10-16 LeetCode977. 有序数组的平方 问题描述 规则 给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。 示例 示例1 输入： 输出： 示例2 输入： 输出： 提示 1 <= A.length <= 10000 10000 <= A <= 10000 A 已按非递减顺序排序。 解析 解题思路 最直观的方法是：遍历原数组对原数组中元素求平方，然后排序； 数据操作分析 见思路分析 复杂度分析 时间复杂度 空间复杂度 编码实现 public class LeetCode…

问题地址 LeetCode每日一题/2020-10-13 LeetCode24. 两两交换链表中的节点 问题描述 规则 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换 示例 给定 1->2->3->4, 你应该返回 2->1->4->3. 解析 解题思路 单链表只能指向下一个节点。这里使用虚拟头节点进行操作； 数据操作分析 操作步骤见下图 复杂度分析 时间复杂度 空间复杂度 编码实现 public class LeetCode0024_SwapNodesInPairs { public…

问题地址 LeetCode每日一题/2020-10-10 LeetCode142. 环形链表 II 问题描述 规则 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 示例 示例1 输入：head = , pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。 示例2 输入：head = , pos = 0 输出：tail connects to n…

问题地址 LeetCode每日一题/2020-10-09 LeetCode141. 环形链表 问题描述 规则 给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true 。 否则，返回 false 。 示例 示例1 输入：head = , pos = 1 输出：true 解释：链表中有一个环，其…