前言

• 背景：算法与数据结构作为技术开发者最基本的技术修养，在日常开发出现的频率非常高
• 本文目的：花尽可能短的时间，快速学习常见的数据结构知识及算法
• 适用阅读人群：所有技术开发者

本文主要内容：

1. 常见、常考的数据结构知识
2. 结合每种数据结构给出常见 & 经典的算法题
3. 每个知识点 & 考题都会从题目知识考点、多种思路分析到手写代码整个过程进行详细解析

---

目录

---

基础知识

1. 数据结构是什么？

• 储备知识：数据的定义
• 定义
• 具体类型
• 核心内容

1.1 储备知识：数据是什么

1.2 定义

相互之间存在一种或多种关系的数据元素的集合。

1.3 具体类型

数据结构的具备类型包括2种：逻辑结构、物理结构。

1.4 核心学习内容

主要包括：

• 排序
• 线性表：数组、链表、栈与队列
• 树：含特殊的树，如二叉树、红黑树等
• 串：如字符串
• 查找
• 图

在后面的章节中，我会详细介绍上述数据结构。

---

2. 算法是什么？

• 定义
• 特点
• 算法设计要求
• 常见算法

2.1 定义

解决特定问题的求解步骤（在计算机中表现为多个指令 = 多个步骤操作）。

2.2 特点

• 可无输入，但一定有输出
• 步骤有限
• 确定性：每个步骤有确定含义、不会出现二义

2.3 算法设计要求

算法的设计需考虑以下性能要求：

• 可行性：即该算法是否 切实 能解决问题
• 健壮性：即该算法是否能全面解决问题，即 考虑、容纳所有异常逻辑，如输入是0、为空、长度不符合等
• 时间效率：即该算法是否能 快速 解决问题，此处采用 指标：时间复杂度 来衡量
• 空间效率：即运行该算法需耗费多少内存空间，此处采用 指标：空间复杂度 来衡量

时间复杂度、空间复杂度介绍如下：

---

常用数据结构及其算法应用

每类数据结构都会有对应的算法应用场景，具体如下：

---

具体说明

在下面的章节中，我会：

• 详细讲解每个算法的应用场景 & 对应经典算法题：知识考点 - 多种思路分析 - 图解算法 - 手写代码
• 旨在：手把手带你剖析常见的数据结构 & 对应经典算法题

排序

1. 简介

具体请看文章：算法总结：这是一份全面&详细的排序算法学习指南

2. 算法应用

• 最简单的排序算法：冒泡排序
• 数据量大时最该选择的算法：简单选择排序
• 不可不了解的排序算法：直接插入排序
• 复杂度最高的排序算法：希尔排序
• 数据量大时最该选择的算法：简单选择排序
• 内存占用最少的排序算法：堆排序
• 稳定性最高的排序算法：归并排序

---

查找

1. 简介

2. 算法应用

对于不同的查找需求场景，会采用不同的查找类型，最终采用的查找方式（查找算法）也有所不同，具体如下

具体请看文章：Carson带你学数据结构：图文详解 - 动态查找、静态查找、散列查找

---

线性表

线性表主要包括：数组、链表、栈与队列

1. 数组

1.1 简介

• 存储线性表的数据元素的方式 = 一段地址连续的存储单元
• 具备：起始位置、数组长度（最大存储容量） & 线性表长度（当前长度），具体如下：

概念	说明
数组长度	存放线性表的空间长度（固定不变）
线性表长度	存放线性表数据元素的长度（动态变化）
地址	存储单元的编号
数组下标	第 i 个元素 = 数组下标第 i-1 的位置

具体请看文章：Carson带你学数据结构：线性表-数组

1.2 算法应用

典型应用1：寻找出现特定次数的数字

• 数组中只出现1次的2个数字
• 数组中出现次数超过一半的数字
• 统计 数字在排序数组中出现的次数：二分法
• 数组中唯一出现1次的数字、其他都出现了3次

典型应用2：寻找符合特定条件的数字

• 数组中数值与下标相等的元素
• 获取数组中最小的k个数
• 排序数组中，0~n-1中缺失的数字
• 打印从1到最大的n位数：大数问题
• 数组中重复的数字（可修改 & 不可修改数组）

典型应用3：不同类型数组的查找

• 二维数组中的查找
• 找出旋转数组的最小数字

典型应用4：数组内元素的排列组合

• 数组所有滑动窗口的最大值
• 连续子数组的最大和
• 把数组的所有数排成最小的数：大数问题
• 数组中的逆序对
• 调整数组顺序，使奇数位于偶数前面

2. 链表

2.1 简介

具体请看文章：Carson带你学数据结构：链表

2.2 算法应用

典型应用1：寻找链表特定节点

• 链表中倒数第k个节点 / 中间节点
• 链表中环的入口节点
• 两个链表的第一个公共节点

典型应用2：复制 & 删除链表

• 删除链表的节点（重复 / 不重复）
• 复杂链表的复制

典型应用3：翻转、合并 & 打印链表

• 翻转链表
• 从尾到头打印链表
• 合并两个排序的链表

3. 栈与队列

3.1 简介

具体请看文章：Carson带你学数据结构：图文解析特殊的线性表 - 栈 & 队列

3.2 算法应用

典型应用1：互相转换

• 2个栈实现队列
• 2个队列实现栈

典型应用2：求最大、最小值

• 获取栈的最小值
• 获取队列的最大值

---

树

1. 简介

2. 存储结构

包括：双亲表示法、孩子表示法、孩子兄弟表示法，具体介绍如下图

3. 树的类型

