关注Java领域相关技术 记录有趣的事情

双指针

LeetCode-234. 回文链表

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

LeetCode-763. 划分字母区间

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

LeetCode-925. 长按键入

问题地址 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…
US-B.Ralph
9 months ago

LeetCode-143. 重排链表

问题地址 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. 解析 解题思路 最直观的想法是使用线性表存…
US-B.Ralph
9 months ago

LeetCode-844. 比较含退格的字符串

问题地址 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 …
US-B.Ralph
9 months ago

LeetCode-19. 删除链表的倒数第N个节点

问题地址 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 数据…
US-B.Ralph
9 months ago

LeetCode-977. 有序数组的平方

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

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

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

LeetCode-142. 环形链表 II

问题地址 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…
US-B.Ralph
9 months ago

LeetCode-141. 环形链表

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