当前位置: 首页 > news >正文

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

http://www.lryc.cn/news/524696.html

相关文章:

  • uniapps使用HTML5的io模块拷贝文件目录
  • css‘s hover VS mobile
  • 工业制造离不开的BOM
  • HTML中的`<!DOCTYPE html>`是什么意思?
  • C语言之斗地主游戏
  • 【玩转全栈】----Django制作部门管理页面
  • Unreal Engine 5 C++ Advanced Action RPG 十章笔记
  • 学习ASP.NET Core的身份认证(基于JwtBearer的身份认证9)
  • 缓存之美:万文详解 Caffeine 实现原理(上)
  • Spark/Kafka
  • 深入浅出:Go语言中的Unicode与字符编码详解
  • 什么是SSL及SSL的工作流程
  • .Net Core微服务入门全纪录(二)——Consul-服务注册与发现(上)
  • AD7606, 逐次逼近型ADC以及一次被GPT坑了的过程.
  • 抬手、放手识别算法
  • 深度学习篇---AnacondaLabelImg
  • 探索云原生可观测性:技术与团队协作的深度结合
  • 解决 Django 5.1 中的 TemplateSyntaxError 错误
  • 基于SSM的自助购药小程序设计与实现(LW+源码+讲解)
  • 04JavaWeb——Maven-SpringBootWeb入门
  • 场馆预定平台高并发时间段预定实现V2
  • 如何利用边缘节点服务打造极致用户体验?
  • C语言之小型成绩管理系统
  • ASP.NET Core 中基于 Cookie 的身份鉴权实现
  • 为什么要学习C++?
  • freecad1.0的编译
  • 汇编与逆向(一)-汇编工具简介
  • .NET Framework
  • LabVIEW太赫兹二维扫描成像系统
  • 图片专栏——概念