剑指offer题目总结(23-44)
需要二刷的题目
题目23 二叉搜索树的后序遍历序列 !
题目24 二叉树和为某一值的路径 !
题目32 整数中1的出现的次数 !
题目34 丑数 三刷
题目36 数组中的逆序对 !
题目41 数组中只出现一次的数字 !
题目42 和为S的连续正数序列 !
题目43 和为S的两个数字 !
题目23 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length == 0) {
return false;
}
return isPost(sequence,0,sequence.length-1);
}
public static boolean isPost(int[] arr,int start,int end)
{
if(start==end) return true;
int less=-1;
int more=end;
for(int i=start;i<end;i++)
{
if(arr[end]>arr[i])//如果是大于
{
less=i;
}else//如果是小于
{
more=more==end?i:more;
}
}
if(less==-1||more==end)
{
return isPost(arr,start,end-1);
}
if(less+1!=more)
{
return false;
}
return isPost(arr,start,less)&&isPost(arr,more,end-1);
}总结：base case的条件
题目24 二叉树和为某一值的路径
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
ArrayList<ArrayList<Integer>> allList=new ArrayList<>();
ArrayList<Integer> list=new ArrayList<>();
f(root,target,list,allList);
return allList;
}
public static void f(TreeNode root, int target,ArrayList<Integer> list,
ArrayList<ArrayList<Integer>> allList)
{
if(root==null) return ;//base 1
target-=root.val;
list.add(root.val);
if(target==0&&root.left==null&&root.right==null)//base case 2
{
allList.add(new ArrayList<>(list));
}
f(root.left,target,list,allList);
f(root.right,target,list,allList);
list.remove(list.size()-1);//当前位置的抛去
}
}题目25 复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
public class Solution {
public RandomListNode Clone(RandomListNode head)
{
if (head == null) {
return null;
}
RandomListNode cur=head;
RandomListNode next=null;
//复制节点
while(cur!=null)
{
next=cur.next;
cur.next=new RandomListNode(cur.label);
cur.next.next=next;
cur=next;
}
cur=head;
RandomListNode copyNode=null;
//复制random节点
while(cur!=null)
{
next=cur.next.next;
copyNode=cur.next;
copyNode.random=cur.random!=null?cur.random.next:null;
cur=next;
}
cur=head;
RandomListNode res=head.next;
//拆分
while(cur!=null)
{
next=cur.next.next;
copyNode=cur.next;
cur.next=next;
//复制节点的下一个指向
copyNode.next=next!=null?next.next:null;//需要注意的地方
cur=next;
}
return res;
}
}题目26 二叉搜索树和双向链表
TreeNode pre=null;
TreeNode cur=null;
public TreeNode Convert(TreeNode pRootOfTree) {
f(pRootOfTree);
return cur;
}
public void f(TreeNode pRootOfTree)
{
if(pRootOfTree==null) return ;
f(pRootOfTree.left);
if(cur==null)
{
cur=pRootOfTree;
pre=pRootOfTree;
}else
{
pre.right=pRootOfTree;
pRootOfTree.left=pre;
pre=pRootOfTree;
}
f(pRootOfTree.right);
}总结：使用两个全局变量
题目27 字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> list=new ArrayList<>();
char[] chas = str.toCharArray();
f(chas,0,list);
Collections.sort(list);
return list;
}
public static void f(char[] chars,int index,ArrayList<String> list)
{
if(index==chars.length-1)
{
String str=String.valueOf(chars);
if(!list.contains(str))
list.add(String.valueOf(chars));
}
for(int i=index;i<chars.length;i++)
{
swap(chars,i,index);
f(chars,index+1,list);
swap(chars,i,index);
}
}
public static void swap(char[] arr,int m,int n)
{
char tmp=arr[m];
arr[m]=arr[n];
arr[n]=tmp;
}
}题目28
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
public class Solution {
public int MoreThanHalfNum_Solution(int [] arr) {
int host=0;
int count=0;
for(int i=0;i< arr.length;i++)
{
if(count==0)
{
host=arr[i];
count=1;
}else if(host!=arr[i])
{
count--;
}else
{
count++;
}
}
count=0;
for(int i=0;i<arr.length;i++)
{
if(arr[i]==host)
{
count++;
}
}
if(count>arr.length/2)
{
return host;
}else
{
return 0;
}
}
}总结：需要最后在检查一下
题目30 最小的K个数
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] arr, int k) {
ArrayList<Integer> list= new ArrayList<>();
if(k>arr.length) return list;
for(int i=0;i<k;i++)
{
heapInsert(arr,i);
}
for(int i=k;i<arr.length;i++)
{
if(arr[i]<arr[0])
{
swap(arr,i,0);
heapify(arr,k,0);
}
}
for(int i=0;i<k;i++)
{
list.add(arr[i]);
}
Collections.sort(list);
return list;
}
public static void swap(int[] arr,int m,int n)
{
int tmp=arr[m];
arr[m]=arr[n];
arr[n]=tmp;
}
public static void heapInsert(int[] arr,int index)
{
while(arr[(index-1)/2]<arr[index])
{
swap(arr,index,(index-1)/2);
index=(index-1)/2;
}
}
public static void heapify(int[] arr,int size,int index)
{
int left=index*2+1;
while(left<size)
{
int largest=left+1<size&&arr[left+1]>arr[left]?left+1:left;
largest=arr[largest]>arr[index]?largest:index;
if(largest==index)
{
break;
}
swap(arr,index,largest);
index=largest;
}
}
}总结：堆的两个操作牢记
题目31 连续子数组的最大和
例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和(子向量的长度至少是1)
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int sum=0;
int max=Integer.MIN_VALUE;
for(int i=0;i< array.length;i++)
{
sum+=array[i];
max=Math.max(max,sum);
sum=sum<0?0:sum;
}
return max;
}
}题目32 整数中1的出现的次数 二刷
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
public class Solution {
public int NumberOf1Between1AndN_Solution(int num)
{
if(num<1)
{
return 0;
}
int len=getNumLen(num);
if(len==1)
{
return 1;
}
int tmp=powerNum(len);//如果是5位数，那么10000
int first=num/tmp;
int firstOne=first==1?num%tmp+1:tmp;
int afterOne=first*(len-1)*(tmp/10);
return firstOne+afterOne+NumberOf1Between1AndN_Solution(num%tmp);
}
public static int powerNum(int len)
{
return (int)Math.pow(10,len-1);
}
public static int getNumLen(int num)
{
int len=0;
while(num!=0)
{
num/=10;
len++;
}
return len;
}
}题目33 把数组拍成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
import java.util.ArrayList;
public class Solution {
public String PrintMinNumber(int [] arr) {
sort(arr);
String str="";
for(int i=0;i<arr.length;i++)
{
str+=arr[i];
}
return str;
}
public static void swap(int[] arr,int m,int n)
{
int tmp=arr[m];
arr[m]=arr[n];
arr[n]=tmp;
}
public static void sort(int[] arr)
{
for(int i=arr.length-1;i>-1;i--)
{
for(int j=0;j<i;j++)
{
String str1=""+arr[j]+arr[j+1];
String str2=""+arr[j+1]+arr[j];
if(Long.parseLong(str1)>Long.parseLong(str2))
{
swap(arr,j,j+1);
}
}
}
}
}题目34 丑数 二刷
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index<7) return index;
int p2=0,p3=0,p5=0;
int[] arr=new int[index];
arr[0]=1;
for(int i=1;i<index;i++)
{
arr[i]=Math.min(arr[p2]*2,Math.min(arr[p3]*3,arr[p5]*5));
if(arr[i]==arr[p2]*2) p2++;
if(arr[i]==arr[p3]*3) p3++;
if(arr[i]==arr[p5]*5) p5++;
}
return arr[index-1];
}
}题目35 第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
public class Solution {
public int FirstNotRepeatingChar(String str) {
if(str==null||str.equals("")) return -1;
int[] map=new int[58];
for(int i=0;i<map.length;i++)
{
map[i]=-1;
}
char[] chas = str.toCharArray();
for(int i=0;i<chas.length;i++)
{
if(map[chas[i]-'A']==-1)
map[chas[i]-'A']=i;
else map[chas[i]-'A']=-2;
}
int i=0;
for(i=0;i<chas.length;i++)
{
if(map[chas[i]-'A']>=0)
{
break;
}
}
return map[chas[i]-'A'];
}
}题目36 数组中的逆序对 二刷
public class Solution {
public int InversePairs(int [] arr) {
int[] count=new int[1];
mergeSort(arr,0,arr.length-1,count);
return count[0];
}
public static void mergeSort(int[] arr,int l,int r,int[] count)
{
if(l==r) return ;
int mid = (l+r)/2;
mergeSort(arr,l,mid,count);
mergeSort(arr,mid+1,r,count);
merge(arr,l,r,mid,count);
}
public static void merge(int[] arr,int l,int r,int mid,int[] count)
{
int p1=l;
int p2=mid+1;
int i=0;
int[] help=new int[r-l+1];
while(p1<=mid&&p2<=r)
{
if(arr[p1]<arr[p2])
{
help[i++]=arr[p1++];
}else
{
System.out.println(arr[p1]+" "+arr[p2]);
help[i++]=arr[p2++];
count[0]=(count[0]+(mid-p1+1))%1000000007;
}
}
while(p1<=mid)
{
help[i++]=arr[p1++];
}
while(p2<=r)
{
help[i++]=arr[p2++];
}
for(int k=0;k<help.length;k++)
{
arr[l+k]=help[k];
}
}
}总结：使用归并排序，同时需要进行排序，其中的核心代码就是
count[0]=(count[0]+(mid-p1+1))%1000000007;
题目37 两个链表的第一个公共结点
public static ListNode noLoop(ListNode head1,ListNode head2)
{
if(head1==null||head2==null)
{
return null;
}
ListNode cur1=head1;
ListNode cur2=head2;
int n=0;
while(cur1.next!=null)
{
cur1=cur1.next;
n++;
}
while(cur2.next!=null)
{
cur2=cur2.next;
n--;
}
if(cur1!=cur2)
{
return null;
}
cur1=n>0?head1:head2;
cur2=cur1==head1?head2:head1;
n=Math.abs(n);
while(n!=0)
{
cur1=cur1.next;
n--;
}
while(cur1!=cur2)
{
cur1=cur1.next;
cur2=cur2.next;
}
return cur1;
}题目38 数字在排序数组中的次数
public class Solution {
public int GetNumberOfK(int [] arr , int k) {
int left=find1(arr,k);
int right=find2(arr,k);
if(left==-1&&right==-1) return 0;
return right-left;
}
public static int find1(int[] arr,int target)
{
int left=0;
int right=arr.length-1;
while(left<=right)
{
int mid=(left+right)/2;
if(arr[mid]>=target)
{
right=mid-1;
}else
{
left=mid+1;
}
}
return right;
}
public static int find2(int[] arr,int target)
{
int left=0;
int right=arr.length-1;
while(left<=right)
{
int mid=(left+right)/2;
if(arr[mid]<=target)
{
left=mid+1;
}else
{
right=mid-1;
}
}
return right;
}
}题目39 二叉树的深度
public class Solution {
public int TreeDepth(TreeNode head) {
if(head==null) return 0;
int left=TreeDepth(head.left);
int right=TreeDepth(head.right);
return left<right?(right+1):left+1;
}
}总结：后序遍历的改写
题目40 平衡二叉树 二刷
public class Solution {
public boolean IsBalanced_Solution(TreeNode head) {
boolean[] res=new boolean[1];
res[0]=true;
getTreeDeepth2(head,0,res);
return res[0];
}
public static int getTreeDeepth(TreeNode head,int deepth,boolean[] res)
{
if(head==null) return deepth;
int left=getTreeDeepth(head.left,deepth+1,res);
if(!res[0])
{
return deepth;
}
int right=getTreeDeepth(head.right,deepth+1,res);
if(!res[0])
{
return deepth;
}
if(Math.abs(left-right)>1)
{
res[0]=false;
}
return Math.max(left,right);
}
}总结：boolean数组的使用和deepth
题目41 数组中只出现一次的数字 二刷
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] arr,int num1[] , int num2[]) {
int res=0;
for(int i=0;i<arr.length;i++)
{
res^=arr[i];
}
res=res&(~res+1);
int count=0;
for(int i=0;i<arr.length;i++)
{
if((res&arr[i])!=0)
{
count++;
}
}
int[] temp1=new int[count];
int[] temp2=new int[arr.length-count];
count=0;
int count2=0;
for(int i=0;i<arr.length;i++)
{
if((res&arr[i])!=0)
{
temp1[count++]=arr[i];
}else
{
temp2[count2++]=arr[i];
}
}
num1[0] = f(temp1, 2);
num2[0] = f(temp2, 2);
}
public static int f(int[] arr,int k)
{
int[] res=new int[32];
for(int i=0;i<arr.length;i++)
{
add(res,arr[i],k);
}
int m = getNumFromKNum(res, k);
return m;
}
public static void add(int[] res,int value,int k)
{
int[] r = getKNumFromNum(value, k);
for(int i=0;i<res.length;i++)
{
res[i]=(res[i]+r[i])%k;
}
}
/*
k进制的数字转化成十进制
*/
public static int getNumFromKNum(int[] arr,int k)
{
int res=0;
int tmp=1;
for(int i=0;i<arr.length;i++)
{
res+=arr[i]*tmp;
tmp=tmp*k;
}
return res;
}
/*
十进制的转化为k进制
*/
public static int[] getKNumFromNum(int value,int k)
{
int[] res=new int[32];
int index=0;
while(value!=0)
{
res[index++]=value%k;
value=value/k;
}
return res;
}
}题目42 和为S的连续正数序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int k) {
ArrayList<ArrayList<Integer>> allList=new ArrayList<>();
int small=1;
int big=2;
int sum=3;
ArrayList<Integer> list=new ArrayList<>();
list.add(1);
list.add(2);
if(sum==k)
{
allList.add(list);
return allList;
}
while((small+big)<=k)//注意循环条件
{
sum=(small+big)*(big-small+1)/2;
if(sum<k)
{
list.add(++big);
}
else if(sum>k)
{
list.remove(0);
small++;
}
else if(sum==k)
{
for(Integer e:list)
{
System.out.print(e+" ");
}
allList.add(new ArrayList<>(list));
list.remove(0);
small++;
}
}
return allList;
}
}题目43 和为S的两个数字
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
int left=0;
int right=array.length-1;
int temp=Integer.MAX_VALUE;
int[] res=new int[2];
int cur=0;
ArrayList<Integer> list=new ArrayList<>();
while(left<right)
{
cur=array[left]+array[right];
if(cur>sum)//大于
{
right--;
}
else if(cur<sum)//小于
{
left++;
}
else //相等
{
if(array[left]*array[right]<temp)
{
temp=array[left]*array[right];
res[0]=array[left];
res[1]=array[right];
}
right--;
left++;
}
}
if(res[0]!=0&&res[0]!=0)
{
list.add(res[0]);
list.add(res[1]);
}
return list;
}
}题目44 左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
public class Solution {
public String LeftRotateString(String str,int n)
{
if(str==null||str.equals("")) return "";
else if(n==0) return str;
else if(n>=str.length()) return str;
char[] chas = str.toCharArray();
int start=0;
int end=chas.length-1;
int lpart=n;
int rpart=chas.length-n;
int minPart=Math.min(lpart,rpart);
int c=lpart-rpart;
while(true)
{
exchange(chas,start,end,minPart);
//交换
if(c==0)
{
break;
}
else if(c>0)
{
start+=minPart;
lpart=c;
}else
{
end-=minPart;
rpart=-c;
}
minPart=Math.min(lpart,rpart);
c=lpart-rpart;
}
return String.valueOf(chas);
}
public static void exchange(char[] chas,int l,int r,int size)
{
char tmp=0;
int i=r-size+1;
while(size--!=0)
{
tmp=chas[l];
chas[l]=chas[i];
chas[i]=tmp;
l++;
i++;
}
}
}
美的集团公司福利 724人发布