牛客剑指offer(20~40题总结)

JZ23

解决方法：

二叉搜索树遍历顺序为左右根；而且左子树的所有值都小于根，根的值小于右子树的所有值。

根据大小关系找出划分点后还需要对右子树的所有值进行比较遍历，在满足二叉搜索树的大小规定后才能再次划分为左子树和右子树进行比较。

class BSTPreOrder {
    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return isBST(sequence, 0, sequence.length - 1);
    }
 
    private boolean isBST(int[] seq, int start, int end) {
        if (start >= end) {
            return true;
        }
        int val = seq[end];
        int split = start;
        for (; split < end && seq[split] < val; split++) ;
        for (int i = split; i < end; i++) {
            if (seq[i] < val) {
                return false;
            }
        }
        return isBST(seq, start, split - 1) &&
               isBST(seq, split, end - 1);
    }
}

题目总结：

抓住题目的重点，后序遍历+二叉排序树。后序遍历则说明能够立刻确定二叉树的根结点，然后结合二叉排序树的特点，左子树的值一定小于根的值，根的值一定小于右子树的值，满足如上条件即为合法。

JZ26

解决方法：

设置一个前驱指针，然后每次当前驱指针的值不空时和后继指针进行连接，然后再变换前驱指针的位置。

知识回顾：线索二叉树

public class Test {
   
   //节点存储结构
   static class Node{   
	   String data;          //数据域
	   Node left;            //左指针
	   Node right;           //右指针
	   boolean isLeftThread = false;    //左指针域类型  false：指向子节点、true：前驱或后继线索
	   boolean isRightThread = false;   //右指针域类型  false：指向子节点、true：前驱或后继线索
	   Node(String data){
		   this.data = data;
	   }
   }
   
   /**
    * 通过数组构造一棵完全二叉树
    */
   static Node createBinaryTree(String[] array,int index) {
	   Node node = null;
	   if(index < array.length) {
		   node = new Node(array[index]);
		   node.left = createBinaryTree(array, index*2+1);
		   node.right = createBinaryTree(array, index*2+2);
	   }
	   return node;
   }
   
   private Node preNode = null;
   
   /**
    * 中序线索化二叉树
    */
   void inThreadOrder(Node node) {
	   if(node == null)
		   return;
	   //处理左子树
	   inThreadOrder(node.left);
	   
	   //处理根节点
	   if(node.left == null) {
		   node.left = preNode;
		   node.isLeftThread = true;
	   }
	   if(preNode!=null && preNode.right==null) {
		   preNode.right = node;
		   preNode.isRightThread = true;
	   }
	   preNode = node;
	   
	   //处理右子树
	   inThreadOrder(node.right);
   }
   
  
   /**
    * 中序遍历线索化二叉树，按照后继方式(找到最左节点开始)
    */
   void inThreadList(Node node) {
	   //找到最左节点
	   while(node!=null && !node.isLeftThread)
		   node = node.left;
	   
	   while(node != null) {
		   //遍历根节点
		   System.out.println(node.data);
		   
		   //如果右指针是线索，直接切换
		   if(node.isRightThread)
			   node = node.right;
		   
		   //如果右指针不是线索，则找到右子树对应左子树的线索
		   else {
			   node = node.right;
			   while(node!=null && !node.isLeftThread)
				   node = node.left;
		   }
	   }
   }
   
  
   /**
    * 中序遍历二叉树，按照前驱方式(找到最右节点开始)
    */
   void preThreadList(Node node) {
	   //找到最右节点
	   while(node!=null && !node.isRightThread)
		   node = node.right;
	   
	   while(node != null) {
		   //遍历根节点
		   System.out.println(node.data);
		   
		   //如果左指针是线索
		   if(node.isLeftThread)
			   node = node.left;
		   
		   else {
			   node = node.left;
			   while(node.right!=null && !node.isRightThread)
				   node = node.right;
		   }
	   }
   }
   
  
   /**
    * 前序线索化二叉树
    */
   void preThreadOrder(Node node) {
	   if(node == null)
		   return;
 
	   //处理当前根节点
	   if(node.left == null) {
		   node.left = preNode;
		   node.isLeftThread = true;
	   }
	   if(preNode.right==null && !preNode.isRightThread) {
		   preNode.right = node;
		   preNode.isRightThread = true;
	   }
	   preNode = node;
	   
	   //处理左子树
	   if(!node.isLeftThread)
		   preThreadOrder(node.left);
	   //处理右子树
	   if(!node.isRightThread)
		   preThreadOrder(node.right);
   }
}

