孙云增的博客

题目给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例：123输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807 代码123456789101112131415161718192021222324252627/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode addTwoNumbers(ListNode l1 ...

题目一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 思路 + 代码思路1利用Map统计每个数字出现的次数。 123456789101112131415161718192021//num1,num2分别为长度为1的数组。传出参数//将num1[0],num2[0]设置为返回结果import java.util.*;public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { ArrayList<Integer> list = new ArrayList<Integer>(); HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int num: array){ if(!map.conta ...

题目输入一棵二叉树，判断该二叉树是否是平衡二叉树。 思路 + 代码平衡二叉树的左右子树的高度差不大于 1。 12345678910111213141516public class Solution { private boolean isBalanced = true; public boolean IsBalanced_Solution(TreeNode root) { height(root); return isBalanced; } private int height(TreeNode root){ if(root==null || !isBalanced) return 0; int left = height(root.left); int right = height(root.right); if(1<Math.abs(left-right)) isBalanced = f ...

题目统计一个数字在排序数组中出现的次数。 思路 + 代码不能遍历，否则时间超出。二分查找，寻找边界位置。 12345678910111213141516171819202122public class Solution { public int GetNumberOfK(int [] array , int k) { if(array==null||array.length==0) return 0; int l = binarySearch(array, k); int h = binarySearch(array, k+1); return (l>array.length-1 || array[l]!=k)?0:h-l; } private int binarySearch(int[] n, int k){ int l = 0, r = n.length; int m; while(l<r) ...

题目输入两个链表，找出它们的第一个公共结点。 思路 + 代码设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。 当访问链表 A 的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问链表 B 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。 1234567891011121314151617181920/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ...

题目在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 题目描述: 123456789题目保证输入的数组中没有的相同的数字数据范围： 对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5 示例112345输入1,2,3,4,5,6,7,0输出7 思路归并排序，先拆分成单个的数字，然后向上归并同时统计逆数数量。 12345678910111213141516171819202122232425262728293031323334353637383940public class Solution { private int count = 0; public int InversePairs(int [] array) { if(array==null || array.length==0) ...

题目在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）. 思路 + 代码用一个LinkedHashMap统计每个字符出现的次数，同时保存顺序。然后String查找该字符第一次出现的位置。 12345678910111213141516171819202122import java.util.*;public class Solution { public int FirstNotRepeatingChar(String str) { if(str==null || str.length()==0) return -1; char[] chs = str.toCharArray(); LinkedHashMap<Character, Integer> map = new LinkedHashMap<Character, Integer>(); int l ...

题目把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 　思路　＋　代码丑数只能是丑数乘以　2、３、５。 按照顺序存储丑数，也就是比较每次丑数的大小。 1234567891011121314151617181920public class Solution { public int GetUglyNumber_Solution(int index) { if(index <= 0) return 0; int[] dp = new int[index]; dp[0] = 1; int i2 = 0, i3 = 0, i5 = 0; for(int i=1; i<index; i++){ dp[i] = Math.min(Math.min(dp[i2]*2, dp[i3]*3), dp[i5]*5) ...

题目输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{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]+""; Array ...

题目求出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后面的 ...