孙云增的博客

题目给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 示例1:12输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2] 示例2:12输入: nums = [1], k = 1输出: [1] 说明:12你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 思路首先用一个HashMap统计不同数字出现的次数。 然后用一个最小堆维护k大小的结果。 这里采用java的优先队列 PriorityQueue 去维护最小堆。 这里需要注意的一点是比较器的设计，部分源代码如下： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162public boolean add(E e) { return offer(e); }public boolean...

题目根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。 思路+代码最简单的思路，两次循环。 1234567891011121314151617class Solution { public int[] dailyTemperatures(int[] T) { int len = T.length; int[] results = new int[len]; for(int i=0; i<len-1; i++){ int tmp = 0; for(int j=...

题目给定一个包含 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 mi...

题目给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如:给定二叉树: [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 So...

题目在未排序的数组中找到第 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 le...

题目根据一棵树的前序遍历与中序遍历构造出二叉树。 注意:你可以假设树中没有重复的元素。 例如，给出 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; } * } */...

题目给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [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开...