而在本题中需要我们构建的是一个双向链表，那就相当于只要 preNode 前驱节点不空，都要将它与后继进行双向连接。

public class Solution {
    TreeNode preNode = null,root = null;
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            return null;
        Convert(pRootOfTree.left);
        if(root == null)
            root = pRootOfTree;
        
        if(preNode!=null)
            preNode.right = pRootOfTree;
        pRootOfTree.left =  preNode;
        preNode = pRootOfTree;
        
        Convert(pRootOfTree.right);
        return root;
    }
}

题目总结：

线索化二叉树一般和前序遍历/中序遍历结合使用，通过维护一个 preNode 来代表遍历时的前一个结点

每次移动前都检查当前结点的左子树是否为空，为空就将它的左子树连接到 preNode；相反的我们也需要将 preNode 的右子树连接到当前结点。

线索化二叉树比较重要，多做多思考。

JZ31

解决方法：

题目要求求出小于等于n的所有整数中出现 1 的次数，那么进行举例分析。

假设数字 N 是个x位数，记 N 的第i位为 Ni，那么可以将 N 写为 NxNx-1Nx-2….N1

这里称 “Ni” 为当前位，记为 cur；
将 “Ni-1 Ni-2 Ni-3…N1” 记为低位，记为 low；
将 “Nx Nx-1 Nx-2… Ni” 记为高位，记为 high:
将 “10^i” 记为位因子，记为 digit；

这里举例计算数字 2304中十位出现1的次数

① 当 cur=0 时

可以发现此时出现1的次数只与高位有关系，个数为 high×digit

② 当cur=1时

可以发现此时1的出现与高位和低位都有关系，个数为 high×digit+low+1

③当cur=2,3....9时

此时1的出现只与高位有关系，个数为 (high+1)×digit

因此可以总结归纳为：

//初始值
high = n/10;
cur = n%10;
low = 0;
digit = 1;

从低位到高位的递推过程：

while high!=0 or cur!=0      //这里high和cur不能同时为0，同时为0表示已经结束递推
    low += cur*digit;        //加上cur层的值
    cur = high%10;           //下层cur等于high的最低位
    high = high/10;          //下层high等于high除去最低位
    digit *= 10;             //每次位因子增加10倍

时间复杂度： O(logn)，循环内的计算操作使用O(1)时间；循环操作次数是N 的位数，即 log10N；

空间复杂度： O(1)

class Solution {
    public int countDigitOne(int n) {
        int digit = 1, res = 0;
        int high = n / 10, cur = n % 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur == 0) res += high * digit;
            else if(cur == 1) res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
}

参考文章：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/

题目总结：

找规律

JZ25

解决方法：

链表深度拷贝，需要将每个结点重新生成一份而不是简单的复制引用。

那么可以建立 HashMap哈希表来指明原结点和新结点之间的对应关系。第一次遍历用于创建结点，此时结点间的关系和指向还没有定义，第二次遍历就专门进行关系的定义和指向的说明。

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null)
            return null;
        HashMap<RandomListNode,RandomListNode> map = new HashMap();
        RandomListNode h1=pHead,h2=pHead;
        
        while(h1!=null){
            map.put(h1,new RandomListNode(h1.label));
            h1=h1.next;
        }
        
        while(h2!=null){
            if(h2.next != null)
                map.get(h2).next = map.get(h2.next);
            else
                map.get(h2).next = null;
            if(h2.random != null)
                map.get(h2).random = map.get(h2.random);
            h2 = h2.next;
        }
        return map.get(pHead);
    }
}

题目总结：

涉及到深拷贝的问题，如果结点间的关系比较复杂，就可以通过建立 HashTable 来解决。

第一次遍历用于建立结点；第二次遍历用于定义关系。

JZ29

解决方法：

