[数据结构与算法]剑指offer-31~40

31.栈的压入、弹出序列（※※）

思路：使用辅助栈
来模拟栈的进出

无脑将元素压入栈 判断栈顶和当前的i 的指向元素是否相等。

• 相等 出栈 然后移动i 继续判断
• 不相等 就继续压栈 直到找到相等的为止
• 最后判断栈是否为空即可。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int index = 0;
        //先把元素放进去 直到和出栈的第一个匹配为止
        for (int num : pushed){
            //一直压栈
            stack.push(num);
            //每压入一个元素之后 判断这个元素是不是当前要出栈的元素
            while (!stack.isEmpty() && popped[index] == stack.peek()){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }
}

32.I 从上到下打印二叉树I

class Solution {
    public int[] levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> res = new LinkedList<>();
        if(root == null) return new int[0];
        queue.add(root);
        while(queue.size() != 0){
            TreeNode node = queue.remove();
            res.add(node.val);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
        int[] arr = new int[res.size()];
        int i = 0;
        for(int num:res){
            arr[i++]= num;
        }
        return arr;

    }
}

32-II.从上到下打二叉树II

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new LinkedList<>();
            for(int i =0 ;i < size;i++){
                TreeNode node = queue.remove();
                temp.add(node.val);
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }
}

32-III.从上到下打印二叉树III（之字形）

思路一：偶数层借助栈颠倒顺序之后再加入当层的list

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        Deque<Integer> stack = new LinkedList<>();
        int level = 0;
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new LinkedList<>();
            level++;
            //加入队列中去
            for(int i =0 ;i < size;i++){
                TreeNode node = queue.remove();
                //偶数进栈 奇数就直接进去
                if(level % 2 == 0){
                    stack.push(node.val);
                }else{
                    temp.add(node.val);
                }

                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            if(level % 2 == 0){
                //借助栈颠倒顺序
                while(!stack.isEmpty()){
                    temp.add(stack.pop());
                }
            }
            //加入结果中
            res.add(temp);
        }
        return res;
    }
}

方法二：利用双端队列的特性

将中间的链表temp 变成由list 接口 变成 LinkdeList 这样还是正常的进出队列。
只是再加入temp 的时候 奇数层是尾插，偶数层是头插即可

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null) return res;
        Queue <TreeNode> queue = new LinkedList<>();
        int level = 0;
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> temp = new LinkedList<>();
            level++;
            //加入队列中去
            for(int i =0 ;i < size;i++){
                TreeNode node = queue.remove();
                if(level % 2 != 0) {
                    temp.addLast(node.val);//尾插
                }else{
                    temp.addFirst(node.val);//头插
                }
                
                //正常的进出队列
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                   queue.add(node.right);
                }
            }
            //加入结果中
            res.add(temp);
        }
        return res;
    }
}

方法三： 使用collecion 的reverse 方法
如果是偶数层的话就revers 当前层的list

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null) return res;
        Queue <TreeNode> queue = new LinkedList<>();
        int level = 0;
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> temp = new LinkedList<>();
            level++;
            //加入队列中去
            for(int i =0 ;i < size;i++){
                TreeNode node = queue.remove();
                temp.add(node.val);
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            if(level % 2 ==0){
                Collections.reverse(temp);
            }
            //加入结果中
            res.add(temp);
        }
        return res;
    }
}

33.二叉搜索树的后序遍历序列

思路：递归遍历
根据二叉搜索树的性质

首先找到第一个比根大的值index，那么说明index 之前的都是根的左子树，那么index之后的应该都是右子树，值一定比根结点值大。如果遇到了并不大于根的值，说明不是二叉搜索树 返回false
然后递归的去判断左子树和右子树是否满足二叉搜索树的性质，同上一样的思想
递归结束的出口

