算法思想题

1.二分查找

2.贪心思想

3.双指针

4.排序 （1）快速排序（2）堆排序（3）桶排序（4）荷兰国旗问题

5.搜索 （1）BFS (2)DFS (3)Backtracking

6.分治

7.动态规划

（1）斐波那契数列     （2）最长递增子序列

（3）最长公共子序列   （4）0-1 背包

（5）数组区间         （6）字符串编辑

（7）分割整数         （8）矩阵路径   （9）其它问题

8.数学

（1）素数             （2）最大公约数

（3）进制转换         （4）阶乘

（5）字符串加法减法   （6）相遇问题

（7）多数投票问题     （8）其它

/***********************************************************************************/

1.二分查找

2.贪心思想

3.双指针

4.排序 

（1）快速排序

（2）堆排序

（3）桶排序

（4）荷兰国旗问题

5.搜索 

(1)BFS 

(2)DFS 

(3)Backtracking

6.分治

7.动态规划

（1）斐波那契数列     

（2）最长递增子序列

（3）最长公共子序列   

（4）0-1 背包

（5）数组区间         

（6）字符串编辑

（7）分割整数         

（8）矩阵总路径  

/*法一：采用递归的思想做，但是递归层次太多是效率不划算*/
     public int uniquePaths(int m, int n) {
            if(m==1||n==1){
                return 1;
            }else{
                return uniquePaths(m-1,n)+uniquePaths(m,n-1);
            }
        }
     /*法二：采用动态规划的思想做，保证矩阵s[][]中的元素s[i][j]存的是第i行到第j行为结束终点时的方法数，
      * 则最后结果是s[m][n]的值，这样做的好处时，矩阵中的每个元素的值都只需要计算一次即可。
      * 但是递归的话则会重复计算相同部分的值。
      * Step1：初始化第0行和第0列的值，s[i][0]=1和s[0][j]=0;
      * Step2：以s[i][j]=s[i-1][j]+s[i][j-1]为计算公式，计算后面的值。
      * Step3：最后返回s[m-1][n-1]
      */
     public int uniquePaths2(int m, int n) {
            if(m==1||n==1){
                return 1;
            }
            int s[][]=new int[m][n];
            for(int i=0;i<m;i++){
                s[i][0]=1;//初始化第一列,但是要注意在代码中第一列中下标j=0；
            }
            for(int j=0;j<n;j++){
                s[0][j]=1;//初始化第一行
            }
            for(int i=1;i<m;i++){
                for(int j=1;j<n;j++){
                    s[i][j]=s[i-1][j]+s[i][j-1];
                }
            }
            return s[m-1][n-1];
        }

 

（9）其它问题

8.数学

（1）素数  

#include <iostream>
using namespace std;
int main()
{
    int n,t=1;
    cin >> n;
    if (n<2)
    {
        cout << n << "不是素数" << endl;//1既不是素数也不是合数，素数从2开始
        return 0;
    }
    for (int i = 2; i < sqrt(n)+1;i++)//也可用n/2，不过计算量要比sqrt大一些
    {
        if (n%i == 0)
        {
            t = 0;
            break;
        }
    }
    if (t) cout << n << "是素数" << endl;
          else cout << n << "不是素数" << endl;
    return 0;
}

           

（2）最大公约数

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a% b);
}

最小公倍数

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

（3）进制转换  

toa函数：

它的功能是将一个10进制的数转化为n进制的值、其返回值为char型。（和上面的strtol效果相反）

例如：itoa(num, str, 2); num是一个int型的，是要转化的10进制数，str是转化结果，后面的值为目标进制。

#include<cstdlib>
#include<cstdio>
int main()
{
int num = 10;
char str[100];
itoa(num, str, 2);
printf("%s\n", str);
return 0;
}

#include <bitset>
#include <iostream>
using namespace std;
int main()
{
    cout << "36的8进制:" << std::oct << 36 << endl;
    cout << "36的10进制" << std::dec << 36 << endl;
    cout << "36的16进制:" << std::hex << 36 << endl;
    cout << "36的2进制: " << bitset<8>(36) << endl;
    return 0;
}

       

（4）阶乘

（5）字符串加法减法   

（6）相遇问题

（7）多数投票问题     

（8）其它

1