剑指offer之26-30题解

怼烎@ 2021-12-17 13:21 244阅读 0赞

# 剑指offer之26-30题解 #

--------------------

## 目录 ##

1.  二叉搜索树与双向链表
2.  字符串的排列
3.  数组中出现次数超过一半的数字
4.  最小的K个数
5.  连续子数组的最大和

--------------------

### 26. 二叉搜索树与双向链表 ###

（一）题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。  
![在这里插入图片描述][20190708200717423.png]  
（二）思路

（三）代码实现

public class Solution {
        
        private TreeNode pre = null;
        private TreeNode head = null;
    
        public TreeNode Convert(TreeNode pRootOfTree) {
        
            inOrder(pRootOfTree);
            return head;
        }
    
        private void inOrder(TreeNode node) {
        
            if (node == null) {
        
                return;
            }
            inOrder(node.left);
            node.left = pre;
            if (pre != null) {
        
                pre.right = node;
            }
            pre = node;
            if (head == null) {
        
                head = node;
            }
            inOrder(node.right);
        }
    }

--------------------

### 27. 字符串的排列 ###

（一）题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

（二）思路

有些地方没看懂，等刷完再回来看。代码先附上。

（三）代码实现

import java.util.ArrayList;
    import java.util.Arrays;
    public class Solution {
        
        private ArrayList<String> ret = new ArrayList<>();
        public ArrayList<String> Permutation(String str) {
        
            if (str.length()==0){
        
                return ret;
            }
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            backtracking(chars,new boolean[chars.length],new StringBuilder());
            return ret;
        }
    
        private void backtracking(char[] chars, boolean[] hasUsed, StringBuilder s) {
        
            if (s.length()==chars.length){
        
                ret.add(s.toString());
                return;
            }
            for (int i = 0; i < chars.length; i++) {
        
                if (hasUsed[i])
                    continue;
                if (i!=0&&chars[i]==chars[i-1]&&!hasUsed[i-1]) //保证不重复
                    continue;
                hasUsed[i] = true;
                s.append(chars[i]);
                backtracking(chars,hasUsed,s);
                s.deleteCharAt(s.length()-1);
                hasUsed[i] = false;
            }
        }
    }

1.  无返回值全排序

public static void printAllPermutations2(String str) {
        
    		char[] chs = str.toCharArray();
    		process2(chs, 0);
    	}
    
    	public static void process2(char[] chs, int i) {
        
    		if (i == chs.length) {
        
    			System.out.println(String.valueOf(chs));
    		}
    		HashSet<Character> set = new HashSet<>();
    		for (int j = i; j < chs.length; j++) {
        
    			if (!set.contains(chs[j])) {
        
    				set.add(chs[j]);
    				swap(chs, i, j);
    				process2(chs, i + 1);
    				swap(chs, i, j);
    			}
    		}
    	}
    
    	public static void swap(char[] chs, int i, int j) {
        
    		char tmp = chs[i];
    		chs[i] = chs[j];
    		chs[j] = tmp;
    	}

--------------------

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

（一）题目描述

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

（二）思路

1.  多投票问题，可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题，使得时间复杂度为O(n)
2.  使用cnt来统计一个元素出现的次数，当遍历到的元素和统计元素相同时，cnt++，否则另cnt–。如果前面查找了i个元素，且cnt==0，说明前i个元素没有majority，或者有majority，但是出现的次数少于i/2，因为如果多余i/2的话cnt就一定不会为0.此时剩下的n-1个元素中，majority的数目依然多余(n-i)/2，因此继续查找就能找出majority。
3.  即用for循环遍历chars，找出最多的一个数字，然后统计这个最多出现的数字的次数，如果大于str.length()/2，则返回。

（三）代码实现

public class Solution {
        
        public int MoreThanHalfNum_Solution(int[] array) {
        
            int majority = array[0];
            for (int i = 1, cnt = 1; i < array.length; i++) {
        
                cnt = array[i] == majority ? cnt + 1 : cnt - 1;
                if (cnt == 0) {
        
                    majority = array[i];
                    cnt = 1;
                }
            }
            int cnt = 0;
            for (int val : array) 
                if (val == majority) 
                    cnt++;
            return cnt > array.length / 2 ? majority : 0;
        }
    }

--------------------

### 29. 最小的K个数 ###

（一）题目描述

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

（二）思路

1.  直接进行排序，list添加前4个即可。如果是海量数据，则使用堆排
2.  利用大小为K的最小堆（特别适合海量数据）。
3.  使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。
4.  维护一个大小为K的最小堆过程如下：在添加一个元素之后，如果大顶堆的大小大于K，那么需要将大顶堆的堆顶元素去除。

（三）代码实现

import java.util.ArrayList;
    import java.util.PriorityQueue;
    public class Solution {
        
        public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        
            if (k > input.length || k <= 0)
                return new ArrayList<>();
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
            for (int num : input) {
        
                maxHeap.add(num);
                if (maxHeap.size() > k)
                    maxHeap.poll();
            }
            return new ArrayList<>(maxHeap);
        }
    }

--------------------

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

（一）题目描述

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

（二）思路

1.  创建一个变量greatestSum存放最大的和，创建遍历sum存放和。
2.  遍历数组，sum如果小于等于0那么直接将val赋给它，否则sum+val。（即只要大于0，就相加）
3.  将sum和greatestSum利用Math函数取得最大值保存

（三）代码实现

public class Solution {
        
        public int FindGreatestSumOfSubArray(int[] array) {
        
            if (array.length == 0 || array == null) 
                return 0;
            int greatestSum = Integer.MIN_VALUE;
            int sum = 0;
            for (int val : array) {
        
                sum = sum <= 0 ? val : sum + val;
                greatestSum = Math.max(greatestSum, sum);
            }
            return greatestSum;
        }
    }

[20190708200717423.png]: /images/20211213/fdfd442fc7d04a298f939d3506c27b28.png