acwhale / light-tips

一些碎片基础知识，厚积薄发 🔥

Light Tips

记录Web开发所需要的一些基础知识，主要是PHP、MySQL、Javascript相关内容，还有一些基础的算法和数据结构。

收藏请点star，如发现有错误欢迎PR

数据结构和算法

算法

• 排序

  • 简单排序
    1. 冒泡排序
    2. 插入排序
  • 希尔排序(插入排序的改进)
  • 选择排序
  • 堆排序(选择排序的改进)
  • 归并排序
  • 桶排序
  • 基数排序
  • 快速排序

• 搜索/查找

  • 线性搜索
  • 二分搜索
  • 插值搜索
  • 树表查找

算法	最快时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
冒泡排序	Ω(n)	Θ(n2)	O(n2)	O(1)	稳定
插入排序	Ω(n)	Θ(n2)	O(n2)	O(1)	稳定
希尔排序	Ω(nlogn)	Θ(n(log(n))2)	O(n(log(n))2)	O(1)	不稳定
选择排序	Ω(n2)	Θ(n2)	O(n2)	O(1)	不稳定
堆排序	Ω(nlogn)	Θ(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	Ω(nlogn)	Θ(nlogn)	O(nlogn)	O(n)	稳定
快速排序	Ω(nlogn)	Θ(nlogn)	O(nlogn)	O(logn)	不稳定
基数排序	Ω(n+b)	Θ(n+b)	O(n+b)	O(n+k)	稳定

O表示上界(小于等于)Ω表示下界(大于等于)Θ表示即是上界也是下界(等于)

数据结构

1. 链表

   • 双链表
   • 环形链表

2. 栈

   • 链表实现
   • 数组实现

3. 队列

   • 链表实现
   • 数组实现
   • 优先队列
   • 环形队列
   • 双端队列

4. 树

   • 二叉树
   • 二叉搜索树

5. 最大堆

   • 最小堆

6. 图

《剑指Offer》

先用PHP解答一遍，稍后Javascript版本的奉上

• 链表

  • 从头到尾打印链表
  • 链表中倒数第k个节点
  • 反转链表
  • 合并两个排序的链表
  • 复杂链表的复制
  • 删除链表中重复的节点
  • 两个链表的第一个公共节点
  • 链表中环的入口节点

• 栈和队列

  • 用两个栈来实现一个队列
  • 栈的压入、弹出序列

• 树

  • 重建二叉树
  • 树的子结构
  • 树的镜像
  • 从上往下打印二叉树
  • 二叉搜索树的后序序列
  • 二叉树中和为某一值的路径
  • 二叉搜索树与双向链表
  • 二叉树的深度
  • 平衡二叉树
  • 二叉树的下一个结点
  • 对称的二叉树
  • 按之字形顺序打印二叉树
  • 把二叉树打印成多行
  • 序列化二叉树
  • 二叉搜索树的第k个结点

PHP

新特性

1. PHP新特性之命名空间、性状和生成器
2. PHP新特性之闭包、匿名函数
3. PHP新特性之字节码缓存和内置服务器

最佳实践

1. PHP最佳实践系列之标准
2. PHP最佳实践之过滤、验证、转义和密码
3. PHP最佳实践之日期、时间和时区
4. PHP最佳实践之数据库
5. PHP最佳实践之多字节字符串、字符编码
6. PHP最佳实践之异常和错误
7. PHP最佳实践之上线准备

Javascript

1. Javascript引擎内部的三种抽象操作
2. 彻底弄懂Javascript闭包

MYSQL

1. MySQL索引相关问题总结