剑指offer（31-40）题解
剑指offer（31-40）题解
剑指offer（31-40）题解
- 31题解--整数中1出现的次数
- 32题解--把数组排成最小的数
- 33题解--丑数（太特么重要了）*******
- 34题解--第一次只出现一次的字符
- 35题解--数组中的逆序对
- 36题解--两个链表的第一个公共结点
- 37题解--数字在升序数组中出现的次数
- 38题解--二叉树的深度
- 39题解--平衡二叉树
- 40题解--数组中只出现一次的数字
31题解–整数中1出现的次数
题目描述
求出1到13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1到13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
思路解析
这里我是暴力的，主要注意一下int，string，char之间的转换即可。
源代码
public class Solution {
public int NumberOf1Between1AndN_Solution(int n)
{
int count=0;
for(int i=1;i<n+1;i++)
{
String str=String.valueOf(i);
char[]ch=str.toCharArray();
for(int j=0;j<ch.length;j++)
{
if(ch[j]=='1')
count++;
}
}
return count;
}
}32题解–把数组排成最小的数
题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思路解析
这里最简单的办法就是全排列输出所有的数字排列然后进行比较但是这样会出现很多重复的情况，比如说出现{321,321}时，他就会出现两种情况。这里是采用给数组排序定义一个排序规则即可，具体代码中有。
源代码
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
String str="";
Integer[]num=new Integer[numbers.length];
for(int i=0;i<num.length;i++)
num[i]=numbers[i];
Arrays.sort(num,comparator);
for(int i=0;i<num.length;i++)
str+=String.valueOf(num[i]);
return str;
}
//定义数组的排序规则，同样也适用于对象列表，队列等数据结构
Comparator<Integer>comparator=new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int sum1=Integer.parseInt(String.valueOf(o1)+String.valueOf(o2));
int sum2=Integer.parseInt(String.valueOf(o2)+String.valueOf(o1));
return sum1-sum2;
}
};
}33题解–丑数（太特么重要了）*******
题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路解析
这里博主用自己的方法跑了80%的样例，一开始就是十几这种小玩意儿，但是后来就突然跑到1500位，算法的复杂度太高了没能跑出来，在这里借鉴了一下别人的思路，是真的给力。 因为丑数是只包含2,3,5这三个质因子的数，所以可以得出丑数的通用公式如下：
又因为他要求我们是从小到大排序然后输出，所以我们就需要对满足这种格式的数据进行排序，但是这里的难点就是我们如何才能实现排序的 思路是既然通用公式已经确定，我们也不能看出其实数据从后部分开始一定都是前某一项的倍数，而且这个倍数一定是由2,3,5交叉组合而成，所以我们只需要通过判断，将次结算之后最小的那个数添加到我们的数组中即可，但是也不要顽疾通过光标来计数，2,3,5这三个质因子的位置。
源代码
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index <= 0)return 0;
int p2=0,p3=0,p5=0;//初始化三个指向三个潜在成为最小丑数的位置
int[] result = new int[index];
result[0] = 1;//
for(int i=1; i < index; i++){
result[i] = Math.min(result[p2]*2, Math.min(result[p3]*3, result[p5]*5));
if(result[i] == result[p2]*2)p2++;//为了防止重复需要三个if都能够走到
if(result[i] == result[p3]*3)p3++;//为了防止重复需要三个if都能够走到
if(result[i] == result[p5]*5)p5++;//为了防止重复需要三个if都能够走到
}
return result[index-1];
}
}34题解–第一次只出现一次的字符
题目描述
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
思路解析
这里我选择的是重新定义一个对象用来存储我们需要的信息，包括字符出现的次数以及该字符以及首次出现时的下标，之后我们只需要将字符一次存入set之后同时进行判断，如果是第一进入就不仅存入set同时存进list之中，否则就说明list中已经有该对象字符了，我们只需要将该对象的val+1即可。最后检测有误只出现一次的字符即可，并且返回相应的数值。
源代码
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
public class Node {
//存储出现的次数
int val;
//存储该字符
char ch;
//存储字符下标
int address;
Node(char ch,int address) {
this.ch =ch;
this.address=address;
this.val=1;
}
}
public int FirstNotRepeatingChar(String str) {
int flag=-1;
char[]ch=str.toCharArray();
//去重后的字符
Set<Character>set=new HashSet<Character>();
List<Node>list=new ArrayList<Node>();
for(int i=0;i<ch.length;i++)
{
//字符首次出现添加到set与list中
if(!set.contains(ch[i]))
{
set.add(ch[i]);
Node node=new Node(ch[i], i);
list.add(node);
}
//多次出现就开始改变node对象的val
else
{
for(int j=0;j<list.size();j++)
{
if(list.get(j).ch==ch[i])
list.get(j).val++;
}
}
}
//检查是否有只出现过一次的字符，有则直接输出相应的下标
for(int i=0;i<list.size();i++)
{
if(list.get(i).val==1)
{
flag=list.get(i).address;
break;
}
}
return flag;
}
}35题解–数组中的逆序对
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1
输入
1,2,3,4,5,6,7,0
输出
7思路解析
其实求逆序数的本质就是冒泡排序过程中的元素交换次数，但是后来的数据量如果还是通过冒泡排序进行测量交换次数的话，显然时间一定是会超的，所以这里我们选择通过归并排序来实现。 还是放上之前的一张模拟图帮助大家理解。
源代码
public class Solution {
static int value=0;
public int InversePairs(int [] array) {
mergesort(array,0,array.length-1);
return value;
}
private void mergesort(int[] array, int l, int r) {
int mid=(l+r)/2;
if(l<r)
{
mergesort(array, l, mid);
mergesort(array, mid+1, r);
merge(array, l,mid, r);
}
}
//合并两个区间
private void merge(int[] array, int l, int mid, int r) {
int left=l;int right=mid+1;
int num[]=new int[r-l+1];
int index=0;
//两个区间都未超过边界
while (left<=mid&&right<=r) {
//左区间目前是较小的值，所以直接赋值即可
if(array[left]<=array[right])
{
num[index++]=array[left++];
}
else {
//区间目前是较大的值。所以很明显left-mid区间的值都是小于left位置上的值，所以符合逆序数的规则，开始计数
num[index++]=array[right++];
value+=mid-left+1;
value%=1000000007;
}
}
//已经有一个区间已经匹配结束了
//这里是右区间匹配结束，只需要依次将左区间的值赋值即可
while(left<=mid)
{
num[index++]=array[left++];
}
//这里是左区间匹配结束，只需要依次将右区间的值赋值即可
while(right<=r)
{
num[index++]=array[right++];
}
for(int i=0;i<index;i++)
{
array[l+i]=num[i];
}
}
}36题解–两个链表的第一个公共结点
题目描述
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
思路解析
这里我们需要明白如果两个链表有公共的节点，那么这两个链表应该是这样的
我这里选择的先将两个链表的元素分别存入两个list之中，之后再比较记录下公共节点在list1中的位置，之后再将list1剩下的节点串起来返回即可。
源代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
import java.util.ArrayList;
import java.util.List;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int flag=-1;
if(pHead1==null||pHead2==null)
return null;
List<ListNode>list1=new ArrayList<ListNode>();
List<Integer>list2=new ArrayList<Integer>();
ListNode node1=pHead1;
while(node1!=null)
{
list1.add(new ListNode(node1.val));
if(node1.next!=null)
node1=node1.next;
else
break;
}
while(pHead2!=null)
{
list2.add(pHead2.val);
if(pHead2.next!=null)
pHead2=pHead2.next;
else
break;
}
//这里要注意break只能跳出一层循环也就是一层for，while循环，所以这里我进行了标注，否则无法跳出这个双层循环
a:for(int i=0;i<list1.size();i++)
{
for(int j=0;j<list2.size();j++)
{
if(list1.get(i).val==list2.get(j))
{
flag=i;
break a;
}
}
}
if(flag>-1)
{
//将标记点之后的节点都串起来
for(int i=flag;i<list1.size()-1;i++)
list1.get(i).next=list1.get(i+1);
return list1.get(flag);
}
else
return null;
}
}37题解–数字在升序数组中出现的次数
题目描述
统计一个数字在排序数组中出现的次数。
思路解析
暴力即可，但是又不用一直暴力，因为此题是有序的数组，所以我们匹配到第一个符合的数开始计数，当数据不同时即跳出循环。
源代码
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int count=0;
for(int i=0;i<array.length;i++)
{
if(array[i]==k)
count++;
//注意count>0，如果不写，可能跑第一个元素就直接跳出循环了
//count>0是为了保证在查找到该数的情况下已经没有所以才跳出循环
if(array[i]!=k&&count>0)
break;
}
return count;
}
}38题解–二叉树的深度
题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路解析
这里我用的是两个队列来实现求深度的操作的通过下面的图来模拟给大家看一遍。
相信有这张图大家就好理解了。
源代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
int count=0;
public int TreeDepth(TreeNode root) {
int count=0;
Queue<TreeNode> queue1=new LinkedList<TreeNode>();
Queue<TreeNode> queue2=new LinkedList<TreeNode>();
if(root==null)
return 0;
queue2.add(root);
while(!queue2.isEmpty())
{
count++;
for(TreeNode node:queue2)
queue1.add(node);
queue2.clear();
//通过queue1将节点的左孩子与右孩子节点再次压入queue2中
for(TreeNode node:queue1)
{
//这句判断是避免孩子节点为空，而报空指针异常
if(node.left!=null)
queue2.add(node.left);
if(node.right!=null)
queue2.add(node.right);
}
queue1.clear();
}
return count;
}
}39题解–平衡二叉树
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
思路解析
首先我们需要理解什么是平衡树 平衡树就是指任意节点的左子树与右子树的高度的差值要小于等于1，看到这里，想必大家也能看出来，这一题我们需要用到上面的方法，我们可以递归检查每一个节点，计算出以该节点的左孩子为根节点的二叉树的高度以及以该节点的右孩子为根节点的二叉树的高度，然后比较他们的差值即可判断是否为平衡树。
源代码
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int TreeDepth(TreeNode root) {
int count=0;
Queue<TreeNode> queue1=new LinkedList<TreeNode>();
Queue<TreeNode> queue2=new LinkedList<TreeNode>();
if(root==null)
return 0;
queue2.add(root);
while(!queue2.isEmpty())
{
count++;
for(TreeNode node:queue2)
queue1.add(node);
queue2.clear();
for(TreeNode node:queue1)
{
if(node.left!=null)
queue2.add(node.left);
if(node.right!=null)
queue2.add(node.right);
}
queue1.clear();
}
return count;
}
public boolean IsBalanced_Solution(TreeNode root)
{
if(root==null)
return true;
//判断是否为平衡树
int cha=Math.abs(TreeDepth(root.left)-TreeDepth(root.right));
if(cha>1)
return false;
//递归检查左孩子节点
if(root.left!=null)
IsBalanced_Solution(root.left);
//递归检查右孩子节点
if(root.right!=null)
IsBalanced_Solution(root.right);
return true;
}
}40题解–数组中只出现一次的数字
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路解析
这题的原理和第34题类似，就不过多说了，主要是对象的部分属性发生了改变，不在包括数组下标这个属性。
源代码
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
public class Node {
int val;
int count;
Node(int val) {
this.val =val;
this.count=1;
}
}
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[])
{
List<Node>list=new ArrayList<Node>();
Set<Integer>set=new HashSet<Integer>();
List<Integer>list1=new ArrayList<Integer>();
for(int i=0;i<array.length;i++)
{
if(!set.contains(array[i]))
{
set.add(array[i]);
Node node=new Node(array[i]);
list.add(node);
}
else
{
for(int j=0;j<list.size();j++)
{
if(list.get(j).val==array[i])
list.get(j).count++;
}
}
}
for(int i=0;i<list.size();i++)
{
if(list.get(i).count==1)
list1.add(i);
}
num1[0]=list.get(list1.get(0)).val;
num2[0]=list.get(list1.get(1)).val;
}
}