题目描述 链接: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/submissions/ 解题思路: 利用递归的思想, 分四种情况: 当前节点空, 返回0 当前节点的左节点飞空, 递归求左子树的最小深度, 返回+1(本身也算一个) 当前节点的右节点飞空, 递归求右子树的最小深度, 返回+1(本身也算一个) 左右节点都空, 返回1 代码: // T: O(n), S: O(n) class Solution { public int minDepth(TreeNode root) { if...

题目描述 链接: https://leetcode-cn.com/problems/same-tree/submissions/给定两个二叉树，编写一个函数来检验它们是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 题目分析 和判断树的左右子树镜面性一样, 可以用两种方法(递归, 迭代)解决问题.时间复杂度, 空间复杂度均为 O(N), O(N). 代码 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode lef...

题目描述 链接: https://leetcode-cn.com/problems/symmetric-tree/submissions/给定一个二叉树，检查它是否是镜像对称的。 题目分析 本题有两种解题方式: 递归方式如果一个树的左子树和右子树镜像对称, 那么这个树是对称的如果同时满足以下条件, 两个树互为镜像:1) 两个根节点具有相同的值2) 每个树的右子树都与另一个树的左子树镜像对称, 每个树的左子树都与另一个树的右子树镜像对称. 迭代方式利用栈来进行迭代. 代码: /** * Definition for a binary tree node. * public cla...

题目描述: 链接: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/submissions/ 解题方法: 递归 O(N), O(N) 迭代(模拟递归) O(N), O(N) 代码: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } ...

题目描述 链接: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 [-1, -1]。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4]示例 2: 输入: nums = [5,7,7,8,8,1...

题目描述: 链接: https://leetcode-cn.com/problems/search-a-2d-matrix/submissions/ 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。示例 1: 输入:matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]target = 3输出: true示例 2: 输入:matrix = [ [1, 3, 5, 7], [10, 11, 1...

题目描述 链接: https://leetcode-cn.com/problems/search-a-2d-matrix-ii/submissions/ 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性： 每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例: 现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]给定 t...

题目描述 链接: https://leetcode-cn.com/problems/single-element-in-a-sorted-array/给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。 示例 1: 输入: [1,1,2,3,3,4,4,8,8]输出: 2示例 2: 输入: [3,3,7,7,10,11,11]输出: 10注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。 代码(二分法): class Solution { public int singleNonDuplicate(int[] nums)...

题目描述 链接: https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode/实现 pow(x, n) ，即计算 x 的 n 次幂函数。 示例 1: 输入: 2.00000, 10输出: 1024.00000示例 2: 输入: 2.10000, 3输出: 9.26100示例 3: 输入: 2.00000, -2输出: 0.25000解释: 2-2 = 1/22 = 1/4 = 0.25 二分快速幂 递归版本注意点: 需要提前判断n是否小于0, 如果小于0, 则需要1 / res.思路:a是偶数次: x^a = x^(...

思想: 将数组分为 有序区 和 无序区, 每一趟排序安排一个无序区中最小数字到有序区的最后一位. 代码: // Time: O(n^2), Space: O(1) public void sort(int[] arr) { if (arr == null || arr.length == 0) return; int n = arr.length; for (int i = 0; i < n; ++i) { int minIdx = i; for (int j = i+1; j < n; ++j) if (arr[...

题目描述 链接:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/ 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 你可以假设数组中不存在重复元素。 示例 1: 输入: [3,4,5,1,2]输出: 1示例 2: 输入: [4,5,6,7,0,1,2]输出: 0 代码: class Solution { public int findMin(int[] nums) { ...

题目描述: 链接: https://leetcode-cn.com/problems/find-the-duplicate-number/给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。 示例 1: 输入: [1,3,4,2,2]输出: 2示例 2: 输入: [3,1,3,4,2]输出: 3说明： 不能更改原数组（假设数组是只读的）。只能使用额外的 O(1) 的空间。时间复杂度小于 O(n2) 。数组中只有一个重复的数字，但它可能不止重复出现一次。 题目分析: 首先分析题...

题目描述 给定一个排好序的数组, 和待找元素target, 如果找到了就返回下标, 没找到就返回它的正确位置.示例 1: 输入: [1,3,5,6], 5输出: 2示例 2: 输入: [1,3,5,6], 2输出: 1 代码: class Solution { public int searchInsert(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low <= high) { int mid = (low + high) /...

题目描述: 链接: https://leetcode-cn.com/problems/binary-search/submissions/题目:用二分查找在一个有序数组当中找一个数, 有返回下标, 无返回-1.示例 1:输入: nums = [-1,0,3,5,9,12], target = 9输出: 4解释: 9 出现在 nums 中并且下标为 4 代码: class Solution { public int search(int[] nums, int target) { int low = 0, high = nums.length - 1; ...