具体请看文章：Carson带你学数据结构：手把手教你学习-树

主要应用是二叉树，所以下面主要介绍二叉树算法的应用

4. 算法应用

典型应用1：基础树遍历算法

• 前序遍历
• 前中序遍历
• 后序遍历
• 层序遍历

典型应用2：遍历应用

• 根据前序 & 中序重建二叉树
• 从上到下打印二叉树：不分行、分行 & 之字形
• 二叉树的深度
• 序列化二叉树
• 判断是不是某二叉搜索树的后序、前序遍历结果

典型应用3：二叉树结构判断

• 判断B是不是A的子树结构
• 判断 二叉树是否对称
• 判断二叉树是否相等

典型应用4：二叉树查找

• 树中两个节点的最低公共祖先
• 二叉搜索树最接近值查找
• 二叉树中和为某一值的路径
• 二叉搜索树的第k大节点
• 二叉树 中序遍历下一个节点

典型应用5：二叉树类型变式

• 二叉搜索树与双向链表
• 输出二叉树的镜像
• 平衡二叉树
  

---

串

1. 简介

2. 存储结构介绍

包括：顺序存储结构 & 链式存储结构

具体请看文章：Carson带你学数据结构：这是一份全面 & 详细的”串“讲解指南

3. 算法应用

典型应用1：字符串转换

• 把数字翻译成字符串
  
• 把字符串转换成整数
  

典型应用2：字符查找

• 第一个只出现一次的字符、字符流中第1个只出现1次的字符、删除1个字符串中的重复字符、删除2个字符串中的重复字符、变位数
  
• 最长不含重复字符的子字符串
  
• 替换 字符串中的空格
  
• 字符串的排列
  

典型应用3：字符串的排列组合

• 字符串的排列
  
• 字符串的组合 / 子集
  

典型应用4：字符串翻转

• 翻转字符串 之 翻转单词顺序
  
• 翻转字符串 之 左旋转字符串
  

典型应用5：字符串匹配判断

• 正则表达式匹配
  
• 判断1个字符串是否表示数值
  

---

图

1.1 简介

具体请看文章：Carson带你学数据结构：手把手带你了解 ”图“ 所有知识！(含DFS、BFS）

1.2 算法应用

典型应用1：基础遍历

• 广度遍历（DFS）
  
• 深度遍历（BFS）
  

典型应用2：最小生成树

• 普利姆算法（Prim）
  
• 克鲁斯卡尔算法（Kruskal）
  

典型应用3：最短路径

• 迪杰斯特拉算法（Dijkstra）
  
• 弗洛伊德算法（Floyd）
  

至此，关于常用的数据结构及典型算法解析已经讲解完毕。

---

总结

本文全面解析了数据结构及其对应常见算法，核心内容都已经记录在Github上：
https://github.com/Carson-Ho/AlgorithmLearning，感谢各位关注点赞。

• Carson带你学数据结构系列文章：
  Carson带你学数据：线性表-数组、链表
  Carson带你学数据：特殊的线性表-栈、队列
  Carson带你学数据：串
  Carson带你学数据：树
  Carson带你学数据：二叉树
  Carson带你学数据：图
  Carson带你学数据：查找

---

欢迎关注Carson_Ho的CSDN博客 ！

博客链接：https://carsonho.blog.csdn.net/

---

请点赞！因为你的鼓励是我写作的最大动力！

1、Z字形变换

6. Z 字形变换

	将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
	
	比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
	
	L   C   I   R
	E T O E S I I G
	E   D   H   N
	之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
	
	请你实现这个将字符串进行指定行数变换的函数：
	
	string convert(string s, int numRows);
	示例 1:
	
	输入: s = "LEETCODEISHIRING", numRows = 3
	输出: "LCIRETOESIIGEDHN"
	示例 2:
	
	输入: s = "LEETCODEISHIRING", numRows = 4
	输出: "LDREOEIIECIHNTSG"
	解释:
	
	L     D     R
	E   O E   I I
	E C   I H   N
	T     S     G

这个题目如果方法想对了就比较简单，如果想不对，那就很绕了。看到这个题目我们可能首先会想到找规律，不过，找规律并不是一件简单的事情，可能会带来很多麻烦。

这就需要我们转变思路，我们需要一层一层的剥开这个字符串。如果横着剥开，那就是数学法，找通项公式，如果竖着按列剥开，事情就简单了很多，我们在按列读取的时候，可以为每一行维护一个字符串，读到哪一行就在后面append字串。

判断在哪一行append字串的方式也很简单，我们设置两个边界，在增长到或者减小到某个边界的时候，读取行的顺序进行反转，不断地从上到下，再从下到上读取，直到取完所有字串。

按照上面的描述，我们就可以得到这样的代码,写的比较清晰了，不在多做解释。

   public String convert(String s, int numRows) {
        if(s==null||s.length()==0||numRows<=1||s.length()<numRows){
            return s;
        }
        StringBuilder[] sbs=new StringBuilder[numRows];
        for(int i=0;i<numRows;i++){
            sbs[i]=new StringBuilder();
        }
        int layer=0;
        boolean turn=false;
        for(int i=0;i<s.length();i++){
            if(!turn){
                sbs[layer++].append(s.charAt(i));
            }else{
                sbs[layer--].append(s.charAt(i));
            }
            if(layer==-1||layer==numRows){
                layer=layer==-1?1:layer-2;
                turn=!turn;
            }
        }
        StringBuilder result=new StringBuilder();
        for(StringBuilder sb:sbs){
            result.append(sb.toString());
        }
        return result.toString();
    }