剑指offer(31-40题)题解

bigsai

发布于 2020-02-19 12:02:23

3440

发布于 2020-02-19 12:02:23

文章被收录于专栏：bigsai

如果有问题，可以加我交流哈！欢迎点个在看收藏

题目描述

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

思路：最笨的方法(可过)。使用字符串，将从1道n的字符串拼凑成新的字符串，然后遍历查找1就可以了。至于数学方法的话当初想了一会感觉考虑点挺多，后面还会再想想。

实现代码：

public class Solution {
        public  int NumberOf1Between1AndN_Solution(int n) {
          StringBuilder str=new StringBuilder();
         for(int i=1;i<=n;i++)
         {
             str.append(i);
         }
         int va=0;
         for(int i=0;i<str.length();i++)
         {
             if(str.charAt(i)=='1')va++;
         }
         return va;
        }
}

参考讨论区： 用数学方法效率更高，不过这个规律还是得经验，，，我还是有点菜当时想了一段时间总是bug。。

在这里插入图片描述

32 把数组排成最小的数

题目描述

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

思路： 贪心算法，主要是一种贪心思想。其实也是个变形排序，其实你不用考虑具体的贪心思想是什么，你要保证整个序列排成的数字最小。那么你就要保证任意两个数字排序的相对数字最小哦。，本质是需要我们考虑最小前缀和组合的问题，但是对于任意两个数，在比较接口中你直接拼凑比较就可以了。但是如果有更好方法后面会学习。

实现代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        Integer[] nums=new Integer[numbers.length];//赋值
        for(int i=0;i<numbers.length;i++)
        {
            nums[i]=numbers[i];
        }
         Arrays.sort(nums, cmp);
         StringBuilder str=new StringBuilder();
         for(int i=0;i<nums.length;i++)
         {
             str.append(nums[i]);
         }
         return str.toString();
        }
     static Comparator<Integer>cmp=new Comparator<Integer>() {

        public int compare(Integer o1, Integer o2) {
            //51 3551
            //921 3
            //51 515
            String a1=o1+"";
            String a2=o2+"";
            return Integer.parseInt(a1+a2)-Integer.parseInt(a2+a1);
        }
    };
}

33 丑数★

题目描述

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

思路：这题自己的方法只过了87%的样例。当数据大的时候就凉了。这题想了一段时间最终忍不住看了题解发现真的太鸡儿秒了！

先说说我自己的想法，怎么想的，他首先没说数据范围是啥，所以我一直以为这个会是一个慢慢试探的过程。

刚开始尝试的肯定是暴力。他说第N个，那我我就一个个试。每个数除以2、3、5直到无法除看看找到第n个。这种最暴力也最好想。我尝试了但是失败了。
我知道任何数都能实现质因数分解。也就是这个丑数要满足(2^a*3^b*5^c)。我抱着侥幸尝试用三层循环(剪枝优化一下次数)，将(2^a*3^b*5^c)的所有可能性全部添加到集合中然后排个序取出。但是结果依然爆炸。
根据第二种的进行优化。我是这样想的，这个序列我们是不是可以用一个优先队列来维护它？比如将1放进去，然后抛出的元素放入到hashset中去重。每次抛出的数值m将m * 2，m * 3, m * 5放入优先队列，然后再抛最小的出来加入set。直到set中元素满了为止。但是面对巨大的数字依然失败了。因为占据大空间，思想没错，但是巨大重复！！

整个过程数组这个结构都被我忽略了！！！！实在hold不出来，忍不住去参考了下讨论区发现这个方法真的是太好了。其实思想还是跟我上面的很相似，只是结构用了最优结构——数组！

简单来说就是用了三个光标，a2,a3,a5.每次比较三个位置分别*2,*3,*5谁最小，然后对应光标往右移动一位。！到结束即可！

看个图就理解了：

实现代码为：

import java.util.*;
public class Solution {
public static int GetUglyNumber_Solution(int index) {
        int a2=0,a3=0,a5=0;
        if(index<7)return index;//小于7都是
        List<Integer>list=new ArrayList<Integer>();
        list.add(1);
        for(int i=1;i<index;i++)
        {
            int min=Math.min(list.get(a2)*2, Math.min(list.get(a3)*3, list.get(a5)*5));
            list.add(min);
            if(min==list.get(a2)*2)a2++;
            if(min==list.get(a3)*3)a3++;
            if(min==list.get(a5)*5)a5++;
        }
        return list.get(index-1);
    }   
}

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

