前言
之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两天晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀
链表的合集
字符串
- 六六力扣刷题字符串之反转字符串
- 六六力扣刷题字符串之反转字符串2
- 六六力扣刷题字符串之替换空格
- 六六力扣刷题字符串之反转字符串中的单词
- 六六力扣刷题字符串之找出字符串中第一个匹配项的下
- 六六力扣刷题字符串之重复的子字符串
双指针
搜索二叉树
题目
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入： root = [3,9,20,null,null,15,7] 输出： [[3],[9,20],[15,7]]
示例 2：
输入： root = [1] 输出： [[1]]
示例 3：
输入： root = [] 输出： []
广度优先搜索
思路和算法
我们可以用广度优先搜索解决这个问题。
我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态，它表示某个节点和它所在的层数，每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类，分类的时候我们可以利用哈希表，维护一个以 level 为键，对应节点值组成的数组为值，广度优先搜索结束以后按键 level 从小到大取出所有值，组成答案返回即可。
考虑如何优化空间开销：如何不用哈希映射，并且只用一个变量 node 表示状态，实现这个功能呢？
我们可以用一种巧妙的方法修改广度优先搜索：
首先根元素入队 当队列不为空的时候 求当前队列的长度 s_is i
依次从队列中取 s_is i 个元素进行拓展，然后进入下一次迭代
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ret = new ArrayList<List<Integer>>(); if (root == null) { return ret; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { List<Integer> level = new ArrayList<Integer>(); int currentLevelSize = queue.size(); for (int i = 1; i <= currentLevelSize; ++i) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } ret.add(level); } return ret; } }
结束
- 首先根节点入队，当队列非空时，重复如下两步操作。
- 对头结点出队，并访问出对结点
- 出队结点的左、右孩子依次入队。
好了，今天就到这了，大家继续加油！冲冲冲！我是小六六，三天打鱼，两天晒网！
