剑指Offer刷题（三）及思路

朴灿烈づ我的快乐病毒、 2023-07-11 06:16 45阅读 0赞

## 数组中出现次数超过一半的数字 ##

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

import java.util.*;
    public class Solution { 
        public int MoreThanHalfNum_Solution(int [] array) { 
            
            int length = array.length;
            if(length<1)return 0;
            if(length == 1) return array[0];
            int times = 0;
    
            Arrays.sort(array);
            int num = array[length/2-1];
            for(int i = 0 ;i<length;i++)
            { 
                if(array[i]==num)times++;
            }
            if(times>length/2)return num;
            return 0;
            
        }
    }

出现次数超过一半，排序后肯定在中间位置，取出中间位置元素，看看到底是不是出现次数超过一半

## 最小的K个数 ##

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

import java.util.*;
    public class Solution { 
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { 
            
            ArrayList<Integer> list = new ArrayList<Integer>();
            if(k>input.length)return list;
            if(k==0)return list;
            merge(input,0,input.length-1);
            for(int i=0;i<k;i++)
            { 
                list.add(input[i]);
            }
            return list;
        }
        
        public static void quicksort(int[] arr ,int begin, int end)
        { 
            int i = begin; int j =end ; int key = arr[begin];
            while(i<j)
            { 
                while(i<j&&arr[j]>=key)j--;
                if(arr[j]<key)
                { int tmp = arr[j]; arr[j] =arr[i]; arr[i]=tmp;}
                while(i<j&&arr[i]<=key)i++;
                if(arr[i]>key)
                { int tmp = arr[j]; arr[j] =arr[i]; arr[i]=tmp;}
            }
            if(begin<i)
            quicksort(arr,begin,i-1);
            if(end>j)
            quicksort(arr,j+1,end);
        }
        
        public static void merge(int[] arr,int low, int high)
        { 
            if(low<high)
            { 
            int mid = (low+high)/2;
            merge(arr,low,mid);
            merge(arr,mid+1,high);
            mergesort(arr,low,high,mid);
            }
    
        }
        public static void mergesort(int[] arr, int low ,int high,int mid)
        { 
            int i=low ;int j=mid+1;
            int[] tmp = new int[arr.length];
            int k = 0;
            while(i<=mid&&j<=high)
            { 
                if(arr[i]<arr[j]) tmp[k++]=arr[i++];
                else
                { 
                    tmp[k++]=arr[j++];
                }
            }
            while(i<=mid)
            { 
                tmp[k++]=arr[i++];
            }
            while(j<=high)
            { 
                tmp[k++]=arr[j++];
            }
            for(int x = 0 ;x<k;x++)
            { 
                arr[low+x]=tmp[x];
            }
            
        }
    }

排序，遍历即可，写了两个排序，一个快排一个归并

## 连续子数组的最大和 ##

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:\{6,-3,-2,7,-15,1,2,2\},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

import java.util.*;
    public class Solution { 
        public int FindGreatestSumOfSubArray(int[] array) { 
            if(array.length==0) return 0;
            if(array.length==1) return array[0];
            int i = 1;
            int max = array[0];
            int res = array[0];
            while(i<array.length)
            { 
                //求以位置i上数字为结尾的子数组最大是多少
                max=Math.max(max+array[i],array[i]);
                //求所有子数组目前的最大和为多少
                res=Math.max(res,max);
                i++;
            }
            
            return res;
        }
    }

动态规划，每次求以位置i结尾的子数组最大和是多少，然后保存最大的那个

## 整数中1出现的次数（从1到n整数中1出现的次数） ##

求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

public class Solution { 
        public int NumberOf1Between1AndN_Solution(int n) { 
            int count = 0;
            while(n>0)
            { 
              String str = String.valueOf(n);  
                for(int i=0;i<str.length();i++)
                { 
                    if(str.charAt(i)=='1')
                        count++;
                }
                n--;
            }
            return count;
            
        }
    }

