剑指offer｜31-40题解题思路及代码(Java版)
剑指offer31到40题总览：
- 整数中1出现的次数(从1到n整数中1出现的次数)
- 把数组排成最小的数
- 丑数
- 第一个只出现一次的字符
- 数组中的逆序对
- 两个链表的第一个公共结点
- 数字在排序数组中出现的次数
- 二叉树的深度
- 平衡二叉树
- 数组中只出现一次的数字
31、整数中1出现的次数(从1到n整数中1出现的次数)
题目描述
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
解题思路
暴力的方法，将1到n变成字符串类型，遍历每个字符，等于'1'则count+1。或其他方法：
先以n=100为例，可知有1的数有1 10 11 12 13 14 15 16 17 18 19 21 31 41 51 61 71 81 91 100。其中11出现了两次1，要算两次。我们换一种数法。
计算个位数为1的个数：1 11 21 31 41 51 61 71 81 91。有10个。
计算十位数为1的个数：10 11 12 13 14 15 16 17 18 19。有10个。
计算百位数为1的个数：100。有1个
可以看到，这样的数法能巧妙地将11计算两次。由此我们可以推出以下巧妙的解法。
参考牛客网的解法：链接：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6
例如我们现在要计算百位数为1的数的个数。n=3141592，我们令i=100，由此利用%100和/100可以将n=3141592分成 31415｜92 ，a=31415，b=92。
我们知道100~199有100个数，这些数的百位数都为1。
当百位数>=2时，3141500则经历了3142个完整的从100~199的数(不管其它位)，从100~199, 1100~1199, 2100~2199, 3100~3199,...,3141100~3141199一共有0~3141个完整的100~199的数。
当百位数=1时，则经历了3141个完整的从100~199的数，然后还有第二部分的b=92，会经历从100~192的一共93个百位数为1的数。
当百位数=0时，则不用考虑第二部分。
综上，则当i=100时，会经历(a+8)/10个完整的100~199共100个数。再加上如果百位数为1，需要考虑的第二部分为(a%10==1)*(b+1)个百位数为1的数。
这里(a+8)/10的原因是，如果百位数>=2，则a+8会发生进位，可以巧妙地多计算一个完整的从100~199的数，而=0或=1时不会计算。如果我们要计算的是整数1~n中出现2的次数，则为(a+7)/10，当百位数>3=时发生进位。
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int count = 0;
for(int i=1; i<=n; i*=10){
int a = n/i;//计算前半部分
int b = n%i;//计算后半部分
if(a%10 == 1){//对前面部分的末位进行判断
count = count + (a/10)*i + (b+1);//加上后半段
}else if(a%10 == 0){
count = count + (a/10)*i;//不需要加上后半段
}else{
count = count + (a/10 + 1)*i;
}
}
return count;
}
}
32、把数组排成最小的数
题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
解题思路
总体思路是基于排序，给数字排一个先后顺序。比较的时候，将数字转化为String类型，对两种拼接类型进行比较，选择拼接的数字比较小的那一种，保持它们在list中的相对顺序。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
if(numbers.length == 0){return "";}
ArrayList<Integer> list = new ArrayList<>();//新建一个list，可用Collections.sort进行排序。
for(int i=0; i<numbers.length; i++){//将数组中的数加入list
list.add(numbers[i]);
}
Collections.sort(list, new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b){//重写compare函数
String s1 = String.valueOf(a);
String s2 = String.valueOf(b);
return (s1+s2).compareTo(s2+s1);//s1+s2比较小则返回-1，升序排列
}
});
String result = "";//将list转化为输出结果
for(int i=0; i<list.size(); i++){
result = result+list.get(i);
}
return result;
}
}
33、丑数
题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路
建立三个队列，对应2、3、5的队列，每次将三个队列的队头元素最小的数出队列，如果有多个相同的最小值，则全出列，这样可以避免重复。出队列之后将其2、3、5的倍数入相应队列。
import java.util.LinkedList;
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index==0){return 0;}
if(index==1){return 1;}
LinkedList<Integer> q2 = new LinkedList<>();
LinkedList<Integer> q3 = new LinkedList<>();
LinkedList<Integer> q5 = new LinkedList<>();
q2.offer(2);//将1*2, 1*3, 1*5入各自的队列
q3.offer(3);
q5.offer(5);
for(int i=2; i<index; i++){
int min = Math.min(Math.min(q2.peek(), q3.peek()), q5.peek());
if(min == q2.peek()){q2.poll();}//这里要是连续的if，而不是if else语法，因为可能发现队头元素一样大的情况，这种要将一样的数全部出队列。
if(min == q3.peek()){q3.poll();}
if(min == q5.peek()){q5.poll();}
q2.offer(min*2);//出了队列之后，将其2，3，5的倍数入相应队列
q3.offer(min*3);
q5.offer(min*5);
}
return Math.min(Math.min(q2.peek(), q3.peek()), q5.peek());
}
}
34、第一个只出现一次的字符
题目描述
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
解题思路
用HashMap记录出现次数
import java.util.HashMap;
public class Solution {
public int FirstNotRepeatingChar(String str) {
if(str.length() == 0){return -1;}
if(str.length() == 1){return 0;}
HashMap<Character, Integer> map = new HashMap<>();
for(int i=0; i<str.length(); i++){//遍历字符串，记录每个字符出现的次数
if(map.containsKey(str.charAt(i))){
int count = map.get(str.charAt(i));
map.put(str.charAt(i), count+1);
}else{
map.put(str.charAt(i), 1);
}
}
for(int i=0; i<str.length(); i++){//遍历字符串，看那一个字符出现次数为1，第一个发现次数为1的返回
if(map.get(str.charAt(i)) == 1){
return i;
}
}
return -1;
}
}
35、数组中的逆序对
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
解题思路
此题需要一个稳定的排序算法，并记录每个数前移多少位，这样才能计算逆序对。稳定的有：冒泡排序、插入排序、归并排序。冒泡和插入排序都是，试了冒泡排序，无法通过。
注意事项
- 本题有一个数组长度特别大的用例，算法应该尽量快。
public class Solution {
long count = 0;
public int InversePairs(int [] array) {
mergeSort(array, 0, array.length);
return (int)(count % 1000000007);
}
public void mergeSort(int[] arr, int start, int end){
if(end-start > 1){
int mid = (end+start+1)/2;
mergeSort(arr, start, mid);//对左半部分递归
mergeSort(arr, mid, end);//对右半部分递归
int i = start;
int j = mid;
int[] temp = new int[end-start];
int index = 0;
while(j != end && i != mid){//合并两个部分，比较i和j指向的数，将更小的数写入temp数组，起到排序作用
if(arr[j] < arr[i]){
temp[index] = arr[j];
count = count + j - start - index;
++j;
}else{
temp[index] = arr[i];
++i;
}
++index;
}
if(j!=end){//如果是后半部分没有读完，则可以不用把后半部分复制到temp数组中，直接向前将前面的数覆盖到原数组中
for(--index; index>-1;index--){
arr[index+start] = temp[index];
}
}else{
for(; index<temp.length; index++){//前半部分没有读完，将前半部分的数复制到temp中
temp[index] = arr[i];
++i;
}
for(int k=0; k<temp.length; k++){//将temp数组整个覆盖到原数组中
arr[k+start] = temp[k];
}
}
}
}
}
36、两个链表的第一个公共结点
题目描述
输入两个链表，找出它们的第一个公共结点。
解题思路
一个方法是先计算两个链表的长度，如果链表1比链表2长k个结点，则链表1先走k个结点，然后与链表2一起走，每走一步判断是否是同一个结点，第一个相同的结点即是返回结果。
另一个方法是用hashmap，先将链表1中的所有结点加入hashmap，然后对链表2中的每个结点，判断是否在hashmap中存在，第一个在hashmap中已经存在的结点，即是返回结果。
import java.util.HashMap;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null || pHead2==null){return null;}
HashMap<ListNode, Integer> map = new HashMap<>();
do{//将链表1中的结点全部入hashmap
map.put(pHead1, 1);
pHead1 = pHead1.next;
}while(pHead1!=null);
do{//对链表2中的每个结点，查看是否已经在hashmap中存在
if(map.containsKey(pHead2)){
return pHead2;
}else{
pHead2 = pHead2.next;
}
}while(pHead2!=null);
return null;
}
}
37、数字在排序数组中出现的次数
题目描述
统计一个数字在排序数组中出现的次数。
解题思路
数组有序，用二分法查找该数组，然后左右扩展看看有多少个。
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array.length == 0){return 0;}
if(array.length == 1){
if(array[0] == k){return 1;}
else{return 0;}
}
int i = 0;
int j = array.length-1;
int index = -1;//index保存要寻找的数的下标
while(i<=j){//当j小于i时循环停止
index = (i+j)/2;
if(array[index] == k){break;}//在该i,j段的中间找到目标值，跳出循环
else if(array[index] < k){//如果中间值小于目标值，则在右侧寻找
i = index+1;
}else{//如果中间值大于目标值，则在左侧寻找
j = index-1;
}
}
int count = 0;
if(array[index]==k){//如果是中间值等于目标值跳出循环，则可左右扩展寻找目标值的个数；如果是因为j<i而跳出，则返回0。
count++;//先将index算上一个
for(int t=index-1; t>=0; t--){//向左寻找个数
if(array[t] < k){
break;
}else{
count++;
System.out.println("+1");
}
}
for(int t=index+1; t<array.length; t++){//向右寻找个数
if(array[t] > k){
break;
}else{
count++;
System.out.println("+1");
}
}
}
return count;
}
}
38、二叉树的深度
题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
解题思路
递归的方法最简洁
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null){return 0;}
int left = TreeDepth(root.left);//求左子树深度
int right = TreeDepth(root.right);//求右子树深度
return left>right? left+1:right+1;//返回更深的子树+1
}
}
39、平衡二叉树
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
解题思路
用递归的方法计算树的深度，如果子树是平衡的，则返回子树深度，如果子树不平衡，则返回-1，然后-1可一路返回到根节点上。
注意事项
- 判断树是否平衡，需要对每个结点计算其左右子树的深度，并判断左右子树的深度差的绝对值是否小于等于1。如果采用从根节点到叶子节点的方法依次计算深度，进而判断是否平衡，则会产生很多重复计算深度的情况。
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null){return true;}
if(getSubtreeDiff(root) == -1){//如果子树差返回了-1，则返回false，树不平衡
return false;
}else{return true;}//子树差返回不是-1，则返回true，树平衡
}
public int getSubtreeDiff(TreeNode root){
if(root==null){return 0;}//如果结点为空，则当前树平衡
int left = getSubtreeDiff(root.left);//计算root左子树是否平衡，如果平衡则返回左子树的高度
if(left == -1){return -1;}//如果左子树不平衡，则可一路返回-1
int right = getSubtreeDiff(root.right);//计算root右子树是否平衡，如果平衡则返回右子树高度
if(right == -1){return -1;}//如果右子树不平衡，则可一路返回-1
return Math.abs(left-right)<=1? 1+Math.max(left, right): -1;//左右子树都是平衡的，那么计算root节点是否平衡，如果左右高度差绝对值小于等于1，则平衡，返回root树的深度；如果不平衡，则返回-1，可一路返回-1
}
}
40、数组中只出现一次的数字
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
解题思路
一种方法是用hashmap，另一种方法是用异或的方法。
我们将数组中的所有数都异或起来得到，则其他相同的数都会被抵消，最后异或的结果，就是两个只出现了一次的数的异或
。
得到了两个数的异或，将它们分开的方法如下：我们利用异或的性质，0^1=1、1^0=1、0^0=0、1^1=0，可以得到当两位不相同时，可以得到1，也就是说，我们可以找到二进制从右至左的第一个1(first1_index)，则num1和num2关于这一位一定相反，一个该位是1，一个该位为0。
我们根据这一个性质，将数组中的数可以分为两部分。一部分是该位为1的数，另一部分是该位为0的数。每组相同的数会被抵消，只剩下一个只出现一次的数。
注意事项
- java中的：与&、或|、非~、异或^、向左位移<<、向右位移>>。
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array.length == 2){
num1[0] = array[0];
num2[0] = array[1];
}
int n = array[0];
for(int i=1; i<array.length; i++){//将数组中所有数异或起来，得到n
n = n ^ array[i];
}
int first1_index = 0;//查找n的二进制中从右至左的第一个1，得到该位的下标first1_index
while((n&1)!=1 && first1_index<32){
n >>= 1;
first1_index++;
}
for(int i=0; i<array.length; i++){
if(((array[i]>>first1_index) & 1)==0){//根据array[i]二进制该位的值是0还是1，进行分组
num1[0]^=array[i];//该位为0的与num1[0]进行异或
}else{
num2[0]^=array[i];//该位为1的与num2[0]进行异或
}
}
}
}
结尾
如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的文章，请点喜欢~*我是蓝白绛，感谢你的阅读！
