有没有一段代码，让你为人类的智慧击节叫好？ 第1页

0x5f3759df

不知道有知道这个梗的没有？

客户的机器有在国内的有在国外的，aws 的机器本机看不到公网 ip，需要判断机器到底在国内还是国外，再来判断后面脚本的执行路径。想了很多办法，包括往我们的服务器发一个请求我们通过ip判断地理位置之类的等等，最后的解决方案：

       # Guess your location, you know it. location='oversea' curl --connect-timeout 1 https://google.com 2>&1 >/dev/null ret=$? if [ $ret -ne 0 ]; then     location='cn' else     .......     

机智如中国人

如何单独使用正则表达式验证所有email地址？

坐稳了！答案是：

(?:(?: )?[ ])*(?:(?:(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*))*@(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*|(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*)*<(?:(?: )?[ ])*(?:@(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*(?:,@(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*)*:(?:(?: )?[ ])*)?(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*))*@(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*>(?:(?: )?[ ])*)|(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*)*:(?:(?: )?[ ])*(?:(?:(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*))*@(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*|(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*)*<(?:(?: )?[ ])*(?:@(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*(?:,@(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*)*:(?:(?: )?[ ])*)?(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*))*@(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*>(?:(?: )?[ ])*)(?:,s*(?:(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*))*@(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*|(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*)*<(?:(?: )?[ ])*(?:@(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*(?:,@(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*)*:(?:(?: )?[ ])*)?(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|"(?:[^" \]|\.|(?:(?: )?[ ]))*"(?:(?: )?[ ])*))*@(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*)(?:.(?:(?: )?[ ])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?: )?[ ])+||(?=[["()<>@,;:\".[]]))|[([^[] \]|\.)*](?:(?: )?[ ])*))*>(?:(?: )?[ ])*))*)?;s*)

上述正则表达式有 6.2kb，由于太过复杂，并不适宜人类阅读，建议直接调用。

我用 Python 3.8.12 做一个测试：（请不断拖拽代码块下方的滑块）

       # 导入正则表达式模块 import re  # 设定验证规则 regex = r'(?:(?:
)?[ 	])*(?:(?:(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*))*@(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*|(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*)*<(?:(?:
)?[ 	])*(?:@(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*(?:,@(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*)*:(?:(?:
)?[ 	])*)?(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*))*@(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*>(?:(?:
)?[ 	])*)|(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*)*:(?:(?:
)?[ 	])*(?:(?:(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*))*@(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*|(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*)*<(?:(?:
)?[ 	])*(?:@(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*(?:,@(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*)*:(?:(?:
)?[ 	])*)?(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*))*@(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*>(?:(?:
)?[ 	])*)(?:,s*(?:(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*))*@(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*|(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*)*<(?:(?:
)?[ 	])*(?:@(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*(?:,@(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*)*:(?:(?:
)?[ 	])*)?(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|"(?:[^"
\]|\.|(?:(?:
)?[ 	]))*"(?:(?:
)?[ 	])*))*@(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*)(?:.(?:(?:
)?[ 	])*(?:[^()<>@,;:\".[] 00-31]+(?:(?:(?:
)?[ 	])+||(?=[["()<>@,;:\".[]]))|[([^[]
\]|\.)*](?:(?:
)?[ 	])*))*>(?:(?:
)?[ 	])*))*)?;s*)'  # 定义验证函数 def mailvalidate(mailaddress):     if (re.fullmatch(regex, mailaddress)):         print("Valid Email")     else:         print("Invalid Email")  # 对地址“contact@wired.me.uk”进行验证 mailvalidate("contact@wired.me.uk")     

验证结果有效：Valid Email

据说，该正则表达式能验证所有 RFC822 格式的email地址！

如果服气请点赞，如果不服请留言。

我在这里提供我见识到的三个精彩算法的解析，强烈地推荐给初学的算法爱好者，它们可能会令你眼界大开，同时坚定你在算法大道上勇往直前的信念。

#3. 二进制是人类的好朋友，在线的树的最近公共祖先（LCA）算法：

利用数的二进制表示可以产生很多加速算法，online-LCA是其中之一。许多算法的加速是对数率的，就是利用了数的二进制表示。

首先定义二维数组：prede[N+1][B+1], N表示树的结点的数量，结点以数字1到N代指，B满足条件：2^(B)>=N

令fa[i]表示结点i的父结点，那么prede[i][b]的含义是：

       prede[i][0] = fa[i]; prede[i][b] = prede[prede[i][b-1]][b-1]; // b >= 1     

也就是说，prede[i][b]指的是从结点i往上走2^(b)步，所到达的结点。如果走到了尽头，就令prede[i][b]为0。

我们只需要O(NlogN)的复杂度，就可以完成prede的初始化。此外，我们还需要预处理出所有结点的高度，也就是depth[i]，定义为：

       depth[root] = 0; depth[i] = depth[fa[i]] + 1;     

当遇到询问LCA(x, y)，我们只需要采取如下行动，就可以O(logN)的代价获得答案：

       int lca(int x, int y) {      if (depth[x] > depth[y]) swap(x, y);      for(int i = B; i >= 0; i --){          //令x和y高度一致          if (depth[prede[y][i]] >= depth[x]) y = prede[y][i];      }      //注意此时有可能出现x == y，那么LCA(x,y) == x，下方的for      //就不起作用了。      for(int i = B; i >= 0; i --){         //如果prede[x][i]和prede[y][i]不相同，说明这两者的高度         //都大于所求的LCA(x,y)，也就是在LCA(x,y)的下方，此时令         //x和y一同往根部以2^(i)的步数爬升         if (prede[x][i] != prede[y][i]) x = prede[x][i], y = prede[y][i];      }      if (x == y) return x;   //此时LCA（x,y) = x      return prede[x][0];     //此时x和y有共同的父结点 }      

上述代码的精髓在于两个for(int i = B; i >= 0; i --)，这里利用了数的二进制表示。可以证明，对于任何严格小于2^(B+1)的非负整数t，下面的代码运行之后可以令a == t，

       int a = 0;    for(int i = B; i >= 0; i --){      if(a + (1<<i) <= t) a += (1<<i); }      

#2. 集合之交，树状数组，动态更改、查询数组前缀和算法。

实现树状数组所需的代码极为简易，实际上它是一棵残缺的线段树，它可以实现一部分线段树的功能（但凡可以化为区间求和的问题基本上都能解决），但是毕竟不如线段树功能完整，有兴趣的读者应该学习一下线段树的知识。

问题描述：利用预处理的前缀和数组pre[N + 1]，我们可以O(1)的代价对静态的数组A[N + 1]求取区间和：

pre[i] = A[0] + A[1] + A[2] + ... + A[i];

A[a] + A[a+1] + A[a+2] + ... + A[b] = pre[b] - pre[a-1];

但是当需要对数组A进行动态的更改时，上述代码就失效了。我们需要一种算法，可以动态地更改以及查询前缀和数组pre[N+1]。下面首先展示树状数组的代码，然后解释其数学原理，它的插入和查询的代价都是O(logN)：

       int Count[BiggestN+1], N; //使用前令Count所有元素为0，规定A[0]没有数                           //据，也就是说数据从A[1]开始存，pre[0]总为零  //实现功能A[i] += add void insert(int i, int add) {     while( i <= N )     {         Count[i] += add;         i += i&(-i);     } } //返回pre[i]的值 int query(int i) {     int num = 0;     while( i > 0 )     {         num += Count[i];         i -= i&(-i);     }     return num; }      

算法中最关键的语句是位操作i&(-i)，读者在稿纸上算一算就可以知道：

i -= i&(-i)的功能是令i的最低的非0位变为0；

i += i&(-i)的功能是令i的最低的非0位变为0，并往更高一位进一。

理解树状数组的行为，需要构造两个集合：

Define lowbit(i) = i&(-i);

up(a) = {a, a1, a2, ...}, ai = a(i-1) + lowbit(a(i-1));

down(a) = {a, a1, a2, ..., 0}, ai = a(i-1) - lowbit(a(i-1));

可以证明，对于任何a <= b的正整数对(a,b)，up(a)和down(b)的交集都有且仅有一个元素。对这个定理进行含糊的说明是很容易的，a == b的情况不必考虑，a < b时，总有一个最大的i，使得b的第i位大于a的第i位（也就是b的第i位是1，而a的第i位是0）,那么对b产生down(b)，对a产生up(a)，它们的唯一交集就是(1<<i)。注意这里讨论的第i位的i是从0开始索引的。读者可以在稿纸上找若干数对进行实验来加深印象。

有了上述定理，我们就不难意会insert函数和query函数的作用了。

#1. 机器浮点数的秘密，"巧夺天工"的完美实例，基于标准浮点数的快速开平方倒数算法

这是一个公开的秘密，这是一个所有程序员得以欣赏的智慧之美。她在许多程序员的心目中高居“最美代码”的第一位，所有溢美之词都无法表达他们所感受到的震撼。

一定会有许多人想在这里贴这段代码，少年，来我这里，我帮你揭开她神秘的面纱。

公式太多，贴图讲解。

Vote Me Up If You Like My Answer ^_^

花费一天一夜写了一个巨复杂的代码，测试我同时发微信的三个女生跟我交往的可能性。

里面涵盖了我苦心计算的各种友好度估分，回复微信长度，回复等待时间，有没有图片，语音，女孩主动程度，
每个都有分值。
以及我发送微信过去，预计收到的微信长度，等待时间。
我还导出微信，整理了一个我的经典套话100句。
供我没话题说的时候随机选择。
经过我一礼拜的实验修正，使得女生回复我的时间，内容长度误差在10%以内。
还可以导出一堆EXCEL图表供我分析。

我每天晚上乐此不疲的和她们三个聊天做实验修改我的参数。

里面一个女孩的对我友好度逐渐远超其他女孩。

超过我设计的100分上限。果断约出来强行牵手

（虽然是程序员也知道表白死，坚决不表白，直接拉手）

最后追到这个小姑娘，完全符合我的预算。

哥那段代码绝对壮绝古今。

我认为我那段代码的最终版已经把追女孩上升到一个模式化。

完全可预计结果。我简直无敌了。

后面因追到女生后一高兴删除了，后面分手懒得再写了。

分手原因是我加班太多。她家人喜欢公务员。。。

真心佩服PID！！！暂时绝对是我觉得最惊艳的东西了。

经典的东西往往是简单的！而PID控制算法恰好就符合了这一点，短短一个公式，十多航。

在工业应用中，PID及其衍生算法几乎是应用最广泛的算法。而它问世的六十、七十年以来，一直在使用，仍未淘汰。至于在我们学生当中，假如对PID足够熟悉，对PID的参数整定熟练的话，我觉得参加电子设计（控制类），飞思卡尔智能车，机器人比赛等这类的比赛，获奖的压力肯定会小很多很多。其他类型的创新项目只要涉及到控制类的，问题也应该不大了吧。至于其他领域，我就不太清楚了，毕竟也没太多接触。

下面来大概介绍下这个算法。

首先，这些介绍都是之前做比赛或是电子设计时，从网上搜集到的各种资料（仔细看完应该可以大概入门了吧）。 所以假如有侵犯个人版权之类的，请联系我。我会立刻改正，并补上作者。毕竟是第一次完整答题，有什么问题，请大家提出，谢谢~

不废话，进入正题，开启搬运工模式

******************************************************************************************

第一，就是这张图了

PID 对应的就是 比例（Proportion）、积分（Integration）、微分（Differentiation），对应着上面的图，意思就是。通过一个输入量（偏差值），经过比例、积分、微分、的运算后（应用时不一定需要三个步骤都有）得到一个输出量（结果）。再把这个输出量直接给执行部件，执行操作。此后通过，传感器得到实际值时，再于目标值作差，传给输入量。接着，一直循环下去。直到你所需要控制的那个量慢慢逼近，达到你设定的目标值为止。

最简单的例子就是，利用PWM，编码器的反馈量来对小车的车速形成一个闭环控制。

连续形式的时域表达式

而我们实际实用时，只需要在公式中定义 、 、 这三个变量。

(实在实在不好意思，后天有一门考试。现在还没好好复习完.....考完再好好整理更新，行嘛？）

下面是一段不完整的程序，还未整理。中间的motorgun,对应的就是PID这个公式。直接可以把一个角度传感器传进来的角度值 通过计算得到一个数字后，把它赋给电机的PWM值。随后经过多次运算，实际角度值就能慢慢接近目标角度值。

       void PID (void) {  NOWPOS = GET_POS();    // 通过传感器获得当前值  MOTOGUN = 0;           //   pid.LastError = NOWPOS - pid.SetPoint; // 用当前值减去目标的，得到输入的那个偏差          pid.SumError+= pid.LastError;   // 中间积分项的累加                   MOTOGUN = pid.P*pid.LastError +                   pid.I*pid.SumError +                   pid.D* (pid.LastError - pid.PrevError)；//此处是PID的公式！！          pid.PrevError = pid.LastError;     MOTOR(MOTOGUN);                 //直接把计算值给了电机PWM程序 }   我先提到这，假如大家对PID特别感兴趣，可以先到网上查找。实在不好意思~~     

分享几个第一次看到就被它的优美深深震撼到的代码：

1、线性求逆元：

       for (int i = 2; i < MAXN; i++)  inv[i] = mul(inv[mod%i], mod - mod / i, mod);      

仅仅两行代码，就实现了在$O(n)$的时间内求出1到n对模m的逆元有木有！？

2、求最大公因数：

       int gcd(int x, int y){return y ? gcd(y, x%y) : x;}      

第一次接触到这样的代码时，我的内心是这样的：

wtf???黑人问号.jpg

3、树状数组

对于单点修改区间求和，树状数组可谓达到了时空复杂度的极限，甚至不多用额外一字节存储空间。来看看它的实现：

修改：

       void add(int i, int x){  for (;i <= n; i += i & -i)tree[i] += x; }      

查询：

       int sum(int i){  int ret = 0;  for(; i; i -= i & -i)ret +=tree[i];  return ret; }      

表示记性不好的我看完一遍也记住了呢。

4、zkw线段树

对于单点修改区间查询的线段树，zkw大神实力教你如何1分钟内码出代码：

修改：

       void set(int x, int value){  val[x += treeLen] = value;  while (x >>= 1)pushUp(x); }      

查询：

       int query(int l,int r){  int ret = 0;  for (l += treeLen - 1, r += treeLen +1; l ^ r ^ 1; l >>= 1, r >>= 1){   if (~l & 1)ret = min(ret, val[l^1]);   if (r & 1)ret = min(ret, val[r ^ 1]);  }  return ret; }      

以上都是一些十分基础但真的让你赞不绝口的算法和数据结构。还有一些稍微复杂一些的栗子，由于手机码代码太不方便了，就以后再更吧。（如果有笔误打错的地方欢迎指正哈）

5、后缀数组的DC3算法，反正学完它的一瞬间我是明白了，天才和普通人的智商差距简直比人和狗还大啊。。。

6、快速傅里叶变换的数论版本（即NTT）：学完后有种想去数学系的冲动（还好后来冷静下来了）。费马素数群的性质居然和复数完美吻合，不得不说是一种奇迹啊。

7、主席树：这是fotile巨佬考场上发明这种数据结构，用于在$O(log n)$的时间复杂度内解决序列区间第k大问题，以及区间内元素的排名。个人感觉他比划分树的设计巧妙多了，有一种自然的美感。

8、Pollard因数分解算法：如果你真的把关于时间复杂度的证明一步步看完后，相信你会有一种豁然开朗的感觉。这个算法真正高的地方在于把生日悖论和递推式循环节巧妙的结合在一起，最后运用递推方程主定理的理论，使得时间复杂度达到了看似不可能的期望$n^0.25$的数量级。

其实现在感觉一切和数据结构或数学有关的算法都是非常优美的，前者在于设计的精巧性，后者在于证明的环环相扣，达到引人入胜的效果。

0 引言

这个题我已经留坑很久很久了，但是最近忙于赶一篇论文，5月31日是投稿截止日期。今天终于是把论文写完了，于是准备把留的坑都填一填。

前辈们已经把很多经典的、让人眼前一亮的代码展示出来了。我虽然不是码农，但也经常会看一些奇怪的代码。这里我列举五个我觉得最有趣、最好玩的代码给大家。这些代码一部分已经在之间的回答给出了，但为了Self-Contained，我也把这些已经给出的代码再次展示出来，并给出原始答案的链接、作者以及出处。

前方多图预警，超长答案预警，建议在WiFi环境下观看。

=============================

1. 真正改变世界的算法：向杰出的数学和计算机科学家们致敬

真正改变世界的是那些依托于数学的，真正高大上的代码。知乎er

提到的“支配世界的10个算法”（The real 10 algorithms that dominate our world，

）就是10个这类典型的算法。让我惊喜的是，这10个算法中竟然有4个与密码学相关（RSA算法，安全Hash算法，整数分解算法，随机数生成算法）。难道说真正掌控世界的是密码学嘛（笑）。作为一个密码学研究者，我感觉很激动啊！具体的内容 知乎er

已经回答的非常详细了，请大家参考他的答案（

）。作为致敬，我仅列出这10个算法，并请大家一起像这些杰出的科学家们致敬。

• 三种排序算法。归并排序（Mergesort），提出者：约翰·冯·诺尼曼（John von Neumann），现代计算机创始人；快速排序（Quicksort），提出者：托尼·霍尔（Tony Hoare），1980年图灵奖获得者；堆排序（Heapsort），基于计算机基本数据结构堆（Heap）的排序方法。
• 傅里叶变换（Fourier Transform），提出者：约瑟夫·傅立叶（Joseph Fourier），温室效应的发现者，名字被刻在埃菲尔铁塔的72位法国科学家与工程师的其中一位。小行星10101号以傅里叶命名；快速傅里叶变换（Fast Fourier Transform），原始提出者：约翰·卡尔·弗里德里希·高斯（Carolus Fridericus Gauss），历史上最重要的数学家之一，被誉为“数学王子”。
• Dijkstra最短路径算法（Dijkstra Shortest Path Algorithm）。提出者：艾兹赫尔·戴克斯特拉（Edsger Wybe Dijkstra），1972年图灵奖获得者。
  
• RSA公钥密码体制（RSA Public Key Cryptosystem）。提出者：罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）。他们为2002年图灵奖获得者。
• 安全Hash算法（Secure Hash Algorithm）。一些经典的安全Hash算法及其提出者们。MD5算法，提出者：罗纳德·李维斯特（Ron Rivest），2002年图灵奖获得者。SHA家族（SHA-1，SHA-224，SHA-256，SHA-384，SHA-512），提出者：美国国家安全局（National Security Agency）。值得注意的是，MD5以及SHA-1算法在2005年由中国密码学家王小云、殷益群、于红波从理论上破解。王小云因“国际通用Hash函数的破解”获颁陈嘉庚科学奖信息技术科学奖。
• 整数分解（Integer Factorization）。该问题已可以在量子计算机上以多项式复杂度解决，被称为秀尔算法（Shor Algorithm），提出者：彼得·威廉·秀尔（Peter Williston Shor），1998年奈望林纳奖（Nevanlinna Prize，计算机科学的数学方面重要贡献奖，每4年一届，得奖者在获奖当年不得大于40岁）获得者。
• 链接分析（Link Analysis）。提出者：Gabriel Pinski、Francis Narin。
• 比例积分微分算法（Proportional Integral Derivative Algorithm）。提出者：尼古拉斯·米诺尔斯基（Nicolas Minorsky）。
• 数据压缩算法（Data Compression Algorithms）。包括数据压缩、图像压缩等等。
• 随机数生成器（Random Number Generation）。

=============================

2. 数学拯救计算机科学算法：Quake III源代码中的玄机

很多知乎er们都提到了一个神奇的数0x5f3759df（

，

等）。追溯这个数的来源，我们就要谈到一个经典游戏Quick III了。Quick III从现在的眼光看来实在不是一个很精细的游戏。但是在当时，Quick III的画质简直是狂暴酷炫掉渣天。在Quick系列，Doom系列，及其3D引擎出现之前，有谁能想到计算机也可以显示如此神奇的3D效果呢？

这个3D引擎的开发者是约翰·卡马克（John Carmack）。他是美国电子游戏程序员，ID Software（一个著名游戏开发公司）的创始人之一。他在1999年，被时代杂志评选为科技领域50大影响力人物榜单，并列名列第10位。为表彰他的在电子游戏和电视游戏领域所作出的杰出贡献，卡马克称为第四位进入互动艺术和科学学院（The Academy of Interactive Arts and Science）名人堂的人物。我们来看看其余人物的名字吧（

）：

• 宫本茂：任天堂公司，《超级马里奥兄弟》的创始人。
• 丹妮·邦顿·贝瑞：名人堂游戏《M·U·L·E》的制作人。
  
• 席德·梅尔：FiraxisGames公司，《文明》系列的制作人。
  
• 铃木裕：世嘉公司，众多街机游戏的制作人。
• 威尔·赖特：Maxis公司，《模拟城市》系列的制作人。
  
• 坂口博信：Square Enix公司，《最终幻想》系列的制作人。
  
• 理查德·加略特：NCsoft / DestinationGames公司，《创世纪》系列的制作人。
  
• 彼得·莫利纽克斯：牛蛙公司，《上帝也疯狂》，《主题公园》，《主题医院》，《地牢守护者》制作人。
  
• 特里普·霍金斯：3DO公司，《魔法门》系列，《英雄无敌》系列，《玩具兵》系列制作人。
  
• 麦克：暴雪公司，《魔兽世界》制作人。

卡马克在计算机领域最重要的贡献是，极大限度地压榨计算机计算性能，实现了一系列令人惊叹的数学函数。其中最知名的就是很多知乎er们提到的开平方取倒数算法，这个算法的基本原理是牛顿迭代法。原文出处来自

。

       float Q_rsqrt( float number ) {     long i;     float x2, y;     const float threehalfs = 1.5F;      x2 = number * 0.5F;     y  = number;     i  = * ( long * ) &y;     i  = 0x5f3759df - ( i >> 1 ); // what the fuck?     y  = * ( float * ) &i;     y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration     // y   = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed      #ifndef Q3_VM     #ifdef __linux__         assert( !isnan(y) ); // bk010122 - FPE?     #endif     #endif     return y; }        

看看这段代码吧，只用了2次叠代，而且其实根本上就没用叠代，因为算一次直接就得到结果了。这个函数的效率比C库函数中执行sqrt()函数再取倒数要快4倍。

为什么能得到如此令人惊叹的效果呢？这段代码最让人费解的就是下面这行代码：

       i  = 0x5f3759df - ( i >> 1 ); // what the fuck?      

这个0x5f3759df是个什么鬼？牛顿迭代法的原理是先猜测一个值，然后从这个值开始进行叠代。因此，猜测的值越准，叠代的次数越少。卡马克选了0x5f3759df这个值作为猜测的结果，再加上后面的移位算法，得到的y非常接近1/sqrt(n)。这样，我们只需要2次牛顿迭代法就可以达到我们所需要的精度。

普渡大学的数学家Chris Lomont看了以后觉得有趣，决定要研究一下卡马克弄出来的这个猜测值有什么奥秘。在精心研究之后，Lomont从理论上也推导出一个最佳猜测值，和卡马克的数字非常接近, 0x5f37642f。Lomont计算出结果以后非常满意，于是拿自己计算出的起始值和卡马克的神秘数字做比赛，看看谁的数字能够更快更精确的求得平方根。结果是卡马克赢了...

Lomont怒了，采用暴力方法一个数字一个数字试过来，终于找到一个比卡马克数字要好上那么一丁点的数字，虽然实际上这两个数字所产生的结果非常近似，这个暴力得出的数字是0x5f375a86。

Lomont为此写下一篇论文，"Fast Inverse Square Root"（这里原文给出的地址有误，论文的地址为http://www.files.sauliaus.info/InvSqrt.pdf）。

感谢开源GPL协议，Quick III的源代码已经公开，我们可以目睹一下Quick III的风采了。源代码下载地址为：

。这个地址需要翻墙才能下载。而那个传说中的代码，位于game/code/q_math.c中。

=============================

3. 二进制的神奇应用：基于位运算的代码系列

看到了Quick III中神奇的代码，想必知乎er们也对二进制和位运算的神奇有了一些感觉了。我最开始觉得二进制运算很有趣，是因为Leetcode中的一道题：Single Number（

）。题目如下：

Given an array of integers, every element appears twice except for one. Find that single one.

问题在于，如何在线性复杂度下实现呢？这里就要用到与或运算了。

二进制运算还有哪些神奇的应用呢？Stanford的一个Ph.D学生Sean Eron Anderson（

）自己维护了一个网站，里面列举了一大堆二进制运算的神奇应用，链接为：

。

我们来简单看几个运算：

1. 计算一个整数的符号：

       int v;      // we want to find the sign of v int sign;   // the result goes here   // CHAR_BIT is the number of bits per byte (normally 8). sign = -(v < 0);  // if v < 0 then -1, else 0.  // or, to avoid branching on CPUs with flag registers (IA32): sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1)); // or, for one less instruction (but not portable): sign = v >> (sizeof(int) * CHAR_BIT - 1);      

2. 检测两个整数的符号是否一致：

       int x, y;               // input values to compare signs bool f = ((x ^ y) < 0); // true iff x and y have opposite signs      

3. 计算一个整数的绝对值：

       int v;           // we want to find the absolute value of v unsigned int r;  // the result goes here  int const mask = v >> sizeof(int) * CHAR_BIT - 1;  r = (v + mask) ^ mask;      

还提到了Google Code上面的一个基于浮点数标准的快速算法库，里面也用到了各种二进制运算，链接为：

。

=============================

4. 能不能把代码写的够混乱：世界混乱C代码大赛

后面的几个就是比较好玩的东西了。首先我们来看看计算机学科的怪胎们是怎么玩坏C语言的。

提到了一个神奇的代码，通过计算代码本身的面积，来计算圆周率的近似值。这个代码来自世界混乱C代码大赛（International Obfuscated C Code Contest，IOCCC）。这个大赛的宗旨是，在C语言本身可以执行的条件下，看谁能写出最有创意的最让人难以理解的C语言代码。代码的长度要求限制在4kb以内。大赛的官方链接为：

。

第23届IOCCC竞赛已经在2014年10月27日结束，但是我似乎找不到源代码。我们来看看第22届IOCCC竞赛中的代码中又没有什么好玩的东西吧。因为有些代码知乎上显示的不太好，我用截图的形式给出。

Best Painting Tool（

）

Most Lazy SKLer （

）

Best Use of 1 Infinite Loop （

）

下面是以前一些比较有趣的代码：

2012，Most Elementray Use of C（

）

2012，Most Functional （

）

1998，Best of Show （

）

=============================

5. 数学也可以画图：用公式绘制任意图形

还记得一直在电视上播放的百岁山广告吗？很多人都说看不懂那个广告。其实那个广告参考了1650年著名数学家笛卡尔与瑞典公主克莉丝汀相恋的故事。具体的故事我就不再赘述了。最后，笛卡尔写给克莉丝汀的情书中出现了这样的公式：

这个公式对应的几何图形为心形，是著名的“心形线”。笛卡尔用这样一种方式，通过数学表达了对克莉丝汀的深深爱意。这封情书最后也被收录到欧洲笛卡尔博物馆中。

浪漫的故事到此为止，这引发了一个有趣的问题：我们能不能用数学公式，来构造任意几何图形呢？这个问题实际上是有解的。有人真的研究了这个问题，并给出了肯定的答案。链接如下：

。我们来看一看一些有趣的图形吧~具体的生成算法课参考上面给出的链接。

美国队长曲线（Captain America-like curve）

台灯曲线（Luxo Jr.like curve）

a^2 + b^2 = c^2

牛顿曲线

=============================

以上。

天才程序员约翰·卡马克（John Carmack）在《雷神之锤 III 竞技场》源代码中的平方根倒数速算法（Fast Inverse Square Root，Fast InvSqrt()）。该算法的意义在于减少了求平方根倒数时浮点运算操作带来的巨大的运算消耗，毫无疑问，这对游戏图形运算具有非凡意义。

自从卡马克写下这段代码，引起诸多能人异士的兴趣和探讨。其中的魔术数字——0x5f3759df——到底是什么鬼——迄今为止仍未能明确这个神秘的特殊常数起源何处......

一段代码，就像天外一剑，惊若天人造，成就如大师卡马克，此生就不枉做一名程序员了。