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

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。

由于二叉搜索树已经是排序好的了，因此我们可以采用中序遍历的方式，对每个结点改变指针的方向

二叉搜索树

我们需要用两个辅助指针，一个pre来记录中序遍历情况下的上一个结点的位置，例如4->6->8->10->11->12->13，然后一个固定好的指针head来标记头结点的位置，例如4.
代码如下

public class Solution {
    private TreeNode pre = null;
    private TreeNode head = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        mid_order(pRootOfTree);
        return head;
    }
    //原函数有返回值，我们在这里递归最好构造一个无返回值类型的函数
    public void mid_order(TreeNode node){
        if(node==null){
            return ;
        }
        /*
        对于此处中序遍历递归看不太清的可以一个一个代入进行分析
        从下面的mid_order(node.left)一句中，其实就是不断往左子节点递归
        递归到什么时候结束呢，10->6->4->null
        ok，到4.left的时候直接返回，那么此时node为4，开始执行下面的语句
        */
        mid_order(node.left);
        //先将node的左节点指向pre，例如此时为4，那么4指向null
        node.left = pre;
        //下面这句话全局只有一次不生效，那就是最原始的时候pre==null
        if(pre!=null){
            pre.right = node;
        }
        //然后将pre移动到node的位置，例如从null移动到4，从4移动到6....
        //亦可以看做链表结点往后移动一个
        pre = node;
        //下面这句话全局只有一次生效，那就是不断的递归到4这个初始结点的时候
        //相当于找到了头结点了，以后再也不会进入这个if语句了
        if(head==null){
            head = node;
        }
        //然后进入node.right
        //为什么这样的顺序是中序遍历呢？
        //可以想象，在上面node等于6的时候，我们先执行了mid_order(6.left)相关的操作
        //此时pre在4，我们执行4,6连接的操作，然后将pre移动到6
        //等于一系列跑完了，再执行mid_order(6.right),即此时要进入8这个结点的操作了
        //后面等8跑完了，就返回到10了，10的10.right执行的时候也会先递归到11
        //所以这样一步步分析，都是顺利成章到的利用递归实现中序遍历了。
        mid_order(node.right);
    }
}

27.字符串的排列

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

这个题是个典型的回溯法，说白了就相当于一个个试，例如“abc”的所有组合，怎么试呢，就是先把a放在第一个，然后再考虑后面的bc，后面的b、c有bc和cb两种，拼接在a后面，就是abc和acb两种了。
代码如下

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    //定义一个存储String的ArrayList
    private ArrayList<String> ret = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        if(str.length()==0){
            return ret;
        }
        //将str转化为字符数组
        char[] chars = str.toCharArray();
        //按chars中的字符的ASCII码的进行字典排序
        Arrays.sort(chars);
        //使用回溯函数，创建两个新的变量
        //一个是布尔数组，用以表示chars中对应位置的字符是否已经被使用过
        //一个是StringBuilder类，用来实时的存储字符串
        backtracking(chars,new boolean[chars.length],new StringBuilder());
        return ret;
        
    }
    //定义一个无返回值类型的回溯函数
    public void backtracking(char[] chars,boolean[] hasUsed,StringBuilder s){
        //当临时变量s的长度等于字符数组的长度的时候，证明已经组装完成了一个字符串
        //则，此时把这个字符串加入到最后的结果中，然后返回退出本次递归
        if(s.length()==chars.length){
            ret.add(s.toString());
            return;
        }
        //对字符数组chars中的所有字符进行遍历
        for(int i=0;i<chars.length;i++){
            //如果这个字符被用过了，那么循环继续，这一步是很关键的
            if(hasUsed[i]){
                continue;
            }
            //这句if语句是确保不会重复
            //1.i!=0是为了chars[i-1]不为空
            //当chars[i]==chars[i-1]时，有可能会发生重复
            /*!hasUsed[i-1]即hasUsed[i-1]为false时，可以尝试去理解
              当前元素等于上一个元素，而且上一个元素没有被用过，证明上一个元素是经历过回溯的
              例如有两个a,即a1,a2
              我们先组合过一次a1a2了，然后通过回溯，使得a1变成了未使用过的状态
              假设我们此时再组合a2a1，在外在看来，实际上还是aa，这就会造成重复，
              所以当当前元素等于上一个元素，且上一个元素是没有被使用的状态时，我们就跳过本次循环
              
            */
            if(i!=0&&chars[i]==chars[i-1]&&!hasUsed[i-1]){
                continue;
            }
            //然后将当前元素加入到s中，且将当前元素标记为已经使用过的状态
            s.append(chars[i]);
            hasUsed[i]=true;
            //然后使用回溯函数进行递归
            backtracking(chars,hasUsed,s);
            //然后将s的最后一个元素进行移除，且将当前的元素标记为未使用
            s.deleteCharAt(s.length()-1);
            hasUsed[i]=false;
            
        }
        
    }
}

