织梦网站如何更新系统,第三方公司做网站价格,免费自助建站哪个最好,宁波外发加工网阿华代码#xff0c;不是逆风#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力#xff01;#xff01; 希望本文内容能够帮助到你#xff01;#xff01; 目录
零#xff1a;集合#xff0c;队列的用法
一#xff1a;字母异位词分组
二#xff1a;二叉树的锯… 阿华代码不是逆风就是我疯 你们的点赞收藏是我前进最大的动力 希望本文内容能够帮助到你 目录
零集合队列的用法
一字母异位词分组
二二叉树的锯齿形层序遍历
三二叉树的最大宽度
四在每个树行中找最大值 零集合队列的用法
1new 一个队列
Queue queue new LinkedList();
2入队
queue.add();
3出队
queue.poll();
4队列的大小
queue.size();常用于for循环用foreach循环也能达到目的
一字母异位词分组
49. 字母异位词分组 class Solution {public ListListString groupAnagrams(String[] strs) {ListListString lists new ArrayListListString();MapString , ListString 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{//不包含ListString list new ArrayList();list.add(curStr);map.put(change,list);}}for(Map.EntryString,ListString 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 ListListInteger zigzagLevelOrder(TreeNode root) {// 思路沿用基础的模版添加一个标志符用于逆序谁逆序队列里的元素逆序ListListInteger lists new ArrayList();if (root null)return lists;QueueTreeNode queue new LinkedList();queue.add(root);Boolean sign true;while (!queue.isEmpty()) {ListInteger 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引进的
3Pair的用法 .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) {// 先把根节点入队ListPairTreeNode, Integer q new ArrayList();q.add(new Pair(root, 1));int ret 0; // 存储最终结果while (!q.isEmpty()) {// 先更新一下结果// 获取这一层的队头和队尾PairTreeNode, Integer t1 q.get(0);PairTreeNode, Integer t2 q.get(q.size() - 1);ret Math.max(ret, t2.getValue() - t1.getValue()1);// 然后遍历下一层把它们的孩子放进新的队列进行覆盖ListPairTreeNode, Integer tem new ArrayList();for(PairTreeNode,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*index1));}}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 ListInteger largestValues(TreeNode root) {ListInteger list new ArrayList();QueueTreeNode queue new LinkedList();if(root null) return list;queue.add(root);while (!queue.isEmpty()) {int num Integer.MIN_VALUE;QueueTreeNode 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 ListString summaryRanges(int[] nums) {int n nums.length;ListString list new ArrayList();int i 0 ; for(; i n ;i){int start nums[i];while(i 1 n nums[i1] - nums[i] 1){i;}if(i 1 n - 1 nums[i1] - 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;}
}
