牛客网算法——名企高频面试题143题（9）

题目描述

给定一棵二叉树，判断琪是否是自身的镜像（即：是否对称）

剑指 Offer 28. 对称的二叉树

package 名企高频面试题143;

/**
 * @Classname 对称二叉树
 * @Description TODO
 * @Date 2020/12/17 10:26
 * @Created by xjl
 */
public class 对称二叉树 {

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

    public boolean isSymmetric(TreeNode root) {
        return root == null ? true : recur(root.left, root.right);
    }

    private boolean recur(TreeNode L, TreeNode R) {
        if (L == null && R == null) return true;
        if (L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

package 名企高频面试题143;

/**
 * @Classname 二叉树镜像
 * @Description TODO
 * @Date 2020/12/17 10:48
 * @Created by xjl
 */
public class 二叉树镜像 {

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        Mirror(root.left);
        Mirror(root.right);
    }
}

题目描述

给出一组可能包含重复项的数字，返回该组数字的所有排列。

package 名企高频面试题143;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Classname 有重复的数字的排列
 * @Description TODO
 * @Date 2020/12/17 10:15
 * @Created by xjl
 */
public class 有重复的数字的排列 {

    @Test
    public void test() {
        ArrayList res = permuteUnique(new int[]{1, 3, 2});
        for (ArrayList list : res) {
            for (int i : list) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    public ArrayList permuteUnique(int[] num) {
        ArrayList ans = new ArrayList();
        ArrayList list = new ArrayList();
        Arrays.sort(num);
        boolean[] vis = new boolean[num.length];
        dfs(num, list, vis, ans);
        return ans;
    }

    private void dfs(int[] num, ArrayList list, boolean[] vis, ArrayList ans) {
        if (list.size() == num.length && !ans.contains(list)) {
            ans.add(new ArrayList(list));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (!vis[i]) {
                list.add(num[i]);
                vis[i] = true;
                dfs(num, list, vis, ans);
                list.remove(list.size() - 1);
                vis[i] = false;
            }
        }
    }
}

题目描述

实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

package 名企高频面试题143;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @Classname 最小栈
 * @Description TODO
 * @Date 2020/12/17 10:51
 * @Created by xjl
 */
public class 最小栈 {

    public int[] getMinStack(int[][] op) {
        ArrayList list = new ArrayList();
        Stack stack = new Stack();
        for (int[] arr : op) {
            if (arr[0] == 1) {
                if (stack.size() == 0) {
                    stack.add(arr[1]);
                    stack.add(arr[1]);
                } else {
                    Integer peek = stack.peek();
                    if (peek >= arr[1]) {
                        stack.add(peek);
                        stack.add(arr[1]);
                    } else {
                        stack.add(arr[1]);
                        stack.add(peek);
                    }
                }
            } else if (arr[0] == 2) {
                stack.pop();
                stack.pop();
            } else {
                Integer ans = stack.peek();
                list.add(ans);
            }
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

    @Test
    public void test() {
        int[] minStack = getMinStack(new int[][]{{1, 3}, {1, 2}, {1, 1}, {3}, {2}, {3}});
        for (int i : minStack) {
            System.out.print(i + " ");
        }
    }
}

给定String类型的数组strArr，再给定整数k，请严格按照排名顺序打印 出次数前k名的字符串。

[要求]

如果strArr长度为N，时间复杂度请达到O(Nlog⁡K)O(N \log K)O(NlogK)

输出K行，每行有一个字符串和一个整数（字符串表示）。 你需要按照出现出现次数由大到小输出，若出现次数相同时字符串字典序较小的优先输出

package 名企高频面试题143;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @Classname 出现topK的数字
 * @Description TODO
 * @Date 2020/12/17 16:10
 * @Created by xjl
 */
public class 出现topK的数字 {
    public String[][] topKstrings(String[] strings, int k) {

        PriorityQueue queue = new PriorityQueue(new MyComparator());

        HashMap map = new HashMap(16);
        for (int i = 0; i < strings.length; i++) {
            if (map.containsKey(strings[i])) {
                map.put(strings[i], map.get(strings[i]) + 1);
            } else {
                map.put(strings[i], 1);
            }
        }
        //入堆
        for (Map.Entry entry : map.entrySet()) {
            queue.add(new MyNode(entry.getKey(), entry.getValue()));
        }
        String[][] result = new String[k][2];
        int j = 0;
        while (j < k && !queue.isEmpty()) {
            MyNode node = queue.poll();
            result[j][0] = node.val;
            result[j++][1] = String.valueOf(node.num);
        }
        return result;
    }

    class MyNode {
        String val;
        int num;

        MyNode(String val, int num) {
            this.num = num;
            this.val = val;
        }
    }

    class MyComparator implements Comparator {
        @Override
        public int compare(MyNode o1, MyNode o2) {
            if (o1.num == o2.num) {
                //字典序小的在前 所以 o1 比 o2
                return o1.val.compareTo(o2.val);
            } else {
                //数量大的在前所以 o2 - o1
                return o2.num - o1.num;
            }
        }
    }
}

题目描述

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

    public int[] solve(int[] xianxu, int[] zhongxu) {
        TreeNode root = buildTree(xianxu, zhongxu);
        List ans = getRightView(root);
        return ans.stream().mapToInt(Integer::valueOf).toArray();
    }

    /**
     * @description TODO  层序遍历
     * @param: root
     * @date: 2020/12/17 16:53
     * @return: java.util.List
     * @author: xjl
     */
    public List getRightView(TreeNode root) {
        LinkedList list = new LinkedList();
        List res = new ArrayList();
        list.add(root);
        while (!list.isEmpty()) {
            int size = list.size();
            TreeNode cur = null;
            while (size > 0) {
                size--;
                cur = list.removeFirst();
                if (cur.left != null) {
                    list.add(cur.left);
                }
                if (cur.right != null) {
                    list.add(cur.right);
                }
            }
            res.add(cur.val);
        }
        return res;
    }

    /**
     * @description TODO 重建的二叉树
     * @param: preorder
     * @param: inorder
     * @date: 2020/12/17 16:53
     * @return: 名企高频面试题143.中序遍历和后序遍历构造二叉树.TreeNode
     * @author: xjl
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //递归函数的出口是
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        //获取到根节点的value的值
        TreeNode root = new TreeNode(preorder[0]);
        //构建left right子树
        int index = findIndex(preorder, inorder);
        // root.left = buildTree( 左子树的前序数组 左子树的中序数组);
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, index + 1), Arrays.copyOfRange(inorder, 0, index));
        //root.right = buildTree(右子树的前序数组 右子树的中序数组);
        root.right = buildTree(Arrays.copyOfRange(preorder, index + 1, preorder.length), Arrays.copyOfRange(inorder, index + 1, inorder.length));
        return root;
    }

    /**
     * @description TODO 为了找到中序遍历的过程中位置
     * @param: preorder
     * @param: inorder
     * @date: 2020/12/17 16:54
     * @return: int
     * @author: xjl
     */
    private int findIndex(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) {
                return i;
            }
        }
        return 0;
    }