这个解法不太行，暂时先写着

## 把数组排成最小的数 ##

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，则打印出这三个数字能排成的最小数字为321323。

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    public class Solution { 
        public String PrintMinNumber(int [] numbers) { 
            ArrayList<Integer> list = new ArrayList<Integer>();
            String s ="";
            for(int i =0 ;i<numbers.length;i++)
            { 
                list.add(numbers[i]);
            }
            Collections.sort(list,new Comparator<Integer>(){ 
                 @Override
                public int compare(Integer str1, Integer str2) { 
                    // TODO Auto-generated method stub 
                        String s1=str1+""+str2;
                        String s2=str2+""+str1;
                         
                        return s1.compareTo(s2);
                    }
                
            });
            for(int x:list)
            { 
                s+=x;
            }
            return s;
        }
    }

重写集合的compare方法

## 丑数 ##

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

/* * 丑数都是由2、3、5相乘得来的 * 可以发现丑数的一个排序为 * 2 3 4 5 6 8 .... */
    import java.util.*;
    public class Solution { 
        public int GetUglyNumber_Solution(int index)     { 
            if(index<=0)return 0;
            ArrayList<Integer> list=new ArrayList<Integer>();
            list.add(1);
            int i2=0,i3=0,i5=0;
            while(list.size()<index)//循环的条件
            { 
                int m2=list.get(i2)*2;
                int m3=list.get(i3)*3;
                int m5=list.get(i5)*5;
                int min=Math.min(m2,Math.min(m3,m5));
                list.add(min);
                if(min==m2)i2++;
                if(min==m3)i3++;
                if(min==m5)i5++;
                
            }
            return list.get(list.size()-1);
        }
    }

刚开始list列表里只有1，然后三个下标 i2 i3 i5都是0，即都指向1  
第一次循环，m2=2,m3=3,m5=5，最小的是m2，把m2=2加入list，并更新i2下标  
第二次循环，m2=4,m3=3,m5=5，最小的是m3，把m3=3加入list，并更新i3下标  
第三次循环，m2=4,m3=6,m5=5，最小的是m5，把m5=5加入list，并更新i5下标  
。。。。。

## 第一个只出现一次的字符 ##

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

import java.util.*;
    public class Solution { 
        public int FirstNotRepeatingChar(String str) { 
            HashMap<Character,Integer> map = new  HashMap<Character,Integer>();
            for(int i = 0;i<str.length();i++)
            { 
                if(map.get(str.charAt(i))==null)
                { 
                    map.put(str.charAt(i),1);
                }
                else{ 
                    map.put(str.charAt(i),map.get(str.charAt(i))+1);
                }
            }
                    
             for(int i=0;i<str.length();i++)
                            { 
                                if(map.get(str.charAt(i))==1){ 
                                    return i;
                                }
                            }
            return -1;
        }
    }

用HashMap保存每个字符和出现的次数

## 数组中的逆序对 ##

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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 { 
        //统计逆序对的个数
        int cnt;
        public int InversePairs(int [] array) { 
            if(array.length != 0){ 
                divide(array,0,array.length-1);
            }
            return cnt;
        }
     
        //归并排序的分治---分
        private void divide(int[] arr,int start,int end){ 
            //递归的终止条件
            if(start >= end)
                return;
            //计算中间值，注意溢出
            int mid = (start + end )/2;
     
            //递归分
            divide(arr,start,mid);
            divide(arr,mid+1,end);
     
            //治
            merge(arr,start,mid,end);
        }
     
        private void merge(int[] arr,int start,int mid,int end){ 
            int[] temp = new int[end-start+1];
     
            //存一下变量
            int i=start,j=mid+1,k=0;
            //下面就开始两两进行比较，若前面的数大于后面的数，就构成逆序对
            while(i<=mid && j<=end){ 
                //若前面小于后面，直接存进去，并且移动前面数所在的数组的指针即可
                if(arr[i] <= arr[j]){ 
                    temp[k++] = arr[i++];
                }else{ 
                    temp[k++] = arr[j++];
                    //a[i]>a[j]了，那么这一次，从a[i]开始到a[mid]必定都是大于这个a[j]的，因为此时分治的两边已经是各自有序了
                    cnt = (cnt+mid-i+1)%1000000007;
                }
            }
            //各自还有剩余的没比完，直接赋值即可
            while(i<=mid)
                temp[k++] = arr[i++];
            while(j<=end)
                temp[k++] = arr[j++];
            //覆盖原数组
            for (k = 0; k < temp.length; k++)
                arr[start + k] = temp[k];
        }
    }

