乐趣区

算法第一课学习笔记

jiezi

一、哈佛大学智商测试（离散数学）

1. 题目

皇帝不是穷人，在守财奴之中也有穷人，所以，有一些（）并不是（）。

  • A. 皇帝，皇帝
  • B. 守财奴，守财奴
  • C. 守财奴，皇帝
  • D. 皇帝，守财奴

2. 解答

这题可以采用离散数学中的逻辑推理来做，
首先，假设下列命题为真：

  • p: 这个人是皇帝
  • q: 这个人是穷人
  • r: 这个人是守财奴
  • 皇帝不是穷人：p → ¬q
  • 在守财奴之中也有穷人：∃x(x∈r ⋀ x∈q)

然后，根据 p → ¬q 得到其逆否命题 q → ¬p 也为真，

此时，由 ∃x(x∈r ⋀ x∈q) 和q → ¬p，根据假言三段论可推知
∃x(x∈r ⋀ x∈¬p)，

翻译之后就是：存在一些人是守财奴且不是皇帝。

故而此题选 C，有一些守财奴并不是皇帝。

3. 相关知识：假言三段论

假言三段论又称假言推理。假言推理总是以假言判断为前提来进行推理的。
在逻辑运算符记号中表示为：

  • p → q
  • q → r
  • 所以 p → r

经典例子：

人都是要死的，
苏格拉底是人，
所以苏格拉底是要死的。

参见：Hypothetical syllogism – Wikipedia

二、天平和硬币

1. 题目

现在有 16 枚外形相同的硬币，其中一枚是假币，且己知假币比真币重量轻。先给定一架
没有砝码的天平，问 至少 需要多少次称量才能找到这枚假币？

思考：给出一种称量方案容易，但如何证明这种方法用到的称量次最少呢？

2. 解答

可以采取三分法，将硬币分为三堆：

  • A：5 枚
  • B：5 枚
  • C：6 枚

先称量 A 和 B，若 A（或 B）较轻，则可以通过将 5 枚硬币再分为 2 枚、2 枚、1 枚三堆来称量，最多需要两次称量找出假币。

若 A 和 B 平衡，则假币在剩下的六枚硬币中，将其分为 2 枚、2 枚、2 枚三堆，天平两端各放两枚，无论平或不平，最多只需要两次称量就能找出假币。

综上，至少需要称量 3 次才能找到假币。

3. 理论下界

既然一次天平称量能得到左倾、右倾、平衡三种情况，若把一次称量当成一位编码，该编码是 3 进制的，则该问题转换为：用多少位编码能够表示 16 呢？

解答：假设需要 n 位，则3^n >= 16, 两边取对数得到n >= 2.52，这表示至少 3 次才能找到该轻质的假币。

三、链表相加

1. 题目

给定两个链表，分别表示两个非负整数，它们的数字按逆序存储在链表中，且每个结点只存储一个数字，计算两个数的和，并且返回和的链表头指针。

例如:

输入:
2 -> 4 -> 3
5 -> 6 -> 4
输出:
7 -> 0 -> 8

2. 分析

因为两个数都是逆序存储，正好可以从头向后依次增加，注意考虑进位以及两个数的位数不相同的情况。

3. 代码

/**
 * 两个链表相加
 */
LinkList add(LinkList L1, LinkList L2){LinkList sum = new LNode(0);
    int carry = 0; // 进位
    LNode *p = sum, *q, *k;
    LNode *p1 = L1->next, *p2 = L2->next;
    while (p1 && p2)
    {
        // 处理加和与进位
        q = new LNode(0);
        q->value = (p1->value + p2->value + carry) % 10;
        carry = (p1->value + p2->value + carry) / 10;
        // 插入结点
        p->next = q;
        p = q;
        // 处理下一位数字
        p1 = p1->next;
        p2 = p2->next;
    }
    // 处理剩下的较长的链
    q = p1 ? p1 : p2;
    while(q){
        // 处理加和与进位
        k = new LNode(0);
        k->value = (q->value + carry) % 10;
        carry = (q->value + carry) / 10;
        // 插入结点
        p->next = k;
        p = k;
        // 处理下一位数字
        q = q->next;
    }
    // 处理可能存在的进位
    if(carry)
        p->next = new LNode(carry);
    return sum;
}

