孙云增的博客

题目输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。 思路 + 代码字符串的排序。 123456789101112131415161718import java.util.*;public class Solution { public String PrintMinNumber(int [] numbers) { if(numbers==null || numbers.length==0){ return ""; } int len = numbers.length; String[] strs = new String[len]; for(int i=0; i<len; i++) strs[i] = numbers[i]+""; Ar...

题目求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。 思路 + 代码暴力穷举会超出时间，这道题的关键是找规律。 [图片来自LeetCode 233](https://leetcode-cn.com/problems/number-of-digit-one/solution/shu-zi-1-de-ge-shu-by-leetcode/) 一个数字，分解为十位、百位、千位…上来看。 因为数字由1~n组成，既有十位、百位、千位等组成。 首先，每十个数，个位数字出现一次。每百位数，个位数字出现十次… n/(i*10)*i, i=1, 10, 100, ... 其次，对于后面的数，例如1611，从百位数来看，前面的数字 1611/100*10=160, 后面数字为11，因此后面的个位数为 1+1=2， 而1620和1650...

题目输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 思路1 + 代码维护一个最小堆，该最小堆即为所求。 类似题目 1234567891011121314import java.util.*;public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { if(input==null || input.length==0 || k>input.length) return new ArrayList<Integer>(); PriorityQueue<Integer> pq = new PriorityQueue<Integer>((o1, o2) -> o2-o1); for(int num:input){ ...

题目输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述： 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。 思路 + 代码典型回溯法，同 全排列 解法类似。 123456789101112131415161718192021222324252627import java.util.ArrayList;public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> res = new ArrayList<String>(); backtracking(res, str.toCharArray(), new StringBuilder(), new boolean[str.length()]); return re...

题目给定一个没有重复数字的序列，返回其所有可能的全排列。 示例：12345678910输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] 思路 + 代码回溯问题。 如果遇到一个问题，不用穷举所有情况找不出答案，就采用回溯。 回溯是DFS的一种，遍历完一条路径后，回退一步，继续寻找下一可能路径。 它与暴力法的区别在于，可以通过剪枝规避掉很多无意义的尝试，且不用每次都从头开始遍历到尾部。 讲解可以参考https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html 12345678910111213141516171819202122232425262728class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>>...

题目输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 思路 + 代码二叉搜索树的中序遍历即为一个排序的顺序，按照该顺序依次构建双向链表即可。 123456789101112131415161718192021222324252627282930313233343536/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { private TreeNode firstHead = null; private TreeNode preHead = null; public TreeNode Convert(TreeNode pRootOfTree) ...

题目输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 思路 + 代码参考 https://github.com/CyC2018/CS-Notes/blob/master/notes/%E5%89%91%E6%8C%87%20Offer%20%E9%A2%98%E8%A7%A3%20-%2030~39.md#35-%E5%A4%8D%E6%9D%82%E9%93%BE%E8%A1%A8%E7%9A%84%E5%A4%8D%E5%88%B6 分为三步： 1. 在每个节点的后面插入复制的节点。 2. 每个复制的节点 random 赋值。 3. 拆分。 12345678910111213141516171819202122232425262728293031323334353637383940414243/*public class RandomListNode { int label; Rand...

题目输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 思路 + 代码递归求解，左右子树分别遍历（深度优先）。 遍历终止条件为节点为null或者是叶子节点且和为目标值。 否则回退列表，寻找更短的路径。 1234567891011121314151617181920212223242526272829303132333435import java.util.ArrayList;/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { private ArrayList<Array...

题目输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 思路 + 代码二叉搜索树的左子树所有节点小于根节点，右子树的所有节点大于根节点。 后序遍历是先访问左子树，后访问右子树。 因此，根节点永远在序列的最后位置。找到根节点数值后，根据前面节点数值与根节点的大小关系，找到左右子树的分割位置，递归求解。 123456789101112131415161718192021222324252627public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { // 初始条件判断 if(sequence==null || sequence.length==0) return false; // 调用重写的辅助函数 return VerifySquenceOfBST(sequence, 0, sequence.le...

题目从上往下打印出二叉树的每个节点，同层节点从左至右打印。 思路 + 代码二叉树的层次遍历，用队列保存同一层次的树节点，然后依次遍历。 类似题目http://sunyunzeng.cn/Leetcode-102-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E6%AC%A1%E9%81%8D%E5%8E%86/ 1234567891011121314151617181920212223242526272829303132333435import java.util.*;/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { public ArrayList<Integer>...