除了暴力求解，可以用分治思想，归并排序时，每有一次逆序，就cnt+1  
要注意`%1000000007`这个操作在每次分治的时候都求一次

## 两个链表的第一个公共结点 ##

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    import java.util.*;
    public class Solution { 
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { 
                 
            if(pHead1==null||pHead2==null)return null;
            Stack<ListNode> stack1 = new Stack<ListNode>();
            Stack<ListNode> stack2 = new Stack<ListNode>();
            ListNode tmpNode1 = pHead1;
            ListNode tmpNode2 = pHead2;
            while(tmpNode1!=null)
            { 
                stack1.push(tmpNode1);
                tmpNode1=tmpNode1.next;
            }
            while(tmpNode2!=null)
            { 
                stack2.push(tmpNode2);
                tmpNode2=tmpNode2.next;
            }
            
            ListNode resNode = null;
            while(!stack1.isEmpty()&&!stack2.isEmpty()&&stack1.peek().val==stack2.pop().val)
            { 
                resNode = stack1.pop();
            }
            
            return resNode;
        }
    }

用两个栈分别保存两个链表，全部结点按顺序如栈  
然后同时对两个栈进行出栈操作，判断弹出的两个结点是否相同，如果两个结点不相同，那么前一个弹出的就是第一个公共结点

## 数字在排序数组中出现的次数 ##

统计一个数字在排序数组中出现的次数。

public class Solution { 
        public int GetNumberOfK(int [] array , int k) { 
           int times =0;
            for(int i = 0;i<array.length;i++)
            { 
                if(array[i]==k)times++;
            }
            return times;
        }
    }

## 二叉树的深度 ##

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    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;
           
            
        }
    
    }

递归求。。。

## 平衡二叉树 ##

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

import java.util.*;
    public class Solution { 
        public boolean IsBalanced_Solution(TreeNode root) { 
            
            if(root == null)return true;
            if(Math.abs(maxDepth(root.left)-maxDepth(root.right))>1)
            { 
                return false;
            }
            return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
            
        }
        
        public int maxDepth(TreeNode root)
        { 
            if(root==null) return 0;
            return 1+ Math.max(maxDepth(root.left),maxDepth(root.right)) ;
        }
    }

平衡二叉树：所有结点的左右子树高度差不超过1

## 数组中只出现一次的数字 ##

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

//num1,num2分别为长度为1的数组。传出参数
    //将num1[0],num2[0]设置为返回结果
    public class Solution { 
        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { 
    
            int index =1;
            for(int i = 0;i<array.length;i++)
            { 
                        boolean repeat = false;
                for(int j= 0;j<array.length;j++)
                { 
                    if(j==i)continue;
                    else
                    { 
                        if(array[j]==array[i])
                        { 
                            repeat=true;
                            break;
                        }
                    }
                }
                if(!repeat)
                { 
                    if(index==1)
                    { 
                    num1[0]=array[i];
                    index++;
                    }
                    else{ 
                        num2[0]=array[i];
                    }
    
                }
            }
        }
    }

复杂度比较高的做法，还有一种是通过异或去做，利用  
`两个相同的数异或结果为0，一个数跟0异或是这个数本身`这个性质