Table of Contents generated with DocToc

• algorithm-in-go-and-c
  • 第一章 数据结构与算法
  • 第二章 算法
  • 第三章 LeetCode
  • 参考

algorithm-in-go-and-c

c 和 go 实现数据结构与算法

第一章 数据结构与算法

Note: C语言实现使用 GBK 编码

• 1 linear list 线性表

  • 1.1 顺序表 静态实现，数据元素是整数
  • 1.2 顺序表 静态实现，数据元素是结构体
  • 1.3 顺序表 动态实现，数据元素是整数
  • 1.4 顺序表 动态实现，数据元素是结构体

• 2 link list 链表

  • 2.1 带头结点的单链表的实现，数据元素是整数
  • 2.2 带头结点的单链表的实现，数据元素是结构体
  • 2.3 不带头结点的单链表的实现
  • 2.4 带头结点的双链表的实现，数据元素是整数
  • 2.5 带头结点的循环单链表的实现，数据元素是整数
  • 2.6 常见的考题

• 3 树

  • 3.1 二叉树的层次遍历
  • 3.2 二叉树的前序遍历、中序遍历和后序遍历，包括递归和非递归两种方法
  • 3.3 中序线索二叉树的创建及求前驱后继的方法
  • 3.4 二叉排序树的各种操作，包括插入、删除、查找
  • B 树-Google golang B-Tree 实现

