算法

加一一、题目66. 加一 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以零开头。 示例 1： 输入：digits = [1,2,3]输出：[1,2,4]解释：输入数组表示数字 123。 示例 2： 输入：digits = [4,3,2,1]输出：[4,3,2,2]解释：输入数组表示数字 4321。 示例 3： 输入：digits = [9]输出：[1,0]解释：输入数组表示数字 9。加 1 得到了 9 + 1 = 10。因此，结果应该是 [1,0]。 提示： 1 <= digits.length <= 100 0 <= digits[i] <= 9 二、题解注意9+1=10 就可以了 1234567891011121314151617181920212223class Solution { public static int[] plusOne(int[] digits) {...

回文数一、题目9. 回文数 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数（如果一个整数向前和向后读都相同，则它是一个 回文数。 例如，121 是回文数，而 123 不是。） 是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 例如，121 是回文，而 123 不是。 示例 1： 输入：x = 121输出：true 示例 2： 输入：x = -121输出：false解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3： 输入：x = 10输出：false解释：从右向左读, 为 01 。因此它不是一个回文数。 提示： -231 <= x <= 231 - 1 进阶：你能不将整数转为字符串来解决这个问题吗？ 二、题解题解一（双指针）1234567891011121314151617181920class Solution { public static boolean isPalindrome(int x) { ...

电话号码的字母组合一、题目17. 电话号码的字母组合 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例 1： 输入：digits = "23"输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例 2： 输入：digits = ""输出：[] 示例 3： 输入：digits = "2"输出：["a","b","c"] 提示： 0 <= digits.length <= 4 digits[i] 是范围 ['2', '9'] 的一个数字。 二、题解题解一...

对称二叉树一、题目101. 对称二叉树 给你一个二叉树的根节点 root ， 检查它是否轴对称。 示例 1： 输入：root = [1,2,2,3,4,4,3]输出：true 示例 2： 输入：root = [1,2,2,null,3,null,3]输出：false 提示： 树中节点数目在范围 [1, 1000] 内 -100 <= Node.val <= 100 进阶：你可以运用递归和迭代两种方法解决这个问题吗？ 二、题解题解一（翻转+判断）推荐面试经典-翻转二叉树 面试经典-相同的树 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode ri...

二叉树1234567891011121314151617181920212223public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } public static TreeNode createTree(){ TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.left.left ...

翻转二叉树一、题目226. 翻转二叉树 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。 示例 1： 输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1] 示例 2： 输入：root = [2,1,3]输出：[2,3,1] 示例 3： 输入：root = []输出：[] 提示： 树中节点数目范围在 [0, 100] 内 -100 <= Node.val <= 100 二、题解题解一（广度优先）1234567891011121314151617181920public static TreeNode invertTreeFromBFS(TreeNode root) { if (root == null || (root.left == null && root.right == null)) { return root; } Queue<TreeNode> queue = new LinkedList&l...

相同的树一、题目100. 相同的树 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 示例 1： 输入：p = [1,2,3], q = [1,2,3]输出：true 示例 2： 输入：p = [1,2], q = [1,null,2]输出：false 示例 3： 输入：p = [1,2,1], q = [1,1,2]输出：false 提示： 两棵树上的节点数目都在范围 [0, 100] 内 -104 <= Node.val <= 104 二、题解 思路： ​ 相同的二叉树，也就是说，两节点，以及两节点的值，都要相同 如果两节点节点相同，即 同为null 捉着同不为 null 同时，值也要相同 ，此时才能说此节点相同 题解一（广度优先）12345678910111213141516171819202122232425262728// 广度优先public static boolean isSameTree(TreeNode p, TreeNod...

二叉树最大深度一、题目104. 二叉树的最大深度 给定一个二叉树 root ，返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1： 输入：root = [3,9,20,null,null,15,7]输出：3 示例 2： 输入：root = [1,null,2]输出：2 提示： 树中节点的数量在 [0, 104] 区间内。 -100 <= Node.val <= 100 二、题解 深度优先遍历（Depth-First Search, DFS）是一种常用的树或图的遍历算法。它从根节点开始，沿着树的深度方向遍历节点，尽可能深入地访问每个分支，直到无法继续深入为止，然后回溯到上一个节点，继续访问其他未访问的分支 深度优先遍历（Depth-First Search, DFS）包括前序遍历、中序遍历和后序遍历： 前序遍历（根节点 -> 左子树 -> 右子树）的结果为： 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 中序遍...

分割链表题目86. 分隔链表 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。 示例 1： 输入：head = [1,4,3,2,5,2], x = 3输出：[1,2,2,4,3,5] 示例 2： 输入：head = [2,1], x = 2输出：[1,2] 提示： 链表中节点的数目在范围 [0, 200] 内 -100 <= Node.val <= 100 -200 <= x <= 200 题解题解一（两次循环法）1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556public class LinkedListPartition { public static void main(String[] args) {// ...

旋转链表题目61. 旋转链表 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 示例 1： 输入：head = [1,2,3,4,5], k = 2输出：[4,5,1,2,3] 示例 2： 输入：head = [0,1,2], k = 4输出：[2,0,1] 提示： 链表中节点的数目在范围 [0, 500] 内 -100 <= Node.val <= 100 0 <= k <= 2 * 109 题解 此题有点难，适合二刷 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586public class RotateRight { public static void main(String[] args) { ...

删除排序链表中的重复元素II题目82. 删除排序链表中的重复元素 II 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。 示例 1： 输入：head = [1,2,3,3,4,4,5]输出：[1,2,5] 示例 2： 输入：head = [1,1,1,2,3]输出：[2,3] 提示： 链表中节点数目在范围 [0, 300] 内 -100 <= Node.val <= 100 题目数据保证链表已经按升序 排列 题解 此题有点难，适合二刷 12345678910111213141516171819202122232425262728293031public class DeleteDuplicates { public static void main(String[] args) { ListNode node1 = new ListNode(1); node1.next = new ListNode(1); no...

删除链表的倒数第N个节点题目19. 删除链表的倒数第 N 个结点 给你一个链表，删除链表的倒数第 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 <= Node.val <= 100 1 <= n <= sz 进阶：你能尝试使用一趟扫描实现吗？ 题解 此题有点难，适合二刷 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263import java.util.ArrayList;import java.util.List;public class RemoveNthF...

反转链表II题目92. 反转链表 II 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。 示例 1： 输入：head = [1,2,3,4,5], left = 2, right = 4输出：[1,4,3,2,5] 示例 2： 输入：head = [5], left = 1, right = 1输出：[5] 提示： 链表中节点数目为 n 1 <= n <= 500 -500 <= Node.val <= 500 1 <= left <= right <= n 进阶： 你可以使用一趟扫描完成反转吗？ 题解题解一 转换为数组再进行处理 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152public class ReverseBetween &#...

随机链表的复制题目138. 随机链表的复制 完全读不懂题，但能看懂案例🤣🤣🤣 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null ...

合并两个有序链表题目21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4] 示例 2： 输入：l1 = [], l2 = []输出：[] 示例 3： 输入：l1 = [], l2 = [0]输出：[0] 提示： 两个链表的节点数目范围是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列 题解 简单，自己做 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071public class MergeTwoLists { public static void main(String[] args) &#...

两数相加题目2. 两数相加 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例 1： 输入：l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]解释：342 + 465 = 807. 示例 2： 输入：l1 = [0], l2 = [0]输出：[0] 示例 3： 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]输出：[8,9,9,9,0,0,0,1] 提示： 每个链表中的节点数在范围 [1, 100] 内 0 <= Node.val <= 9 题目数据保证列表表示的数字不含前导零 题解 简单，注意点:超过10向前进一 12345678910111213141516171819202122232425262728293031323334353...

环形链表题目141. 环形链表 给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。 示例 1： 输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 输入：head = [1,2], pos = 0输出：true解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 输入：head = [1], pos = -1输出：false解释：链表中没有环。 提示： 链表中节点的数目范围是 [0, 104] -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个 有...

基本计算器题目224. 基本计算器 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。 示例 1： 输入：s = "1 + 1" 输出：2 示例 2： 输入：s = " 2-1 + 2 " 输出：3 示例 3： 输入：s = "(1+(4+5+2)-3)+(6+8)" 输出：23 提示： 1 <= s.length <= 3 * 105 s 由数字、'+'、'-'、'('、')'、和 ' ' 组成 s 表示一个有效的表达式 ‘+’ 不能用作一元运算(例如， “+1” 和 "+(2 + 3)" 无效) ‘-‘ 可以用作一元运算(即 “-1” 和 "-(2 + 3)" 是有效的) 输入中不存在两个连续的操作符 每个数字和运行的计算将适合于一个有符号的 32位 整数 题解 毫无意义毫无营...

逆波兰表达式求值150. 逆波兰表达式求值 题目 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意： 有效的算符为 '+'、'-'、'*' 和 '/' 。 每个操作数（运算对象）都可以是一个整数或者另一个表达式。 两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。 输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用 32 位 整数表示。 示例 1： 输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 示例 2： 输入：tokens = ["4","13","5","/","+"] 输出：6 解释...

最小栈题目155. 最小栈 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。 示例 1: 输入：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]] 输出：[null,null,null,null,-3,null,0,-2] 解释：MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minS...