Leetcode-剑指Offer-Log-0
Day 1. 栈与队列 ( Easy )
剑指 Offer 09. 用两个栈实现队列
栈的特点是后进后出，队列是先进后出。使用双栈相当于使用其中一个栈作为暂存的区域，来实现队列的功能。
剑指 Offer 30. 包含min函数的栈
题目要求：实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
考虑栈后入先出的特点，解题思路是，在入栈时，每个元素添加一个额外属性：当前最小值。
Day 2. 链表 ( Easy )
剑指 Offer 06. 从尾到头打印链表
两种思路：
辅助栈。利用栈后进先出的特性，额外开辟一个栈暂存链表数据，出栈时即为逆序。
递归。利用递归，先走到链表结尾，回溯时依次将值加入到队列中。
代码：
vector<int> reversePrint(ListNode* head){
if(!head) return {};
int val = head->val;
vector<int> ret = reversePrint(head->next);
ret.push_back(val);
return ret;
}
粗暴法。顺序保存，用algorithm库直接reverse。
剑指 Offer 24. 反转链表
数据结构入门题目。三种基本解法。
迭代法。使用双指针。设置一个cur指针指示当前所在位置，一个pre指针指向前一个节点。
初始状态下，cur指向的是head节点，pre指向NULL。
迭代过程中，先暂存cur->next所指向的节点为temp，将cur->next指向pre，再将pre更新为cur，cur更新为temp，完成翻转。
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while(cur){
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
辅助栈法。先遍历链表，保存value到栈中，再依次出栈，重新为链表赋值。
递归法。核心思想是，对于当前节点cur，将下一个节点cu r->next为头节点的链表进行翻转，然后将cur->next节点的next指针指向cur，完成翻转。
需要注意三个情况，（1）输入为NULL时，直接返回head（2）处理head节点时，head->next在反转后最后应该为NULL（3）最后需要返回反转后的新的头节点。
ListNode* reverseList(ListNode* head) {
if(!head || !head->next ) return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
剑指 Offer 35. 复杂链表的复制
该题关键在于如何记录原链表和新链表的节点对应关系。直观解法是使用哈希，即Map。
哈希表法。空间复杂度为O(n)，时间复杂度为O(n)，遍历两遍原链表。
原地复制。首先将每个节点复制一遍，添加到原有节点之后，如1->2->3->NULL复制为1->1->2->2->3->3->NULL；从头开始遍历链表，将random指针指向对应节点或NULL；将链表拆分。该方法可以将空间复杂度降低为O(1)。
Day 3. 字符串 ( Easy )
剑指 Offer 05. 替换空格
使用string API操作，可以使用find、erase、insert原地操作；也可以遍历操作，新建字符串，使用append。
一定要用时间复杂度为O(n)。
可以使用双指针，用vector。
可以使用array数组，第一遍遍历确定空格数量，确定新数组的长度，第二遍遍历就可以直接复制给新数组。
从前往后遍历替换会导致元素被覆盖，则可以考虑从后往前遍历。
剑指 Offer 58 - II. 左旋转字符串
使用string API操作，则使用substr获取子串。
原地反转。思路是先反转n以前的子串，再反转n以后的子串，最后反转整个子串，可以得到一个拼接后的子串。问题化简为三个字符串反转问题。
原地字符串反转，使用双指针解法。
class Solution {
public:
void reverseString(string &s, int i, int j){
while(i < j){
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
i++;j--;
}
}
string reverseLeftWords(string s, int n) {
reverseString(s, 0, n-1);
reverseString(s, n, s.length()-1);
reverseString(s, 0, s.length()-1);
return s;
}
};
Day 4. 查找算法 ( Easy )
剑指 Offer 03. 数组中重复的数字
最直接思路是利用哈希表，C++中使用map。时间复杂度O(n)，空间复杂度也为O(n)。
排序后遍历。先原地排序（如堆排序），若相邻元素相同，则return。
原地交换。题干中指明，所有数字都在 0～n-1 的范围内，数组索引和值是一对多的关系，因此可以通过交换值，使得数组的索引和值达到对应。即
若nums[i] = i，则继续下一个i；
若nums[i] = nums[nums[i]]，说明有两个索引指向同一个值，找到该值；
否则交换nums[i]和nums[nums[i]]的值，这一步的最终必然可以将值换到与索引匹配的位置，或者找到重复值。
时间复杂度为O(n)，空间复杂度为O(1)。
剑指 Offer 53 - I. 在排序数组中查找数字 I
在有序数组中查找数字出现次数，明显可以用二分查找法。
可以通过二分查找找到第一个出现的数字，也可以直接使用二分查找确定左右范围。
剑指 Offer 53 - II. 0～n-1中缺失的数字
同样使用二分查找。需要注意，二分查找要点在于边界值判断、循环条件判断，并且两者需要匹配。例如，left和right值如果存在不更新，直接等于mid的情况，那么while条件需要设置为不包括left=right。
Day 5. 查找算法 (Medium)
⭐️ 剑指 Offer 04. 二维数组中的查找
一开始以为要用二分查找，但发现并不适用，并且会超时。
参考评论后，可以从矩阵右上角开始看，可以发现矩阵分布规律，类似一个二叉搜索树。
因此可以设置row和col，从右上角开始，若当前val大于target，则向二叉树的左子树，即col–；若val小于target，则row++；否则返回。
需要注意可能有输入为空数组的情况。
剑指 Offer 11. 旋转数组的最小数字
简单题做法是，直接遍历查找，时间复杂度是O(n)。
进阶做法，将时间复杂度降低为O(logN)。使用二分查找。
指针left、right分别指向头和尾，中间为mid。分以下情况，注意开闭区间：
- 若mid大于right，说明最小值必在(mid,right]之间，因此取left=mid+1；
- 若mid小于right，说明最小值在[left, mid]之间，因此取right=mid；
- 若mid和right相等，则说明(mid, right]中间的值有重复的，需要去重，但无法确定中间是否会存在更小值，如[1,1,1,1,0,1,1,]，因此需要right–。
为什么不和left比较呢？因为旋转数组的特征是，右边一定比左边小。若考虑与left比较：
-
若mid小于left，说明最小值在(left, mid]之间；
-
若mid大于left，则说明左边是升序，但不能说明最小值位置，因为可能有[1,2,3,4,5]这类旋转长度为0的数组。
二分查找要点：二分查找有几种写法？它们的区别是什么？ - Jason Li的回答 - 知乎 https://www.zhihu.com/question/36132386/answer/530313852
剑指 Offer 50. 第一个只出现一次的字符
使用哈希表，遍历两次。
Day 6. 搜索与回溯算法 (Easy)
三题BFS
剑指 Offer 32 - I. 从上到下打印二叉树
二叉树的层序遍历，利用一个队列来实现。
需要注意可能有输入为空数组的情况。
剑指 Offer 32 - II. 从上到下打印二叉树 II
层序遍历BFS。与上题区别在于按层进行打印，分别保存到不同vector中。
核心思路是，当前遍历队列时，队列中只有这一层的节点。
个人做法是，使用一个临时的队列变量保存下一层的节点，当前层的队列为空时，遍历下一个队列，代码略微繁琐。
网上做法普遍是，在while的一次循环中，再加入一个for循环，次数为当前队列长度；之后下一层节点可以直接加入到队列中（因为当前层的遍历个数已经确定）。该种做法相对更节省空间。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(!root) return ans;
queue<TreeNode *> points;
points.push(root);
while(points.size()){
int col=points.size();
vector<int> ans1;
for(int i=0;i<col;i++){
TreeNode *temp=points.front();
points.pop();
ans1.push_back(temp->val);
if(temp->left) points.push(temp->left);
if(temp->right) points.push(temp->right);
}
ans.push_back(ans1);
}
return ans;
}
};
剑指 Offer 32 - III. 从上到下打印二叉树 III
再上一题基础上，判断每一层的层数，并进行reverse。
Day 7. 搜索与回溯算法 (Easy)
剑指 Offer 26. 树的子结构
判断二叉树B是不是二叉树A的子结构，只需要判断三种情况：B是不是A的从根节点开始的子结构；B是不是A的左子树的从根节点开始的子结构；B是不是A的右子树的从根节点开始的子结构。
判断两个二叉树是否从根节点开始重合，使用DFS。需要注意，顺序上要先判断B的节点，为NULL时，说明已经相同，
bool dfs(TreeNode* a, TreeNode*b){
if(b==NULL) return true;
if(a==NULL) return false;
return a->val==b->val && dfs(a->left, b->left) && dfs(a->right, b->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A==NULL || B==NULL) return false;
return dfs(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
剑指 Offer 27. 二叉树的镜像
递归实现。
剑指 Offer 28. 对称的二叉树
首先想法是使用上一题的镜像，在判断原始二叉树和镜像二叉树是否相同。但显然这个方法比较繁琐。
回到对称二叉树本身性质：对于二叉树中任意两个对称节点，该节点的left和right值相同，且left的left与right的right相同，left的right与right的left相同，因此可以有：
bool isSymmetricSub(TreeNode* leftNode, TreeNode* rightNode){
if(!leftNode && !rightNode) return true;
if((leftNode&&rightNode)==false || leftNode->val != rightNode->val) return false;
return isSymmetricSub(leftNode->left, rightNode->right) && isSymmetricSub(leftNode->right, rightNode->left);
}
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return isSymmetricSub(root->left, root->right);
}
Day 8. 动态规划 (Easy)
剑指 Offer 10- I. 斐波那契数列
入门题。使用DP或者备忘录的递归。
剑指 Offer 10- II. 青蛙跳台阶问题
与上一题类似。
剑指 Offer 63. 股票的最大利润
动态规划：
- 状态定义：设动态规划列表为dp，dp[i]为前i天的最大利润；
- 转移方程：前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格)
- 初始状态：dp[0]=0
- 返回值：dp[n-1]最后一天利益
int maxProfit(vector<int>& prices) {
int maxp = 0;int minPrice = INT_MAX;
for(auto iter=prices.begin();iter!=prices.end();iter++){
minPrice = min(minPrice, *iter);
maxp = max(maxp, *iter - minPrice);
}
return maxp>=0?maxp:0;
}
Day 8. 动态规划 (Medium)
动态规划方法 https://labuladong.gitee.io/algo/1/3/
⭐️ 剑指 Offer 42. 连续子数组的最大和
从暴力计算到动态规划。
暴力计算：
-
计算每一个sum(i, j)，时间复杂度为O(n^3)（i、j遍历所有，求和遍历i到j）；
-
也可以将sum(i, j)转化为sum(i, j-1)+value_j，时间复杂度为O(n^2)（i遍历所有，j遍历从i到结尾，记录最大值）；
动态规划：
如果要以O(n)复杂度解决问题，那么就要在一次遍历过程中，得到以当前元素为结尾的所有数组的最大值dp[i]，在此基础上，获得所有这些最大值的最大值maxValue。
而在计算以A元素为起始，以B元素为结尾的数组和后，在计算以B+1元素为结尾的数组和时，只需要在前一个数组和的基础上，加上B+1元素，而前一个数组和（A起始，B结束）必然是小于dp[i]的，因此
- dp[i] = max(nums[i], nums[i]+dp[i-1])
- maxValue = max(maxValue, dp[i])
int maxSubArray(vector<int>& nums) {
int maxValue = nums[0];
int dp = nums[0];
for(int i = 1; i < nums.size(); i++){
dp = max(dp+nums[i], nums[i]);
maxValue = max(dp, maxValue);
}
return maxValue;
}
剑指 Offer 47. 礼物的最大价值
动态规划：
将到达每格的礼物最大价值记录为dp table。到达每一个格时，当前格的最大价值=max(左边格子的最大价值, 上边格子的最大价值)，因此遍历每一个格子即可，因为没有负值，因此最后取右下角格子的值。需要注意边界的行和列。时间复杂度为O(MN)。
进一步优化，可以将dp table直接保存在输入的二维数组中。空间复杂度为O(1)。
int maxValue(vector<vector<int>>& grid) {
if(grid.size()==0) return 0;
for(int row=0;row < grid.size(); row++){
for(int col = 0;col < grid[0].size(); col++){
if(row+col == 0) continue;
else if (row == 0) grid[row][col] += grid[row][col-1];
else if(col == 0) grid[row][col] += grid[row-1][col];
else grid[row][col] += max(grid[row-1][col], grid[row][col-1]);
}
}
return grid[grid.size()-1][grid[0].size()-1];
}
可以进一步优化，当M、N较大时，遍历过程中的if判断语句仍然耗时，因此可以将对边界的判断移出来单独计算，两层循环从1开始。
Day 9. 动态规划 (Medium)
剑指 Offer 46. 把数字翻译成字符串
关键在于，第一位到第n位的数字的翻译方法的数量，取决于前两位是否可以被翻译，即
dp[i] = dp[i-1] + (dp[i-2:i]可以被翻译) ? 1 : 0;
而如何取出第i位的前两位，可以使用取余的方法。
这一题从左往右和从右往左处理是一样的。
剑指 Offer 48. 最长不含重复字符的子字符串
如果暴力求解，长度为N的字符串，计算所有子字符串，复杂度为O(N^2)，而判断当前字符是否在子串中，复杂度为O(N)，因此暴力的复杂度为O(N^3)。
动态规划：
用DP的思想求解，核心在于，要记录当前字符为结尾的最大不重复子串的值。
则可以得到状态转移方程：
- 若当前字符s[i]前一次出现位置，不在前一个字符的最大子串范围内，则dp[j] = dp[j-1] + 1；
- 否则，dp[j] = j - i，i为该字符上一次出现的位置。
由于要判断字符在子串中的位置，直接的思路是利用string的find_last_of函数，但复杂度高，因此可以使用哈希表记录，进一步，可以用数组替换Map，提高速度。字符的ASCII范围在0～127，因此可以用128维数组表示。
int lengthOfLongestSubstring(string s) {
map<char, int> charMap;
int maxLen = 0;
int lastLen = 0;
for(int i = 0; i < s.size(); i++){
auto iter = charMap.find(s[i]);
int curLen = (iter==charMap.end()) ? lastLen+1 : min(i - iter->second, lastLen+1);
charMap[s[i]] = i;
lastLen = curLen;
maxLen = max(curLen, maxLen);
}
return maxLen;
}
动态规划的思路可以从暴力方法逐步优化得到。
滑动窗口：
这一题用滑动窗口的方法更为合适，本质思路与DP相同。DP方法记录的是子串（长度），而滑动窗口记录的是子串起始位置。
需要注意，字符左起始位置初始值的设置。
int lengthOfLongestSubstring(string s) {
map<char, int> charMap;
int maxLen = 0;
int lastBeg = -1;
for(int i = 0; i < s.size(); i++){
auto iter = charMap.find(s[i]);
int curBeg = (iter==charMap.end()) ? lastBeg : max(lastBeg, iter->second);
charMap[s[i]] = i;
lastBeg = curBeg;
maxLen = max(maxLen, i - curBeg);
}
return maxLen;
}
Day 11. 双指针 (Easy)
剑指 Offer 18. 删除链表的节点
设置pre和cur双指针。
需要注意删除头节点的特例。
剑指 Offer 22. 链表中倒数第k个节点
设置快慢指针，快指针移动k-1步后，慢指针开始移动。
需要注意题目是否提及特例，如：k可能为0；k可能超过链表长度；head可能为NULL等。
Day 12. 双指针 (Easy)
剑指 Offer 25. 合并两个排序的链表
使用双指针很容易完成。每次取链表中的较小值，当其中一个链表遍历结束，直接与另一链表剩余部分拼接。
小trick在于构造一个伪头节点，可以涵盖两个链表起始位置以及出现NULL的情况。
也可以使用递归做法。
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
ListNode* ret;
if(l1->val < l2->val){
ret = l1;
ret->next = mergeTwoLists(l1->next, l2);
}else{
ret = l2;
ret->next = mergeTwoLists(l1, l2->next);
}
return ret;
}
剑指 Offer 52. 两个链表的第一个公共节点
暴力解法，使用哈希表。先遍历并记录链表A，再遍历和查询链表B的元素。时间复杂度为O(M+N)，空间复杂度为O(M)。
双指针法。降低空间复杂度至O(1)。
创建两个指针，分别指向两个链表的头节点，同时开始遍历。当指针遇到链表结尾时，继续从另一个链表头开始遍历，直至两个指针相同。
分情况证明正确性：
- 当两链表相交时，若相交前长度一致，则会在相交的地方停止遍历，若不一致，则会在遍历两链表m+n的长度后停止。
- 若两链表不相交，则会停止在链表的尾部NULL（若相同长度则各自停止，若不同则停在另一个链表）。
可以考虑链表为空的情况。
Day 13. 双指针 (Easy)
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
**首尾双指针。**left指针向右移动，right指针向左移动，当left指向偶数切right指向奇数，则swap；
**快慢双指针。**fast用于查找要调换位置的奇数，slow指向奇数要放的位置，因为进行swap时，fast指向的是奇数，slow前的全是奇数，slow和fast之间的，全部是偶数（因为fast已经经过，所以都被调换到slow前）。
剑指 Offer 57. 和为s的两个数字
若数组为无序，可以使用hashmap的思路，记录已有的数字，每次判断是否已存在对应的另一个数字。
本题为有序数组，因此可以用双指针法。设置前后指针，两边往中间找。
剑指 Offer 58 - I. 翻转单词顺序
string reverseWords(string s) {
string ret = "";
int beg = 0;
s += " ";
for(int i=0;i<s.size();i++){
if(s[i] == ' '){
if(beg!=i) ret = s.substr(beg, i-beg) + " " + ret;
beg = i+1;
}
}
if(ret.size()!=0)ret.pop_back();
return ret;
}
Day .14 搜索与回溯算法 (Medium)
剑指 Offer 12. 矩阵中的路径
矩阵搜索题，使用DFS+剪枝。
DFS的思路比较容易想，但剪枝的处理会略微复杂。在矩阵中搜索，需要考虑上、下、左、右四个方向，同时要考虑矩阵边界和已经经过的位置。
在本题中，保存经过的位置，可以使用'\0’替换走过的路径，在进入四个方向的遍历前，置为'\0'，返回后恢复原值，以此节省存储空间。
此外，由于字符串的开头可能是任意一个位置，因此还需要对矩阵每个位置进行遍历。
对于M*N的矩阵，字符串长度为K，对矩阵每个位置进行K次递归，时间复杂度为$O(3^KMN) $；递归深度不超过K，空间复杂度为$O(K)$。
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
rows = board.size();
cols = board[0].size();
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(dfs(board, word, i, j, 0)) return true;
}
}
return false;
}
private:
int rows, cols;
bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
if(i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;
if(k == word.size() - 1) return true;
board[i][j] = '\0';
bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = word[k];
return res;
}
};
剑指 Offer 13. 机器人的运动范围
DFS+剪枝
解题思路与上一题相同。在本题中，可以只考虑向下和向右的移动。
BFS
也可以借助队列，使用BFS
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> visited(m, vector<bool>(n, 0));
int res = 0;
queue<vector<int>> que;
que.push({ 0, 0, 0, 0 });
while(que.size() > 0) {
vector<int> x = que.front();
que.pop();
int i = x[0], j = x[1], si = x[2], sj = x[3];
if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
visited[i][j] = true;
res++;
que.push({ i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
que.push({ i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
}
return res;
}
};
Day 15. 搜索与回溯算法 (Medium)
剑指 Offer 34. 二叉树中和为某一值的路径
二叉树搜索，使用回溯法，思想和DFS相同：
判断边界->判断成立条件->进行下一轮遍历。
这一题需要注意的是，如何保存每一种路径，使用的方法是每进入一个新的递归，为路径path加入节点，退出时删去这个节点；若路径可用，则将路径加入到最终返回的vector中。
本题也可以使用BFS，但实现上更复杂，不推荐。
剑指 Offer 36. 二叉搜索树与双向链表
将二叉搜索树转化为一个递增的双向链表，结合二叉搜索树的性质，使用中序遍历即可，将每个遍历到的节点加入到双向链表中，最后将双向链表的尾节点和头节点相连。
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(root == nullptr) return nullptr;
dfs(root);
head->left = pre;
pre->right = head;
return head;
}
private:
Node *pre, *head;
void dfs(Node* cur) {
if(cur == nullptr) return;
dfs(cur->left);
if(pre != nullptr) pre->right = cur;
else head = cur;
cur->left = pre;
pre = cur;
dfs(cur->right);
}
};
剑指 Offer 54. 二叉搜索树的第k大节点
二叉搜索树的特性是，左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。其中序遍历（左、根、右）得到的是从小到大的递增序列。
因此可以使用中序遍历的逆序，并且判断到达k个节点后提前返回。
class Solution {
public:
vector<int> kmax;
void inorder_reverse(TreeNode* node, int k){
if(kmax.size() > k || node==nullptr) return;
inorder_reverse(node->right, k);
kmax.emplace_back(node->val);
inorder_reverse(node->left, k);
}
int kthLargest(TreeNode* root, int k) {
inorder_reverse(root, k);
return kmax[k-1];
}
};
Day 16. 排序 (Easy)
⭐️剑指 Offer 45. 把数组排成最小的数
求拼接后的最小数字，本质是排序问题。
两个数字的字符串x和y，排序规则为
- x+y>y+x，则x > y
- x+y<y+x，则x < y
C++中字符串的字典序排序直接用>、<符号即可。
具体排序的方法，可以选择：
1、自己实现。则本题转化为排序算法的实现。根据时间和内存限制选择最佳算法。
2、使用内置sort函数，并重载compare函数。
static bool compare(const string &a,const string &b)
{
return a+b<b+a;
}
//////////
// or
/////////
sort(strs.begin(), strs.end(), [](string& x, string& y){ return x + y < y + x; });
快排模板
Paritition1(int A[], int low, int high) {
int pivot = A[low];
while (low < high) {
while (low < high && A[high] >= pivot) {
--high;
}
A[low] = A[high];
while (low < high && A[low] <= pivot) {
++low;
}
A[high] = A[low];
}
A[low] = pivot;
return low;
}
void QuickSort(int A[], int low, int high) //快排母函数
{
if (low < high) {
int pivot = Paritition1(A, low, high);
QuickSort(A, low, pivot - 1);
QuickSort(A, pivot + 1, high);
}
}
剑指 Offer 61. 扑克牌中的顺子
自己的方法：
设置辅助数组，将五张牌记录下来，存在则置1；同时记录0的个数。
找到数组中非零的最小值，则从该数往后五个位置中，为1的数的个数+之前记录的0的个数=5，则说明为顺子。
题解方法：
五张牌为顺子的充分条件：
- 除大小王外，所有牌无重复；（若有重复，必然不能五张为顺子）
- 除大小王外，最大牌-最小牌<5；（若大于等于5，即使有王，也无法连续）
因此遍历一次获取最大值、最小值、是否重复即可。
Day 17. 排序 (Medium)
剑指 Offer 40. 最小的k个数
考察排序算法。
TODO: 实现多种算法