编程珠玑 第二章总结

第二章主要强调了编程过程前中后，需要捕捉自己的灵感。
具体问题：
仅仅使用十几个字节的额外空间将一个n元向量x在正比于n的时间内向左旋转i个位置。

最容易想到的方法solution1：
solution1：开辟一个大小为i的内存块m，将x的前i个数放入m中，然后将x后n - i个数向左移动i位，再将m中的数填入x的最后i位中。
这样在极端情况下，要开辟n - 1个元素大小的内存块。

比较好的解法，是采用左右手翻转规则。x = ab
a(r)表示a的翻转
ab -> a(r)b(r) -> ba，异常简洁。
代码实现：

#include <iostream>
#include <vector>
using namespace std;

void reserve_v(vector<int> &v, int i, int j) {
    while(i < j) {
        swap(v[i], v[j]);
        i++;
        j--;
    }
}
int main(int argc, char *argv[]) {
    vector<int> v = {0, 13, 4, 5, 6, 2, 3, 0};
    // "i" is the count of elements moved left in circle;
    int i = 3;
    reserve_v(v, 0, i - 1);
    reserve_v(v, i, v.size() - 1);
    reserve_v(v, 0, v.size() - 1);
    for (auto i:v) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

如果将abc->cba，如何操作？
cba = (a(r)b(r)c(r))(r)，所以可以将a、b、c分别作逆序，然后在整个做逆序。