Lucky Le の Blog

110. 平衡二叉树 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 思路：定义一个深度优先辅助方法，返回值为当前节点的深度，如果返回值为-1表示以当前节点为根的子树不是平衡二叉树。 返回-1的条件有三个：左子树返回-1，右子树返回-1，或者左右子树高度差大于1。 1234567891011121314151617181920212223242526272829303132333435/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, ...

剑指 Offer 40. 最小的k个数 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例 1： 输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1] 思路：我们的目标是找到递增排序后的第k个数。可以采用快排的思想，快排的partition操作会确定pivot在排序后的位置，将这个位置index与k进行比较，如果等于k，则返回[0, index]的数；如果index < k，则在右半边继续找；如果index > k，则在左半边找。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152class Solution { private static final Random random = new Random(System.currentTimeMillis()); public int[] g ...

剑指 Offer 16. 数值的整数次方 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。 示例 1： 输入：x = 2.00000, n = 10 输出：1024.00000 思路参考题解：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/ 思路是使用快速幂。简单来说就是将指数改写为二进制。然后通过循环复制x *= x，在指数二进制为1的位置，将结果乘上x即res *= x。详细的描述可以看参考题解。 对于指数为负数的处理，如果指数为负数，x = 1 / x并将指数再设置为正数即可。比如2−12^{-1}2−1可以转化为(12)1(\frac12)^1(21​)1 12345678910111213141516171819class Solution { public double myPow(double x, ...

236. 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 示例 1： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 思路：如果root为p和q的最近公共祖先，则一共有三种情况： p和q在root的两侧 p = root，且q在root的左子树或者右子树中； q = root，且p在root的左子树或者右子树中； 考虑使用先序遍历，遇到p或者q时返回。从下往上回溯，当p和q在root异侧时，返回root。 详见代码： 123456789101112131415161718192021222324252627/** * Definition for a binary tree node. * public class TreeNode ...

剑指 Offer 54. 二叉搜索树的第k大节点 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。 思路：对于二叉搜索树，中序遍历的倒序是递减的。题目中求第K打节点，可以转化为中序遍历倒序的第k个节点。 中序遍历过程中，如果–k之后，k的值为0，则表示遍历到第k个节点了 123456789101112131415161718192021222324252627282930313233/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { private int k; private int ans; public int kthLargest(TreeNode root, int k) { ...

113. 路径总和 II 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1： 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]] 思路：回溯思想+DFS实现，因为要返回所有的路径，因此用path记录当前遍历的路径。当遍历到叶节点并且节点的值等于targetSum时，即找到符合条件的路径。 遍历时更新targetSum为targetSum - 当前节点的value 注意回溯时将路径path中最后一个节点移除。 1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * Definition for a binary tree node. * public class TreeNode { * int val ...

79. 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例 1： 输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED” 输出：true 思路：采用深度优先和回溯的思路。是一道比较典型的回溯题。 定义了一个方向数组用于深度遍历时确定方向。 定义visited数组用于记录元素是否已经访问过。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960class Solution { private final static int[] DI ...

剑指 Offer 52. 两个链表的第一个公共节点 输入两个链表，找出它们的第一个公共节点。 示例 1： 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 思路：如果A为Null或者B为NUll，则不会相交； 定义两个指针分别从A和B开始同时向后走，假设A到相交节点的距离为a（示例中则为2），B到相交节点的距离为b（示例中则为3），重合部分长度为c（示例中则为3）。 如果指针A完，即A为Null后，继续从B开始向后遍历；同理B走完后从A继续遍历；两个指针相遇时，即在相交节点。 相交是指针A走的距离为a+c+b；指针B走的距离为b+c+a。 ...

3. 无重复字符的最长子串 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2: 输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3: 输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。 提示： 0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成 思路：采用滑动窗口的思路，保证窗口内的字符不重复。采用HashMap记录字符最后一次出现的下标。右指针向右遍历的过程中，如果遇到重复字符，则更新左指针，记录字符在map中的下标，并更新返回值。 1234567891011121314151617181920class Solution { public ...

剑指 Offer 46. 把数字翻译成字符串 题目：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 样例： 输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi” 其中：0≤num<2310 \leq num < 2^{31}0≤num<231 思路：动态规划题的核心是找到状态转移方程，以及定义好初始状态。 定义：dp[i]表示第i个数字结尾的方案数，那么转移方程有两种情况： 当xix_ixi​和xi−1x_{i-1}xi−1​两个数字可以被翻译，即在[10, 25]区间内，dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i - 1] + dp[i - 2]dp[i]=dp[i−1]+dp[i−2] 当xix_ixi​和xi−1x_{ ...