关注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
11 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
11 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
11 months ago

LeetCode-145. 二叉树的后序遍历

问题地址 LeetCode每日一题/2020-09-29 LeetCode145. 二叉树的后序遍历 问题描述 规则 给定一个二叉树,返回它的 *后序 遍历。 示例 输入: 1 \ 2 / 3 输出: 进阶 递归算法很简单,你可以通过迭代算法完成吗? 解析 解题思路 后序遍历:是按照访问左右根的顺序遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。整个遍历过程天然具有递归的性质。 递归遍历树的时候隐式的维护一个栈,我们使用迭代的方法遍历树,需要自己维护栈; 下面介绍一种方法标记法,针对树的前、中、后序遍历可以写统一模板的代码; 在使用栈时,无法同时处理访问节…
US-B.Ralph
a year ago

LeetCode-113. 路径总和 II

问题地址 LeetCode每日一题/2020-09-26 LeetCode113. 路径总和 II 问题描述 规则 给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 注意 你可以假设树中没有重复的元素。 示例 示例一: 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: , ] 解析 解题思路 从根节点开始遍历每一条路径,当遍历到叶子节点且该路径节点之和等于sum则将其添加到结果集中; 数据操作分析 遍历整棵树 当节点为空,直接返回; …
US-B.Ralph
a year ago

LeetCode-78. 子集

问题地址 LeetCode每日一题/2020-09-20 LeetCode78. 子集 问题描述 规则 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明 解集不能包含重复的子集。 示例 示例一: 输入: nums = 输出: ,   ,   ,   ,   ,   ,   ,   [] ] 解析 解题思路 每个元素都有两个选项,选择、不选择; 题目示例,元素1可以考虑选择或不选择,然后考察2,以此类推; 其递归树为: 一个子树就是一个递归调用,对当前枚举的数,选和不选可以分出两个分支,分别对应两个递归的子调用,在子调用中,考察下一个数。 当 inx 越界(in…
US-B.Ralph
a year ago

LeetCode-94. 二叉树的中序遍历

问题地址 LeetCode每日一题/2020-09-14 LeetCode94. 二叉树的中序遍历 问题描述 规则 给定一个二叉树,返回它的中序 遍历。 示例 示例: 输入: 1 \ 2 / 3 输出: 进阶 递归算法很简单,你可以通过迭代算法完成吗? 解析 解题思路 递归 二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。 数据操作分析 根据中序遍历的定义只需要遍历左子树、root、右子树即可 遍历的终止条件是 root==nu…
US-B.Ralph
a year ago

LeetCode-77. 组合

问题地址 LeetCode每日一题/2020-09-08 LeetCode77. 组合 问题描述 规则 给定两个整数 $n$ 和 $k$,返回 $1 ... n$ 中所有可能的 $k$ 个数的组合。 示例 示例一: 输入: n = 4, k = 2 输出: , , , , , , ] 解析 解题思路 使用递归思路来解题; 题目的结果可以理解为: 从n个里面先选1个; 从n-1个里面选出剩下的k-1个; 数据操作分析 复杂度分析 时间复杂度 空间复杂度 编码实现 public class LeetCode0077_Combinations { List<List<Integer>…
US-B.Ralph
a year ago

LeetCode-557. 反转字符串中的单词 III

问题地址 LeetCode每日一题/2020-08-30 LeetCode557. 反转字符串中的单词 III 问题描述 规则 给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例1 输入:"Let's take LeetCode contest" 输出:"s'teL ekat edoCteeL tsetnoc" 提示 在字符串中,每个单词由单个空格分隔,并且字符串中不会有任何额外的空格。 解析 解题思路 方案一:栈 利用栈先进后出的特点:遍历字符串s,非空格字符入栈,遇到空格时出栈。 方案二: 使用空格切分字符串,遍历字符串数组,反转每个字符串。 复杂…
US-B.Ralph
a year ago

LeetCode-20. 有效的括号

问题地址 LeetCode每日一题/2020-08-14 LeetCode20. 有效的括号 问题描述 规则 给定一个只包括'(',')','{','}','' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例1 输入: "()" 输出: true 示例2 输入: "()[]{}" 输出: true 示例3 输入: "(]" 输出: false 示例4 输入: "(" 输出: false 示例5 输入: "{[]}" 输出: true 解析 解题思路 根据有效字符串的定义: - 左括号…
US-B.Ralph
a year ago