编程之法学习

前记

所有内容来自：
https://www.kancloud.cn/kancloud/the-art-of-programming
https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/

本人只是将这里作为自己的笔记，记录不全，只写下自己觉得对自己有影响作用的东西，全篇见上述网页。

字符串

旋转字符串

三步反转法：

1. 首先将原字符串分为两个部分，即X:abc，Y:def；
2. 将X反转，X->X^T，即得：abc->cba；将Y反转，Y->Y^T，即得：def->fed。
3. 反转上述步骤得到的结果字符串X^TY^T，即反转字符串cbafed的两部分（cba和fed）给予反转，cbafed得到defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。

字符串包含

要求：如何最快地判断字符串B中所有字母是否都在字符串A里？
题目里面前几种方法是怎么想出来的……完全不懂为啥要搞得那么复杂？
下面这种方法可以避免开26位的数组，直接用一个32位int搞定。

// “最好的方法”，时间复杂度O(n + m)，空间复杂度O(1)
bool StringContain(string &a,string &b)
{
    int hash = 0;
    for (int i = 0; i < a.length(); ++i)
    {
        hash |= (1 << (a[i] - 'A'));
    }
    for (int i = 0; i < b.length(); ++i)
    {
        if ((hash & (1 << (b[i] - 'A'))) == 0)
        {
            return false;
        }
    }
    return true;
}

字符串转整数

注意处理溢出、输入为空。

static const int MAX_INT = (int)((unsigned)~0 >> 1);
static const int MIN_INT = -(int)((unsigned)~0 >> 1) - 1;
    if (sign > 0 && (n > MAX_INT / 10 || (n == MAX_INT / 10 && c > MAX_INT % 10)))
    {
        n = MAX_INT;
        break;
    }
    else if (sign < 0 && (n >(unsigned)MIN_INT / 10 || (n == (unsigned)MIN_INT / 10 && c > (unsigned)MIN_INT % 10)))
    {
        n = MIN_INT;
        break;
    }

最长回文子串

方法一：

直接对每一个字符进行分析，从它开始向左右扩展，验证是否是回文，其中需要分奇偶。

方法二：

Manacher算法，O(n)

首先通过在每个字符的两边都插入一个特殊的符号，将所有可能的奇数或偶数长度的回文子串都转换成了奇数长度。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。
此外，为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#。
以字符串12212321为例，插入#和$这两个特殊符号，变成了 S[] = “$#1#2#2#1#2#3#2#1#”，然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左或向右扩张的长度（包括S[i]）。
比如S和P的对应关系：
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
可以看出，P[i]-1正好是原字符串中最长回文串的总长度，为5。

接下来怎么计算P[i]呢？Manacher算法增加两个辅助变量id和mx，其中id表示最大回文子串中心的位置，mx则为id+P[id]，也就是最大回文子串的边界（我感觉这个应该是右边界最靠右的一个，而不是最大回文子串）。得到一个很重要的结论：
如果mx > i，那么P[i] >= Min(P[2 * id - i], mx - i)

// 输入，并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
// 遍历所有字符，记作i
for (i = 1; s[i] != '\0'; i++) 
{
    p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) 
        p[i]++;
    if (i + p[i] > mx) 
    {
        mx = i + p[i];
        id = i;
    }
}
//找出p[i]中最大的

字符串全排列

