数学趣题

1. 格雷码

• 定义：格雷码是一个数列集合，每个数使用二进制表示，每两个相邻的数之间只有一个位元的值不同，同时最后一个数与第一个数之间也只有一个位元值不同。
• 性质：
  • 奇数项： 它与前一个格雷码相比只改动了最右边一个位元的值
  • 偶数项： 相对前一个格雷码只改变了从右数第一个1左边的一个位元的值

2. 循环移动

• 问题：给定长度为n的数组和数字i，将数组循环左移i位
• 思路：根据i将原数组分为ab两部分，原问题就变为通过ab求ba，此时可以将a翻转，将b翻转，最后将数组整体翻转。这种方式时间与空间都消耗的较少。
• 如：将数组0123456789循环左移3位
  • 数组分为a: 012 b: 3456789
  • ab分别翻转： 210 9876543
  • ab整体翻转： 3456789012

3. 找出小于n的所有素数

• 思路：从2开始，将1~n中所有2的倍数去除，3的倍数去除，直到根号n结束，剩下的数就是小于n的所有素数。

4. 找出一个字符串中有重复的且长度最长的子字符串及其长度。

   1. 对与字符串按照子字符串长度从大到小递减的方式扫描
   2. 查找源字符串中是否有重复的子字符串，若有，就结束。没有就减小子字符串的长度并重复改步骤。

5. 魔幻方阵

• 定义： 一个n阶的幻方是一个由整数1、2、3……n^2组成的方阵，方阵的每行的整数和、每列上的整数和、及两条对角线中的每条整数和都等于同一个整数s，s被称为改幻方的幻和。
• 杨辉斜排法（仅适用于n为奇数的情况）
  1. 将1放在第一行的中间，其余数按顺序、按以下规则放置
  2. 其余整数放在当前整数的斜右上方，其中有几种放置数的情况
     1. 若要放置的数处于第一行的上面，则将它置于最底行的对应列位置
     2. 若要放置的书在最右边一列的右侧，则将其放置于对应行的最左边一列。
     3. 若要放置的数字应放置的位置已经有数字放置，则将该数字置于上个放置好的数字的正下方。

6. 寻找最大的n个数

• 问题： 从一些各不相同的无序数中，找到最大的n个数
  • 直观想法： 利用快排对数据排序，然后取出最大的n个数，假设共有m个数，则时间复杂度为mlogm
    但是
  • 但若m很大，数据很多，无法一次全部都入到内存，则直接排序不再适用，此时可以考虑挑选数据集前n个数放入数组中，然后遍历升序的书，发现比数组n中最小的数大的数，就将数组中最小的数替换出来，找出n个数中最小的数可以使用小根堆，根节点的值最小，每次替换后需对数组排序，堆排序时间复杂度为logn，则总的时间复杂度为mlogn。

7. 查找数组中的最大值和最小值

• 直观想法： 遍历数组，同时与最大值、最小值作比较，一次遍历即可得到结果，这个过程中元素比较次数为2n
• 优化解法
  1. 将数组元素两两分为一组，进行组内排序，小的放前面，大的放后面。这种操作在原始数组上进行，无需额外空间，此时比较n/2次
  2. 在原始数组下标为奇数的数据中找出最大值，此时比较n/2次
  3. 在原始数组下标为偶数的数据中找出最小值，此时比较n/2次
     这种方法总共比较了3n/2次，较2n次少

8. 遍历一次单链表找到它的中间节点
   设置两个指针p和q，让p每次前进2个节点，q每次前进1个节点，当p走到终点时，q恰好在中间位置

9. 判断单链表是否有环
   设置连个指针p和q，让p每次前进2个节点，q每次前进1个节点，这样如果存在环，p指针一定会与q指针相遇，若无环，则p指针必定会先成为null

10. 判断两个链表是否相交
    若两个单链表相交，则他们相交节点之后的所有节点应该是两个链表共有的，所以最后一个节点必然相等，我们只要找到两个链表的尾节点，判断它们是否相等即可，这种思想的时间按复杂度为length(h1)+length(h2)

11. 蜗牛爬杆问题

一根31cm长的细杆，2cm、7cm、12cm、17cm、25cm处各有一只蜗牛。开始时，蜗牛头朝做还是朝右是任意的，他们只会向前走或调头，但不会后退，当任意两只蜗牛碰头时，它们会同时调头走，但速度不变，每秒走0.5cm，计算蜗牛全部离开杆的最长时间和最短时间。

• 思路：蜗牛相遇时，同时调头，速度不变，可理解为俩蜗牛“擦肩而过”，方向，速度都未变，此时蜗牛离开的最长时间按为处于2cm的那只蜗牛走到最右边的时间(31-2)/0.5=58s,蜗牛离开的最短时间为处于“中间”的那只走到离它最近的一边的时间(31-17)/0.5=28s