题目描述

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

思路：用hashmap储存记录每个字母出现的次数。然后再进行遍历查找第一个出现一次的字母返回位置。

实现代码：

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

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

思路：至于逆序数，一般有三种方法求解，首当其中的就是暴力的O(n^2^)的方法，但是这种方法复杂度过高一看这个数据范围肯定是过不了的。18年夏天遇到过逆序数记录下来，但是写的不够好，从写了一下！

今天刚写的归并排序和逆序数各位一定好好看看，进行了详细分析。

然后可以采用树状数组或者归并排序求解逆序数。当然，笔者这里采用的是归并排序。

实现代码为：

public class Solution {
    static int value=0;
  public static int InversePairs(int [] array) {        
        mergesort(array,0,array.length-1);
        return value;

    }   
    private static 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 static void merge(int[] array, int l, int mid, int r) {

        int lindex=l;int rindex=mid+1;
        int team[]=new int[r-l+1];
        int teamindex=0;
        while (lindex<=mid&&rindex<=r) {
            if(array[lindex]<=array[rindex])
            {
                team[teamindex++]=array[lindex++];
            }
            else {              
                team[teamindex++]=array[rindex++];
                value+=mid-lindex+1;
                value%=1000000007;
            }
        }
        while(lindex<=mid)
          {
              team[teamindex++]=array[lindex++];

          }
        while(rindex<=r)
          {
              team[teamindex++]=array[rindex++];
          } 
        for(int i=0;i<teamindex;i++)
        {
            array[l+i]=team[i];
        }   
    }
}

36 两个链表的第一个公共节点

题目描述

输入两个链表，找出它们的第一个公共结点

思路：这题的吧不要用暴力匹配的O(n^2^)的方法。大家直到链表是一条直的对吧？然后一个链表节点相同也就是后面都相同是吧？ 所以如果有相同节点的话那么一定从那个节点到最后都是相同的。并且肯定在短的后面才可能匹配。

至于实现方式其实还是蛮多的，比如你可以先遍历一次分别把两个长度求出来然后把长的节点往后移到相同长度，然后一个个比较就好。当然这样可能跑2次但是影响确实不大。你也可以借助外部空间然后将遍历一次的存下来。然后从后往前找到第一个不一样的那个后面就是了。 当然笔者采用上面一个方法并没有采用外部空间。

实现代码为：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
   public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
              int lp1=getlen(pHead1);   
              int lp2=getlen(pHead2);
              while (lp1>lp2) {
                pHead1=pHead1.next;lp1--;
            }
              while (lp1<lp2) {
                    pHead2=pHead2.next;lp2--;
                }
              while (pHead1!=pHead2) {
                pHead1=pHead1.next;
                pHead2=pHead2.next;
            }
              return pHead1;
        }
    private int getlen(ListNode pHead1) {
        int len=0;
        ListNode team=pHead1;
        while (team!=null) {
             team=team.next;
             len++;
        }
        return len;
    }
}

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

题目描述

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

思路：数组问题，一般枚举能过但是不够优雅。有序的数组、序列当然可以使用二分法哈！先二分找到其中任意一个数字所在的序号，然后根据这个坐标左右试探就可以直到多少个啦！

实现代码为：

public class Solution {
     public int GetNumberOfK(int [] array , int k) {
           int l=0,r=array.length;
           int mid=(l+r)/2;
           while (l<r) {
            if(array[mid]==k)
            {
                return search(array,mid);
            }
            else if (array[mid]<k) {
                l=mid+1;mid=(l+r)/2;
            }
            else {
                r=mid;mid=(l+r)/2;
            }
        }
           return 0;
        }

    private int search(int[] array, int mid) {
        int l=mid-1,r=mid+1;
        int value=0;
        while (l>=0&&array[l]==array[mid]) {
            value++;l--;
        }
        while (r<array.length&&array[r]==array[mid]) {
            value++;r++;
        }
        return value+1;
    }
}

38 二叉树的深度

题目描述

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

思路：因为二叉树有左右子节点，左右节点的问题。每个孩子都要比自己更深一层，对于这个问题，你可以自己定义一个包含次数的结构体或者类用队列或者栈进行遍历找到最大的。但是这题可以直接使用递归进行求解。父节点和子节点之间的关系就是deep(parent)=max(parent.left,parent.right)+1。当然，这里的left和right节点也要判空之类的处理。