• 当前的下标范围如果出现了 start== end 的情况说明已经是根节点
• 如果出现了 start > end 的情况说明根节点的某一个子树是空的也要退出

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null) return true;
        if(postorder.length == 0 || postorder.length == 1) return true;
        int rootValue = postorder[postorder.length-1];
        //使用的是闭区间
        return judege(postorder,0,postorder.length-1);
    }

    private boolean judege(int[] postorder, int start, int end) {
        if(start >= end) return true;
        int key = postorder[end];
        int i = 0;
        //说明的是假使找到了左子树
        for(i = start; i < end;i++){
            if(postorder[i]  > key){
                break;
            }
        }
        int j = 0;
        for(j = i;j < end;j++){
            if(postorder[j]  < key){
                return false;
            }
        }
        return judege(postorder,start,i-1) && judege(postorder,i,end-1);
    }
}

34.二叉树中和为某一值的路径（※）

这个题就是典型的深度优先遍历，结合回溯一起。
还是按照根左右的顺序对树进行遍历，
如果当前的根为空，说明遍历结束了，返回，这条路径走完了，但是没有结果。
如果当前的根不为空，并且target的值大于根的值，那么就继续去遍历当前根的左右子树的路径。注意遍历完左右子树的路径之后，需要把根从当前的path移除（回溯的体现）。
如果当前的根的值等于target 并且根没有左右子树，说明这条路径是符合的，加入结果集。
如果当前的根不为空，并且target的值小于根的值 那么也返回，优化剪枝，回溯移除当前遍历的元素 （这个剪枝就要具体题目具体分析了）

一般的剪枝是这样的，但是这个题有一个地方就是 target 可能本身就是负值，这样的剪枝是不正确的

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res ;
    LinkedList<Integer> path;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        res = new LinkedList<>();
        path = new LinkedList<>();
        preOrder(root,target);
        return res;
    }

    private void preOrder(TreeNode root, int target) {
       if(root == null) return;

        //先判断当前的元素是否可以加入根
        //但是这样的话没有考虑到负数的情况
        path.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null){
            res.add(new LinkedList<>(path));
            path.removeLast();
            return;
        }
        //遍历完了但是不满足
        if(root.left == null && root.right == null) {
            path.removeLast();
            return;
        }
        preOrder(root.left,target);
        preOrder(root.right,target);
        //表示当前的这个根左右都处理过了 可以出去了
        path.removeLast();
    }
}

35.复杂链表的复制 （※※）

思路一：哈希表辅助解决

哈希表用来存储 新节点和老结点的映射关系。

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        Node prev = new Node(-1);
        Node fakeHead = prev;
        //复制链表和next 
        while(cur != null){
            Node temp = new Node(cur.val);
            prev.next = temp;
            prev = temp;
            map.put(cur,temp);
            cur = cur.next;
        }
        cur = head;
        //遍历random
        while(cur != null){
            //分别获取对应的新的结点的映射
            Node temp = map.get(cur);
            temp.random = map.get(cur.random);
            cur = cur.next;
        }
        return fakeHead.next;
    }
}

思路二：将新链表和老链表结合在一起
之后再进行拆分

• 注意 random可以指向null 判定的时候要注意！
• 拆分的时候走到倒数第二个结点也就是老链表的最后一个结点 就停下来 否则新链表会空指针异常

