目录
1.折半查找
题目：给一个严格递增数列，函数int Search_Bin(SSTable T, KeyType k)用来二分地查找k在数列中的位置。
函数接口定义：
void Print_Factorial ( const int N );其中T是有序表，k是查找的值。
裁判测试程序样例：
输入样例：/* 请在这里填写答案 */
###输入格式：
第一行输入一个整数n，表示有序表的元素个数，接下来一行n个数字，依次为表内元素值。 然后输入一个要查找的值。
###输出格式：
输出这个值在表内的位置，如果没有找到，输出"NOT FOUND"。
输入样例：
3
12.3 34 -5
输出样例：
12.30
解题思路：这道题就是完全直接考察折半查找：先定义出middle，然后将要需要查找的数，与middle位置的数进行比较，如果middle的数比较大，那么，将查找范围缩小到0到middle-1的位置，想反，如果middle的数比较小，则将范围缩小到middle+1到end。
int Search_Bin(SSTable T, KeyType k) { int left = 1,right = T.length; while(left<=right) { int mid = (left+right)/2; if(T.R[mid].key<k) { left = mid+1; } else if(T.R[mid].key>k) { right = mid-1; } else { return mid; } } return 0; }
2.求自定类型元素序列的中位数
题目：本题要求实现一个函数，求N个集合元素A[]的中位数，即序列中第⌊(N+1)/2⌋大的元素。其中集合元素的类型为自定义的ElementType。
函数接口定义：
ElementType Median( ElementType A[], int N );
其中给定集合元素存放在数组
A[]中，正整数N是数组元素个数。该函数须返回N个A[]元素的中位数，其值也必须是ElementType类型。
裁判测试程序样例：
#include <stdio.h> #define MAXN 10 typedef float ElementType; ElementType Median( ElementType A[], int N ); int main () { ElementType A[MAXN]; int N, i; scanf("%d", &N); for ( i=0; i<N; i++ ) scanf("%f", &A[i]); printf("%.2f\n", Median(A, N)); return 0; } /* 你的代码将被嵌在这里 */
输入样例：
3
12.3 34 -5
输出样例：
12.30
解题思路：由于是找中位数，因此，如果给出的数是按序排列的，那么，中间的那个数就是我们要找的中位数了。我们使用排序算法来进行排序，经过测试，使用冒泡、插入排序等等会不通过，因为这些排序比较慢，而使用希尔排序则🆗。
对于希尔排序的使用，可以通过数据结构与算法：排序_二肥是只大懒蓝猫的博客-CSDN博客
这篇文章来学习。
void shellsort(ElementType* A, int N) { int gap = N; while (gap > 1) { gap = gap / 3 + 1; for (int i = 0; i < N - gap; i++) { int end = i; ElementType temp = A[end + gap]; while (end >= 0) { if (A[end] > temp) { A[end + gap] = A[end]; end -= gap; } else break; } A[end + gap] = temp; } } } ElementType Median(ElementType A[], int N) { shellsort(A, N); return A[N / 2]; }
3.螺旋矩阵
题目：给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
解题思路：对于这道题，我们需要分析我们在循环打印的时候，终止条件的什么？开始条件是什么？
![8~}]GQR68B]FL(Y%WSN1S$X.png](https://ucc.alicdn.com/pic/developer-ecology/ipajprmaanvwy_54aa76e55abd4130b06a6990a2a25335.png?x-oss-process=image/resize,w_1400/format,webp "8~}]GQR68B]FL(Y%WSN1S$X.png")
如上图所示，我们需要定义四个指向数组的变量：top、bottom、left和right，用来对每条边上的数组进行变量，每当完成一轮，那么数组就会缩小一圈，则top需要++，right--，bottom--和left++。
class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector <int> ans; if(matrix.empty()) { return ans; } int left = 0; int right = matrix[0].size()-1; int top = 0; int bottom = matrix.size()-1; while(true) { //向右 for(int i = left;i<=right;i++) { ans.push_back(matrix[top][i]); } top++; if(top>bottom) break; //向下 for(int i = top;i<=bottom;i++) { ans.push_back(matrix[i][right]); } right--; if(right<left) break; //向左 for(int i = right;i>=left;i--) { ans.push_back(matrix[bottom][i]); } bottom--; if(bottom<top) break; // 向上 for(int i = bottom;i>=top;i--) { ans.push_back(matrix[i][left]); } left++; if(left>right) break; } return ans; } };
4.对称二叉树
题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
解题思路：这道题其实就是跟让我们判断A子树的左孩子是否与B子树的右孩子相等，并且A子树的右孩子是否与B子树的左孩子相等，如果相等，那么就是对称的。这里跟判断是否相同的树那道题类似。一开始的做的时候，我自作聪明地先找出这棵树的镜像，再判断这两棵树是否相等，但是做着做着我就发现，不用那么麻烦，因为这棵树的最一开始的根压根不用去判断，直接取它的左右子树当作树的镜像去判断就好了。
而且，我拿这棵树去造镜像的时候，发现，原本的树结构被我改变了。。。。我弄了半天。。。才发现这个问题，我吐了。
class Solution { public: bool check(TreeNode* p,TreeNode* q) { if(p==nullptr && q==nullptr) { return true; } if(p==nullptr || q==nullptr) { return false; } if(p->val!=q->val) { return false; } return check(p->left,q->right) && check(p->right,q->left); } bool isSymmetric(TreeNode* root) { if(root==nullptr) { return true; } return check(root->left,root->right); } };
