算法训练营-第二周-哈希树堆图

一.哈希表

定义

键值映射关系

<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaibastwh0eUlfWtHFU7I7zSmtzRfDgg25fic8eCx7QZkrTibs8yKjCAQ1oQ/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />

时间复杂度

写入 O(1)

读取 O(1)

扩容 O(n)

哈希函数

把key转成index寻找值

index = HashCode ("001121") % Array.length = 7

<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaib9ywjXKqGDwR8iaNia8BHhPcYt6rwMI5L2EyAMTIql226icxIGicicV1Kdpw/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />

实战题目

242. 有效的字母异位词

/*


    1.暴力 sort 遍历比较 
        时间复杂度 O(nlogn)
        空间复杂度 O(1)
    2.哈希表 比较字母出现的频次
        或者26个大小的数组，一边自增，一边自减。所有的都为0则相等。
        时间复杂度O(n)
        空间复杂度O(26)
*/
public class ValidAnagram {

    /**
     * 解法1 排序后比较
     * 
     * 分别将两个字符串排序，然后比较
     * 
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     */
    public boolean isAnagram(String s, String t){
        if (s.length() != t.length())  return false;
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }

    /**
     * 解法2 计数器
     * 
     * 用计数器统计每个字符出现的次数
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static boolean isAnagram2(String s, String t){
        if (s.length() != t.length()) return false;
        int[] table = new int[26];
        for (int i = 0; i < s.length(); i++) {
            //当前字符 - a，a = 97
            table[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            table[t.charAt(i) - 'a']--;
            //减 1 之后出现次数小于就说明就在 s 中从未出现的字符
            if (table[t.charAt(i) - 'a'] < 0) return false;
        }
        return true;
    }
}

49. 字母异位词分组

/*
    方法一：
        用HashMap接收最后的结果，
        对原数组字符串进行遍历，转成字符数组，排序，转成字符串
        key为排序后的字符串，value为原来的元素。
        
        返回HashMap.values。
            时间复杂度 O(NKlogK) N是字符串数组个数 K为字符串最大长度
            空间复杂度 O(NK) 开辟的ans哈希表
    方法二：建议课后背诵
        和方法一一个意思。只是用26个数组去接。没什么意义。只是时间复杂度小。不用排序。
        时间复杂度 O(N * (K > 26 ? K : 26)) N是字符串数组个数 K为字符串最大长度
        空间复杂度 O(NK)
*/
/*
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        for (String s : strs) {
            char[] ca = s.toCharArray(); // 每个元素变成字符串数组
            Arrays.sort(ca); // 数组排序
            String key = String.valueOf(ca); // 转成字符串作为Key。key: 排序后的数组  value：字母异位词的集合
            if (!ans.containsKey(key)) ans.put(key, new ArrayList()); // 结果里没有这个key，就放入key，值为数组
            ans.get(key).add(s); // 数组里加原来这个元素
        }
        return new ArrayList(ans.values());
    }
}
*/
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        int[] count = new int[26];
        for (String s : strs) {
            Arrays.fill(count, 0); // 数组每个值赋0
            for (char c : s.toCharArray()) count[c - 'a']++; // 字母对应位自增
            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]); // #2#1#0#0
            }
            String key = sb.toString(); // 转成字符串作为密钥
            if (!ans.containsKey(key)) ans.put(key, new ArrayList()); // 相同key，放一个数组里
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

1. 两数之和

/*
    找出数组中两个数字满足目标值的两个数字
        方法一：暴力迭代
            i -> 0, len - 2
                j -> i+1, len - 1
                    nums[i] + nums[j] == target
        时间复杂度O(n^2)
        空间复杂度O(n)
        方法二： 利用哈希表，两次迭代
            第一次，将所有数字放入哈希表中，
            第二次，遍历哈希表，查找目标值-当前值的结果是否在哈希中
        时间复杂度O(n * 2)
        空间复杂度O(n)    
        方法三：利用哈希表，一次迭代
            其实只需要一次，先判断目标值-当前值的结果是否在哈希中，
                不存在，在把值放进去。
        时间复杂度：O(n)
        空间复杂度：O(n)


*/
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

二.树

定义

树是n个节点的有限集。

在非空树中，有如下特点：

• 有且一个根节点

• 当n>1时，其余节点可分为m个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

树的遍历

（1）深度优先

前序：根左右

<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaib40oOC9T5IzJjSPAcrhUDicVG9HdKGVEwySEC3EvX1NqdricI68Arqm6g/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />

中序：左根右

<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaibnS3Lgz89n4peOQL0dpOibjibhyUtqdKbMFNtwn4DTfOO7fFRcqhWH1Zg/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />

后序：左右根

<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaibM9ibtl8CeLLhDykSFKJAwsljsBOCMqAKVNr4FMO1UC8RUrXYyd9Nb4Q/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />

实现方式：递归或栈。

（2）广度优先

层序：一层一层遍历。

<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaib81wdmp22Bz3N1Ju6TtB2oiaIgpDFdBrTCXYic3czK5mEfTxcoA59gY1w/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />

实现方式：队列。

三.二叉树

二叉树

二叉，顾名思义，这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。

满二叉树?

一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。

完全二叉树

对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

倒数第二层满，最后一层全靠左

img

二叉查找树

定义

二叉查找树在二叉树的基础上增加了以下几个条件：

• 如果左子树不为空，则左子树上所有节点的值均小于根节点的值。

• 如果右子树不为空，则右子树上所有节点的值均大于根节点的值。

• 左、右子树也都是二叉查找树。

<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom: 33%;" />

作用

• 查找==》二分查找。
• 排序==》中序遍历。

实现方式

• 链表。
• 数组：对于稀疏二叉树来说，数组表示法是非常浪费空间的。

实战题目

589. N叉树的前序遍历

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<Integer>();
        Stack<Node> stack = new Stack<Node>();
        if(root == null)
            return res;
        stack.push(root);
        while(!stack.isEmpty())
        {
            Node node = stack.pop();
            res.add (node.val);
            for(int i =  node.children.size()-1;i>= 0;i--)
            {
                stack.add(node.children.get(i));
            }  
        }
        return res;
    }
}

590. N叉树的后序遍历

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
//迭代实现：直接反转先序结果即可
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res_pre = new ArrayList<>();
        if(root == null)
            return res_pre;
        Stack<Node> s = new Stack<>();
        s.push(root);
        while(!s.isEmpty()){
            Node n = s.pop();
            res_pre.add(n.val);
            for(Node node : n.children)
                s.push(node);
        }
        Collections.reverse(res_pre);
        return res_pre;
    }
}

429. N叉树的层序遍历

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> levelOrder(Node root) {
        helper(root, 1);
        return res;
    }

    public void helper(Node root, int level) {
        if (root == null) return;
        if (res.size() < level) res.add(new ArrayList<Integer>());
        res.get(level - 1).add(root.val);
        for (Node child : root.children) 
            helper(child, level + 1);
    }
}

104. 二叉树的最大深度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

112. 路径总和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return root.val == sum;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

94. 二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 * [1,null,2,3]
 * 二叉树的中序遍历。题目说不让用递归。这题只能用栈。
        中序遍历：左-根-右
 *      方法一：递归
 *          时间复杂度 O(n)
 *          空间复杂度 O(n)
 *      方法二：栈的遍历。建议背诵。
            指针不为空，栈不为空，就不结束。
            指针不为空，就一直找左儿子，放左儿子
            直到左儿子没了，就开始弹。放入结果中。然后指右儿子。
 *          时间复杂度 O(n)
 *          空间复杂度 O(n)
        方法三：莫里斯遍历
 */
 public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 结果链表
        List<Integer> res = new ArrayList<>();
        // 栈：工具人角色
        Stack<TreeNode> stack = new Stack<>();
        // curr 当前指针，从根开始
        TreeNode curr = root;
        // 指针不为Null且栈非空
        while (curr != null || !stack.isEmpty()) {
            // 放的步骤：指针不为null。将左边的都放先进去。当没有左儿子了，就开始弹。
            while (curr != null) {
                // 把指针放进去
                stack.push(curr);
                // 指向左子树
                curr = curr.left;
            }
            // 弹出栈顶值，值放入结果链表。指针指向右儿子。
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}
/*
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }


    public void helper(TreeNode root, List<Integer> res) {
        // 根不为空
        if (root != null) {
            // 左子树不为空
            if (root.left != null) {
                // 就放左子树
                helper(root.left, res);
            }
            // 然后放中间数
            res.add(root.val);
            // 右子树不为空，就放右子树
            if (root.right != null) {
                helper(root.right, res);
            }
        }
    }
}*/

22. 括号生成

/*
    生成所有n个有效括号
        输入：n = 3
        输出：[
               "((()))",
               "(()())",
               "(())()",
               "()(())",
               "()()()"
             ]
 */


 // 递归
// public class Solution {


//     ArrayList<String> res = new ArrayList<>();


//     public List<String> generateParenthesis(int n) {
//         // 初始条件
//         generate(0, 0, n, "");
//         // 结束条件
//         return res;
//     }


//     // 处理
//     private void generate(int leftCnt, int rightCnt, int n, String s) {
//         // 下钻
//         // 如果左、右括号等于n个，将值放入结果中
//         if (leftCnt == n && rightCnt == n) {
//             res.add(s);
//             return;
//         }
//         // 只要左括号没有达到n个，就可以加
//         if (leftCnt < n) generate(leftCnt + 1, rightCnt, n, s + "(");
//         // 右括号数量如果小于左括号，就可以加
//         if (rightCnt < leftCnt) generate(leftCnt, rightCnt + 1, n, s + ")");
//         // 清除全局临时变量
//     }


//     public static void main(String[] args) {
//         System.out.println(new Solution().generateParenthesis(3));
//     }
// }