class Solution {
    public Node copyRandomList(Node head) {
        //直接复制到老链表上
        Node cur = head;
        if(head == null) return null;
        while(cur != null){
            Node temp = new Node(cur.val);
            temp.next = cur.next;
            cur.next = temp;
            cur = cur.next.next;
        }

        //然后进行随机指向的的复制
        cur = head;
        while(cur != null){
           if(cur.random == null){ //这里
                cur.next.random = cur.random;
            }else {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        //新老链表拆分
        cur = head;
        Node newHead = cur.next;
        Node temp = newHead;
       while(cur.next!= null && cur.next.next != null){
            cur.next = cur.next.next;
            temp.next = temp.next.next;
            temp = temp.next;
            cur = cur.next;
        }
        cur.next = null;
        return newHead;
    }
}

36.二叉搜索树与双向链表（※）

二叉搜索树进行中序遍历

perv 永远实现遍历到的前一个结点，然后进串起来就可以。
最后注意头和尾要相互指向！

class Solution {
    Node head;
    Node prev ;//用来保存遍历到的上一个结点
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        //对树进行中序遍历
        dfs(root);

        //最后只需要对head 头结点和尾结点进行调整即可
        head.left = prev;
        prev.right = head;
        return head;
    }

    private void dfs(Node root) {
        if(root == null) return;
        dfs(root.left);

        //最深的递归root 此时是最后一个结点
        if(prev == null) {
            head = root;//确定head的指向
        }else {
            //当前驱不再是空的时候前驱的right 就可以有指向了
            prev.right = root;
        }
        //将当前的root的左指针指向前驱
        root.left = prev;
        //更改前序指向
        prev = root;
        
        dfs(root.right);
    }
}

37.序列化二叉树（※※）

整体来说都是借助队列的方式，需要灵活脑袋！
注意特殊字符的处理[] 以及，分割
序列化的过程是借助队列进行层序遍历。 （这个就比较简单了）
反序列化的过程其实也是借助队列，需要用一个下标保存该访问的是分割后的那一个元素。
初始化 第一个元素进入队列，然后index 指向第二个

之后让队列的首元素出队列，然后根据index 的指向这是左右结点。同时将左右结点入队列，注意处理null的情况

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        //对这棵树进行层序遍历进行还原
        StringBuilder sb = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (queue.size()!= 0){
            TreeNode temp = queue.remove();
            if(temp == null){
                sb.append("null").append(",");
            }else {
                sb.append(temp.val).append(",");
            }
            if(temp != null){
                queue.add(temp.left);
                queue.add(temp.right);
            }
        }
        //去掉最后一个,
        sb.replace(sb.length()-1,sb.length(),"");
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        TreeNode root = null;
        if(data .equals("[]")) return root;
        //先去掉[] 同时用，分开
        String[] split = data.substring(1,data.length()-1).split(",");
        if(split.length == 0) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        //让root的结点进入队列
        root = new TreeNode(Integer.parseInt(split[0]));
        queue.add(root);

        //同时指针指向index 为1的数组下标
        int i = 1;
        while (queue.size() != 0){
            TreeNode temp = queue.remove();
            //左孩子串起来 同时进入队列
            if(!split[i].equals("null")) {
                temp.left = new TreeNode(Integer.parseInt(split[i]));
                queue.add(temp.left);
            }
            i++;
            if(!split[i].equals("null")) {
                temp.right = new TreeNode(Integer.parseInt(split[i]));
                queue.add(temp.right);
            }
            i++;
        }
        return  root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

38.字符串的排列 （※※）

使用回溯的做法，枚举每一个位置，出现的字符，同时进行使用特殊的标记，记录当前字符是否被枚举过。

思路一：回溯 + set去重

最后需要对结果进行去重

class Solution {
    String[] str ;
    Set<String> list = new HashSet<>();

    public String[] permutation(String s) {
        if(s == null) return str;
        char[] arr = s.toCharArray();
        int length = arr.length;
        dfs(arr,0,length);
        str = new String[list.size()];
        int i = 0;
        for(String string : list){
           str[i++] = string;
        }
        return str;


    }

    //枚举每一个字符出现的位置

    //需要一个变量来记忆哪一个字符被枚举过了
    StringBuilder sb = new StringBuilder();

    private void dfs(char[] arr, int index, int length) {
        if(index == length){
            list.add(sb.toString());
            return;
        }

        // 枚举index的位置 去 遍历每一个字符
        for(int i = 0; i< length;i++){
            if(arr[i] == '.') continue;
            //这样来表示枚举过了
            char ch =arr[i];
            sb.append(ch);
            arr[i] = '.';
            dfs(arr,index+1,length);

            //还原回去
            arr[i] = ch;
            sb.deleteCharAt(sb.length()-1);
        }
    }

}

思路二： 进行剪枝的操作，这个做法在之前也用过
对字符串进行排序，那么相邻的字符就会在一起，然后如果当前的字符和前一个字符相等，并且前一个字符没有被枚举过，那么当前字符就跳过。

这样的思路在前面的剪枝也用到过，是一个很经典的做法。这种剪枝的思想很重要！

class Solution {
    String[] str ;
    List<String> list = new LinkedList<>();

