算法

查找：二分查找

排序

• 快排
  • 基于快排思想解决的问题
  • 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;
    }