碎碎念

title: 俊文碎碎念date: 2020-11-27 12:09:33
tags: C++
categories: mumble

动态规划的方法求序列X,Y的最长公共子序列

以两个序列 X、Y 为例子： 设有二维数组 f[i][j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有：
f[1][1] = same(1,1);
f[i][j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]}
其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位完全相同时为“1”，否则为“0”。
最后f[lenX][lenY]即为最长公共子序列的值。
该算法的空间、时间复杂度均为O(n^2)，经过优化后，空间复杂度可为O(n)。
4.代码实现：
#include <cstdlib> 　　
#include <iostream> 　　
using namespace std; 　　
#define N 105 　　
int dp[N+1][N+1] ; 　　
char str1[N] , str2[N]; 　　
int maxx(int a , int b) 　　
{ 　　
　　if(a > b) 　　
　　　　return a ;
　　return b ; 　　
} 　　
int LCSL(int len1 , int len2) 　　
{ 　　
　　int i , j ; 　　
　　int len = maxx(len1 , len2); 　　
　　for( i = 0 ; i <= len; i++ ) 　　
　　{ 　　
　　　　dp[i][0] = 0 ;dp[0][i] = 0 ; 　　
　　} 　　
　　for( i = 1 ; i<= len1 ; i++) 　　
　　{
　　　　for( j = 1 ; j <= len2 ; j++) 　　
　　　　{ 　　
　　　　　　if(str1[i - 1] == str2[j - 1]) 　　
　　　　　　{ 　　
　　　　　　　　dp[i][j] = dp[i - 1][ j - 1] + 1 ; 　　
　　　　　　} 　　
　　　　　　else 　　
　　　　　　{ 　　
　　　　　　　　dp[i][j] = maxx(dp[i - 1][ j ] , dp[i][j - 1]) ; 　　
　　　　　　} 　　
　　　　}
　　}　　
　　return dp[len1][len2]; 　　
} 　　
int main() 　　
{ 　　
　　while(cin >> str1 >> str2) 　　
　　{ 　　
　　　　int len1 = strlen(str1) ; 　　
　　　　int len2 = strlen(str2) ; 　　
　　　　cout<<LCSL(len1 , len2)<<endl; 　　
　　} 　　
　　return 0; 　　
}

sizeof求传入数组的长度问题

对传入数组求sizeof得到的只会是数组类型指针的大小，以下是解决办法
#include <iostream>
using namespace std;
/*测试*/
void test(int list[], int len)
{
    cout << len;
    return;
}
int main()
{
    int list[10] = { 1,4,3,5,7,9,2,6,8,0 };
    test(list, sizeof(list) / sizeof(int));
    return 0;
}

memset 头文件

#include <string> ×
#include <string.h> √

结构体struct和typedef后面接指针的含义

typedef struct file{
...
}*FileP,FileInfo;
] 给struct file 取个别名为FileInfo 给struct file * 取个别名为FileP

特殊字符的输出

想以符号输出如：\ " "这类符号时要用 \+符号的形式，会影响编程
cout<<"\\\\"; 输出结果为 \\
cout<<"\"";   输出结果为 "
cout<<"""";   输出结果为 空
cout<<"\";    编译不过

二叉树的基本操作

链接

C++中push_back,push_front,insert的用法

链接

include使用方法简介

链接