实现代码为：

/**
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;
         return Math.max(TreeDepth(root.left), TreeDepth(root.right))+1;            
        }
}

39 平衡二叉树

题目描述

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

思路：至于平衡二叉树(avl)，之所以平衡，是因为它的任意一个左右节点的高度相差都小于等于1. 如果有不了解的可以参考以前写的一篇avl二叉平衡树。但是这个跟文中写的的其实不太一样，是因为之前我创造二叉树的时候有个height值每次插入的时候动态维护，判断是否平衡。但是显然这题什么都没有，需要自己完成所有。

好吧，来就来，不就是判断每个节点都要满足左右高度都要相差在1之内嘛！上面那题，不就是求高度的嘛？！！我用个队列把所有点存下来，然后一个个判断可还行？虽然可能效率不一定高。但是还是能过的。

实现代码为：

import java.util.ArrayDeque;
import java.util.Queue;
public class Solution {
     public boolean IsBalanced_Solution(TreeNode root) {
         if(root==null)return true;
            Queue<TreeNode>q1=new ArrayDeque<TreeNode>();
            q1.add(root);
            while (!q1.isEmpty()) {
                TreeNode team=q1.poll();
                if(Math.abs(TreeDepth(team.left)-TreeDepth(team.right))<=1)
                {
                    if(team.left!=null)q1.add(team.left);
                    if(team.right!=null)q1.add(team.right);
                }
                else {
                    return false;
                }       
            }
            return true;
        }

     public int TreeDepth(TreeNode root) {
            if(root==null)return 0;
             return Math.max(TreeDepth(root.left), TreeDepth(root.right))+1;        
            }
}

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

题目描述

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

思路：这题只能用普通方法过，但是还是有技巧的。感觉可以用位运算但是奈何自己没想出来。两个相同的数进行异或^运算等于0.而0和任何数异或等于它自己。如果只求1个数那可能好搞一些，但是后面会研究讨论区大佬的位运算方案。

对于普通思路，可能大部分人会用hashmap先添加，最后遍历两个次数等于1个的两个数返回。但是其实可以使用hash进行减。如果存在这个元素，就减去这个元素。如果不存在那就加入hash中，那么最终剩的2个元素其实就是我们出现一次的元素。由于java底层用hashmap维护hashset我就用hashmap了差不了太大。

实现代码为：

import java.util.HashMap;
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
   public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
            HashMap<Integer, Integer>map=new HashMap<Integer, Integer>();
            for(int i=0;i<array.length;i++)
            {
                if(map.containsKey(array[i])) {map.remove(array[i]);}
                else {
                    map.put(array[i],1);
                }
            }
            int count=0;
            for(Integer va:map.keySet())
            {
                if(count++==0)num1[0]=va;
                else {
                    num2[0]=va;
                }
            }
        }
}

参考讨论区： 这题的讨论区很妙，用^来解决问题。至于讨论区的题解稍微解释一下：大概就是将数组一分为2份！就是说先异或到最后得到一个数，肯定是a^b的值。这个数位位1的那个肯定就是两个位不同的。比如10100.第三位就是a和b不同的，然后我们就再次遍历所有数，用两个数进行异或，如果第三位为1xx那么和a1异或，如果为0xx那么和a2异或。就相当于把这个数逻辑一分为2.因为所有数除了这两都出现两次，所以是可以消下去的！

实现代码为：

链接：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811?f=discussion
来源：牛客网

public class Solution {
    public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2)    {
        int length = array.length;
        if(length == 2){
            num1[0] = array[0];
            num2[0] = array[1];
            return;
        }
        int bitResult = 0;
        for(int i = 0; i < length; ++i){
            bitResult ^= array[i];
        }
        int index = findFirst1(bitResult);
        for(int i = 0; i < length; ++i){
            if(isBit1(array[i], index)){
                num1[0] ^= array[i];
            }else{
                num2[0] ^= array[i];
            }
        }
    }

    private int findFirst1(int bitResult){
        int index = 0;
        while(((bitResult & 1) == 0) && index < 32){
            bitResult >>= 1;
            index++;
        }
        return index;
    }

    private boolean isBit1(int target, int index){
        return ((target >> index) & 1) == 1;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-02-03，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自 bigsai 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度