算法

作者: tingjieee_19e5 | 来源:发表于2018-05-09 13:59 被阅读0次

    查找:二分查找

    排序

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

    相关文章

      网友评论

          本文标题:算法

          本文链接:https://www.haomeiwen.com/subject/zdggcftx.html