这里用到了一个hasUsed数组来标记字符是否被使用过，而且在回溯函数中每次的参数都是chars，其实关键就是这个hasUsed，与之前用python写的例如使用了b之后，将ac拼接作为新的数组来输入到回溯函数中不同，这里的做法是，用hasUsed来标记某个元素是否被使用过，即每次进入递归的时候都需要完整的对一个长度为chars.length的chars字符数组进行遍历；
这么解释起来可能有点抽象，用一个简单的实例来证明，我用0代表没被使用过，1代表被使用过，从最开始的[a0,b0,c0]来跑递归函数；
在for循环中，当i=0时，a被使用过了，立马进入了递归，即此时chars变成了[a1,b0,c0]，可以观察到在进入了这一层递归的时候for循环依然要从下标为0的位置开始跑，只是此时a的状态为1了，则跳过本次循环，进入到b，b未被使用，则chars被改为了[a1,b1,c0]，然后顺利成章的进入到了第二层循环的循环，此时abc出炉，然后一个回溯，将c标记为0，然后返回后b也被标记为0，则进入了a1状态下的，第三个字符，起手先将第三个字符加入，变成ac，然后将c标记为1，此时b为0，则最后为acb；
同理当最最最外层循环的第一个字符跑完后，将a标记为0，开始对第二个字符进行操作，即b；
最后按递归的顺序，所有的字符都是按照字典序添加的，如下所示
a b c
a c b
b a c
b c a
c a b
c b a

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

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

该题最好的解法当然是O(n)时间复杂度的，用到两个变量，一个变量key用来存储所谓的“关键元素”，一个变量cnt用来存储关键元素key的出现次数，将key初始化为array[0]，cnt初始化为1.具体算法流程为：1、先判断cnt是否为0，如果为0，则将当前元素赋给key，且cnt=0；否则的话判断当前元素与key是否相等，如果相等则cnt+1，不相等则cnt-1；2.找到了key元素之后还需要进行检查，因为例如12345这种情况最后的key就是5,所以还要检查key元素在数组中出现的次数是否大于数组长度的一般，总结起来就是一句话，大于数组长度一半的元素一定会留下来成为key元素，但key元素并不一定是大于数组长度一般的元素，因此要进行检查。
代码如下

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length==0){
            return 0;
        }
        int key = array[0];
        //从数组第一个元素开始进行循环遍历
        for(int i=1,cnt=1;i<array.length;i++){
            //如果cnt等于0，那么就重新计数和确定key元素
            //否则，就确定cnt数值如何变化
            if(cnt==0){
                key=array[i];
                cnt=1;
            }else{
                cnt=array[i]==key?cnt+1:cnt-1;
            }
            
        }
        //找到key元素之后，来对key元素进行验证
        int cnt=0;
        for(int j=0;j<array.length;j++){
            cnt=array[j]==key?cnt+1:cnt;
        }
        return cnt>array.length/2?key:0;
    }
}

29.最小的K个数

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

本题最简单的思路就是用堆排来做，用一个容量为K的大根堆去维护数组，如果当新元素加入堆之后容量超过了K，那么就抛弃堆顶元素，而java中实现堆的最简单的方法就是封装好的优先队列，但是注意由于队列的性质是先进先出，只能弹出队列首部的元素，因此我们需要对优先队列进行降序即可。
代码如下

import java.util.PriorityQueue;
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //如果k<0或者input为空或者k大于input的长度，那么返回一个空的ArrayList
        if(k<0||input.length==0||k>input.length){
            return new ArrayList<>();
        }
        //用优先队列创建一个大根堆，注意由于队列先进先出的性质，所以我们要进行降序
        //这里用o1,o2指代两个元素，用o2-o1代表降序
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2)->o2-o1);
        for(int i=0;i<input.length;i++){
            maxHeap.add(input[i]);
            //如果优先队列的容量大于K，则弹出队列首部的元素
            if(maxHeap.size()>k){
                maxHeap.poll();
            }
        }
        return new ArrayList<>(maxHeap);
    }
}

30.连续子数组的最大和

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

典型的入门DP问题，用一个dp数组来存储以array中每个元素为结尾的可能的最大连续子数组和，试想，当我处理第i项时，已经存储了前面i-1个元素的最大连续子数组和，如果前面这个和即dp[i-1]已经小于0了，那我要前面的何用？以我array[i]结尾的如果把前面的加上岂不是越加越小？所以此时dp[i]就等于array[i]，如果前面的大于或者等于0，那么把前面的加起来，岂不是美滋滋？所以此时dp[i]=dp[i-1]+array[i];
dp方程如下：

从第1项开始
dp[i] = dp[i-1]>0?dp[i-1]+array[i]:array[i];

求出了以array中每个元素为结尾能够得到的连续子数组的最大值的一个数组，然后求出这个数组的最大值，即可.
代码如下

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0){
            return 0;
        }
        //先复制一份原数组
        int[] dp = array.clone();
        //动态规划过程
        for(int i = 1;i<array.length;i++){
            dp[i] = dp[i-1]>0?dp[i-1]+array[i]:array[i];
        }
        int max = dp[0];
        //求出dp数组的最大值
        for(int num:dp){
            max = Math.max(max,num);
        }
        return max;
    }
}