在了解next_permutation算法是怎么一个过程之前，咱们得先来分析下“下一个排列”的性质。
假定现有字符串(A)x(B)，它的下一个排列是：(A)y(B’)，其中A、B和B’是“字符串”(可能为空），x和y是“字符”，前缀相同，都是A，且一定有y > x。
那么，为使下一个排列字典顺序尽可能小，必有：

• A尽可能长
• y尽可能小
• B’里的字符按由小到大递增排列

现在的问题是：找到x和y。怎么找到呢？咱们来看一个例子。
比如说，现在我们要找21543的下一个排列，我们可以从左至右逐个扫描每个数，看哪个能增大（至于如何判定能增大，是根据如果一个数右面有比它大的数存在，那么这个数就能增大），我们可以看到最后一个能增大的数是：x = 1。
而1应该增大到多少？1能增大到它右面比它大的那一系列数中最小的那个数，即：y = 3，故此时21543的下一个排列应该变为23xxx，显然 xxx(对应之前的B’）应由小到大排，于是我们最终找到比“21543”大，但字典顺序尽量小的23145，找到的23145刚好比21543大。

next_permutation算法

定义

• 升序：相邻两个位置ai < ai+1，ai 称作该升序的首位
• 步骤（二找、一交换、一翻转）
  找到排列中最后（最右）一个升序的首位位置i，x = ai
  找到排列中第i位右边最后一个比ai 大的位置j，y = aj （最右边比ai大的位置，找到的是最右侧比ai大的最小的数。如果比ai小，交换后更小，故不行，所以只能比ai大。）
  交换x，y
  把第(i+ 1)位到最后的部分翻转

还是拿上面的21543举例，那么，应用next_permutation算法的过程如下：

• x = 1；
• y = 3
• 1和3交换得23541
• 翻转541得23145

数组

最小的k个数

也可参见http://blog.csdn.net/ns_code/article/details/26966159

• 可以先选出k个并且找其中最大值，之后后面的数据都分别和最大值比较。复杂度kn

• 可以使用胜者树，建好后直接一个个输出最小值。n+klgn（建立用n-1，之后每一次更新可以算作lgn）

• 可以用最大堆：nlogk
  更好的办法是维护容量为k的最大堆，原理跟解法二的方法相似：
  1、用容量为k的最大堆存储最先遍历到的k个数，同样假设它们即是最小的k个数；
  2、堆中元素是有序的，令k1<k2<…<kmax（kmax设为最大堆中的最大元素）
  3、遍历剩余n-k个数。假设每一次遍历到的新的元素的值为x，把x与堆顶元素kmax比较：如果x < kmax，用x替换kmax，然后更新堆（用时logk）；否则不更新堆。
  这样下来，总的时间复杂度:O（k+（n-k）logk）=O（nlogk）。此方法得益于堆中进行查找和更新的时间复杂度均为：O(logk)（若使用解法二：在数组中找出最大元素，时间复杂度：O（k））。

• 在《数据结构与算法分析–c语言描述》一书，第7章第7.7.6节中，阐述了一种在平均情况下，时间复杂度为O（N）（最坏kn）的快速选择算法。如下述文字：
  选取S中一个元素作为枢纽元v，将集合S-{v}分割成S1和S2，就像快速排序那样
  如果k <= |S1|，那么第k个最小元素必然在S1中。在这种情况下，返回QuickSelect(S1, k)。
  如果k = 1 + |S1|，那么枢纽元素就是第k个最小元素，即找到，直接返回它。
  否则，这第k个最小元素就在S2中，即S2中的第（k - |S1| - 1）个最小元素，我们递归调用并返回QuickSelect(S2, k - |S1| - 1)。

注意：上述O（N）平均复杂度是建立在快排Partition算法之上的，这个Partition算法O（N）可以找到元素的index

寻找和为指定值的两个数

• 可以直接来对所有数进行遍历，已知一个数找它对应的数，可以先排序之后再进行二分查找，最后复杂度是NlogN

• 排序后，可以将原数组转换为（定值-本身）的数组，这样新的数组就是一个从大到小的，两个指针分别在两个数组的两个方向进行扫描，类似归并排序的合起来的步骤。也可以不写出来那个新的数组，直接两个指针加个运算判断即可。

寻找和为指定值的若干个数

• 回溯法+剪枝
• 拆分问题为两个：是否放入最后一个数，如果放入的话，就相当于总和为v-n的规模为n-1；若不放入，就是总和为v规模为n-1，这样下去。

0-1背包问题

0-1背包问题是最基础的背包问题，其具体描述为：有N件物品和一个容量为V的背包。放入第i件物品耗费的费用是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。
简单分析下：这是最基础的背包问题，特点是每种物品仅有一件，可以选择放或不放。用子问题定义状态：即F[i, v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
F[i, v] = max{F[i-1, v], F[i-1, v-Ci ] + Wi}
根据前面的分析，我们不难理解这个方程的意义：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前 i-1 件物品相关的问题。即：
如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为 F[i-1, v ]；
如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-Ci的背包中”，此时能获得的最大价值就是F[i-1, v-Ci]再加上通过放入第i件物品获得的价值Wi。

最大连续子数组和

事实上，当我们令currSum为当前最大子数组的和，maxSum为最后要返回的最大子数组的和，当我们往后扫描时，

• 对第j+1个元素有两种选择：要么放入前面找到的子数组，要么做为新子数组的第一个元素；
• 如果currSum加上当前元素a[j]后不小于a[j]，则令currSum加上a[j]，否则currSum重新赋值，置为下一个元素，即currSum = a[j]。

同时，当currSum > maxSum，则更新maxSum = currSum，否则保持原值，不更新。

注：对于元素j+1，如果该元素之前的连续几个数之和（也就是当前的最大和）大于0，那就说明自己加上他们才是最大的，不会出现后面连续几个比现在选的连续几个之和还要大（否则在选后面连续几个的第一个的时候就会清空前面的）。比如 1 2 -4 5 8，这样的话不会出现1 2 -4在一起影响到5的情况。

跳台阶

斐波那契类似，要从1开始向后算，保存下来之前计算过的内容。

奇偶调序

类似快排的partition

荷兰国旗（把小球按照三个颜色排列）

借鉴partition过程设定三个指针完成重新排列。也就是说，一个指针指向红球最后一个，一个指向白球最后一个，一个指向篮球最后一个。如果发现不是蓝球，若为红球，则红白指针分别++并且调换；否则若为白球，则白球++和当前蓝指针调换。

他的网页上给的思路是这样的：（现在移动中间的指针，前后两个指针从头开始）

需要用到三个指针：一个前指针begin，一个中指针current，一个后指针end，current指针遍历整个数组序列，当

1. current指针所指元素为0时，与begin指针所指的元素交换，而后current++，begin++ ；
2. current指针所指元素为1时，不做任何交换（即球不动），而后current++ ；
3. current指针所指元素为2时，与end指针所指的元素交换，而后，current指针不动，end– 。

为什么上述第3点中，current指针所指元素为2时，与end指针所指元素交换之后，current指针不能动呢？因为第三步中current指针所指元素与end指针所指元素交换之前，如果end指针之前指的元素是0，那么与current指针所指元素交换之后，current指针此刻所指的元素是0，此时，current指针能动么？不能动，因为如上述第1点所述，如果current指针所指的元素是0，还得与begin指针所指的元素交换。

ok，说这么多，你可能不甚明了，直接引用下gnuhpc的图，就一目了然了：

完美洗牌算法

有个长度为2n的数组{a1,a2,a3,…,an,b1,b2,b3,…,bn}，希望排序后{a1,b1,a2,b2,….,an,bn}，请考虑有无时间复杂度o(n)，空间复杂度0(1)的解法。

位置置换pefect_shuffle1算法

为方便讨论，我们设定数组的下标从1开始，下标范围是[1..2n]。 还是通过之前n=4的例子，来看下每个元素最终去了什么地方。
起始序列：a1 a2 a3 a4 b1 b2 b3 b4 数组下标：1 2 3 4 5 6 7 8
最终序列：b1 a1 b2 a2 b3 a3 b4 a4
从上面的例子我们能看到，前n个元素中，

• 第1个元素a1到了原第2个元素a2的位置，即1->2；
• 第2个元素a2到了原第4个元素a4的位置，即2->4；
• 第3个元素a3到了原第6个元素b2的位置，即3->6；
• 第4个元素a4到了原第8个元素b4的位置，即4->8；

那么推广到一般情况即是：前n个元素中，第i个元素去了 第（2 * i）的位置。
上面是针对前n个元素，那么针对后n个元素，可以看出：

• 第5个元素b1到了原第1个元素a1的位置，即5->1；
• 第6个元素b2到了原第3个元素a3的位置，即6->3；
• 第7个元素b3到了原第5个元素b1的位置，即7->5；
• 第8个元素b4到了原第7个元素b3的位置，即8->7；

推广到一般情况是，后n个元素，第i个元素去了第 (2 (i - n) ) - 1 = 2 i - (2 n + 1) = (2 i) % (2 * n + 1) 个位置。
再综合到任意情况，任意的第i个元素，我们最终换到了 (2 i) % (2 n + 1)的位置。为何呢？因为： > 当0 < i < n时， 原式= (2i) % (2 n + 1) = 2i； > 当i > n时，原式(2 i) % (2 * n + 1)保持不变。
因此，如果题目允许我们再用一个数组的话，我们直接把每个元素放到该放得位置就好了。也就产生了最简单的方法pefect_shuffle1

走圈算法cycle_leader

因为之前perfect_shuffle1算法未达到时间复杂度O（N）并且空间复杂度O（1）的要求，所以我们必须得再找一种新的方法，以期能完美的解决本节开头提出的完美洗牌问题。
让我们先来回顾一下2.1节位置置换perfect_shuffle1算法，还记得我之前提醒读者的关于当n=4时，通过位置置换让每一个元素到了最后的位置时，所形成的两个圈么？我引用下2.1节的相关内容：
当n=4的情况：
起始序列：a1 a2 a3 a4 b1 b2 b3 b4 数组下标：1 2 3 4 5 6 7 8
最终序列：b1 a1 b2 a2 b3 a3 b4 a4
即通过置换，我们得到如下结论：

• 我们可以看出有两个圈， > 一个是1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1；
• 一个是3 -> 6 -> 3。”

这两个圈可以表示为（1,2,4,8,7,5）和（3,6），且perfect_shuffle1算法也已经告诉了我们，不管你n是奇数还是偶数，每个位置的元素都将变为第（2*i） % （2n+1）个元素：
因此我们只要知道圈里最小位置编号的元素即圈的头部，顺着圈走一遍就可以达到目的，且因为圈与圈是不相交的，所以这样下来，我们刚好走了O（N）步。

神级结论：若2*n=（3^k - 1），则可确定圈的个数及各自头部的起始位置

对于2*n =(3^ k-1)这种长度的数组，恰好只有k个圈，且每个圈头部的起始位置分别是1,3,9，…3^(k-1)。

我们可以把中间那两段长度为n-m和m的段交换位置，即相当于把m+1..n，n+1..n+m的段循环右移m次（为什么要这么做？因为如此操作后，数组的前部分的长度为2m，而根据神级结论：当2m=3^k-1时，可知这长度2m的部分恰好有k个圈）

从上文的分析过程中也就得出了我们的完美洗牌算法，其算法流程为：

• step 1 输入数组　A[1..2 n] > step 1 找到 2 m = 3^k - 1 使得 3^k <= 2 n < 3^(k +1)
• step 2 把a[m + 1..n + m]那部分循环移m位 （就像之前的题，直接前半部分后半部分翻转后整体反转）
• step 3 对每个i = 0,1,2..k - 1，3^i是个圈的头部，做cycle_leader算法，数组长度为m，所以对2 m + 1取模。
• step 4 对数组的后面部分A[2 m + 1.. 2 n]继续使用本算法, 这相当于n减小了m。

公众号推荐

推荐一波自己的公众号：五道口的程序狐

里面有一个聊天机器人，抚慰你的心灵

如有需要，联系contact@fhao.top