• 考研机试题

    目录

    头文件与STL

    #include 
#include 
#include 
using namespace std;

vector.insert(vector.begin(),2,99)//在头部插入2个99
vector.erase(vector.begin() + 5, vector.end()) //删除第5个以后的元素

map<string,int>
map.insert(pair<string, int>())
map.count() //0或1
map.earse() //删除

string s;
s.find()
s.substr(int start,int length) //切割子串
//输入含空格字符串
getline(cin,s); 
    
    
//优先队列    
priority_queue<int,vecotr<int>,greater<int>>; //less是降序
 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    python输入

    import sys
for line in sys.stdin:
  arr = line.split()
//拼接列表
  ' '.join(list)
  a = int(arr[0])
    
    
    


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    动态规划

    最大数组子串和

    dp[i]其实代表的是以i结尾的最大子串和

    for(int i=0;i>a[i];
    // 需要额外的ans存储max，因为是子串
    dp[i+1]=max(dp[i]+a[i],a[i]);
    ans=max(dp[i+1],ans);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    最长公共子序列

    动态规划

    for(int i=1;i<=s1.size();i++){
	for(int j=1;j<=s2.size();j++){
        if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;
        else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    最长连续公共子串

    //t存储公共子串在s1中的末尾位置
int t=0;
//最大长度，要额外的maxLen存储max，因为是子串
int maxLen=0;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(s1[i-1]==s2[j-1]){
            dp[i][j]=dp[i-1][j-1]+1;
            // =号确保 如果不唯一，则输出s1中的最后一个。
            if(dp[i][j]>=maxLen){
                maxLen=dp[i][j];
                //存储公共子串在s1中的末尾位置，可以输出子串
                t=i-1;
            }
        } 
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    最长递增子序列

    https://www.nowcoder.com/practice/cf209ca9ac994015b8caf5bf2cae5c98?tpId=40&tags=&title=&difficulty=0&judgeStatus=0&rp=1&sourceUrl=

    dp[i]只代表以i结尾的最长递增子序列数

    for(int i=0;ia[j])dp[i]=max(dp[j]+1,dp[i]);
        ans=max(dp[i],ans);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    最大上升子序列和

    和上述最长递增子序列思路一致，不过dp[i]代表以i结尾的最长递增子序列的和，用ans存储结果

    0-1背包

    int dp[1001][1001];//代表前i个物体，背包为j的最大价值
int n,bag;
int v[10001],w[10001];
cin>>n>>bag;
for(int i=1;i<=n;i++){
    cin>>v[i]>>w[i];
}
dp[0][0]=0;
for(int i=1;i<=n;i++){
    for(int j=1;j<=bag;j++){
        if(j>=v[i]){
            dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
        }
        else{
            dp[i][j]=dp[i-1][j];
        }
    }
}
cout<
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    多重背包

    每种物品无限件

    for(int i=1;i<=n;i++){
    for(int j=v[i];j<=m;j++){
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5

    多重背包问题 I

    第 i 种物品最多有 si件，

    //将 si拆成多个物品，即01背包
 while(s--)
{
    a[++t]=v;
    b[t]=w;
}//死拆，把多重背包拆成01背包

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    整数拆分

    一个整数总可以拆分为2的幂的和

    //奇数
if(i%2)dp[i]=dp[i-1];
//偶数 ？没想明白***
else dp[i]=(dp[i-1]+dp[i/2])%1000000000;

    • 1
    • 2
    • 3
    • 4

    最小邮票

    dp[0][0]=0;
for(int i=1;i<=m;i++){
    //代表集不齐
    dp[0][i]=1e9;
}


for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(j-a[i]>=0)
        dp[i][j]=min(dp[i-1][j-a[i]]+1,dp[i-1][j]);
        else
        dp[i][j]=dp[i-1][j];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    最大子矩阵

    子矩阵的和：pivot - dp[k-1][j] - dp[i][q-1] + dp[k-1][q-1]

     for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> matrix[i][j];
            //计算机前缀和
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i][j];
        }
    }
	
    int  ans = INT_MIN;
    //记录最大子矩阵位置
    int x1,x2,y1,y2;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int pivot = dp[i][j];
            for (int k = 1; k <= i; k++) {
                for (int q = 1; q <= j; q++) {
                    if((pivot - dp[k-1][j] - dp[i][q-1] + dp[k-1][q-1])>ans){
                        ans = max(ans, pivot - dp[k-1][j] - dp[i][q-1] + dp[k-1][q-1]);
                        x1=k;
                        x2=i;
                        y1=q;
                        y2=j;
                    }
                    
                }
            }
        }
    }
    cout << ans<
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    数学问题

    朴素法筛素数

    求n以内的所有素数，时间O(nlog(logn))【不是最优：例如14会被2和7筛重复2次】

    void get_primes(int n){
	for(int i=2;i

线性筛素数

时间O(n)，解决重复筛

for（int i=2;i<=n;i++){
    //i没被筛，加入
    if(!st[i]) primes[prime_count++]=i;
    for(int j=0;jn) break;
        //翻倍，一个数 * 素数一定为合数 
        st[primes[j]*i]=true;
        //退出循环，避免之后重复进行筛选
        if(i%primes[j]==0) break;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

快速幂

int qmi(int a,int b, int p){
    if(b==0)return 1 ; 
    int k = qmi(a,b/2,p)%p;
    // k*k可能会超过int 
    if(b%2==0)return (1LL*k*k) %p;
    else return ((1LL*k*k)%p*a)%p;
    
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

石子合并

贪心：只能合并相邻的最小的两堆

int n;
	int min_idx=0;
	int min_sum=1e7;
//	边界处理
	ve.push_back(1e7);
	int ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		ve.push_back(x);
		if(min_sum>ve[i]+ve[i-1]){
			min_sum=ve[i]+ve[i-1];
			min_idx=i;
		}
	}

	while(ve.size()>2){
		ans += min_sum;
		ve[min_idx]=ve[min_idx]+ve[min_idx-1];
		ve.erase(ve.begin()+min_idx-1);
		
		min_sum=1e7;
//		min_idx=0;
	
		if(ve.size()<=2) break;	
		for(int i=1;ive[i]+ve[i-1]){
			min_sum=ve[i]+ve[i-1];
			min_idx=i;
		}
			
		}
	}

	cout<

锯木棍

贪心-思想是WPL最小带权路径,永远合并最小的两个

#include 
#include 
#include 
#include 
using namespace std;
//自定义比较结构体
struct cmp{
    //函数重载 注意两个括号！！！
	bool operator()(int a,int b){
        //稳定
		if(a==b) return false;
		else return a>b;
		
	}
};

int main(int argc, char** argv) {
    //priority_queue,greater> que;
	priority_queue,cmp> que;
	int n,l;
	cin>>n>>l;
	int tmp;
	int ans=0;
	while(n--){
		cin>>tmp;
		que.push(tmp);
	}	
	while(que.size()!=1){
		int a=que.top();
		que.pop();
		int b=que.top();
		que.pop();
			
		que.push(a+b);
		ans=ans+a+b;
	}
	cout<

并查集

int Find(int a){
    int x=a;
    while(s[x]>0){
        x=s[x];
    }
    return x;
}
void Union(int a,int b){
    root1=Find(a);
    root2=Find(b);
    if(root2==root1)return ;
    else{
        s[root2]=root1;
    }
    
}

Dijkstra单源最短路

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，确定一个最短的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
    
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    	
        st[t] = true;
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];

}

