2017百度春季实习生编程题参考解题报告

日历(前端题)

分析

这道题主要考察日期计算，还有一点Dom操作知识，难度中等。

参考code

function calendar(year, month) {
    var bLeap = (year % 4 === 0 && year % 100 !== 0) || year % 400 === 0;
    var nCount = [0, 31, bLeap ? 29 : 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31][month] || 0;
    var nStart = new Date(year, month - 1, 1).getDay();
    nStart = (nStart - 1 + 7) % 7;
    // 当前
    var oNow = new Date();
    var nNowDate = oNow.getDate();
    var bCurrent = oNow.getFullYear() === year && oNow.getMonth() + 1 === month;

    // 渲染
    var aTd = [].slice.call(document.getElementsByTagName('td'), 0);
    var nVal = 1;
    aTd.forEach(function (oTd, nIndex) {
        oTd.className = bCurrent && nVal === nNowDate ? 'current' : '';
        if (nIndex >= nStart && nVal <= nCount) {
            oTd.innerHTML = nVal;
            nVal++;
        } else {
            oTd.innerHTML = '';
        }
    });
}

度度熊回家

分析

暴力枚举忽略的点,然后维护答案就行了

参考code

#include <bits/stdc++.h>

using namespace std;

int a[55];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int ans = 100000;
    for(int i = 0; i < n; i++) {
        int res = 0;
        int last = a[0];
        for(int j = 1; j < n - 1; j++) {
            if(i == j) continue;
            res += abs(a[j] - last);
            last = a[j];
        }
        res += abs(a[n - 1] - last);
        ans = min(ans, res);
    }
    cout << ans << endl;
    return 0;
}

买帽子

分析

丢进set去重,取第三小就行了,没有就-1.

参考code

#include <bits/stdc++.h>

using namespace std;

int n;
set<int> S;
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int x; cin >> x;
        S.insert(x);
    }
    int cnt = 0;
    for(auto &x : S) {
        cnt++;
        if(cnt == 3) {
            cout << x << endl;
            break;
        }
    }
    if(cnt < 3) cout << -1 << endl;
    return 0;
}

有趣的排序

分析

本质是在找原序列可以作为排序后序列前缀序列的长度。然后用n减掉这部分长度就好。
看code,可能更容易明白。

参考code

#include <bits/stdc++.h>

using namespace std;

vector<int> x;
int solve(vector <int> a) {
    vector <int> b;
    b = a;
    sort(b.begin(), b.end());
    int q,n = a.size()-1;
    q = -1;
    for(int i = 0; i <= n; i++) {
        if (a[i] == b[q + 1]) {
            q++;
            if(q == n) break;
        }
    }
    return n - q;
}
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int tmp; cin >> tmp;
        x.push_back(tmp);
    }
    cout << solve(x) << endl;
    return 0;
}

寻找三角形

分析

暴力枚举,统计就好了。
这里需要计算一个三角形面积,用叉积或者海伦公式都可以。

参考code

#include <bits/stdc++.h>

using namespace std;

#define mul(x) ((x)*(x))

char type[55];
double x[55], y[55], z[55];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> type[i] >> x[i] >> y[i] >> z[i];
    }
    double ans = 0.0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            for(int k = 0; k < j; k++) {
                int ok = 0;
                if(type[i] == type[j]) if(type[i] == type[k]) ok = 1;
                if(type[i] != type[j]) if(type[i] != type[k]) if(type[j] != type[k]) ok = 1;
                if(!ok) continue;
                double ux = x[j] - x[i], uy = y[j] - y[i], uz = z[j] - z[i];
                double vx = x[k] - x[i], vy = y[k] - y[i], vz = z[k] - z[i];
                double area = sqrt( mul(ux * vy - vx * uy) + mul(uy * vz - vy * uz) + mul(uz * vx - ux * vz) );
                ans = ans > area * 0.5 ? ans : area * 0.5;
            }
        }
    }
    printf("%.5lf\n", ans);
    return 0;
}

不等式数列

分析

dp[i][j]表示前i个数字构成的数列中，恰有j个‘<’号的方案数（‘>’号就有i - j - 1个）。

dp[i][j] = dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1)

参考code

#include <bits/stdc++.h>

using namespace std;

int n, k, ans;
int dp[1005][1005];
int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        dp[i][0] = 1;
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= k; j++)
            dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1)) % 2017;
    cout << dp[n][k] % 2017 << endl;
    return 0;
}