一、哈佛大学智商测试（离散数学）
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 → qq → 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;}