四、链表的部分翻转

1. 题目

给定一个链表，翻转该链表从 m 至 n 位置的元素，要求直接翻转，不能申请新空间。（假定参数的范围满足：1 <= m <= n <= 链表长度）

例如

输入:
1 -> 2 -> 3 -> 4 -> 5, m=2, n=4
输出:
1 -> 4 -> 3 -> 2 -> 5

2. 分析

空转 m - 1 次，找到第 m - 1 个结点，即开始翻转的第一个结点的前驱，记为 head，再以 head 为起始结点遍历 n - m 次，将第 i 次遍历的结点使用头插法插入到 head 的 next 中，最后得到翻转之后的链表。

3. 代码

示意图：

/**
 * 链表从 m 到 n 进行翻转
 */
LinkList reverse(LinkList &L, int m, int n){
    LNode* p = L->next, *pre, *phead, *pnext;
    int i = 0;
    for(; i < m-1; i++){
        phead = p;
        p = p->next;    
    }  
    pre = p;
    p = p->next;
    for(; i < n; i++){
       pnext = p->next;
       p->next = phead->next;
       phead->next = p;
       pre->next = pnext;
       p = pnext; 
    }
    return L;
}

五、链表划分

1. 题目

给定一个链表和一个数 x，将链表划分为两个部分，使得划分后小于 x 的结点在前面，大与 x 的结点在后面。在这两个部分中元素要保持原来链表中的出现顺序。

例如

给定链表 1 -> 4 -> 3 -> 2 -> 5 -> 2 和 x=3
返回 1 -> 2 -> 2 -> 4 -> 3 -> 5

2. 分析

分别申请两个指针 p1 和 p2，小于 x 的添加到队列 p1 中，大与等于 x 的添加到 p2 中，最后将 p2 链接到 p1 的末端即可。
该算法时间复杂度为 O(N)，空间复杂度为 O(1)，该算法其实说明了 快速排序对于单链表存储结构依然适用。

3. 代码

/**
 * 链表划分
 */
LinkList divide(LinkList &L, int x){
    // p_left_head 小于 x 的元素
    // p_right_head 大于等于 x 的元素
    LNode* p_left_head = new LNode(-1);
    LNode* p_right_head = new LNode(-1);
    // 分别指向两个链表当前的最后一个元素
    LNode* left = p_left_head;
    LNode* right = p_right_head;
    LNode* p = L->next;
    while(p){if(p->value < x){
            left->next = p;
            left = p;
        } else {
            right->next = p;
            right = p;
        }
        p = p->next;
    }
    // 将 right 链接到 left 尾部
    left->next = p_right_head->next;
    right->next = NULL;
    // 将链表赋值给 L
    L->next = p_left_head->next;
    // 销毁两个链表的头结点
    delete p_left_head;
    delete p_right_head; 
    return L;
}

六、排序链表去重

1. 题目

给定一个排好序的链表，删除其重复元素，只保留重复元素第一次出现的结点，进一步考虑，若将重复元素全部删除呢？

2. 代码

/**
 * 已排序链表去重(相同元素只保留其中一个)
 */
LinkList remove_repeat_item_1(LinkList& L){
    LNode *p = L, *q = p->next;
    while (q){if(q->value == p->value){
            p->next = q->next;
            delete q;
        } else 
            p = q;
        q = p->next;
    }
    return L;
}
/**
 * 已排序链表去重(相同元素全部删除)
 */
LinkList remove_repeat_item_2(LinkList& L){
    LNode *pre = L, *cur = L->next, *next;
    bool isDup;
    while (cur)
    {
        next = cur->next;
        isDup = false;
        while (next && (cur->value == next->value))
        {
            pre->next = next;
            delete cur;
            cur = next;
            next = cur->next;
            isDup = true;
        }
        if(isDup){
            // 此时 cur 与原数据重复，删除
            pre->next = next;
            delete cur;
        } else {pre = cur;}
        cur = next;
    }
    return L;
}
退出移动版