stdin += can for 可能 array ont true
1, 大富翁游戏,玩家根据骰子的点数决定走的步数,即骰子点数为 1 时可以走一步,点数为 2 时可以走两步,点数为 n 时可以走 n 步。求玩家走到第 n 步(n<= 骰子最大点数且是方法的唯一入参)时,总共有多少种投骰子的方法。
题解:
写出前面的几个, 1 -> 1; 2 -> 2 ; 3 -> 4; 4 -> 8; 5 -> 16; 6 -> 32; 可以得到是 二的 n-1 次幂。
- #include <cstdio>
- int main(){
- int n, ans;
- while(scanf("%d", &n) != EOF){
- if(n <= 0){
- printf("%d\n", 0);
- continue;
- }
- ans = 1;
- for(int i=1; i<n; ++i){
- ans *= 2;
- }
- printf("%d\n", ans);
- }
- return 0;
- }
2, 给你六种面额 1、5、10、20、50、100 元的纸币,假设每种币值的数量都足够多,编写程序求组成 N 元(N 为 0~10000 的非负整数)的不同组合的个数。
题解:
多一个 bill 选项, 则可以从 该 bill 值的 0,1,2 ... j/bill , 这么多种集合。dp[i][j] = dp[i][j] + dp[i-1][j - k*bill[i] ];
- #include < iostream > #include < cstdio > #include < cstring > #include < cstdlib > using namespace std;
- const int MAXN = 10000 + 10;
- const int BILL[6] = {
- 1,
- 5,
- 10,
- 20,
- 50,
- 100
- };
- int n,
- dp[6][MAXN];
- void init() {
- memset(dp, 0, sizeof(dp));
- for (int i = 0; i < MAXN; ++i) {
- dp[0][i] = 1;
- }
- for (int i = 1; i < 6; ++i) {
- for (int j = 1; j < MAXN; ++j) {
- for (int k = 0; k * BILL[i] <= j; ++k) {
- dp[i][j] += dp[i - 1][j - k * BILL[i]];
- }
- }
- }
- }
- int main() {
- freopen("in.txt", "r", stdin);
- init();
- while (scanf("%d", &n) != EOF) {
- printf("%d\n", dp[5][n]);
- }
- return 0;
- }
3, 给定一组非负整数组成的数组 h,代表一组柱状图的高度,其中每个柱子的宽度都为 1。 在这组柱状图中找到能组成的最大矩形的面积(如图所示)。 入参 h 为一个整型数组,代表每个柱子的高度,返回面积的值。
题解:
经典的最大矩形问题。使用 left and right array, 分别记录每一个 pt 可以扩展的最大距离。
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <cstdlib>
- using namespace std;
- const int MAXN = 10000 + 10;
- int n, tmp, ans, num[MAXN], lft[MAXN], rgt[MAXN];
- int main(){
- while(scanf("%d", &n) != EOF){
- for(int i=1; i<=n; ++i){
- scanf("%d", &num[i]);
- }
- num[0] = num[n+1] = 0;
- for(int i=1; i<=n; ++i){
- tmp = i - 1;
- while(num[i] <= num[tmp]){
- tmp = lft[tmp] - 1;
- }
- lft[i] = tmp + 1;
- }
- for(int i=n; i>=1; --i){
- tmp = i + 1;
- while(num[i] <= num[tmp]){
- tmp = rgt[tmp] + 1;
- }
- rgt[i] = tmp - 1;
- }
- ans = 0;
- for(int i=1; i<=n; ++i){
- ans = max(ans, num[i]*(rgt[i] - lft[i] + 1));
- }
- printf("%d\n", ans );
- }
- return 0;
- }
4, 给出两个字符串(可能包含空格), 找出其中最长的公共连续子串, 输出其长度。
题解:
使用 动态规划。
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <cstdlib>
- using namespace std;
- const int MAXN = 100 + 10;
- char ch1[MAXN], ch2[MAXN];
- int dp[MAXN][MAXN];
- int get_line(char *line, int max_size){
- int c, len = 0;
- while( (c = getchar()) != EOF && len < max_size ){
- line[len++] = c;
- if(c == '\n'){
- break;
- }
- }
- line[len] = '\0';
- return (len - 1);
- }
- int main(){
- int ans = 0;
- int len1 = get_line(ch1, MAXN);
- int len2 = get_line(ch2, MAXN);
- memset(dp, 0, sizeof(dp));
- for(int i=0; i<len1; ++i){
- for(int j=0; j<len2; ++j){
- if(ch1[i] == ch2[j]){
- dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1);
- ans = max(ans, dp[i+1][j+1]);
- }
- }
- }
- printf("%d\n", ans);
- return 0;
- }
美团点评 2017 秋招笔试编程题
来源: http://www.bubuko.com/infodetail-2142968.html