Algorithm
LeetCode算法题
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N A P L S I I G Y I R And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows); Example 1:
Input: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR” Example 2:
Input: s = “PAYPALISHIRING”, numRows = 4 Output: ”PINALSIGYAHRPI” Explanation:
P I N A L S I G Y A H R P I
Java 程序实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public String convert(String s, int numRows) {
if (s == null || s.length() <= 1) {
return s;
}
if (numRows <= 1) {
return s;
}
// init appender
StringBuilder[] sbs = new StringBuilder[numRows];
IntStream.range(0, numRows).forEach(i -> sbs[i] = new StringBuilder());
int len = s.length();
int N = numRows;
for (int i = 0; i < len; i++) {
int remainder = i % ( 2 * N - 2);
int idx = remainder < N ? remainder : 2 * N - 2 - remainder;
sbs[idx].append(s.charAt(i));
}
IntStream.range(1, numRows).forEach(i -> sbs[0].append(sbs[i]));
return sbs[0].toString();
}
}
Review
(Induced subgraphs of hypercubes anda proof of the Sensitivity Conjecture)[http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf] (Decades-Old Computer Science Conjecture Solved in Two Pages)[https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/]
敏感度猜想，涉及布尔型数据，以及其上的函数关系:
-
假设x是一个n维数组，其中每个分量都是取值于0或1的布尔数。
-
假设函数f:{0，1}^n—>{0，1}，亦即定义域是n维数组，同时每个分量都是布尔数；取值也是布尔数。
-
翻转x第i个分量的值(就是数组中第i个值如果是0，则变成1；是1，则变成0)，得到x_i，如果f(x_i)≠f(x)，就称f对x在第i个分量处敏感。
-
f对x可能在若干分量处都敏感，记敏感分量的数目为s(f，x)。
-
当x取遍n维布尔数组后，记s(f，x)的最大值为s(f)。
到此为止，就得到了布尔函数敏感性的定义，但是，猜想本身用到的是布尔函数的块敏感性！
简单说一下，就是上面步骤③里，x_i的角标不再是i，而是集合A，A本身是集合{1,2，……，n}的某个子集。对特定的想，相应的定义，把{1,2，……，n}分化成若干不想交子集，保证f对每个子集都是敏感的。必然有种方式使子集个数最多，子集个数记为相应的bs(f，x)，进一步得到bs(f)。
1994年，数学家Noam Nisan和Mario Szegedy提出了敏感度猜想Sensitivity Conjecture：
1
存在一个多项式P，对所有的布尔函数f，都成立 bs(f)≤P[s(f)]！
在计算机科学和数理逻辑，乃至代数学里，布尔函数无疑是是否重要的研究对象。同时，我们知道，布尔函数有许多复杂性测度，并且几乎所有这些测度——包括决策树复杂性，证书复杂性，随机查询复杂度和其它许许多多——已知都是多项式相关的。
最新证明的提出者、埃默里大学的数学助理教授Hao Huang向我们解释猜想的价值和意义：“在数学中，布尔函数是最基本的离散主题之一——就像数字，图形或几何形状一样。但是，其它测度都是多项式相关的，而如果猜想为真，则敏感度也是如此，否则的话，它就是很反常的量。”
Tip
有始有终，以始为终，增强时间观念；软件开发最终还是工程实践，以落地为准，理论与实践相结合，注意其工程属性。
