深大CS2021机试备战打卡

2019上机题目回顾

听说因为是第一次设计机试，难度和细节处理的都不太好，题目描述的并不清楚。

姑且可以确定的是，只能使用C语言。

题目回顾：参考链接。

字符串缩写

第五题 字符串缩写 输入一个字符串，其中有数字(0-9)和字母，如果按照ASCII表是连续的，并且长度大于2，则将其缩写并且输出。 输入用例： 1234aberst 12defhijk 输出用例： 1-4aber-t 12d-fh-k

My Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
    输入一个字符串，其中有数字(0-9)和字母，如果按照ASCII表是连续的，并且长度大于2，则将其缩写并且输出。
*/
const int MAXN = 10005;
int main()
{
    char str[MAXN];
    char ans[MAXN];
    while(scanf("%s", str) != EOF) {
//        printf("%s\n", str);
        int len = strlen(str);
//        printf("len = %d\n", len);
        int i = 0, idx = 0;
        while(i < len) {
            ans[idx ++] = str[i];
//            if(i == 0) continue;
            int size = 1;
            while ((i + size < len) && (str[i+size]-str[i] == size)) {
                ++ size;
            }
            if(size > 2) {
                ans[idx ++] = '-';
                ans[idx ++] = str[i+size-1];
                ans[idx] = '\0';
            } else if(size == 2) {
                ans[idx ++] = str[i+1];
                ans[idx] = '\0';
            }
            i += size;
//            printf("%d: %s\n", i, ans);
        }
        ans[idx] = '\0';
        printf("%s\n", ans);
    }
    return 0;
}

说明

总觉得不是很难，但确实又感觉自己写的代码很丑，没想到哪里能优化。刷算法题常使用C++，突然换成C后，使用C字符数组有些跟不上节奏。

逆排序

第六题 逆排序 第一行输入一个数字n,第二行输入n个数字，组成有n个元素的数组A，如果A[i]>A[i+1],则称这两个数为逆排序，要求输出数组中最长的逆排序的长度，并且将其元素输出 输入用例： 5 12 13 25 10 5 7 18 16 15 20 14 13 10 输出用例： 3 25 10 5 4 20 14 13 10

My Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int MAXN = 100;
int main() {
    int n;
    int arr[MAXN];

    while(scanf("%d", &n) != EOF) {
        int maxLen = -1;
        int start = 0, tmpLen = 1;
        for(int i = 0; i < n; ++ i) {
            scanf("%d", &arr[i]);
            if(i == 0) continue;
            if(arr[i] < arr[i-1]) {
                tmpLen ++;
            } else {
                tmpLen = 1;
                start = i;
            }
            if(tmpLen > maxLen) {
                maxLen = tmpLen;
            }
        }
//        for(int i = 0; i < n; ++ i) {
//            printf(" %d", arr[i]);
//        }
        printf("%d", maxLen);
//        printf("start = %d\n", start);
        for(int i = 0; i < maxLen; ++ i) {
            printf(" %d", arr[i+start]);
        }
        printf("\n");
    }
    return 0;
}

说明

只需要比较局部相邻的两个数，可以写出时间复杂度O(n)的算法。

给出一个相似的的练习题：剑指 Offer 51. 数组中的逆序对，有些难度。

理财

第七题 理财 你有本金10万元，存进银行的第三年(从第一年算起)后每年会有100元的利息，如果这些利息不取出，则在第三年后会会产生100元的利息，问你N年后有多少钱?（答案保留两位小数） 输入用例: 1 4 6 输出用例： 10.00 10.02 10.05

My Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        if(n < 3) printf("10.00\n");
        else {
            double s = 0.00, t = 1;
            for(int i = 3; i <= n; ++ i) {
                if(i >= 6) {
                    ++ t;
                }
                s += 0.01 * t;
            }
            printf("%.2f\n", s + 10.f);
        }
    }
    return 0;
}

说明

这题描述的确实离谱。“第三年后”是相对谁的，连蒙带猜，姑且分析一下。

类似生兔子的问题，无非是带些浮点数。

特例分析：不妨我们取n=7，可以发现，产生利润的本金是从开始到第四年，上一年的利润和前一年的利润对今年无影响。

