程序员进阶之算法练习（一）

前言

我对编程能力的认知包括三块：

• 基础知识：数据库、操作系统、网络原理等；
• 编码能力：软件架构（MVVM、MVP）、设计模式、编程语言（C、JAVA、C++）等；
• 思考能力：分析需求、算法设计、数学基础等；

大学时代，身边很多计算机、软件、网络专业的人就对算法存在莫名的反感；
刚出校门那会觉得自己玩了三年多算法没用，面试大公司的后台开发，问的都是Linux、网络编程、项目经验等；
开始项目开发之后，用到的更多是设计模式、数据库、网络编程，每日都是频繁的业务代码实现；
写了几年业务代码，慢慢熟悉工作之后，决定再捡起算法和数学。

对于来求职的人，我负责的技术面试流程都会按照这三大块大致询问一遍。
大多数人对于算法设计和数学这一块基本都是空白。

算法学习

算法的学习最简单的方式就是多练习。找一个提供算法练习的网站，思考，编码，验证，最后再看看别人的思路。
这次题目来自于codeforces，IDE用的Xcode。

实践

看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。

A

题目链接
题目大意：N（N为偶数）个数字a[i] (1 ≤ a[i] ≤ 100)，把数字平分 N/2 组，使得每组的数字和相等。
代码实现：

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        node[i].pos = i + 1;
        cin >> node[i].value;
    }
    sort(node, node + n);
    for (int i = 0; i < n / 2; ++i) {
        cout << node[i].pos << " " << node[n - i - 1].pos << endl;
    }

题目解析：

假设最后的和为k，那么有k = sum / (N / 2); sum为所有数字之和。
对于数字a[i]，在数组中查找没有分配过的a[j] = k - a[i]即可。

优化：对n个数字的数组从小到大排序，对于a[0]（最小），它的另一个必然是a[n - 1]（最大）;
证明：假设a[0]对应的是a[n -2]，并且a[n -2] < a[n -1]，那么对于a[n -1]的数字和另外一个数字之和必然大于a[0]+a[n - 2]；

B

题目链接
题目大意：NxN的棋盘，每个格子可以放一个车，有M个车，问：每个车放完后，棋盘还剩多少格子是所有车攻击范围外？
n and m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ min(100 000, n^2))

代码实现：

  long long n, m, sum;
    cin >> n >> m;
    sum = n * n;
    long long rowNum, colNum;
    rowNum = colNum = 0;
    while (m--) {
        int x, y;
        cin >> x >> y;
        if (!row[x]) {
            sum -= n - colNum;
        }
        if (!col[y]) {
            sum -= n - rowNum;
        }
        if (!row[x] && !col[y]) {
            ++sum;
        }
        if (!row[x]) {
            ++rowNum;
            row[x] = 1;
        }
        if (!col[y]) {
            ++colNum;
            col[y] = 1;
        }
        
        cout << sum << " ";
    }

题目解析：

棋盘放下去一个车有横竖的影响，分开考虑。
对于横行，如果之前已经放过，没有影响；如果之前没有放过，那么看有多少列已经添加，得出影响到的cell为n - colNum;
对于纵列，如果之前已经放过，没有影响；如果之前没有放过，那么看有多少行已经添加，得出影响到的cell为n - rowNum;
如果行和列都没添加过，那么会有个重叠的计算，需要去除：sum = sum + 1;

C

题目链接
题目大意：长度为n的字符串，找到最短的区间，包含字符串出现过的所有字符，输出区间长度。
n (1 ≤ n ≤ 100 000)
代码实现：

  
    int n, sum = 0;
    cin >> n;
    cin >> str;
    for (int i = 0; i < n; ++i) {
        if (!flag[str[i]]) {
            flag[str[i]] = 1;
            ++sum;
        }
    }
    
    int left = 0, k = 0;
    int ret = n;
    for (int i = 0; i < n; ++i) {
        if (!c[str[i]]) {
            ++k;
        }
        ++c[str[i]];
        
        if (k == sum) { //[left, i]区间，存在答案
            while (c[str[left]] > 1) {
                --c[str[left]];
                ++left;
            }
            ret = min(ret, i - left + 1);
        }
        
    }
    
    cout << ret << endl;

题目解析：

假设[1, right] 包含了所有的字符，其中：[left, right]这个区间就包含了所有的字符，那么[1, left]可以舍弃；

D

题目链接
题目大意：n个人要走一段路，路的长度为l，人的速度为v1，租了一辆载客量为k的车，速度为v2，上下车和车掉头的时间忽略不计；所有人只坐一次汽车； 问：最少需要多少时间才能完成这段路程？
(1 ≤ n ≤ 10 000, 1 ≤ l ≤ 10^9, 1 ≤ v1 < v2 ≤ 10^9, 1 ≤ k ≤ n)
代码实现：

    long long n, v1, v2, l, k;
    cin >> n >> l >> v1 >> v2 >> k;
    long m = (n + k - 1) / k;
    double tmp = (v2 - v1) * 1.0 / (v1 + v2);
    double t2 = l /((m - 1) * 1.0 * v1 * (tmp + 1) + v2);
    double tb = tmp * t2;
    double ret = (m - 1) * tb + m * t2;
    printf("%.7f", ret);

题目解析：

要尽快的到达目的地，我们可以制定如下的策略：
1、车每次都要尽可能载更多的人；
2、车在开的同时人也走；
3、车开一段路后就让人下车，接着走，然后回去接新的人；

 要让时间最少，则必须所有人到达终点时间的时间一致；
 * 因为每个人只能坐一次车，那么每个人坐车的时间应该是一致的，假设其为T1；车子每次载客完之后还要回来，这个时间为T2；
 * 把人分成m组（由n和k统计而得），除了最后一组人，车每次都要经历一次T1+T2，最后一次组是T2的时间；
 * 每个人走路的路程=v1 * （T1 + T2) * (m - 1)；
 每个人坐车的路程=v2 * t；
 v1 * （T1 + T2) * (m - 1) + v2 * t = l
 * T1和T2受到速度v1和v2的影响
 车子开出去的路程 v2 * T2;
 人被接到之前走的路程 v1 * (T1 + T2);
 车子返程的时间 v2* T2;
 v2 * T2 = v1 * (T1 + T2) + v2 * T2;

总结

这次所有题目的代码在这里CF701。