Data Structure and Algorithmic Practice

【任务1 - 数组与链表】

1、数组

• 实现一个支持动态扩容的数组
• 实现一个大小固定的有序数组，支持动态增删改操作
• 实现两个有序数组合并为一个有序数组
• 学习哈希表思想，并完成leetcode上的两数之和(1)及Happy Number(202)！(要求全部用哈希思想实现！)

2、链表 实现单链表、循环链表、双向链表

• 支持增删操作
• 实现单链表反转
• 实现两个有序的链表合并为一个有序链表
• 实现求链表的中间结点

实现：assignment1

【任务2 - 栈、队列与递归】

1、栈

• 用数组实现一个顺序栈
• 用链表实现一个链式栈
• 编程模拟实现一个浏览器的前进、后退功能

2、队列

• 用数组实现一个顺序队列
• 用链表实现一个链式队列
• 实现一个循环队列

3、递归

• 编程实现斐波那契数列求值f(n)=f(n-1)+f(n-2)
• 编程实现求阶乘n!
• 编程实现一组数据集合的全排列

实现：assignment2

【任务3-排序与二分查找】

1、排序

• 实现归并排序、快速排序、插入排序、冒泡排序、选择排序、希尔排序、堆排序、计数排序、桶排序和基数排序
• 完成leetcode上的返回滑动窗口中的最大值(239)
• 编程实现 O(n) 时间复杂度内找到一组数据的第 K 大元素

2、二分查找

• 实现一个有序数组的二分查找算法
• 实现模糊二分查找算法（比如大于等于给定值的第一个元素）

实现：assignment3

【任务4- 散列表（哈希表）和字符串】

1、哈希表

• 实现一个基于链表法解决冲突问题的散列表
• 实现一个LRU缓存淘汰算法

2、字符串

• 实现一个字符集，只包含a～z这26个英文字母的Trie树
• 实现朴素的字符串匹配算法

实现：assignment4

【任务5-二叉树和堆】

1、二叉树

• 实现一个二叉查找树，并且支持插入、删除、查找操作
• 实现查找二叉查找树中某个节点的后继、前驱节点
• 实现二叉树前、中、后序以及按层遍历
• 完成leetcode上的验证二叉搜索树(98)及二叉树层次遍历(102,107)！（选做）

2、堆

• 实现一个小顶堆、大顶堆、优先级队列
• 实现堆排序
• 利用优先级队列合并K个有序数组
• 求一组动态数据集合的最大Top K（选做）
• 第三天堆排序学习（复习）

3、竞赛树、搜索树和平衡二叉搜索树

• 实现赢者树的创建和比赛
• 实现二叉搜索树的创建，以及增、删、改、查等功能，实现二叉搜索树的升序输出（中序遍历）
• 实现AVL、红-黑、B/B+平衡搜索树的增、删、改、查等功能，实现二叉搜索树的升序输出（中序遍历）

实现：assignment5

【任务6-图】

1、图

• 实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法
• 实现图的深度优先搜索、广度优先搜索
• 实现 Dijkstra算法、Bellman-Ford算法、SPFA算法、Floyd-Warshall算法和A*
• 实现图的最小生成树Prim算法（适合稠密图）、Kruskal算法（适合稀疏图）
• 实现拓扑排序的 Kahn 算法、DFS 算法

实现：assignment6

【任务7-递归、回溯、分治和动态规划】

1、递归

• 通过LeetCode上【70. 爬楼梯】（见任务2递归实现）

2、回溯

• 利用回溯算法求解八皇后问题
• 利用回溯算法求解0-1背包问题

3、分治

• 利用分治算法求一组数据的逆序对个数

4、动态规划

• 0-1背包问题
• 最小路径和（详细可看Minimum Path Sum）
• 编程实现莱文斯坦最短编辑距离
• 编程实现查找两个字符串的最长公共子序列
• 编程实现一个数据序列的最长递增子序列

实现：assignment7