孙云增的博客

题目给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。 示例1：12输入: [1,3,4,2,2]输出: 2示例2：12输入: [3,1,3,4,2]输出: 3说明：1234不能更改原数组（假设数组是只读的）。只能使用额外的 O(1) 的空间。时间复杂度小于 O(n2) 。数组中只有一个重复的数字，但它可能不止重复出现一次。 思路 + 代码易想到方法 不符合题目要求，因为需要额外的空间。 用链表或者HashMap存储数值，遇到相同的已存储的数就返回。空间复杂度最坏O(n)，时间复杂度最坏O(n)。 或者先排序，遇到相同的数返回。时间复杂度视排序方法而定，最好O(log(n))。 巧妙算法1 巧用快慢指针。 数组的索引与存储的数值之间形成了特殊链表。 如果存在重复的数，因为数组大小是 n+1，数字范围是1~n，所以该链表存在环。 环的入口即为结果。 答案的求解变成环入口的求解。思路 123456789101112131415161718class Solution &# ...

题目数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。 每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。 您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。 示例1：123输入: cost = [10, 15, 20]输出: 15解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。 示例2：123输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]输出: 6解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。 注意：121. cost 的长度将会在 [2, 1000]。2. 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。 思路典型的动态规划问题，上楼梯问题。 注意的是，最后的结果是最后一阶楼梯与倒数第二个楼梯中取最小值。 代码class Solution { public int minCo ...

题目给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如:给定二叉树: [3,9,20,null,null,15,7],12345 3 / \9 20 / \ 15 7 返回其层次遍历结果： 12345[ [3], [9,20], [15,7]] 思路 + 代码二叉树相关算法题两种解题思路：递归和迭代。 递归方法 用一个辅助函数，更新结果。 记录遍历的层数，并按照从左到右的顺序依次在相应层数List中记录数值。 返回结果。 代码1234567891011121314151617181920212223242526272829/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { ...

题目描述给定一个二叉树，返回它的中序 遍历。 示例:12345678输入: [1,null,2,3] 1 \ 2 / 3输出: [1,3,2] 进阶:递归算法很简单，你可以通过迭代算法完成吗？ 思路 + 代码递归方法递归截止条件：root==null 递归执行条件： list.add(inorderTraversal(root.left)) list.add(root.val) list.add(inorderTraversal(root.right)) 代码 12345678910111213141516171819202122232425262728/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solut ...

题目在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例 1:12输入: [3,2,1,5,6,4] 和 k = 2输出: 5 示例 2::12输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4 思路 + 代码简单办法，最容易想到的：用一个长度为 k 存储最大到第k大的数，然后返回数组最后一个元素，即为结果。 1234567891011121314151617181920212223class Solution { public int findKthLargest(int[] nums, int k) { // 数组初始化 int[] results = new int[k]; for(int i=0; i<k; i++){ results[i] = Integer.MIN_VALUE; } // 特殊情况处理 int len = ...

题目根据一棵树的前序遍历与中序遍历构造出二叉树。 注意:你可以假设树中没有重复的元素。 例如，给出 12前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 12345 3 / \9 20 / \ 15 7 思路先序遍历：先根节点 后左子树 最后右子树 中序遍历：先左子树 再根节点 最后右子树 所以先序遍历的第一个数值为根节点，在中序遍历中找到根节点位置，前面为左子树的中序遍历，后面为右子树的中序遍历。 Java代码如下:123456789101112131415161718192021222324252627282930/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */cla ...

题目给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。12345 1 / \ 2 2 / \ / \3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 12345 1 / \2 2 \ \ 3 3 说明: 如果你可以运用递归和迭代两种方法解决这个问题，会很加分。 思路二叉树的一个典型套路就是递归求解。左右树分别对待。 注意递归截止条件以及是否对称的判断条件。 代码123456789101112131415161718192021222324252627/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { ...

题目给定一个 n × n 的二维矩阵表示一个图像。 将图像顺时针旋转 90 度。 说明： 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。 示例1：12345678910111213给定 matrix = [ [1,2,3], [4,5,6], [7,8,9]],原地旋转输入矩阵，使其变为:[ [7,4,1], [8,5,2], [9,6,3]] 示例2：123456789101112131415给定 matrix =[ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16]], 原地旋转输入矩阵，使其变为:[ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11]] 思路如果可以拷贝矩阵，则可以每一行与每一列同时旋转。 但是要求在原矩阵中操作，所以需要每一个元素进行位置旋转变换。 一个4*4的矩阵如下图所示： 顺时针旋转即相同颜色的元素进行依次替换。 对于四阶矩阵，先从最外圈i=0开始，到 ...

题目设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) — 将元素 x 推入栈中。pop() — 删除栈顶的元素。top() — 获取栈顶元素。getMin() — 检索栈中的最小元素。 示例:12345678MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.getMin(); --> 返回 -2. 思路1可以用两个栈，一个栈用来维护当前栈内最小的元素，一个栈用来维度当前栈内的元素。 属于投机取巧的方法。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445class MinStack { ...

题目给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。 找到所有在 [1, n] 范围之间没有出现在数组中的数字。 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。 示例：12345输入:[4,3,2,7,8,2,3,1]输出:[5,6] 思路将出现数字位置的数置为负数。 关键点：置负数时一定取绝对值后取负数，否则会出现负负得正的情况。 例如： 1[2,1,2,4] 1[-2,-1,2,-1] 代码123456789101112131415class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> list = new ArrayList<>(); int len = nums.length; for(int i=0; i<l ...