【算法】集合List和队列

 

阿华代码，不是逆风，就是我疯

你们的点赞收藏是我前进最大的动力！！

希望本文内容能够帮助到你！！

目录

零：集合，队列的用法

一：字母异位词分组

二：二叉树的锯齿形层序遍历

三：二叉树的最大宽度

四：在每个树行中找最大值

零：集合，队列的用法

1：new 一个队列

Queue<> queue = new LinkedList<>();

2：入队

queue.add();

3：出队

queue.poll();

4：队列的大小

queue.size();常用于for循环，用foreach循环也能达到目的

一：字母异位词分组

49. 字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> lists = new ArrayList<List<String>>();
        Map<String , List<String>> map = new HashMap<>();

        for(int i = 0 ; i < strs.length ; i++){
            String curStr = strs[i];
            String change = sort(strs[i]);
            if(map.containsKey(change)){
                //包含
                map.get(change).add(curStr);
            }else{
                //不包含
                List<String> list = new ArrayList<>();
                list.add(curStr);
                map.put(change,list);
            }
        }
        for(Map.Entry<String,List<String>> entry : map.entrySet()){
            lists.add(entry.getValue());
        }
        return lists;

    }

    //给字符串排序
    public String sort(String s){
        char[] ch = s.toCharArray();
        Arrays.sort(ch);
        return String.valueOf(ch);
    }
}

二：二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历

心得：

1：集合在反转的时候返回类型为void，不能因为偷懒写成lists.add(Collections.reverse(list));

2：在判定当前节点的val是否入集合，和孩子节点是否入队列时。干脆全都判断一下是否为null，当然有更简洁的写法，这里求稳

3：队列判断空，用的是.isEmpty();  不是null！！！

4：集合翻转用的是Collections.reverse();

5：这里的标志符sign也可以使用int类型，模2判断奇偶

/**
 * 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 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 思路沿用基础的模版，添加一个标志符用于逆序，谁逆序队列里的元素逆序
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null)
            return lists;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        Boolean sign = true;

        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 让对头元素的val值进入集合，再让该元素的左右孩子入队
                TreeNode curNode = queue.poll();

                if (curNode != null) {
                    list.add(curNode.val);
                }
                if (curNode.left != null) queue.add(curNode.left);
                if (curNode.right != null) queue.add(curNode.right);
            }
            if (sign == true) {
                lists.add(list);
                sign = false;
            } else {
                Collections.reverse(list);
                lists.add(list);
                sign = true;
            }
        }
        return lists;
    }
}

三：二叉树的最大宽度

662. 二叉树最大宽度

心得：

1：用集合来模拟队列

因为有些队列的容器只能查到队头，查不到队尾，使用集合可以很容易计算出该层的宽度

2：新认识一个类型Pair<>类型，可以将两个无关联的类型数据联系在一起

这是java8引进的

3：Pair的用法  .getKey() , .getValue() 通常搭配遍历来使用，这道题暴力解法会溢出

/**
 * 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;
 * }
 * }
 */

// 使用Pair 类型标识节点+下标
// 使用层序遍历的方式，但是使用集合的形式模拟队列
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        // 先把根节点入队
        List<Pair<TreeNode, Integer>> q = new ArrayList<>();
        q.add(new Pair<>(root, 1));

        int ret = 0; // 存储最终结果

        while (!q.isEmpty()) {
            // 先更新一下结果
            // 获取这一层的队头和队尾
            Pair<TreeNode, Integer> t1 = q.get(0);
            Pair<TreeNode, Integer> t2 = q.get(q.size() - 1);
            ret = Math.max(ret, t2.getValue() - t1.getValue()+1);

            // 然后遍历下一层把它们的孩子放进新的队列，进行覆盖
            List<Pair<TreeNode, Integer>> tem = new ArrayList<>();
            for(Pair<TreeNode,Integer> t : q){
                //获取当前层的当前节点
                TreeNode node = t.getKey();
                Integer index = t.getValue();
                if(node.left != null){
                    tem.add(new Pair<>(node.left,2*index));
                }
                if(node.right != null){
                    tem.add(new Pair<>(node.right,2*index+1));
                }
            }
            q = tem;
        }
        return ret;

    }
}

四：在每个树行中找最大值

515. 在每个树行中找最大值

/**
 * 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 {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) return list;
        queue.add(root);

        while (!queue.isEmpty()) {
            int num = Integer.MIN_VALUE;
            Queue<TreeNode> q = new LinkedList<>();
            for (TreeNode node : queue) {
                if (node != null) {
                    num = Math.max(num, node.val);
                    if (node.left != null) {
                        q.add(node.left);
                    }
                    if (node.right != null) {
                        q.add(node.right);
                    }
                }

            }
            list.add(num);
            queue = q;
        }
        return list;
    }
}