AlgorithmicPractice

本篇是关于LeetCode算法练习的总结(题目主要来源于剑指offer)，内容划分为以下章节：

注:
main.cpp展示测试效果;

一.基础数据结构

1.1 字符串

序号	题目(解答链接)	LeetCode(原题链接)
1	Implement strStr()	实现 strStr()
2	Reverse String	反转字符串
3	Reverse Words in a String	翻转字符串里的单词
4	String to Integer (atoi)	字符串转换整数 (atoi)
5	First Unique Character in a String	字符串中的第一个唯一字符
6	Add Binary	二进制求和
7	Longest Substring Without Repeating Characters	无重复字符的最长子串
8	II. Left rotate string	II. 左旋转字符串
9	Rotate String	旋转字符串
10	Replace spaces	替换空格

1.2 数组

序号	题目(解答链接)	LeetCode(原题链接)
1	Remove Duplicates from Sorted Array	删除排序数组中的重复项
2	Median of Two Sorted Arrays	寻找两个正序数组的中位数
3	Merge Sorted Array	合并两个有序数组
4	3sum	三数之和
5	Majority Element	多数元素
6	Search A 2d Matrix Ⅱ	搜索二维矩阵 II
7	Find First And Last Position Of Element In Sorted Array	在排序数组中查找元素的第一个和最后一个位置
8	Spiral Matrix	螺旋矩阵

二.链表

序号	题目(解答链接)	LeetCode(原题链接)
1	Reverse Linked List	反转链表
2	Add Two Numbers	两数相加
3	Linked List Cycle	环形链表
4	Merge Two Sorted Lists	合并两个有序链表
5	Remove Nth Node From End of List	删除链表的倒数第N个节点
6	Middle of the Linked List	链表的中间结点
7	Design Linked List	设计链表
8	Delete The Node Of The Linked List	删除链表的节点
9	The K-th Last Node In The Linked List	链表中倒数第k个节点
10	Intersection Of Two Linked Lists	相交链表
11	Copy List With Random Pointer	复制带随机指针的链表
12	reverse nodes in k group	K 个一组翻转链表

三.栈和队列

序号	题目(解答链接)	LeetCode(原题链接)
1	Valid Parentheses	有效的括号
2	Longest Valid Parentheses	最长有效括号
3	Evaluate Reverse Polish Notation	逆波兰表达式求值
4	Design Circular Deque	设计循环双端队列
5	Implement queue with two stacks	用两个栈实现队列
6	Min Stack	最小栈
7	Validate Stack Sequences	验证栈序列

四.二叉树

序号	题目(解答链接)	LeetCode(原题链接)
1	Maximum Depth of Binary Tree	二叉树的最大深度
2	Invert Binary Tree	翻转二叉树
3	Balanced Binary Tree	平衡二叉树
4	Symmetric Tree	对称二叉树
5	Same Tree	相同的树
6	Binary Tree Preorder Traversal	二叉树的前序遍历
7	Binary Tree Inorder Traversal	二叉树的中序遍历
8	Binary Tree Postorder Traversal	二叉树的后序遍历
9	Binary Tree Level Order Traversal II	二叉树的层次遍历
10	Balidate Binary Search Tree	验证二叉搜索树(BST)
11	Path Sum	路径总和
12	Path Sum II	路径总和 II
13	Tree substructure	树的子结构
14	Lowest Common Ancestor Of A Binary Tree	二叉树的最近公共祖先
15	The k-th largest node of the binary search tree	二叉搜索树的第k大节点
16	Serialize And Deserialize Binary Tree	二叉树的序列化与反序列化
17	Postorder traversal sequence of binary search tree	二叉搜索树的后序遍历序列
18	check completeness of a binary tree	二叉树的完全性检验
19	diameter of binary tree	二叉树的直径

五.排序

5.1 排序

序号	题目(解答链接)	LeetCode(原题链接)
1	Kth Largest Element in an Array	数组中的第K个最大元素
2	Sort List	排序链表
3	Reverse pair in array	数组中的逆序对

5.2 排序算法

序号	排序(示例链接)
1	冒泡排序
2	选择排序
3	插入排序
4	希尔排序
5	快速排序
6	归并排序
7	堆排序

六.二分查找

序号	题目(解答链接)	LeetCode(原题链接)
1	Sqrt(x)	x 的平方根
2	Numbers missing from 0 to n-1	0～n-1中缺失的数字
3	Find Minimum In Rotated Sorted Array	寻找旋转排序数组中的最小值
4	Find First and Last Position of Element in Sorted Array	在排序数组中查找元素的第一个和最后一个位置 II

七.动态规划