思路很清晰，对数组进行排序即可。但是关键是排序方法的选择。

快速排序不稳定，时间复杂度最坏可能为 O(n^2)，不考虑；

归并排序需要用到辅助空间，而且必须达到最底层后才能回溯处理，不考虑；

堆排序虽然不稳定，但是每一步都能够得出当前的最大/最小值，题目中要求前K 个数，那么不需要对整个数组完全排序，只要取到了前 K个数就退出。因此堆排序最合适。

public class Solution {
    ArrayList<Integer> res = new ArrayList<Integer>();
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(k > input.length)
             return res;
        HeapSort(input,k);
        return res;
    }
    
  // 堆排序对堆的调整
    public void HeapAdjust(int[] arr,int start,int end){
        int tmp = arr[start];
        int i = start*2+1;
        while(i <= end){
            if(i+1<=end && arr[i+1]<arr[i])
                i++;
            if(arr[i]>=tmp)
                break;
            arr[start] = arr[i];
            start = i;
            i = i*2+1;
        }
        arr[start] = tmp;
    }
   
  // 堆排序递归交换堆顶和堆尾并重新调整
    public void HeapSort(int[] arr,int k){
        int len = arr.length;
        for(int i=len/2-1;i>=0;i--)
            HeapAdjust(arr,i,len-1);
        
        for(int i=len-1;i>=0 && k>0;i--){
            res.add(arr[0]);
            k--;
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            HeapAdjust(arr,0,i-1);
        }
    }
}

题目总结：

各种排序算法一定要烂熟于心，快排、归并、堆排序尤其重要。

归并排序在之前的一道题目中出现过，意思是要我们求数组中位于位于前面比它大的数的个数。巧用了归并排序的思想，归并采用分治的思维，在合并的时候是两个有序的数组，而且后面的数组的位置一定是在另一个数组的后面的，那么根据大小关系就能很快求出。

堆排序在这个题目中体现了它的优势，多刷题多总结。

JZ33

解决方法：

题目中定义了丑数的概念，质因子只能是 2、3、5（1除外）。也就是说一个数如果为丑数，那么它就只能通过任意个数的 2、3、5相乘得到。那么我们只需要关注如何将数相乘和如何取值。

如何将数相乘：丑数*丑数=丑数，每一个丑数都有乘以 2、3、5 的机会，将这些值进行去重剩下的就是新的丑数，那么为了保证每个数都有乘以 2、3、5的机会，需要给 2、3、5各自设置一个指针下标（比如 i、j、k）表示此时乘到哪里了。

如何取值：每次加入的丑数都要保证最小，这样才能保证之后的乘法运算不会漏掉值，那么每次三个下标（2、3、5）和当前各自对应的数相乘后取其中的最小值作为当次的结果，并且将当前指针往后移动一位。注意如果当前的结果可以由多个指针对应的数相乘得到，那么各指针都需要往后移动一位。

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        		if(index<=0)
			return 0;
		ArrayList<Integer> list = new ArrayList();
		int p2=0,p3=0,p5=0;
		list.add(1);
		
	    for(int i=0;i<index;i++) {
	    	int cur = Math.min(list.get(p2)*2, Math.min(list.get(p3)*3, list.get(p5)*5));
	    	list.add(cur);
	    	if(cur%2 == 0)
	    		p2++;
	    	if(cur%3 == 0)
	    		p3++;
	    	if(cur%5 == 0)
	    		p5++;
	    }
	    
	    return list.get(index-1);
    }
}

题目总结：

这类数学题型需要仔细分析，分析各个结果的结构规律然后进行求解。

JZ35

解决方法：

逆序对的定义：两个数字，前面一个数字大于后面的数字，那么这两个数字组成一个逆序对。逆序对可以看成相对位置间的大小关系的比较。

这里需要我们联想到归并排序的排序过程，归并排序的思想是分治，分而后治。治的过程就体现了相对位置的排序，因为排序中是两个已经排好序的数组，而且后面一个数组的位置一定是在前一个数组的后面。那么比较的时候，如果前一个数组的某个值大于后面数组当前位置的值，这就是一个逆序对，另外前一个数组是有序递增的，也就是说前一个数组对应位置的后序所有值都比后面数组的当前位置的值要大，这就是很多的逆序对。