这段时间有2年能产生0.01的利润，外加本金10（万）元产生的0.01，也因此，比第七年比第六年的基础上增加0.03，也即10.08。

母亲节

第八题 母亲节 母亲节是在每年五月份的第二个星期日，给定年份，求出当年母亲节的日期 输入用例： 1919 2019 输出用例： 1919-5-11 2019-5-12

My Code

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*
1919-5-11
2019-5-12
*/
const int MAXN = 2500;
int isLoop(int n) {
    return (n%4==0 && n%100 != 0) || (n%400 == 0);
}
int main() {
    int ans[MAXN];
    ans[1919] = 11;
    for(int i = 1920; i < 2200; ++ i) {
        if(isLoop(i)) {
            ans[i] = ans[i-1] - 2;
        } else {
            ans[i] = ans[i-1]-1;
        }
        if(ans[i] < 8) {
            ans[i] += 7;
        } else if(ans[i] > 14) {
            ans[i] -= 7;
        }
    }
//    for(int i = 1919; i < 2200; ++ i) {
//        printf("%d-%d-%d\n", i, 5, ans[i]);;
//    }
    int n;
    while(scanf("%d", &n) != EOF) {
        printf("%d-%d-%d\n", n, 5, ans[n]);
    }
    return 0;
}

说明

估计是几个要点：也就是判断闰年和每个月多少天的常识？

假设输入的n是大于1919的，进行分析。

我是先在EXCEL中特殊值找的规律，能注意到第二个周日日期只能分布在区间[8, 14]，通过分析5月1日的可能的分布，进而能推断出其他日期的分布。

=(A2&"-5-1")-WEEKDAY(A2&"-5-1",2)+14中WEEKDAY()函数计算5月1日是星期几，并且返回以星期一作为日历开始格式（星期一、星期二如此排列，格式同最上打卡表）中的位置，进而确定周一的日期；再加上14天就到了第二个周日（母亲节）。

一年是365天（闰年则是366天），而通过已知的日期按周进行加减，一次移动7*52=364天，因此母亲节的日期与上一年差1天（或2天）。考虑到限定到区间[8,14]，因此将越界的日期及时调整一个周即可补足。

字符串排序

第九题 字符串排序 输入一个字符串，字母按照顺序递增，要求输出所有的排序 输入用例： abc ab 输出用例： abc acb bac bca cab cba ab ba

My Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000
int hashTable[MAXN];
char str[MAXN], ans[MAXN];

void dfs(int idx, int len) {
    if(idx == len) {
        ans[len] = '\0';
        printf("%s\n", ans);
        return;
    }
    for(int i = 0; i < len; ++ i) {
        char c = str[i];
        if(hashTable[c] == 0) {
            ans[idx] = c;
            hashTable[c] = 1;
            dfs(idx+1, len);
            hashTable[c] = 0;
        }
    }
}
int main() {

    while(scanf("%s", str) != EOF) {
        int len = strlen(str);
//        printf("len = %d\n", len);
//        printf("%s\n", str);
        for(int i = 0; i < MAXN; ++ i) {
            hashTable[i] = 0;
        }
        dfs(0, len);
    }
    return 0;
}

C与C++有些细节不太一样，比如想要申请静态数组，int arr[MAXN];报错，需要使用#define，参考则可以知道。

Use #define. In C++ there is const that would allow const int a = 6; to work, but even const is not enough in C.

说明

思维上就考察递归和DFS。

C字符串输出前，需要添加终止符。

如果使用c++的话，stl中有next_permutation()处理全排列问题。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    string s;
    while(cin >> s) {
        do {
            cout << s <<endl;
        } while(next_permutation(s.begin(), s.end()));
    }
    return 0;
}

总结

当自己正在用C写这些题，有一丝感觉——像一名初学者在学习C——颇有些可爱😊。

当初大致扫过一边题目，有些轻视。但一遍下来，用自己很久不用的C也是很不习惯，虽然说Cpp与C很类似，但绝不相同。特别是字符串和数组的细节上，在这次刷题过程中，全都需要自己处理，着实繁琐，却很有必要。

提高熟练度，还需要更多练习。