【算法】集合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;}
}

五： 汇总区间

228. 汇总区间

感悟：最讨厌边界问题了，呕！！！~~~干就完了

然后就是StringBuilder尾追的时候，支持很多类型！！！！

class Solution {public List<String> summaryRanges(int[] nums) {int n = nums.length;List<String> list = new ArrayList<>();int i = 0 ; for(; i < n ;i++){int start = nums[i];while(i + 1 < n && nums[i+1] - nums[i] == 1){i++;}if(i + 1 == n - 1 && nums[i+1] - nums[i] == 1){i = n-1;}int end = nums[i];StringBuilder builder = new StringBuilder();if(start != end){builder.append(start);builder.append("->");builder.append(end);}else{builder.append(start);}list.add(builder.toString());}if(i == n-1){int last = nums[n-1];StringBuilder builder = new StringBuilder();builder.append(last);list.add(builder.toString());return list;}return list;}
}