编程题算法总结
求最大公约数 最小公倍数
最大公约数
辗转相除法
大的a除小的b，得到余数如果是0，那么b就是最大公约数，否则就取余数做那个小的，本来的b就成了大的继续操作。
int n,m;
//辗转相除法,ab最大公约数 = ab余数和b的最大公约数
int yu,a,b;
a = n>m?n:m;
b = n>m?m:n;
while(1)
{
yu = a % b;
if(yu == 0) break;
a = b;
b = yu; //已经是余数了，一定比b小
}
//b就是
更相减损法
大的a 小的b，a-b=0就找到了，否则a = a-b循环
int a,b;
int cal = a*b;
//更相减损法 ,a = a-b
while(a!=b)
{
if(a>b)
a = a-b;
else b = b-a;
}
//b就是
最小公倍数
偷懒法
先求最大公约数，由最大公约* 最小公倍数 = a* b
迭乘法
最小公倍数一定是其中某个数的n倍
int a,b;
int cal = a*b;
int i = 1;
//迭乘法求最小公倍数
while(a*i%b!=0)
{
i++;
}
//a*i就是
正序数组插值
int arr[10],x;
//正序数组和要插入的值
int i = 8;
while(i>=0&&arr[i]>x) //注意从后面开始遍历，移动到后面的那个
{
arr[i+1] = arr[i];
i--;
}
arr[i+1] = x;
for (int i = 0; i < 10; i++)
{
printf("%d\n",arr[i]); //打印输出
}
以上其实是插入的算法，如果是删除，需要从前向后遍历，然后把后面的元素往前移
编辑距离
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
- 删除一个字符；
- 插入一个字符；
- 将一个字符改为另一个字符。
对任给的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数
> 三种操作分别是：插入 删除 替换
需要清楚的点：
-
两字符串A和B，给A插入相当于给B删除，反之亦然（例如cat和cate）
-
替换A相当于替换B（例如cat和fat）
-
故本质操作就三种 ： ① A插 ② B插 ③ 替换
dp[i][j]表示从 A 的前 i 个 字符转换到 B 的 前 j 个 字 符所需的最短步数
（例如A是qwert B是aserty 那么最终输出结果就是dp[5][6]）
-
dp[i-1][j-1]到dp[i][j]需要进行替换操作。若A的第 i 位(其实就是当前操作位）等于 B的第 j 位（当前操作位），那么就不需要替换，因此dp[i][j] = dp[i-1][j-1] ，否则dp[i][j] = dp[i-1][j-1]+1
-
dp[i-1][j]到d[i][j]需要进行删除操作。dp[i][j] = dp[i-1][j] + 1
-
dp[i][j-1]到d[i][j]需要进行添加操作。dp[i][j] = dp[i][j-1] + 1
★当A与B末位相同时：
dp[i][j] = min(dp[i][j−1]+1,dp[i−1][j]+1,dp[i−1][j−1])
★当A与B末位不相同时：
dp[i][j] =min(dp[i][j−1]+1,dp[i−1][j]+1,dp[i−1][j−1]+1)
那么，我们要怎么从dp[0][0] 到 dp[i][j]呢？
很简单，每一步做出判断，替换、删除、添加哪个短就选哪个！
这里需要注意
- dp[a][b]代表着前面所有步数的最短选择！
- 由于不知道AB长度，因此A插和B插不可以混为一谈！
注意事项:
边界情况，A或B为空，直接输出不为空的数组长度即可
#include <stdio.h>
using namespace std;
int main(){
//注意！！数组是从0开始索引的，所以第i位就是i-1的索引，以此类推！！
string a,b;
getline(cin,a);
getline(cin,b);
int len1 = a.length();
int len2 = b.length(); //接受输入记录长度
int dp[len1][len2]; //定义dp数组
for (int i = 0; i < len1; i++) {dp[i][0] = i;}
for (int j = 0; j < len2; j++) {dp[0][j] = j;} //边界情况,同时也是初始化
for (int i = 1; i < len1; i++)
{
for (int j = 1; j < len2; j++) //ij从1开始，因为已经初始化过了,从0开始会溢出
{
if(a[i-1] == b[j-1]) //A的第i位与B的第j位相同的情况
dp[i][j] = min(min(dp[i][j-1]+1, dp[i-1][j]+1),dp[i-1][j-1]);
else
dp[i][j] = min(min(dp[i][j-1]+1, dp[i-1][j]+1),dp[i-1][j-1]+1);
}
}
cout<<dp[len1-1][len2-1]<<endl;
return 0;
}
寻找回文子串
#include<iostream>
using namespace std;
int main()
{
string s;
while(getline(cin,s))
{
int len = s.length();
int dp[len][len]; //dp[i][j]表示i-j段是否为回文，是的话就表示长度 否的话就是0
//从i处，一个一个改变终点直到结尾，是否存在回文？不存在的话，i往前走一个重复上述操作。
//那么，怎么判断某段是否是回文呢？
//ij相等 是回文 例如a
//ij差一且si=sj，比如aa,是。若si≠sj，不是。
//ij差大于1,且si=sj，比如abcba，此时看s[i+1] s[j-1]是否为回文,
//若i从开头开始遍历，会出现abeda这种，虽然a=a,但是bed是否为回文并没有判断！！！！
int maxlen = 1;
for(int i = len-1; i >= 0; i--){
for(int j = i; j < len; j++){
if(i == j)
{
//maxlen = 0;
dp[i][j] = 1;
}
if(s[i]==s[j] && j==i+1){
maxlen=max(maxlen,2);
dp[i][j] = 1; //记录一下i-j是回文串
}
if(s[i]==s[j] && j>i+1 && dp[i+1][j-1]){
maxlen = max(maxlen,j-i+1); //一定要注意写max!!!!
dp[i][j] = 1;
}
}
}cout<<maxlen<<endl;
}
return 0;
}