学习日记4.22-4.26

2022.4.22 1、链表刷题：

• 面试题 02.07. 链表相交
• 142. 环形链表 II（还没刷完）

2、哈希表刷题：

• 242. 有效的字母异位词 数组
• 349. 两个数组的交集 HashSet
• 202. 快乐数 HashSet
• 1. 两数之和 HashMap
• 454. 四数相加 II HashMap
  1和454都是用目标数与某数相减的值代入HashMap中。

理论知识：哈希表理论基础 总结：

• 一般来说哈希表都是用来快速判断一个元素是否出现集合里。
• 对于哈希表，要知道哈希函数和哈希碰撞在哈希表中的作用.
  哈希函数是把传入的key映射到符号表的索引上。
  哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。
• 三种哈希结构：
  • 数组
  • HashSet
  • HashMap
• 什么时候使用数组做哈希表？ 数组就是简单的哈希表，但是数组的大小是受限的！题目包含小写字母，那么使用数组来做哈希最合适不过。
• 什么时候使用HashSet做哈希表？ 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。那就考虑HashSet。
• 什么时候使用HashMap做哈希表？ 同时存放两个元素，且两个元素有对应关系。

3、二叉树刷题：

二叉树的递归遍历三要素：
1、确定递归函数的参数和返回值
2、确定终止条件
3、确定单层递归的逻辑

• 144. 二叉树的前序遍历
• 94. 二叉树的中序遍历
• 145. 二叉树的后序遍历

理论知识： 二叉树基础篇 ：

• 二叉树（没有值）
  • 满二叉树
  • 完全二叉树
• 二叉搜索树（有序树）
  • 平衡二叉搜索树（它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。）
• 二叉树的存储方式（一般用链式存储）
  • 链式存储
  • 顺序存储
• 二叉树的遍历方式
  • 深度优先遍历（先往深走，遇到叶子节点再往回走）
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
      
  • 广度优先遍历 （一层一层的去遍历）
    • 层次遍历（迭代法）
• 节点定义：（TreeNode）

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;
   }
}

2022.4.24 星期天 1、字符串刷题：

344. 反转字符串
541. 反转字符串 II
1、法1：用StringBuffer方法 (可以直接用类中的reverse方法)
2、法2：用数组方法 （将字符串转char数组、s.toCharArray()）
剑指 Offer 05. 替换空格
1、法1：使用辅助数组（对于很多数组填充问题）
2、法2：扩容，大小为带填充后的大小，然后在从后向前进行 *** 作。（good！）
总结：要么变字符串数组，要么用StringBuilder。

2022.4.25 星期一

上午 字符串刷完
下午 +晚上 双指针
晚上 回溯
字符串刷完，
双指针刷完，
栈与队列
二叉树
回溯