public class Solution {
	int count = 0;
    public int InversePairs(int [] array) {
        mergeSort(array,0,array.length-1);
        return count;
    }
    
     void merge(int []array,int start,int mid,int end) {
    	int []temp = new int[end-start+1];
    	int i=start,j=mid+1,index=0;
    	
    	while(i<=mid && j<=end) {
    		if(array[i]<=array[j])
    			temp[index++] = array[i++];
    		else {
    			count += (mid-i+1);
                count = count%1000000007;
    			temp[index++] = array[j++];
    		}
    	}
    	while(i<=mid) temp[index++] = array[i++];
    	while(j<=end) temp[index++] = array[j++];
        for(index=0;index<temp.length;index++)
        	array[start++] = temp[index];
    }
    
    void mergeSort(int []array,int start,int end) {
    	if(start == end)
    		return;
		int mid = ((end-start)>>1)+start;
	    mergeSort(array,start,mid);
	    mergeSort(array,mid+1,end);
	    merge(array,start,mid,end);
    }
}

题目总结：

归并排序的核心用到了分治，分治又是基于保持相对位置的分治；

堆排序的排序规则则可以用到部分排序中，比如说取一个数组中的前N个最小数等等。

JZ37

解决方法：

题目关键词升序数组。一看见有序就立刻联想到二分法。

二分查找，找到比当前数小一点的值的位置；二分查找，找到比当前数大一点的值；结束

二分查找如果没有找到完全匹配，那么会返回比当前值稍大一点的值的位置

public class Solution {
	public int GetNumberOfK(int []array,int k) {
		return getIndex(array,k+0.5)-getIndex(array,k-0.5);
	}
	
	public int getIndex(int []array,double num) {
		int s = 0,e = array.length-1,mid;
		while(s <= e) {
			mid = (((e-s)>>1)+s);
			if(array[mid] > num)
				e = mid-1;
			else if(array[mid] < num)
				s = mid+1;
			else
				return mid;
		}
		return s;
	}
}

题目总结：

有序数组—–二分法

JZ39

解决方法：

既然规定了平衡二叉树的任意结点的左右子树的高度差不能超过1，那么求出来进行比较就可以了。

要保证当前结点的二叉树是平衡二叉树，需要保证左子树是平衡二叉树、右子树是平衡二叉树、左右子树的深度差不超过1

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null)
            return true;
        boolean flag = Math.abs(getDepth(root.left)-getDepth(root.right))<=1?true:false;
        return flag && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    
    public int getDepth(TreeNode root){
        if(root == null)
            return 0;
        if(root.left==null && root.right==null)
            return 1;
        return Math.max(getDepth(root.left),getDepth(root.right))+1;
    }
}

题目总结：

比较简单，无

JZ40

解决方法：

其它数字都出现了两次，另外两个数字分别出现了1次。

重复出现去重问题，肯定会联想到哈希表，但是用了就GG了。

这里介绍另外一种重复去重的方法（异或法，适用于数组全体或大部分重复的情况）。因为异或运算相同为0，不同为1.

重点！（敲黑板）

要找出两个数字，需要将数组分组，如果能够保证 ①两个数字分到了不同的组；②相同的数字分到了同一个组；就完成了目的。

如何分组呢？这两个数字不同，那么它们的二进制表示法中肯定存在某一位是不同的，如果我们找到这一位，这两个数字按照这一位进行分离。对于其它数字而言，由于存在和它们相同的另外一个数，那么就一定能够分配到同一个数组中。

最后分别对两个数组进行异或运算求解，由于相同的数字都分配到了同一个组，那么异或后一定为0，因此最后同一组的数据异或的结果一定只剩下单独出现的那个数了。

public int[] FindNumsAppearOnce (int[] array) {
    int res=0,index=1;
    for(int i=0;i<array.length;i++)
        res ^= array[i];
    while((res&index)==0)
        index <<= 1;
    int a=0,b=0;
    for(int num:array){
        if((num&index)==0)
            a ^= num;
        else
            b ^= num;
    }
    if(a>b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
    return new int[]{a,b};
}