零：集合，队列的用法1：new 一个队列
Queue<> queue = new LinkedList<>();
2：入队
queue.add();
3：出队
queue.poll();
4：队列的大小
queue.size();常用于for循环，用foreach循环也能达到目的
一：字母异位词分组49. 字母异位词分组
代码语言：javascript复制class Solution {
public List
List
Map
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
list.add(curStr);
map.put(change,list);
}
}
for(Map.Entry
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判断奇偶
代码语言：javascript复制/**
* 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
if (root == null)
return lists;
Queue
queue.add(root);
Boolean sign = true;
while (!queue.isEmpty()) {
List
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() 通常搭配遍历来使用，这道题暴力解法会溢出
代码语言：javascript复制/**
* 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
q.add(new Pair<>(root, 1));
int ret = 0; // 存储最终结果
while (!q.isEmpty()) {
// 先更新一下结果
// 获取这一层的队头和队尾
Pair
Pair
ret = Math.max(ret, t2.getValue() - t1.getValue()+1);
// 然后遍历下一层把它们的孩子放进新的队列，进行覆盖
List
for(Pair
//获取当前层的当前节点
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. 在每个树行中找最大值
代码语言：javascript复制/**
* 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
Queue
if(root == null) return list;
queue.add(root);
while (!queue.isEmpty()) {
int num = Integer.MIN_VALUE;
Queue
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尾追的时候，支持很多类型！！！！
代码语言：javascript复制class Solution {
public List
int n = nums.length;
List
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;
}
}