序号	题目(解答链接)	LeetCode(原题链接)
1	Climbing Stairs	爬楼梯
2	Unique Paths	不同路径
3	Maximum Subarray	最大子序和
4	Best Time to Buy and Sell Stock	买卖股票的最佳时机
5	The greatest value of gifts	礼物的最大价值
6	Word Search	单词搜索
7	Integer Break	整数拆分
8	Regular Expression Matching	正则表达式匹配
9	n dice points	n个骰子的点数

八.哈希表

序号	题目(解答链接)	LeetCode(原题链接)
1	Two Sum	两数之和
2	The first character that appears only once	第一个只出现一次的字符
3	Repeating numbers in the array	数组中重复的数字

九.其他

9.1 滑动窗口

序号	题目(解答链接)	LeetCode(原题链接)
1	Sliding Window Maximum	滑动窗口最大值
2	The maximum value of the queue	队列的最大值
3	And is a sequence of consecutive positive Numbers for S	和为s的连续正数序列

9.2 递归

序号	题目(解答链接)	LeetCode(原题链接)
1	Fibonacci Number	斐波那契数
2	Construct Binary Tree From Preorder And Inorder Traversal	从前序与中序遍历序列构造二叉树
3	Powx N	Pow(x, n)

9.3 回朔算法

序号	题目(解答链接)	LeetCode(原题链接)
1	Arrangement of strings	字符串的排列
2	Robot's range of motion	机器人的运动范围

9.4 分治算法

序号	题目(解答链接)	LeetCode(原题链接)
1	The smallest k number	最小的k个数
2	Majority Element	多数元素
3	convert binary search tree to sorted doubly linked list	二叉搜索树与双向链表

9.5 堆

序号	题目(解答链接)	LeetCode(原题链接)
1	Find Median From Data Stream	数据流的中位数

十.数学

10.1 位运算

序号	题目(解答链接)	LeetCode(原题链接)
1	Number Of 1 Bits	位1的个数
2	No addition, subtraction, multiplication and division	不用加减乘除做加法
3	Number of occurrences of numbers in the array	数组中数字出现的次数
4	Number of occurrences of numbers in the array II	数组中数字出现的次数 II

10.2 其他

序号	题目(解答链接)	LeetCode(原题链接)
1	Valid Number	有效数字
2	Nth Digit	第N个数字
3	Print n digits from 1 to maximum	打印从1到最大的n位数
4	Ugly Number II	丑数 II
5	Number Of Digit One	数字 1 的个数
6	Adjust the array order so that odd numbers are in front of even numbers	调整数组顺序使奇数位于偶数前面
7	Find 1+2+...+n	求1+2+…+n
8	And two numbers for s	和为s的两个数字
9	The last number left in the circle	圆圈中最后剩下的数字
10	Straight in playing cards	扑克牌中的顺子
11	Translate numbers into strings	把数字翻译成字符串
12	Build product array	构建乘积数组
13	LRU Cache	LRU缓存
14	LFU Cache	LFU缓存
15	Largest rectangle in histogram	柱状图中最大的矩形

热门题型练习

序号	LeetCode(题目链接)	备注	题解
1	反转链表
2	二叉树的最近公共祖先	-2
3	环形链表 II	-1
4	最大子序和	-2
5	合并两个有序链表
6	数组中的第K个最大元素
7	二叉树的前序遍历	1
8	K个一组翻转链表	:2
9	用两个栈实现队列	-1
10	相交链表	-2
11	LRU缓存机制	-2
12	买卖股票的最佳时机	:1
13	二叉树的完全性检验	:2
14	反转字符串
15	二叉树的层次遍历
16	二叉树的直径	-2
17	翻转二叉树	-1
18	两数之和	-1
19	无重复字符的最长子串	-1
20	分隔链表	-2	题解
21	旋转数组	-1	题解
22	路径总和 II	-1
23	翻转字符串里的单词	-1
24	字符串解码	-2	题解
25	爬楼梯	-1
26	螺旋矩阵	-1
27	LFU缓存	-2
28	x 的平方根	-1	题解
29	零钱兑换	-2	题解

---

知识点

1. 算法知识

• 单调栈,单调队列和优先队列
• 散列表(哈希表)
• 字符串匹配(BF/RK/BM/KMP/Trie树/AC自动机)
• 树(AVL/红黑树/B/B+/2-3/堆/堆排序)
• 图(关键路径/最小生成树/最短路径/拓扑排序)
• 其他(跳表/并查集/BitMap/Bloom filter/LRU)

TODO:

• 基本算法思想(贪心/回溯/分治/动态规划)

2. 算法问题处理

• 海量数据处理

3. 算法知识收藏

• 算法知识收藏(blog/img/pdf)

---

附:

1. 性能对比图

• 如果需要经常添加或删除结点，链表可能是一个不错的选择。
• 如果需要经常按索引访问元素，数组可能是比链表更好的选择。

2. 十大排序算法比较图

3. 算法知识体系图

4. 常用算法时间复杂度