Python进制转换(整数无限大)

import sys

for line in sys.stdin:
    a = line.split()
    a=int(a[0])
    b=bin(a)
    s=(b[2:][::-1])
    print(int(s,2))

全排列

回溯法

void dfs(int k){
	if(k==n+1){
		for(int i=1;i<=n;i++){
			cout<>n;
    dfs(1);
    
}

神奇的口袋

有一个神奇的口袋，总容积是40，有n个物品,体积为Vi，装满40有多少种装法

void dfs(int u,int j){
    if(u==40){
        ans++;   
    }
    else{
        //从j开始，前面用过的舍弃掉，防止重复
        for(int i=j;i

全排列II

带有重复元素的全排列

void dfs(int k){
	if(k==n+1){
		for(int i=1;i<=n;i++){
			cout<>n;
   //使重复的元素排在一起
    sort(a,a+n);
    dfs(1);
    
}

放苹果

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

//处理边界
for(int i=0;i<=m;i++){
    //为0的可以不用处理，数组默认为0
    //1个盘子的
    dp[i][1]=1;
}
for(int i=0;i<=n;i++){
    //0个苹果的
    dp[0][i]=1;
}

for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
        //如果盘子多，多余的用不到的盘子都是没用的
        if(j>i){
            dp[i][j]=dp[i][i];
        }
        //如果苹果多，dp[i][j]等于 有空盘子的(挑一个盘子为空)+没有空盘子(每个盘子初始都放一个苹果)的状态
        else{
            dp[i][j]=dp[i][j-1]+dp[i-j][j];
        }

    }
}

求第k小

使用快排划分的思想

#include 
#include 
/**求第k小 */
using namespace std;
int n;
int a[10001];
int k;
void partition(int start,int end) {
	int pivot=a[start];
	int l=start;
	int r=end;
	while(lpivot) {
			r--;
		}
		swap(a[l],a[r]);
	}
	a[l]=pivot;
	if(l==k-1) {
		cout<>n;
	cin>>k;
	for(int i=0; i>a[i];
	}
	partition(0,n-1);
	return 0;
}

八皇后问题

哈夫曼编码

priority_queue,greater q;
int alpha[26];
//去最小的两个

KMP算法

//字符串下标都从0开始
void getNextTable(int m){
    int j=0;
    next[0]=-1;
    int i=-1;
    while(j

遍历建立二叉树

TNode(char c):data©,left(nullptr),right(nullptr){};

using TreeNode = struct TNode{
	char data;
	struct TNode* left;
	struct TNode* right;
	TNode(char c):data(c),left(nullptr),right(nullptr){};
};

TreeNode* Build(TreeNode* root,char c){
    
	if(c=='#')return NULL;
//	C style：(TreeNode*)malloc(sizeof(TreeNode))
	root=new TNode(c);
	char c1=s[cnt++];
	root->left=Build(root->left,c1);
	char c2=s[cnt++];
	root->right=Build(root->right,c2);
	
	return root;
}

void Inorder(TreeNode* root){
	if(root->left)
	Inorder(root->left);
	cout<data<right)
	Inorder(root->right);
	
}
void postOrder(TreeNode* root){
	
}


int main(int argc, char** argv) {
	TreeNode* T=NULL;
	T=Build(T,s[cnt++]);
	Inorder(T);
	
	return 0;
}
  • 相关阅读:
    持续集成工具jenkins操作
    MySQL的主从同步原理
    Redis最快速入门，一篇搞定(超详细)
    IDEA Debug调试简单程序的时候不需要进入源码
    增减网络20220101
    进程通信的方式
    PyCharm 的初始设置
    MySQL 默认隔离级别是RR，为什么阿里等大厂会改成RC？
    线上宝塔部署的springboot项目在执行elasticsearchRepository.saveAll后就挂掉的解决方法
    搭建HBase分布式集群
  • 原文地址：https://blog.csdn.net/weixin_51277037/article/details/136751990