    public String[] permutation(String s) {
        if(s == null) return str;
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        int length = arr.length;
        dfs(arr,0,length);
        str = new String[list.size()];
        int i = 0;
        for(String string : list){
           str[i++] = string;
        }
        return str;


    }

    //枚举每一个字符出现的位置

    //需要一个变量来记忆哪一个字符被枚举过了
    StringBuilder sb = new StringBuilder();

    private void dfs(char[] arr, int index, int length) {
        if(index == length){
            list.add(sb.toString());
            return;
        }

        // 枚举index的位置 去 遍历每一个字符
        for(int i = 0; i< length;i++){
            if(arr[i] == '.' ||( i >0 && arr[i]== arr[i-1] && arr[i-1]!= '.')) continue;

            //这样来表示枚举过了
            char ch =arr[i];
            sb.append(ch);
            arr[i] = '.';
            dfs(arr,index+1,length);

            //还原回去
            arr[i] = ch;
            sb.deleteCharAt(sb.length()-1);
        }
    }

}

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

思路一 ： 排序之后返回最中间的那一个

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

思路二：map

class Solution {
    public int majorityElement(int[] nums) {
       HashMap<Integer,Integer> map = new HashMap<>();
       for(int num:nums){
           map.put(num,map.getOrDefault(num,0)+1);
       }
       int key = nums.length/2;
       for(Map.Entry<Integer,Integer> mapping : map.entrySet()){
           if(mapping.getValue() > key) return mapping.getKey();
       }
       return -1;
    }
}

40. 最小的k个数

思路一：排序+数组拷贝

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k >= arr.length) return arr;
        Arrays.sort(arr);
        int[] res = new int[k];
        System.arraycopy(arr,0,res,0,k);
        return res;
    }
}

这里一定要注意数组拷贝的函数 System.arraycopy()
这个写法容易被笑话…哭泣

思路二：topK的最值问题
由于java中的优先级队列是小堆，筛选出来的是较大值，所以自己改一个，改成一个大根堆。这样可以筛选出来较小的tok值

如果当前的堆里的元素已经有k个
那么下一个元素如果比堆顶小，那么移除堆顶，当前元素进入堆中即可。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k >= arr.length) return arr;
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return  o2-o1;
            }
        });

        for(int num : arr){
            if(queue.size() < k){
                queue.add(num);
            }else{
                if(queue.size()!= 0 && num < queue.peek()){
                    queue.remove();
                    queue.add(num);
                }
            }
        }
        
        int[] res = new int[queue.size()];
        int i = 0;
        for(int num:queue){
            res[i++] = num;
        }
        return  res;


    }
}

怎么说，如果纯idea 可能比较器哪里写不出来

//所以用lamda表达式会比较好写一些
Queue<Integer> queue = new PriorityQueue<>((v1,v2)->v2-v1);

思路三：快排！！！

根据快排的思路，比如选择第一个数字作为基准，调整把比这个数字小的放到前面，比这个数字大的放到后面。每一次调整完毕之后，看一下分界线的左边的数字个数，如果比k大，那么继续对左边进行调整，如果比k小，对右边进行调整，如果等于k，就可以退出来。因为并没有要求数字的有序性。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k == 0 || arr.length == 0) return new int[0];
        //不用完全把数据排成有序的 只需要知道比当前数字小的有多少个数字就可以了
        int index = quickSort(arr,0,arr.length-1,k);
        return Arrays.copyOfRange(arr,0,index+1);
    }

    private int quickSort(int[] arr, int start, int end, int k) {
        int splitIndex = quickSortInternal(arr,start,end);
        if(splitIndex + 1 > k){
            return quickSort(arr,start,splitIndex -1,k);
        }else if(splitIndex + 1 < k) {
            return quickSort(arr,splitIndex+1,end,k);
        }else {
            return splitIndex;
        }
    }

    private  int quickSortInternal(int[] arr, int start, int end) {
        int key = arr[start];
        int left = start;
        int right = end;

        while (left < right){
            while (left < right && arr[right] >= key){
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left]  <= key){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
}