// 递归。确保括号有效性。只要要求左括号先行于右括号。
class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(n, n, "");
        return res;
    }


    private void dfs(int left, int right, String curStr) {
        if (left == 0 && right == 0) { // 左右括号都不剩余了，递归终止
            res.add(curStr);
            return;
        }
        // 第一次会进去。第二次会有两个分叉
        if (left > 0) { // 如果左括号还剩余的话，可以拼接左括号
            dfs(left - 1, right, curStr + "(");
        }
        // 第一次是进不去的，因为左右是相等的。第二次进入后，左右等号数量又相等了。
        if (right > left) { // 如果右括号剩余多于左括号剩余的话，可以拼接右括号
            dfs(left, right - 1, curStr + ")");
        }
    }
}

98. 验证二叉搜索树

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



    方法一：根据定义，左子树必须小于当前节点
                    右子树必须大于当前节点
        时间复杂度 O(n)
        空间复杂度 O(n)
    方法二：中序遍历是递增的，用临时变量去接，每次都比较
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    // 判断是否是有效二叉搜索树，左子树小于当前节点，右子树大于当前节点
    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        // null符合要求
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        // 左边这个：有效的是左节点与最大值。右边这个：有效的是右节点与最小值。
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}


 // 通过中序遍历来验证
class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }
}

104. 二叉树的最大深度

public class MaximumDepthOfBinaryTree {

    /**
     * 解法1 递归
     * 
     * 递归循环做的事情：先求左子树深度，再求右子树深度，然后取两者最大，再加上自身一层的深度
     * 
     * 时间复杂度: O(n)
     * 空间复杂度: 最坏时树完全不平衡 O(n)，最好时树完全平衡 O(logn)
     * @param root：根节点
     * @return 树的最大深度
     */
    public int maxDepth(TreeNode root) {
        //递归终止条件：叶子节点无左右子节点
        if (root == null)
            return  0;
        else {
            //左子树深度
            int leftHeight = maxDepth(root.left);
            //右子树深度
            int rightHeight = maxDepth(root.right);
            // + 1 表示每次递归结束，求深度的时候，要把自身所在一层深度加上
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

105. 从前序与中序遍历序列构造二叉树

public class ConstructBinaryTreeFromPreorderAndInorderTraversal {


    /**
     * 解法1 递归
     *
     * 前序便利的第一个元素一定是树的根，然后这个根将中序遍历分成左右两颗子树，再通过移动指针递归两个子树，不停给左右子节点赋值，最后完成树的构建
     *
     * @param preOrder: 前序遍历
     * @param inOrder: 中序遍历
     * @return 构建好树返回根节点
     */
    public TreeNode buildTree(int[] preOrder, int[] inOrder){
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < inOrder.length; i++)
            map.put(inOrder[i], i);
        return build(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1, map);
    }

    /**
     * @param pre : 前序遍历 preOrder
     * @param ps  : preOrder start
     * @param pe  : preOrder end
     * @param in  : 中序遍历 inOrder
     * @param is  : inOrder start
     * @param ie  : inOrder end
     * @param map : inOrder map - key: 中序遍历数组元素 value: 元素数组下表
     * @return 构建完成返回根节点
     */
    private TreeNode build(int[] pre, int ps, int pe, int[] in, int is, int ie, Map<Integer, Integer> map) {
        if (ps > pe || is > ie) return null;
        //前序遍历的第一个元素一定是树的根
        TreeNode root = new TreeNode(pre[ps]);

        //找到这个根在中序遍历中的位置，它将中序遍历分成了左右两颗子树
        int rootIndex = map.get(root.val);

        //距离 = 根在中序遍历中的位置 - 左子节点的位置
        int distance = rootIndex - is;

        /**
         * ps + 1        : 前序遍历中 - 左子树的开始节点
         * ps + distance : 前序遍历中 - 左子树的结束节点
         * is            : 中序遍历中 - 左子树的开始节点
         * rootIndex - 1 : 中序遍历中 - 左子树的结束节点
         */
        root.left = build(pre, ps + 1, ps + distance, in, is, rootIndex - 1, map);
        /**
         * ps + distance + 1 : 前序遍历中 - 右子树的开始节点
         * pe                : 前序遍历中 - 右子树的结束节点
         * rootIndex + 1     : 中序遍历中 - 右子树的开始节点
         * ie                : 中序遍历中 - 右子树的结束节点
         */
        root.right = build(pre, ps + distance + 1, pe, in, rootIndex + 1, ie, map);
        return root;
    }
}

111. 二叉树的最小深度

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

    /**
     * 解法1 递归
     * 
     * 取左子树的深度和右子树的深度两者最小为树的最小深度
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：最坏 O(n)，最好 O(logn)
     * 
     * @param root: 根节点
     * @return 返回二叉树的最小深度
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;                   
        }
        if (root.left != null && root.right!= null) 
            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        else 
            //如果左子节点为空或者右子节点为空，那么 root 有一个叶子节点也算是一层，所以取 max，再加上当前节点所在的一层
            //如果左右子节点都为空，那么返回节点所在的一层
            return Math.max(minDepth(root.left), minDepth(root.right)) + 1;
    }
}