算法算法

查找：二分查找
排序

快排
- 基于快排思想解决的问题
- partition，
  - 第k大的数字
归并
几种排序算法的时间复杂度，稳定性等

DP
斐波那契数列

递归导致大量重复计算
循环，保存中间结果

变种

跳台阶
小矩形覆盖大矩形

连续子数组的最大和求最大路径和求最长公共子序列排列，组合，回溯法 ex.1

/* *打印出一个字符串的全部排列。 */

ex.2

/* *打印出一个字符串的组合。 */

排列

全排列：从第一个数字起，每个数字分别与它后面的数字交换
去重全排列：从第一个数字起，每个数组分别与它后面非重复出现的数字交换

组合

基于递归
基于位图

ex.3

/* *输入一个含有8个数字的数组，判断有没有可能把这8个数字分配放到正方体 *的8个顶点上，是得正方体上三组相对的面上的4个顶点的和都相等 */ //求8个数字的全部排列，然后判断排列是否满足题目给出的条件

【算法】ex.4

/* *8皇后问题。在8*8的棋盘上拜放8个皇后，使其不能相互攻击，即8个皇后 *不能处于同一行，同一列或者同一对角线上。 */ //初始化一个columnIndex[8]数组，第i个数表示位于第i行的列数，因此用0-7来 //初始化数组，然后做全排列，逐个判断是否满足不同行、列、对角线的要求//初始化一个columnIndex[8]数组，第i个数表示位于第i行的列数 // 使用回溯法，从第一行第一列初始化数组

回溯法

//8皇后 int C[8] = {0}; cout << search(0)<< endl； int tot = 0; void search(int cur) { if(cur == 8) tot++; else for (int i = 0; i < 8; ++i) { int ok = 1; C[cur] = i; for(int j = 0; j< cur; ++j) { if(C[cur]==C[j] || cur-C[cur]==j-C[j] || cur+C[cur]==j+C[j]){ of = 0; break; } } if(ok)search(cur+1); } }

//矩阵中的路径 //从任意格子出发，检查是否满足路径，同数组表示访问的路径表示已经到达过的位置以及当前到达的位置 //先检查当前格子，是否满足条件，满足则向另外4个方向出发，不满足则返回 bool hasPath(char* matrix, int rows, int cols, char* str) { if(matrix == NULL || rows < 1 || cols < 1 || str == NULL) return false; bool *visited= new bool[rows * cols]; memset(visited, 0, rows*cols*sizeof(bool)); int pathLength = 0; for(int row = 0; row < rows; ++row) { for(int col = 0; col < cols; ++col) { if(hasPathCore(matrix,rows,cols,row,col,str,pathLength,visited)) { delete [] visited; return true; } } } delete [] visited; return false; } bool hasPathCore(char* matrix, int rows, int cols,int row,int col, char* str,int& pathLength,bool* visited){ if(str[pathLength] == '\0') return true; bool hasPath = false; if(row >= 0 && row < rows && col >=0 && col < cols && matrix[row * cols + col] == str[pathLength]&& !visited[row * cols + col]) { ++pathLength; visited[row * cols + col] = true; hasPath = hasPathCore(matrix,rows,cols,row+1,col,str,pathLength,visited) || hasPathCore(matrix,rows,cols,row,col+1,str,pathLength,visited) || hasPathCore(matrix,rows,cols,row-1,col,str,pathLength,visited) || hasPathCore(matrix,rows,cols,row,col-1,str,pathLength,visited); if(!hasPath) { --pathLength; visited[row * cols + col] = false; } } return hasPath; }

// 机器人的运行范围 // 使用一个数组来记录已访问的位置， //从(0，0)出发，每次移动位置都要检查是否满足要求。 // 如果满足要求则设置记录数组，并且增加路程int movingCount(int threshold, int rows, int cols) { if(threshold <= 0 || rows <= 0 || cols <= 0) return 0; bool *visited = new bool[rows * cols]; for(int i = 0; i < rows * cols; ++i) visited[i] = false; int count = movingCountCore(threshold,rows,cols,0,0,visited); delete [] visited; return count; } int movingCountCore(int threshold, int rows, int cols,int row,int col,bool *visited){ int pathLength = 0; if(row >=0 && row < rows && col >= 0 && col < cols && !visited[row * cols + col] && checkOk(threshold, row, col)) { visited[row * cols + col] = true; pathLength = 1 + movingCountCore(threshold,rows,cols,row,col+1,visited) + movingCountCore(threshold,rows,cols,row+1,col,visited) + movingCountCore(threshold,rows,cols,row-1,col,visited) + movingCountCore(threshold,rows,cols,row,col-1,visited); } return pathLength; } bool checkOk(int threshold, int row, int col) { int tmp = 0; while(row > 0){ tmp += row % 10; row = row / 10; } while(col > 0){ tmp += col % 10; col = col / 10; } if(tmp <= threshold) return true; return false; }