腾讯8.23笔试 后台
1 删除链表
#include #include #include using namespace std; int main() { int n,k,m; scanf("%d %d",&n,&k); scanf("%d",&m); if(k != 1) printf("%d ",m); for(int i=2;i<=n;i++){ scanf("%d",&m); if(i != k) printf("%d ",m); } return 0; }
2 最小k字符串 :没写出来
3 两个数的拆分之和
// 思路678 分为99 和剩余的部分的 使得9最多就可以了,这样一定是最大的 #include<iostream> #include<cstring> #include<stdio.h> using namespace std; long long get_ws(long long n){ long long k =0; while(n>0){ n /=10; k = k*10 + 9; } return k/10; } int main(){ long long res,k,m,j; int n; scanf("%d",&n); while(n--){ scanf("%ld",&m); if(m < 19){ printf("%d\n",m); continue; } k = get_ws(m); j = m - k; res = 0; while(k > 0){ res += k % 10; k /= 10; } while(j > 0){ res += j % 10; j /= 10; } } printf("%ld", res); return 0; }
4 刷木板的问题 DP问题
#include<iostream> #include<cstring> #include<stdio.h> using namespace std; const int N =5050; int a[N]; int solve(int l,int r){ if(l > r) return 0; int k = l; for(int i = l; i <= r;i++){ if(a[k] > a[i]) k = i; }//找到最短的 int sum = a[k]; for(int i = l;i <= r; i++){//所有数都减去这个最小的数 a[i] -= sum; } return min(r - l + 1, solve(l,k-1) + solve(k + 1,r) + sum);//在横着涂和竖着涂中取最小值 } int main(){ int n; scanf("%d",&n); for(int i = 0;i < n;i++){ scanf("%d",&a[i]); } printf("%d\n",solve(0,n-1)); return 0; }
5 回文串问题
/* f(i,j)表示 i到j 判断是不是会回文串 f(i,j) = min(f(i,j),f(i,k)+f(k+1,j)) */ #include<iostream> #include<cstring> #include<stdio.h> using namespace std; int f[505][505]; string s; bool is_huiwen(int l,int r){ while(l <= r){ if(s[l] != s[r]){ break; } l++; r--; } if(l >= r){ return true; } else{ return false; } } int main(){ int n; int l,r; cin>>s; n = s.size(); for(int i=0 ;i <n;i++){ for(int j =0; j<n;j++){ f[i][j] = j - i + 1; } f[i][i] = 1; } for(int i=0 ;i <n;i++){ for(int j =i+1; j<n;j++){ if(is_huiwen(i,j)) f[i][j] = 1; } } for(int i=0 ;i < n;i++){ for(int j =i+1; j<n;j++){ for(int k = i; k<j;k++){ if(f[i][k] + f[k+1][j] < f[i][j]){ f[i][j] = f[i][k] + f[k+1][j]; } } } } scanf("%d",&n); while(n--){ scanf("%d %d",&l,&r); l--; r--;//数组坐标是0开始,实际上的r和l是1开始 if(l <= r){ printf("%d\n",f[l][r]); } else{ printf("%d\n",f[r][l]); } } return 0; }#笔试题目#