孙云增的博客

题目设计一个支持 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...

题目请判断一个链表是否为回文链表。 示例1：12输入: 1->2输出: false 示例2：12输入: 1->2->2->1输出: true进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 思路用 栈+快慢指针 或者 快慢指针+反转链表 快慢指针是用来寻找中间节点。栈是用来反转链表。 代码 栈 + 快慢指针 1234567891011121314151617181920212223242526272829303132/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public boolean isPalindrome(ListNode head) { if(head==null|...

题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 示例1:12345输入： 2输出： 2解释： 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶 示例2:123456输入： 3输出： 3解释： 有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶 思路递归或者动态规划。 第n阶楼梯的走法 = 第n-1阶楼梯走法 + 第n阶楼梯走法。 边界条件，n<=3。 代码1234567891011121314// 动态规划class Solution { public int climbStairs(int n) { if(n<=3) return n; int[] dp = new int[n]; for(int i=0;i<3;i++){ dp[i] = i+1; }...

题目你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 示例1：1234输入: [1,2,3,1]输出: 4解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。  偷窃到的最高金额 = 1 + 3 = 4 。 示例2：1234输入: [2,7,9,3,1]输出: 12解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。  偷窃到的最高金额 = 2 + 9 + 1 = 12 。 思路动态规划 用一个数组维护截止到当前偷窃的最大值。更新条件：dp[i]=max(nums[i]+dp[i-1], dp[i-1])。 代码123456789101112131415class Solution { public int rob(i...

题目给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例： 123输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 思路动态规划。 用一个数组维护一个包含当前数字的最大子序列，取该数组的最大值即为结果。 代码12345678910111213class Solution { public int maxSubArray(int[] nums) { int len = nums.length; int result = nums[0]; int[] dp = new int[len]; dp[0] = nums[0]; for(int i=1; i<len; i++){ dp[i] = Math.max(dp[i-1]+nums[i], nums[i]); result = Math.max(dp...

题目给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。 二叉搜索树：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。 思路因为二叉搜索树左子树、根节点及右子树已经拍好顺序，所以只需遍历右子树计算累加值，然后对根节点与左子树分别累加。 可采用递归或遍历方法。首先累加右子树数值，然后依次修改根节点与左子树的数值。 代码1 递归1234567891011121314151617181920/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = ...

题目给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例:12输入: [0,1,0,3,12]输出: [1,3,12,0,0] 说明: 1. 必须在原数组上操作，不能拷贝额外的数组。 2. 尽量减少操作次数。 思路1采用双循环，当遇到零元素时，与后面序列中第一个非零元素交换。 时间复杂度: $O(n!)$ 结果:执行用时 : 16 ms内存消耗 :37.4 MB 代码12345678910111213141516class Solution { public void moveZeroes(int[] nums) { int len = nums.length; for(int i=0;i<len-1;i++){ if(nums[i]==0){ int j =i+1; while(j<len&&nums[j]==0){ ...

题目将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例1：12输入：1->2->4, 1->3->4输出：1->1->2->3->4->4 思路1分为两步： 第一步： 记录所有的链表的数值并排序。因为链表的长度未知，所以需要用 List 来存储。 第二步： 按照排序后的链表数值，建立对应链表。 代码12345678910111213141516171819202122232425262728293031323334/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode mergeTwoLists(ListNode l1, List...

题目给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在众数。 示例1： 12输入: [3,2,3]输出: 3 示例2： 12输入: [2,2,1,1,1,2,2]输出: 2 思路 + 代码法1. 我的方法，超笨。用一个Map记录数字出现的次数，然后当次数大于n/2时返回。 代码 12345678910111213141516class Solution { public int majorityElement(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); int len = nums.length; for(int i=0; i<len; i++){ if(map.get(nums[i])!=null){ Integer num = map.get...