利用指针解决算法问题 | 晓江南的博客

报数问题

n个人围成一圈，编号依次为1…n，(n<=1000000)，从第一个人开始1-2报数，报到2的出列。输入n，输出最后剩下的一个人的编号。
样例输入：
13
样例输出：
11

// 使用数组的解法
int countByArray(int n){
    vector<int> v = vector<int>(n); // 1表示已经出列，初始都是0
    int current = 0;
    for (int i = 1; i <= n-1; i++){
        while(v[current] == 1) { // 找下一个0
            current = (current + 1) % n;
        }
        current = (current + 1) % n;  // 报数1，留在队列中
        while(v[current] == 1) { // 再找下一个0
            current = (current + 1) % n;
        }
        v[current] = 1;   // 报数2，出列
    }
    while(v[current]) {
        current = (current + 1) % n;
    }
    return current + 1;
}

每报数一圈都要循环n次，每轮报完数后人数减半，总共需要报数logn圈，所以此算法的时间复杂度是O(nlogn)。由于已经出队的仍然在队列中，还是要占用遍历的时间，我们希望把已经出队的删掉，链表中删掉一个元素的时间是O(1)，用循环链表解决此问题，算法的时间复杂度是O(n)。

class ListNode {    // 链表的节点类
public:
    int id; // 编号
    ListNode* next = 0;   // 指向下一个节点的指针
    ListNode(int id0){  // 初始化函数
        id = id0;
    }
};

// 使链表解法
int countByLink(int n){
    ListNode* head = new ListNode(1);
    ListNode* tail = head;

    for (int i = 2; i <= n; i++){  // 创建链表
        tail->next = new ListNode(i);
        tail = tail->next;
    }
    tail->next = head;    // 连接成环

    ListNode* current = head; // 开始报数（当前节点报1）
    for (int i = 1; i <= n-1; i++){
        current->next = current->next->next;  // 删除下一个节点（报2）
        current = current->next;  // 挪到下一个节点（报1，注意报2的已经删掉了）
    }
    return current->id;
}

分析：
这是一个约瑟夫环问题，可以推广到更一般的情况。n个人围成一圈，编号依次为1…n，(n<=1000000)，从第一个人开始1-m报数，报到m的出列。输入n，输出最后剩下的一个人的编号。
用循环链表去解决的话，算法的时间复杂度是O(nm)。

下面利用数学推导，如果能得出一个通式，就可以利用递归、循环等手段解决。下面给出推导的过程：
（1）第一个被删除的数为 (m - 1) % n。
（2）假设第二轮的开始数字为k，那么这n - 1个数构成的约瑟夫环为k, k + 1, k + 2, k +3, …..,k - 3, k - 2。做一个简单的映射。
k —–> 0
k+1 ——> 1
k+2 ——> 2
…
…
k-2 ——> n-2
这是一个n -1个人的问题，如果能从n - 1个人问题的解推出 n 个人问题的解，从而得到一个递推公式，那么问题就解决了。假如我们已经知道了n -1个人时，最后胜利者的编号为x，利用映射关系逆推，就可以得出n个人时，胜利者的编号为 (x + k) % n。其中k等于m % n。代入(x + k) % n <=> (x + (m % n))%n <=> (x%n + (m%n)%n)%n <=> (x%n+m%n)%n <=> (x+m)%n
（3）第二个被删除的数为(m - 1) % (n - 1)。
（4）假设第三轮的开始数字为o，那么这n - 2个数构成的约瑟夫环为o, o + 1, o + 2,……o - 3, o - 2.。继续做映射。
o —–> 0
o+1 ——> 1
o+2 ——> 2
…
…
o-2 ——> n-3
这是一个n - 2个人的问题。假设最后的胜利者为y，那么n -1个人时，胜利者为 (y + o) % (n -1 )，其中o等于m % (n -1 )。代入可得 (y+m) % (n-1)
要得到n - 1个人问题的解，只需得到n - 2个人问题的解，倒推下去。只有一个人时，胜利者就是编号0。下面给出递推式：
f [1] = 0;
f [ i ] = ( f [i -1] + m) % i; (i>1)
有了递推公式，实现就非常简单了，给出循环的两种实现方式。

参考链接：约瑟夫环问题

int countByFormula(int n, int m) {
    if(n < 1 || m < 1)
        return -1;

    vector<int> f(n+1, 0);
    for(int i = 2; i <= n; i++)
        f[i] = (f[i-1] + m) % i;
    return f[n] + 1;
}

1-2报数问题的特殊解法

1-2报数问题为报到2的出队，问最后剩下的一个人的编号。
结论：
$$J(n)=1, 当n=2^k$$
$$J(n)=2m+1, 当n=2^k+m$$
分情况讨论。
当n=2^k时：
如果只有2个人，显然剩余的为1号

如果有4个人，第一轮除掉2,4，剩下1,3，3死，留下1

如果是8个人，先除去2,4,6,8,之后3,7，剩下1,5，除去5，又剩下1了
……
因为每轮都会出队一半的人，每一轮的开始编号都是从编号为1的人开始，最终编号为1的人会剩下。
当n=2^k+m时：
当n=5时，2号出队，3号报数“1”，3->4->5->1形成一个n=2^2时的问题，那么剩余的人就为3号。
当n=9时，2号出队，3号报数“1”，3->4->5->6->7->8->9->1形成一个n=2^3时的问题，那么剩余的人就为3号。
当n=13时，2,4,6,8,10号出队，11号报数“1”，11->12->13->1->3->5->7->9形成一个n=2^3时的问题，那么剩余的人就为11号。
……
根据上面的递推，剩余的人的编号就为2m+1。

int countBy(int n) {
    int r = log2(n);
    int m = n - pow(2.0, r);
    return (m == 0) ? 1 : (2 * m + 1)
}

本题的算法时间复杂度就是计算对数的时间复杂度，为O(logn)。

作业题目

说出以下每条语句的含义：

int* i;    // 声明一个变量i，类型是指向整数的指针
double* d; // 声明一个变量d，类型是指向double类型的指针
Point* p;  // 声明一个变量p，类型是指向Point类型的指针
*i=3;      // 给i指向的变量赋值为3
p->x=4;    // 给p所指向的对象的成员变量x赋值为4
int *p, *q, **r; // 声明3个变量，p和q是指向整型的指针，r是指向指针的指针，指针变量同样占据内存中的某个位置
int* a[10];  // 声明一个指针数组a，数组的大小是10，存储变量的类型为指向整型的指针
vector<int*> v; // 声明一个vector容器变量v，存储变量的类型为指向整型的指针
vector<int>* v2;  // 声明一个指针变量v2，它指向的是一个存储整型变量的vector
int i = *p**q;  // 定义一个整型变量i并初始化，初始化的值为指针p指向的变量乘以指针q指向的变量。解引用运算符的优先级高于乘运算符。
*p+=i;  // 指针p指向的变量或内存单元的值加赋值i
q=&(i+*p); // &为取地址运算符。这条语句有语法错误。
r=&p;  // 指针p的地址赋给r，r为指针的指针

使用链表解决1-3报数问题。

int count3(int n) {
    ListNode* head = new ListNode(1);
    ListNode* tail = head;

    for (int i = 2; i <= n; i++){  // 创建链表
        tail->next = new ListNode(i);
        tail = tail->next;
    }
    tail->next = head;    // 连接成环

    ListNode* current = head; // 开始报数（当前节点报1）
    while(current->next != current){
        current = current->next;  // 向前走一步
        current->next = current->next->next;  // 删除报数3的
        current = current->next;  // 挪到下一个节点报1
    }
    return current->id;
}