• 4 图

  • 4.1 BFS (Breadth First Search 广度优先遍历）
  • 4.2 DFS (Depth First Search 深度优先搜索)
  • 4.3 单源最短路径算法(Floyd(弗洛伊德)算法)
  • 4.4 拓扑排序
  • 4.5 关键路径

• 5 hash 哈希表

• 6 queue 队列

  • 6.1 循环队列的数组实现，队尾指针指向队尾的下一个元素，没有length的辅助变量
  • 6.2 循环队列的数组实现，队尾指针指向队尾的下一个元素，增加了length的辅助变量
  • 6.3 循环队列的数组实现，队尾指针指向队尾元素，没有length的辅助变量
  • 6.4 循环队列的数组实现，队尾指针指向队尾元素，增加了length的辅助变量
  • 6.5 队列的链表实现（带头结点）

• 7 stack 栈

  • 7.1 顺序栈的实现，数据元素是整数
  • 7.2 链栈的实现，数据元素是整数
  • 7.3 顺序栈检查括号是否匹配，支持()[]{}三种括号
  • 7.4 用顺序栈实现中缀表达式转后缀表达式

• 8 排序算法

  • 8.1 冒泡排序
  • 8.2 桶排序
  • 8.3 计数排序
  • 8.4 堆排序
  • 8.5 插入排序
  • 8.6 归并排序
    • 递归的方法实现
    • 循环的方法实现
  • 8.7 快速排序
  • 8.8 基数排序
  • 8.9 选择排序
  • 8.10 希尔排序

• 9 数组和广义表

• 10 串

• 11 查找

  • 11.1 顺序查找
  • 11.1 二分查找

• 12 递归

第二章 算法

• 1 蛮力法 Exhausitive Attack
  • 51 n 皇后
• 2 分治法 Divide and Conquer
• 3 贪心法 Greedy Method
  • 46 跳跃游戏II
  • 55 跳跃游戏
  • 121 只有买和卖一次交易次数-->状态DP
  • 122 不限交易次数买卖股票-->状态DP
  • 123 买卖股票最多交易 2 次-->状态DP
  • 188 买卖股票最多交易 K 次
  • 309 冷冻期买卖股票
• 4 动态规划 dynamic programming
  • 70 爬楼梯
  • 72 编辑距离
  • 118 杨辉三角
  • 124 二叉树中的最大路径和
  • 198 打家劫舍
  • 300 最长递增子序列
  • 322 零钱兑换
  • 377 组合总和 Ⅳ
  • 494 目标和-->01背包转换
  • 516 最长回文子序列-->区间DP
  • 543 二叉树的直径-->树形DP
  • 583 两个字符串的删除操作
  • 687 最长同值路径-->树形DP
  • 746 使用最小花费爬楼梯
  • 1143 最长公共子序列

第三章 LeetCode

• 1 hash

  • 1 两数之和
  • 49 字母异位词分组
  • 128 最长连续序列
  • 1512 最长连续序列
  • 2441 与对应负数同时存在的最大正整数

• 2 链表

  • 2 两数相加
  • 11 盛最多水的容器-->双向指针
  • 15 三数之和-->相向指针
  • 19 删除链表的倒数第 N 个结点
  • 21 合并两个有序链表-->归并排序
  • 24 两两交换链表中的节点
  • 25 K个一组翻转链表
  • 61 旋转链表
  • 82 删除排序链表中的重复元素II
  • 83 删除排序链表中的重复元素
  • 92 反转链表II--中间部分反转
  • 125 验证回文串
  • 138 随机链表的复制
  • 141 环形链表-->快慢指针
  • 142 环形链表II-->快慢指针
  • 143 重排链表
  • 146 LRU 缓存
  • 148 排序链表
  • 160 相交链表
  • 167 两数之和 II 输入有序数组-->相向指针
  • 203 移除链表元素-->删除节点
  • 206 反转链表--中间部分反转
  • 234 回文链表
  • 237 删除链表中的节点
  • 283 移动零
  • 328 奇偶链表
  • 344 反转字符串
  • 445 两数相加 II
  • 876 链表的中间节点-->快慢指针
  • 1290 二进制链表转整数-->遍历链表
  • 1669 合并两个链表
  • 2058 找出临界点之间的最小和最大距离
  • 2130 链表最大孪生和
  • 2181 合并零之间的节点
  • 2487 从链表中移除节点
  • 2807 在链表中插入最大公约数-->插入节点
  • 2816 翻倍以链表形式表示的数字
  • 2824 统计和小于目标的下标对数目-->相向双指针
  • 3217 从链表中移除在数组中存在的节点

• 3 sliding windows 滑动窗口-->同向双指针

  • 03 无重复字符的最长子串-->不定长滑动窗口
  • 209 长度最小的子数组
  • 239 滑动窗口最大值-->单调队列
  • 438 找到字符串中所有字母异位词
  • 643 子数组最大平均数 I-->定长滑动窗口
  • 713 乘积小于 K 的子数组
  • 1004 最大连续1的个数 III
  • 1343 大小为 K 且平均值大于等于阈值的子数组数目
  • 1438 绝对差不超过限制的最长连续子数组
  • 1456 定长子串中元音的最大数目-->定长滑动窗口
  • 1493 删掉一个元素以后全为 1 的最长子数组
  • 2090 半径为 k 的子数组平均值
  • 2730 找到最长的半重复子字符串
  • 2779 数组的最大美丽值
  • 2958 最多 K 个重复元素的最长子数组-->不定长滑动窗口
  • 3090 每个字符最多出现两次的最长子字符串-->不定长滑动窗口

• 4 二分查找

  • 33 搜索旋转排序数组
  • 34 在排序数组中查找元素的第一个和最后一个位置
  • 35 搜索插入位置
  • 153 寻找旋转排序数组中的最小值
  • 154 寻找旋转排序数组中的最小值II
  • 162 寻找峰值
  • 275 H 指数 II-->求最大
  • 704 二分查找
  • 744 寻找比目标字母大的最小字母
  • 1283 使结果不超过阈值的最小除数-->求最小
  • 1901 寻找峰值II
  • 2187 完成旅途的最少时间->求最小
  • 2529 正整数和负整数的最大计数

• 5 binary tree 二叉树

  • 94 In-order Traversal 中序遍历
  • 98 验证二叉搜索树-->分别前序，中序，后序遍历方案
  • 100 相同的树
  • 101 对称二叉树
  • 102 二叉树的层序遍历
  • 103 二叉树的锯齿形层序遍历
  • 104 二叉树的最大深度
  • 105 从前序与中序遍历序列构造二叉树
  • 106 从中序与后序遍历序列构造二叉树
  • 107 二叉树的层序遍历 II
  • 108 将有序数组转换为二叉搜索树
  • 110 平衡二叉树
  • 111 二叉树的最小深度
  • 112 路径总和
  • 113 路径总和II
  • 114 二叉树展开为链表
  • 116 填充每个节点的下一个右侧节点指针
  • 129 求根节点到叶节点数字之和
  • 144 二叉树的前序遍历-->遍历二叉树
  • 199 二叉树右视图
  • 226 翻转二叉树
  • 230 二叉搜索树中第K小的元素
  • 235 二叉搜索树的最近公共祖先
  • 236 二叉树的最近公共祖先
  • 437 路径总和III-->前缀和+哈希表
  • 501 二叉搜索树中的众数
  • 513 找树左下角的值
  • 530 二叉搜索树的最小绝对差
  • 559 N 叉树的最大深度
  • 700 二叉搜索树中的搜索
  • 889 根据前序和后序遍历构造二叉树
  • 938 二叉搜索树的范围和
  • 951 翻转等价二叉树:选择任意节点，然后交换它的左子树和右子树
  • 1123 最深叶节点的最近公共祖先
  • 1302 层数最深叶子节点的和
  • 1609 奇偶树
  • 2476 二叉搜索树最近节点查询
  • 2583 二叉树中的第 K 大层和

• 6 backtracking 回溯

  • 17 电话号码的字母组合-->子集型回溯
  • 22 括号生成-->组合回溯
  • 39 组合总和
  • 46 全排列
  • 77 组合-->剪枝优化
  • 78 子集
  • 79 单词搜索-->剪枝优化
  • 93 复原 IP 地址-->剪枝优化
  • 131 分割回文串-->子集型回溯
  • 216 组合总和III-->剪枝优化
  • 257 二叉树的所有路径
  • 306 累加数
  • 679 24 点游戏
  • 784 字母大小写全排列

• 7 栈

  • 20 有效的括号
  • 42 接雨水
  • 155 最小栈-->前缀最小值
  • 394 字符串解码
  • 496 下一个更大元素 I: nums1 是 nums2 的子集
  • 503 下一个更大元素 II: 循环数组
  • 739 每日温度

• 8 数组

  • 53 最大子数组和-->前缀和
  • 56 合并区间
  • 75 颜色分类
  • 136 只出现一次的数字-->位运算
  • 136 多数元素-->摩尔投票法
  • 189 轮转数组
  • 238 除自身以外数组的乘积->前后缀
  • 303 区域和检索-数组不可变-->前缀和
  • 560 和为 K 的子数组-->前缀和
  • 1094 拼车-->差分数组
  • 2848 与车相交的点-->差分数组
  • 3427 变长子数组求和 -->前缀和

• 9 图

  • 200 岛屿数量
  • 207 课程表-->拓扑排序
  • 208 实现 Trie (前缀树)
  • 210 课程表II-->拓扑排序
  • 695 岛屿的最大面积-->网格图 DFS
  • 994 总价值可以被 K 整除的岛屿数目
  • 3619 岛屿数量-->网格图 DFS

• 10 堆

  • 315 数组中的第K个最大元素
  • 347 前 K 个高频元素

• 11 矩阵

  • 48 旋转图像
  • 73 矩阵置零

• 12 位运算

  • 461 汉明距离
  • 1356 根据数字二进制下 1 的数目排序
  • 3226 使两个整数相等的位更改次数
  • 3370 仅含置位位的最小整数

参考

• The Algorithms 组织开源的多种语言算法实现