位运算的常见操作和题目
最后更新于：2022-04-01 16:18:01
# 一、位运算基本操作
<table border="1" cellspacing="0" cellpadding="0" style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px"><tbody><tr><td valign="top"><p><span style="font-size:18px">& </span></p></td><td valign="top"><p><span style="font-size:18px"> 与 </span></p></td><td valign="top"><p><span style="font-size:18px">1 & 1 = 1；1 & 0 = 0；0 & 0 = 0 只有当两个位都为1时，结果为1</span></p></td></tr><tr><td valign="top"><p><span style="font-size:18px">| </span></p></td><td valign="top"><p><span style="font-size:18px"> 或 </span></p></td><td valign="top"><p><span style="font-size:18px">1 | 1 = 1；1 | 0 = 1；0 | 0 = 0 只有两个位都为0时，结果为0</span></p></td></tr><tr><td valign="top"><p><span style="font-size:18px">^ </span></p></td><td valign="top"><p><span style="font-size:18px">异或</span></p></td><td valign="top"><p><span style="font-size:18px">1 ^ 1 = 0；1 ^ 0 = 1；0 ^ 0 = 0 两个位相同时为0，相异时为1</span></p></td></tr><tr><td valign="top"><p><span style="font-size:18px">~ </span></p></td><td valign="top"><p><span style="font-size:18px">取反</span></p></td><td valign="top"><p><span style="font-size:18px">0变1，1变0</span></p></td></tr><tr><td valign="top"><p><span style="font-size:18px"><< </span></p></td><td valign="top"><p><span style="font-size:18px">左移</span></p></td><td valign="top"><p><span style="font-size:18px">各二进位全部左移若干位，高位丢弃，低位补0</span></p></td></tr><tr><td valign="top"><p><span style="font-size:18px">>> </span></p></td><td valign="top"><p><span style="font-size:18px">右移</span></p></td><td valign="top"><p><span style="font-size:18px">二进位全部右移若干位，<strong>对无符号数</strong>，高位补0；</span></p><p><span style="font-size:18px"><strong>有符号数</strong>，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）</span></p></td></tr></tbody></table>
1、以上运算符，仅~是单目运算符，其他都是双目运算符。
2、位操作仅针对整型数据，对float、double进行位操作会出错。
3、VS2010 和GCC均采用算术右移：对负数右移，会在其高位补符号位，也就是补1。
4、还有其他复合位操作： &= |= <<= >>=
# 二、位操作的运用
### 1、奇偶性的判断
对于二进制表示来说，其最右位为1则该数为奇数，最右位为0则该数为偶数。
~~~
int a;
cin >> a;
if (a & 1)
cout << "奇数" << endl;
if ((a & 1) == 0) //注意：&的优先级低于==的优先级，因此if内部与运算必须加括号！
cout << "偶数" << endl;
~~~
### 2、 不借助变量交换两个数
具体查看文章：[不借助变量交换两个数](http://blog.csdn.net/u013074465/article/details/44342629)
### 3、取相反数
也就是将正数n变为-n，将负数n变为-n。
将整数取反加1即可得到其相反数：
例如，32位系统中正数13（二进制表示为00000000 00000000 00000000 00001101），
取反为（11111111 11111111 11111111 11110010），
然后再加1为（11111111 11111111 11111111 11110011），计算机中数是用二进制的补码表示的，
因此取反加1的结果（11111111 11111111 11111111 11110011）即为-13的二进制补码表示形式。
常见的一个等式：-n = ~(n - 1) = ~n + 1
例子：求某整数的绝对值：
~~~
//求某整数的绝对值
int my_abs(int number) {
if (number < 0) {
return ~number + 1; //或return -number; 或return ~(n - 1)
}
return number;
}
~~~
### 4、整数二进制表示中最右边的1
获取整数二进制表示中最右侧的1：n & (-n) 等价于 n & ~(n - 1) 。
例如，n = 1100， -n = 0100， 那么n & (-n) = 0100，这样就获取到了二进制表示中最右侧的1。
去除整数二进制表示中最右侧的1：n & (n - 1)
例如，n = 1100，n - 1 = 1011，那么n & (n - 1) = 1000，这样就去除了二进制表示中最右侧的1。
在文章[位操作实现加减乘除四则运算](http://blog.csdn.net/u013074465/article/details/42680239#t3)中的乘法操作就用到了本小结提到的这两个技巧。
### 5、32位系统某数右移/左移32位或更多位
在移位运算时，byte、short和char类型移位后的结果会变成int类型，对于byte、short、char和int进行移位时，规定实际移动的次数是移动次数和32的余数，也就是移位33次和移位1次得到的结果相同。
参考文章：[位移操作的另类情况](http://blog.csdn.net/u013074465/article/details/44645817)
# 三、位运算相关的题目
### 1、二进制中1的个数
用到了n & (n - 1)
(1)方法一：参考文章：[整数的二进制表示中1的个数](http://blog.csdn.net/u013074465/article/details/42617293)
方法二：[二进制位的翻转和二进制表示中1的个数](http://blog.csdn.net/u013074465/article/details/45485959)
(2) 输入两个数A和B，输出将A转换为B所需改变的二进制的位数。
方法：首先，A异或B得到的是A和B中不相同位数组成的数，然后再求这个数二进制表示中1的个数，即为所求。
### 2、数组中只出现一次的数字
用到了n & (n - 1)
数组中仅出现一次的一个数字、仅出现一次的两个数字
参考文章：[http://zhedahht.blog.163.com/blog/static/2541117420071128950682/](http://zhedahht.blog.163.com/blog/static/2541117420071128950682/)
数组中仅出现一次的三个数字
参考文章：[http://zhedahht.blog.163.com/blog/static/25411174201283084246412/](http://zhedahht.blog.163.com/blog/static/25411174201283084246412/)
### 3、不用加减乘除做加法
参考文章：[http://zhedahht.blog.163.com/blog/static/254111742011125100605/](http://zhedahht.blog.163.com/blog/static/254111742011125100605/)
### 4、位操作实现加减乘除运算
[位操作实现加减乘除四则运算](http://blog.csdn.net/u013074465/article/details/42680239)
### 5、不借助变量交换两个数
参考文章：[不借助变量交换两个数](http://blog.csdn.net/u013074465/article/details/44342629)
### 6、比较两个数大小
参考文章：[不借助if、switch等语句求两个数较大的一个](http://blog.csdn.net/u013074465/article/details/42684559)
### 7、二进制位的翻转
[字符串合并处理（二进制位的倒序）](http://blog.csdn.net/u013074465/article/details/45485515)
[二进制位的翻转](http://blog.csdn.net/u013074465/article/details/45485959)
### 8、二进制表示的高低位交换
[http://blog.csdn.net/morewindows/article/details/7354571](http://blog.csdn.net/morewindows/article/details/7354571)
### 9、位操作与空间压缩
[http://blog.csdn.net/morewindows/article/details/7354571#t6](http://blog.csdn.net/morewindows/article/details/7354571#t6)
### 10、bitmap对海量数据排序
[bitmap对海量无重复的整数排序](http://blog.csdn.net/u013074465/article/details/46956295)
### 11、求两个数中较小的那个
y ^ ((x ^ y) & -(x < y))
分析：当x < y时，-(x < y)为-1，其补码形式全为1，则(x ^ y) & -(x < y) = x ^ y，则上述表达式返回的是较小的数x；
当x >= y时，-(x < y)为0，补码形式为全0，则(x ^ y) & -(x < y) = 0， 则表达式返回的是较小的数y。
n个骰子的点数
最后更新于：2022-04-01 16:17:59
题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。
方法一：递归
思路：设n个骰子某次投掷点数和为s的出现次数是F(n, s)，那么，F(n, s)等于n - 1个骰子投掷的点数和为s - 1、s - 2、s - 3、s -4、s - 5、s - 6时的次数的总和：F(n , s) = F(n - 1, s - 1) + F(n - 1, s - 2) + F(n - 1, s - 3) + F(n - 1, s - 4) + F(n - 1, s - 5) + F(n - 1, s - 6)。
~~~
#include <iostream>
#include <time.h>
#include <vector>
#include <assert.h>
#include <list>
#include <math.h>
using namespace std;
//计算n个骰子某次投掷点数和为s的出现次数
int CountNumber(int n, int s) {
//n个骰子点数之和范围在n到6n之间，否则数据不合法
if(s < n || s > 6*n)
return 0;
//当有一个骰子时，一次骰子点数为s(1 <= s <= 6)的次数当然是1
if(n == 1)
return 1;
else
return CountNumber(n-1, s-6) + CountNumber(n-1, s-5) + CountNumber(n-1, s-4) +
CountNumber(n-1, s-3) +CountNumber(n-1, s-2) + CountNumber(n-1, s-1);
}
void listDiceProbability(int n) {
int i=0;
unsigned int nTotal = pow((double)6, n);
for(i = n; i <= 6 * n; i++) {
printf("P(s=%d) = %d/%d\n", i, CountNumber(n,i), nTotal);
}
}
int main() {
listDiceProbability(3);
}
~~~
方法二：循环《剑指offer》题43
KMP(Knuth-Morris-Pratt)算法
最后更新于：2022-04-01 16:17:56
# 一、朴素匹配算法
也就是暴力匹配算法。设匹配字符串的长度为n，模式串的长度为m，在最坏情况下，朴字符串匹配算法运行时间为O((n - m + 1)m)。如果m = n / 2， 那么该算法的复杂度就是Θ(n ^ 2)。由于不需要预处理，朴素字符串匹配算法运行时间即为其匹配时间。
strstr()函数就可以用这个方法实现，尽管效率不高：
~~~
//strstr函数
char *strStr(const char *str, const char *substr) {
if (substr == NULL || str == NULL)
return NULL;
if (!*substr)
return const_cast<char*>(str);
const char *p1 = str;
const char *p2 = substr;
const char *p1_advance = str;
//p1_advance指针前进strlen(substr)-1位
//因为当str中还未匹配的位数小于substr的长度时，肯定不可能再匹配成功了
for (p2 = substr + 1; *p2; ++p2)
++p1_advance;
for (p1 = str; *p1_advance; p1_advance++) {
char *p1_old = (char *)p1;
p2 = substr;
while (*p1 && *p2 && *p1 == *p2) {
++p1;
++p2;
}
if (!*p2)
return p1_old;
p1 = p1_old + 1;
}
return NULL;
}
int main() {
char str[100] = {'\0'};
char substr[100] = {'\0'};
scanf("%s %s", str, substr);
if (strStr(str, substr) != NULL)
printf("true\n");
else
printf("false\n");
}</span>
~~~
# 二、KMP算法
参考文章：[http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html](http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html)
July的文章把该算法讲得挺透彻了：[KMP算法](http://blog.csdn.net/v_JULY_v/article/details/7041827#t3)。
设匹配字符串的长度为n，模式串的长度为m。该算法的匹配时间为Θ(n)，用到了一个辅助函数GetNext()，它在Θ(m)时间内根据模式预先计算出来，并且存储在数组next[0...m]中。模式的前缀函数GetNext包含模式与其自身的偏移进行匹配的信息。这些信息可用于在朴素的字符串匹配算法中避免对无用的偏移进行检测。KMP利用模式串中已知的匹配信息，不再把搜索位置移动到比较过的位置（即不做无用的匹配），这样提高了效率。
KMP完整代码如下：
~~~
void GetNext(char* pattern,int next[]) {
int k = -1;
int j = 0;
int length_pattern = strlen(pattern);
next[0] = -1;
while (j < length_pattern - 1) {
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || pattern[j] == pattern[k]) {
++k;
++j;
next[j] = k;
}
else
k = next[k];
}
}
int KmpSearch(char* text, char* pattern) {
int i = 0;
int j = 0;
int length_text = strlen(text);
int length_pattern = strlen(pattern);
int *next = new int[length_pattern];
GetNext(pattern, next);
for (int i = 0; i < length_pattern; ++i)
cout << next[i] << " ";
cout << endl;
while (i < length_text && j < length_pattern) {
//①如果j = -1,或者当前字符匹配成功(即text[i] == pattern[j]),令i++，j++
if (j == -1 || text[i] == pattern[j]) {
++i;
++j;
}
else
//②如果j != -1,且当前字符匹配失败(即text[i] != pattern[j]),
//则令i不变,j = next[j]，next[j]即为j所对应的next值
j = next[j];
}
delete[] next;
if (j == length_pattern)
return i - j;
else
return -1;
}
//int main() {
// char str[100] = {'\0'};
// char substr[100] = {'\0'};
// scanf("%s %s", str, substr);
// for (int i = 0 ; i < 10; ++i)
// cout << substr[i] << " ";
// cout << endl;
// cout << KmpSearch(str, substr) << endl;
//}
~~~
由于需要根据自己的理解对文章内容进行标注，所以将july的文章摘录如下：
# -----------------------以下为july文章--------------------------------
# 从头到尾彻底理解KMP
作者：July
时间：最初写于2011年12月，2014年7月21日晚10点 全部删除重写成此文，随后的半个多月不断反复改进。
### 1. 引言
本KMP原文最初写于2年多前的2011年12月，因当时初次接触KMP，思路混乱导致写也写得混乱。所以一直想找机会重新写下KMP，但苦于一直以来对KMP的理解始终不够，故才迟迟没有修改本文。
然近期因在北京开了个[算法班](http://www.julyedu.com/course/index/category/algorithm.html#m10)，专门讲解数据结构、面试、算法，才再次仔细回顾了这个KMP，在综合了一些网友的理解、以及跟我一起讲算法的两位讲师朋友曹博、邹博的理解之后，写了9张PPT，发在[微博](http://weibo.com/1580904460/BeCCYrKz3#_rnd1405961034764)上。随后，一不做二不休，索性将PPT上的内容整理到了本文之中（后来文章越写越完整，所含内容早已不再是九张PPT 那样简单了）。
KMP本身不复杂，但网上绝大部分的文章（包括本文的2011年版本）把它讲混乱了。下面，咱们从暴力匹配算法讲起，随后阐述KMP的流程 步骤、next 数组的简单求解 递推原理 代码求解，接着基于next 数组匹配，谈到有限状态自动机，next 数组的优化，KMP的时间复杂度分析，最后简要介绍两个KMP的扩展算法。
全文力图给你一个最为完整最为清晰的KMP，希望更多的人不再被KMP折磨或纠缠，不再被一些混乱的文章所混乱，有何疑问，欢迎随时留言评论，thanks。
### 2. 暴力匹配算法
假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？
如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：
- 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
- 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。
理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：
~~~
int ViolentMatch(char* s, char* p)
{
int sLen = strlen(s);
int pLen = strlen(p);
int i = 0;
int j = 0;
while (i < sLen && j < pLen)
{
if (s[i] == p[j])
{
//①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
i++;
j++;
}
else
{
//②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
i = i - j + 1;
j = 0;
}
}
//匹配成功，返回模式串p在文本串s中的位置，否则返回-1
if (j == pLen)
return i - j;
else
return -1;
}
~~~
举个例子，如果给定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示：
*1.* S[0]为B，P[0]为A，不匹配，执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[1]跟P[0]匹配，相当于模式串要往右移动一位（i=1，j=0）
*2*. S[1]跟P[0]还是不匹配，继续执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i = i - (j - 1)，j = 0”，i从2变到4，j一直为0）
> 
*3*. 直到S[4]跟P[0]匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来S[5]跟P[1]匹配（i=5，j=1）> 
*4*. S[5]跟P[1]匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此进行下去
> 
*5*. 直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相当于S[5]跟P[0]匹配（i=5，j=0）
> 
*6*. 至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]，但因为S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，从而让S[5]跟P[0]匹配。
而S[5]肯定跟P[0]失配。为什么呢？因为在之前第4步匹配中，我们已经得知S[5] = P[1] = B，而P[0] = A，即P[1] != P[0]，故S[5]必定不等于P[0]，所以回溯过去必然会导致失配。那有没有一种算法，让i 不往回退，只需要移动j 即可呢？
答案是肯定的。这种算法就是本文的主旨KMP算法，它利用之前已经部分匹配这个有效信息，保持i 不回溯，通过修改j 的位置，让模式串尽量地移动到有效的位置。
### 3. KMP算法
### 3.1 定义
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明☺）：
- 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
- 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
- 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
- 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的[3.3.3节](http://blog.csdn.net/v_july_v/article/details/7041827#t9)中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。
很快，你也会意识到next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。
转换成代码表示，则是：
~~~
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
~~~
继续拿之前的例子来说，当S[10]跟P[6]匹配失败时，KMP不是跟暴力匹配那样简单的把模式串右移一位，而是执行第②条指令：“如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]”，即j 从6变到2（后面我们将求得P[6]，即字符D对应的next 值为2），所以相当于模式串向右移动的位数为j - next[j]（j - next[j] = 6-2 = 4）。
> 
向右移动4位后，S[10]跟P[2]继续匹配。为什么要向右移动4位呢，因为移动4位后，模式串中又有个“AB”可以继续跟S[8]S[9]对应着，从而不用让i 回溯。**相当于在除去字符D的模式串子串中寻找相同的前缀和后缀，然后根据前缀后缀求出next 数组，最后基于next 数组进行匹配**（不关心next 数组是怎么求来的，只想看匹配过程是咋样的，可直接跳到下文[3.3.4节](http://blog.csdn.net/v_july_v/article/details/7041827#t10)）。
> 
### 3.2 步骤
- ①寻找前缀后缀最长公共元素长度
- 对于P = p0 p1 ...pj-1 pj，寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。举个例子，如果给定的模式串为“abab”，那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示：
> 
> 比如对于字符串aba来说，它有长度为1的相同前缀后缀a；而对于字符串abab来说，它有长度为2的相同前缀后缀ab（相同前缀后缀的长度为k + 1，k + 1 = 2）。
- ②求next数组
- next 数组考虑的是除当前字符外的最长相同前缀后缀，所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后，只要稍作变形即可：将第①步骤中求得的值整体右移一位，然后初值赋为-1，如下表格所示：
> 
> 比如对于aba来说，第3个字符a之前的字符串ab中有长度为0的相同前缀后缀，所以第3个字符a对应的next值为0；而对于abab来说，第4个字符b之前的字符串aba中有长度为1的相同前缀后缀a，所以第4个字符b对应的next值为1（相同前缀后缀的长度为k，k = 1）。
- ③根据next数组进行匹配
- 匹配失配，j = next [j]，模式串向右移动的位数为：j - next[j]。换言之，当模式串的后缀pj-k pj-k+1, ..., pj-1 跟文本串si-k si-k+1, ..., si-1匹配成功，但pj 跟si匹配失败时，因为next[j] = k，相当于在不包含pj的模式串中有最大长度为k 的相同前缀后缀，即p0 p1 ...pk-1 = pj-k pj-k+1...pj-1，故令j = next[j]，从而让模式串右移j - next[j] 位，使得模式串的前缀p0 p1, ..., pk-1对应着文本串 si-k si-k+1, ..., si-1，而后让pk 跟si 继续匹配。如下图所示：
综上，KMP的next 数组相当于告诉我们：当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟文本串在i 处的字符匹配失配时，下一步用next [j] 处的字符继续跟文本串i 处的字符匹配，相当于模式串向右移动 j - next[j] 位。
接下来，分别具体解释上述3个步骤。
### 3.3 解释
#### 3.3.1 寻找最长前缀后缀
如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：
也就是说，原模式串子串对应的各个前缀后缀的公共元素的最大长度表为（下简称《最大长度表》）：
#### 3.3.2 基于《最大长度表》匹配
因为模式串中首尾可能会有重复的字符，故可得出下述结论：
| 失配时，模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度值 |
|-----|
下面，咱们就结合之前的《最大长度表》和上述结论，进行字符串的匹配。如果给定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟文本串匹配，如下图所示：
- 1. 因为模式串中的字符A跟文本串中的字符B、B、C、空格一开始就不匹配，所以不必考虑结论，直接将模式串不断的右移一位即可，直到模式串中的字符A跟文本串的第5个字符A匹配成功：
- *2*.继续往后匹配，当模式串最后一个字符D跟文本串匹配时失配，显而易见，模式串需要向右移动。但向右移动多少位呢？因为此时已经匹配的字符数为6个（ABCDAB），然后根据《最大长度表》可得失配字符D的上一位字符B对应的长度值为2，所以根据之前的结论，可知需要向右移动6 - 2 = 4 位。
- *3*. 模式串向右移动4位后，发现C处再度失配，因为此时已经匹配了2个字符（AB），且上一位字符B对应的最大长度值为0，所以向右移动：2 - 0 =2 位。
- *4*. A与空格失配，向右移动1 位。
- *5*. 继续比较，发现D与C 失配，故向右移动的位数为：已匹配的字符数6减去上一位字符B对应的最大长度2，即向右移动6 - 2 = 4 位。
- *6*. 经历第5步后，发现匹配成功，过程结束。
通过上述匹配过程可以看出，问题的关键就是寻找模式串中最大长度的相同前缀和后缀，找到了模式串中每个字符之前的前缀和后缀公共部分的最大长度后，便可基于此匹配。而这个最大长度便正是next 数组要表达的含义。
#### 3.3.3 根据《最大长度表》求next 数组
由上文，我们已经知道，字符串“ABCDABD”各个前缀后缀的最大公共元素长度分别为：
而且，根据这个表可以得出下述结论
- 失配时，模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
上文利用这个表和结论进行匹配时，我们发现，当匹配到一个字符失配时，其实没必要考虑当前失配的字符，更何况我们每次失配时，都是看的失配字符的上一位字符对应的最大长度值。如此，便引出了next 数组。
给定字符串“ABCDABD”，可求得它的next 数组如下：
把next 数组跟之前求得的最大长度表对比后，不难发现，next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。意识到了这一点，你会惊呼原来next 数组的求解竟然如此简单：就是找最大对称长度的前缀后缀，然后整体右移一位，初值赋为-1（当然，你也可以直接计算某个字符对应的next值，就是看这个字符之前的字符串中有多大长度的相同前缀后缀）。
换言之，对于给定的模式串：ABCDABD，它的最大长度表及next 数组分别如下：
根据最大长度表求出了next 数组后，从而有
| 失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值 |
|-----|
而后，你会发现，无论是基于《最大长度表》的匹配，还是基于next 数组的匹配，两者得出来的向右移动的位数是一样的。为什么呢？因为：
- 根据《最大长度表》，失配时，模式串向右移动的位数 = 已经匹配的字符数 - 失配字符的上一位字符的最大长度值
- 而根据《next 数组》，失配时，模式串向右移动的位数 = 失配字符的位置 - 失配字符对应的next 值
- 其中，从0开始计数时，失配字符的位置 = 已经匹配的字符数（失配字符不计数），而失配字符对应的next 值 = 失配字符的上一位字符的最大长度值，两相比较，结果必然完全一致。
所以，你可以把《最大长度表》看做是next 数组的雏形，甚至就把它当做next 数组也是可以的，区别不过是怎么用的问题。
#### 3.3.4 通过代码递推计算next 数组
接下来，咱们来写代码求下next 数组。
基于之前的理解，可知计算next 数组的方法可以采用递推：
- *1*. 如果**对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于next[j] = k**。
- 此意味着什么呢？究其本质，**next[j] = k 代表p[j] 之前的模式串子串中，有长度为k 的相同前缀和后缀**。有了这个next 数组，在KMP匹配中，当模式串中j 处的字符失配时，下一步用next[j]处的字符继续跟文本串匹配，相当于模式串向右移动j - next[j] 位。
举个例子，如下图，根据模式串“ABCDABD”的next 数组可知失配位置的字符D对应的next 值为2，代表字符D前有长度为2的相同前缀和后缀（这个相同的前缀后缀即为“AB”），失配后，模式串需要向右移动j - next [j] = 6 - 2 =4位。
向右移动4位后，模式串中的字符C继续跟文本串匹配。
- **2**. 下面的问题是：已知next [0, ..., j]，如何求出next [j + 1]呢？
对于P的前j+1个序列字符：
- 若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；
- 若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1, …, pk-1 pk"跟后缀“pj-k pj-k+1, …, pj-1 pj"相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next 数组（next [0, ..., k, ..., j]）进行P串前缀跟P串后缀的匹配。
一般的文章或教材可能就此一笔带过，但大部分的初学者可能还是不能很好的理解上述求解next 数组的原理，故接下来，我再来着重说明下。
如下图所示，假定给定模式串ABCDABCE，且已知next [j] = k（相当于“p0 pk-1” = “pj-k pj-1” = AB，可以看出k为2），现要求next [j + 1]等于多少？因为pk = pj = C，所以next[j + 1] = next[j] + 1 = k + 1（可以看出next[j + 1] = 3）。代表字符E前的模式串中，有长度k+1 的相同前缀后缀。
但**如果pk != pj 呢**？说明“p0 pk-1 pk” ≠ “pj-k pj-1 pj”。换言之，当pk != pj后，字符E前有多大长度的相同前缀后缀呢？很明显，因为C不同于D，所以ABC 跟 ABD不相同，即字符E前的模式串没有长度为k+1的相同前缀后缀，也就不能再简单的令：next[j + 1] = next[j] + 1 。所以，咱们只能去寻找长度更短一点的相同前缀后缀。
结合上图来讲，若能**在前缀**“ p0 pk-1 pk ” 中不断的递归前缀索引k = next [k]，找到一个字符pk’ 也为D，代表pk’ = pj，且满足p0 pk'-1 pk' = pj-k' pj-1 pj，则最大相同的前缀后缀长度为k' + 1**，从而next [j + 1] = k’ + 1 = next [k' ] + 1。否则前缀中没有D，则代表没有相同的前缀后缀，next [j + 1] = 0。
那为何递归前缀索引k = next[k]，就能找到长度更小的相同前缀后缀呢？这又归根到next数组的含义。**为了寻找长度相同的前缀后缀，我们拿前缀 p0 pk-1 pk 去跟后缀pj-k pj-1 pj匹配，如果pk 跟pj 失配，下一步就是用p[next[k]] 去跟pj 继续匹配，如果p[ next[k] ]跟pj还是不匹配，则下一步用p[ next[ next[k] ] ]去跟pj匹配**。相当于模式串的自我匹配，所以不断的递归k = next[k]，直到要么找到长度更小的相同前缀后缀，要么没有长度更小的相同前缀后缀。
所以，因最终在前缀ABC中没有找到D，故E的next 值为0：
模式串的后缀：AB
DE
模式串的前缀：AB
C
前缀右移两位：
A> > BC
读到此，有的读者可能又有疑问了，那能否举一个能在前缀中找到字符D的例子呢？OK，咱们便来看一个能在前缀中找到字符D的例子，如下图所示：
给定模式串DABCDABDE，我们很顺利的求得字符D之前的“DABCDAB”的各个子串的最长相同前缀后缀的长度分别为0 0 0 0 1 2 3，但当遍历到字符D，要求包括D在内的“DABCDABD”最长相同前缀后缀时，我们发现pj处的字符D跟pk处的字符C不一样，换言之，前缀DABC的最后一个字符C 跟后缀DABD的最后一个字符D不相同，所以不存在长度为4的相同前缀后缀。
怎么办呢？既然没有长度为4的相同前缀后缀，咱们可以寻找长度短点的相同前缀后缀，最终，因在p0处发现也有个字符D，p0 = pj，所以p[j]对应的长度值为1，相当于E对应的next 值为1。
综上，可以通过递推求得next 数组，代码如下所示：
~~~
void GetNext(char* p,int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++k;
++j;
next[j] = k;
}
else
{
k = next[k];
}
}
}
~~~
用代码重新计算下“ABCDABD”的next 数组，以验证之前通过“最长相同前缀后缀长度值右移一位，然后初值赋为-1”得到的next 数组是否正确，计算结果如下表格所示：
从上述表格可以看出，无论是之前通过“最长相同前缀后缀长度值右移一位，然后初值赋为-1”得到的next 数组，还是之后通过代码递推计算求得的next 数组，结果是完全一致的。
#### 3.3.5 基于《next 数组》匹配
下面，我们来基于next 数组进行匹配。
还是给定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟文本串匹配，如下图所示：
在正式匹配之前，让我们来再次回顾下上文2.1节所述的KMP算法的匹配流程：
- **“**假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
- 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
- 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
- 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即**移动的实际位数为：j - next[j]**，且此值大于等于1。**”**
- *1*. 最开始匹配时
- P[0]跟S[0]匹配失败
- 所以执行“如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]”，所以j = -1，故转而执行“如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++”，得到i = 1，j = 0，即P[0]继续跟S[1]匹配。
- P[0]跟S[1]又失配，j再次等于-1，i、j继续自增，从而P[0]跟S[2]匹配。
- P[0]跟S[2]失配后，P[0]又跟S[3]匹配。
- P[0]跟S[3]再失配，直到P[0]跟S[4]匹配成功，开始执行此条指令的后半段：“如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++”。
- 2. P[1]跟S[5]匹配成功，P[2]跟S[6]也匹配成功, ...，直到当匹配到P[6]处的字符D时失配（即S[10] != P[6]），由于P[6]处的D对应的next 值为**2**，所以下一步用**P[2]**处的字符C继续跟S[10]匹配，相当于向右移动：j - next[j] = 6 - 2 =4 位。
- *3*. 向右移动4位后，P[2]处的C再次失配，由于C对应的next值为**0**，所以下一步用**P[0]**处的字符继续跟S[10]匹配，相当于向右移动：j - next[j] = 2 - 0 = 2 位。
- *4*. 移动两位之后，A 跟空格不匹配，模式串后移1 位。
- *5*. P[6]处的D再次失配，因为P[6]对应的next值为**2**，故下一步用**P[2]**继续跟文本串匹配，相当于模式串向右移动 j - next[j] = 6 - 2 = 4 位。
- *6*. 匹配成功，过程结束。
匹配过程一模一样。也从侧面佐证了，next 数组确实是只要将各个最大前缀后缀的公共元素的长度值右移一位，且把初值赋为-1 即可。
#### 3.3.6 基于《最大长度表》与基于《next 数组》等价
我们已经知道，利用next 数组进行匹配失配时，模式串向右移动 j - next [ j ] 位，等价于已匹配字符数 - 失配字符的上一位字符所对应的最大长度值。原因是：
1. j 从0开始计数，那么当数到失配字符时，j 的数值就是已匹配的字符数；
1. 由于next 数组是由最大长度值表整体向右移动一位（且初值赋为-1）得到的，那么失配字符的上一位字符所对应的最大长度值，即为当前失配字符的next 值。
但为何本文不直接利用next 数组进行匹配呢？因为next 数组不好求，而一个字符串的前缀后缀的公共元素的最大长度值很容易求。例如若给定模式串“ababa”，要你快速口算出其next 数组，乍一看，每次求对应字符的next值时，还得把该字符排除之外，然后看该字符之前的字符串中有最大长度为多大的相同前缀后缀，此过程不够直接。而如果让你求其前缀后缀公共元素的最大长度，则很容易直接得出结果：0 0 1 2 3，如下表格所示：
然后这5个数字 全部整体右移一位，且初值赋为-1，即得到其next 数组：-1 0 0 1 2。
#### 3.3.7 Next 数组与有限状态自动机
next 负责把模式串向前移动，且当第j位不匹配的时候，用第next[j]位和主串匹配，就像打了张“表”。此外，next 也可以看作有限状态自动机的状态，在已经读了多少字符的情况下，失配后，前面读的若干个字符是有用的。
#### 3.3.8 Next 数组的优化
行文至此，咱们全面了解了暴力匹配的思路、KMP算法的原理、流程、流程之间的内在逻辑联系，以及next 数组的简单求解（《最大长度表》整体右移一位，然后初值赋为-1）和代码求解，最后基于《next 数组》的匹配，看似洋洋洒洒，清晰透彻，但以上忽略了一个小问题。
比如，如果用之前的next 数组方法求模式串“abab”的next 数组，可得其next 数组为-1 0 0 1（0 0 1 2整体右移一位，初值赋为-1），当它跟下图中的文本串去匹配的时候，发现b跟c失配，于是模式串右移j - next[j] = 3 - 1 =2位。
右移2位后，b又跟c失配。事实上，因为在上一步的匹配中，已经得知p[3] = b，与s[3] = c失配，而右移两位之后，让p[ next[3] ] = p[1] = b 再跟s[3]匹配时，必然失配。问题出在哪呢？
问题出在不该出现p[j] = p[ next[j] ]。为什么呢？理由是：当p[j] != s[i] 时，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ]，必然导致后一步匹配失败（因为p[j]已经跟s[i]失配，然后你还用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很显然，必然失配），所以**不能允许p[j] = p[ next[j ]]**。如果出现了p[j] = p[ next[j] ]咋办呢？如果出现了，则需要再次递归，即令next[j] = next[ next[j] ]。
所以，咱们得修改下求next 数组的代码。
~~~
//优化过后的next 数组求法
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++j;
++k;
//较之前next数组求法，改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
}
~~~
利用优化过后的next 数组求法，可知模式串“abab”的新next数组为：-1 0 -1 0。可能有些读者会问：原始next 数组是前缀后缀最长公共元素长度值右移一位， 然后初值赋为-1而得，那么优化后的next 数组如何快速心算出呢？实际上，只要求出了原始next 数组，便可以根据原始next 数组快速求出优化后的next 数组。还是以abab为例，如下表格所示：
只要出现了p[next[j]] = p[j]的情况，则把next[j]的值再次递归。例如在求模式串“abab”的第2个a的next值时，如果是未优化的next值的话，第2个a对应的next值为**0**，相当于第2个a失配时，下一步匹配模式串会用**p[0]**处的a再次跟文本串匹配，必然失配。所以求第2个a的next值时，需要再次递归：next[2] = next[ next[2] ] = next[0] = -1（此后，根据优化后的新next值可知，第2个a失配时，执行“如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符”），同理，第2个b对应的next值为0。
对于优化后的next数组可以发现一点：如果模式串的后缀跟前缀相同，那么它们的next值也是相同的，例如模式串abcabc，它的前缀后缀都是abc，其优化后的next数组为：-1 0 0 -1 0 0，前缀后缀abc的next值都为-1 0 0。
然后引用下之前3.1节的KMP代码：
~~~
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
~~~
接下来，咱们继续拿之前的例子说明，整个匹配过程如下：
*1*. S[3]与P[3]匹配失败。
* 2*. S[3]保持不变，P的下一个匹配位置是P[next[3]]，而next[3]=0，所以P[next[3]]=P[0]与S[3]匹配。
*3*. 由于上一步骤中P[0]与S[3]还是不匹配。此时i=3，j=next [0]=-1，由于满足条件j==-1，所以执行“++i, ++j”，即主串指针下移一个位置，P[0]与S[4]开始匹配。最后j==pLen，跳出循环，输出结果i - j = 4（即模式串第一次在文本串中出现的位置），匹配成功，算法结束。
### 3.4 KMP的时间复杂度分析
相信大部分读者读完上文之后，已经发觉其实理解KMP非常容易，无非是循序渐进把握好下面几点：
1. 如果模式串中存在相同前缀和后缀，即pj-k pj-k+1, ..., pj-1 = p0 p1, ..., pk-1，那么在pj跟si失配后，让模式串的前缀p0 p1...pk-1对应着文本串si-k si-k+1...si-1，而后让pk跟si继续匹配。
1. 之前本应是pj跟si匹配，结果失配了，失配后，令pk跟si匹配，相当于j 变成了k，模式串向右移动j - k位。
1. 因为k 的值是可变的，所以我们用next[j]表示j处字符失配后，下一次匹配模式串应该跳到的位置。换言之，失配前是j，pj跟si失配时，用p[ next[j] ]继续跟si匹配，相当于j变成了next[j]，所以，j = next[j]，等价于把模式串向右移动j - next [j] 位。
1. 而next[j]应该等于多少呢？next[j]的值由j 之前的模式串子串中有多大长度的相同前缀后缀所决定，如果j 之前的模式串子串中（不含j）有最大长度为k的相同前缀后缀，那么next
[j] = k。
如之前的图所示：
接下来，咱们来分析下KMP的时间复杂度。分析之前，先来回顾下KMP匹配算法的流程：
“KMP的算法流程：
- 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
- 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
- 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。”
我们发现如果某个字符匹配成功，模式串首字符的位置保持不动，仅仅是i++、j++；如果匹配失配，i 不变（即 i 不回溯），模式串会跳过匹配过的next [j]个字符。整个算法最坏的情况是，当模式串首字符位于i - j的位置时才匹配成功，算法结束。
所以，如果文本串的长度为n，模式串的长度为m，那么匹配过程的时间复杂度为O(n)，算上计算next的O(m)时间，KMP的整体时间复杂度为O(m + n)。
### 4. 扩展1：BM算法
KMP的匹配是从模式串的开头开始匹配的，而1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了一种新的字符串匹配算法：Boyer-Moore算法，简称BM算法。该算法从模式串的尾部开始匹配，且拥有在最坏情况下O(N)的时间复杂度。在实践中，比KMP算法的实际效能高。
BM算法定义了两个规则：
- 坏字符规则：当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外，如果"坏字符"不包含在模式串之中，则最右出现位置为-1。
- 好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。
下面举例说明BM算法。例如，给定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”，现要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。
*1*. 首先，"文本串"与"模式串"头部对齐，从尾部开始比较。"S"与"E"不匹配。这时，"S"就被称为"坏字符"（bad character），即不匹配的字符，它对应着模式串的第6位。且"S"不包含在模式串"EXAMPLE"之中（相当于最右出现位置是-1），这意味着可以把模式串后移6-(-1)=7位，从而直接移到"S"的后一位。
*2*. 依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。但是，"P"包含在模式串"EXAMPLE"之中。因为“P”这个“坏字符”对应着模式串的第6位（从0开始编号），且在模式串中的最右出现位置为4，所以，将模式串后移6-4=2位，两个"P"对齐。
*3*. 依次比较，得到 “MPLE”匹配，称为"好后缀"（good suffix），即所有尾部匹配的字符串。注意，"MPLE"、"PLE"、"LE"、"E"都是好后缀。> 
*4*. 发现“I”与“A”不匹配：“I”是坏字符。如果是根据坏字符规则，此时模式串应该后移2-(-1)=3位。问题是，有没有更优的移法？> 
*5*. 更优的移法是利用好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串中上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。
所有的“好后缀”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPLE”的头部出现，所以后移6-0=6位。
可以看出，“坏字符规则”只能移3位，“好后缀规则”可以移6位。每次后移这两个规则之中的较大值。这两个规则的移动位数，只与模式串有关，与原文本串无关。> 
*6*. 继续从尾部开始比较，“P”与“E”不匹配，因此“P”是“坏字符”，根据“坏字符规则”，后移 6 - 4 = 2位。因为是最后一位就失配，尚未获得好后缀。
由上可知，BM算法不仅效率高，而且构思巧妙，容易理解。
### 5. 扩展2：Sunday算法
上文中，我们已经介绍了KMP算法和BM算法，这两个算法在最坏情况下均具有线性的查找时间。但实际上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法虽然通常比KMP算法快，但BM算法也还不是现有字符串查找算法中最快的算法，本文最后再介绍一种比BM算法更快的查找算法即Sunday算法。
Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：
- 只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。
- 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1；
- 否则，其移动位数 = 模式串中最右端的该字符到末尾的距离+1。
下面举个例子说明下Sunday算法。假定现在要在文本串"substring searching algorithm"中查找模式串"search"。
*1*. 刚开始时，把模式串与文本串左边对齐：
substr**i**ng searching algorithm
search
^
*2*. 结果发现在第2个字符处发现不匹配，不匹配时关注文本串中参加匹配的最末位字符的下一位字符，即标粗的字符 i，因为模式串search中并不存在i，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7，从 i 之后的那个字符（即字符n）开始下一步的匹配，如下图：
substring sea**r**ching algorithm
search
^
*3*. 结果第一个字符就不匹配，再看文本串中参加匹配的最末位字符的下一位字符，是'r'，它出现在模式串中的倒数第3位，于是把模式串向右移动3位（r 到模式串末尾的距离 + 1 = 2 + 1 =3），使两个'r'对齐，如下：
substring searching algorithm
search
^
*4*. 匹配成功。
回顾整个过程，我们只移动了两次模式串就找到了匹配位置，缘于Sunday算法每一步的移动量都比较大，效率很高。完。
### 6. 参考文献
1. 《算法导论》的第十二章：字符串匹配；
1. 本文中模式串“ABCDABD”的部分图来自于此文：[http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html](http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html)；
1. 本文3.3.7节中有限状态自动机的图由微博网友@龚陆安 绘制：[http://d.pr/i/NEiz](http://d.pr/i/NEiz)；
1. 北京7月暑假班邹博半小时KMP视频：[http://www.julyedu.com/video/play/id/5](http://www.julyedu.com/video/play/id/5)；
1. 北京7月暑假班邹博第二次课的PPT：[http://yun.baidu.com/s/1mgFmw7u](http://yun.baidu.com/s/1mgFmw7u)；
1. 理解KMP 的9张PPT：[http://weibo.com/1580904460/BeCCYrKz3#_rnd1405957424876](http://weibo.com/1580904460/BeCCYrKz3#_rnd1405957424876)；
1. 详解KMP算法（多图）：[http://www.cnblogs.com/yjiyjige/p/3263858.html](http://www.cnblogs.com/yjiyjige/p/3263858.html)；
1. 本文第4部分的BM算法参考自此文：[http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html](http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html)；
1. [http://youlvconglin.blog.163.com/blog/static/5232042010530101020857](http://youlvconglin.blog.163.com/blog/static/5232042010530101020857/)；
1. 《数据结构 第二版》，严蔚敏 & 吴伟民编著；
1. [http://blog.csdn.net/v_JULY_v/article/details/6545192](http://blog.csdn.net/v_JULY_v/article/details/6545192)；
1. [http://blog.csdn.net/v_JULY_v/article/details/6111565](http://blog.csdn.net/v_JULY_v/article/details/6111565)；
1. Sunday算法的原理与实现：[http://blog.chinaunix.net/uid-22237530-id-1781825.html](http://blog.chinaunix.net/uid-22237530-id-1781825.html)；
1. 模式匹配之Sunday算法：[http://blog.csdn.net/sunnianzhong/article/details/8820123](http://blog.csdn.net/sunnianzhong/article/details/8820123)；
1. 一篇KMP的英文介绍：[http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm](http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm)；
1. 我2014年9月3日在西安电子科技大学的面试&算法讲座视频（第36分钟~第94分钟讲KMP）：[http://www.julyedu.com/video/play/id/7](http://www.julyedu.com/video/play/id/7)。
### 7. 后记
对之前混乱的文章给广大读者带来的困扰表示致歉，对重新写就后的本文即将给读者带来的清晰表示欣慰。希望大部分的初学者，甚至少部分的非计算机专业读者也能看懂此文。有任何问题，欢迎随时批评指正，thanks。
July、二零一四年八月二十二日晚九点。
字符串的排列/组合
最后更新于：2022-04-01 16:17:54
# 排列
字符串“abc”的全排列：
abc
acb
bac
bca
cba
cab
求整个字符串的排列，可以分为两步：
第一步，求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。第二步，固定第一个字符，求后面所有字符的全排列。这个时候仍然把后面所有字符分为两部分：第一个字符以及其后所有字符。这是一个典型的递归问题。
例如字符串“abc”的全排列：以a开头的全排列是a{bc}，递归得到bc的全排列，而bc的全排列又是以b开头，c的全排列（即c自己）；
同样，以b开头的全排列是b{ac}，递归得到ac的全排列，而ab的全排列又是以a开头，c的全排列。……
[http://blog.csdn.net/cinderella_niu/article/details/42930281](http://blog.csdn.net/cinderella_niu/article/details/42930281)
### 无重复的全排列 递归方法
如下是递归算法：
~~~
//全排列
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
void Permutation(char str[], int index, int size) {
cout << "Permutation(" << index << ", " << size << ")" << endl;
if (index == size - 1) {
//cout << "全排列："; //cout << str << endl;由于是全排列，还可以用这句打印结果
for (int i = 0; i < size; i++)
cout << str[i];
cout << endl;
}
else {
for (int i = index; i < size; i++) {
//cout << "\t" << str;
swap(str[index], str[i]);
//cout << " swap(" << index << ","<< i << ") " << str << endl;
Permutation(str, index + 1, size);
//cout << "---\t" << str;
swap(str[index], str[i]);
//cout << " swap(" << index << ","<< i << ") " << str << endl << endl;
}
}
}
~~~
~~~
int main() {
char test[] = "abc";
Permutation(0, sizeof(test) - 1);
}
~~~
下图分别是运行注释内语句和去掉注释内语句的运行结果：
另一种写法：
~~~
void Permutation(char* pStr, char* pBegin)
{
assert(pStr && pBegin);
if(*pBegin == '\0')
printf("%s\n",pStr);
else
{
for(char* pCh = pBegin; *pCh != '\0'; pCh++)
{
swap(*pBegin,*pCh);
Permutation(pStr, pBegin+1);
swap(*pBegin,*pCh);
}
}
}
~~~
### 有重复的全排列 递归方法
由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如abb，第一个数与后面交换得bab、bba。然后abb中第二数就不用与第三个数交换了，但对bab，它第二个数与第三个数是不相同的，交换之后得到bba。与由abb中第一个数与第三个数交换所得的bba重复了。所以这个方法不行。
*换种思维*，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数a与第三个数b交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑bab，它的第二个数与第三个数交换可以得到解决bba。此时全排列生成完毕。
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数。
~~~
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
~~~
~~~
//在pszStr数组中，[nBegin,nEnd)中是否有数字与下标为nEnd的数字相等
bool IsSwap(char *pszStr, int nBegin, int nEnd)
{
for (int i = nBegin; i < nEnd; i++)
if (pszStr[i] == pszStr[nEnd])
return false;
return true;
}
//k表示当前选取到第几个数,m表示共有多少数.
void PermutationHaveSameword(char *pszStr, int k, int m)
{
if (k == m)
{
static int s_i = 1;
printf(" 第%3d个排列\t%s\n", s_i++, pszStr);
}
else
{
for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
{
if (IsSwap(pszStr, k, i))
{
swap(pszStr[k], pszStr[i]);
PermutationHaveSameword(pszStr, k + 1, m);
swap(pszStr[k], pszStr[i]);
}
}
}
}
~~~
~~~
int main(void)
{
char str[] = "aba";
PermutationHaveSameword(str, 0, sizeof(str) - 2);
//Combination(str);
//Permutation(str, 0, sizeof(str) - 1);
return 0;
}
~~~
### 排列的非递归实习
这个木有懂，参考[http://blog.csdn.net/MoreWindows/article/details/7370155#t2](http://blog.csdn.net/MoreWindows/article/details/7370155)
至此我们已经运用了递归与非递归的方法解决了全排列问题，总结一下就是：
1．全排列就是从第一个数字起每个数分别与它后面的数字交换。
2．去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。
3．全排列的非递归就是由后向前找替换数和替换点，然后由后向前找第一个比替换数大的数与替换数交换，最后颠倒替换点后的所有数据。
### 全排列的变形：部分排列
问题：从0-9这十个数字中选取3个数字进行排列，打印所有的组合结果。
这个问题就是全排列的变种了，全排列是求出了所有字母的排列方式，该题是求出了部分字母排列的方法。只需要将本文第一个程序“无重复的全排列 递归方法”中，程序结束的条件由if (index == size - 1)改为 if (index == m)即可，其中m是指要进行全排列的字符个数，比如m = 3。
~~~
//全排列
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
//从size个字符中选取m个字符进行全排列，打印排列结果
void Permutation(char str[], int index, int m, int size) {
if (index == m) { //和本文第一个程序比只是这里打印时不太相同
for (int i = 0; i < m; i++)
cout << str[i];
cout << "\t";
}
else {
for (int i = index; i < size; i++) {
swap(str[index], str[i]);
Permutation(str, index + 1, size);
swap(str[index], str[i]);
}
}
}
~~~
测试从0-9中选两个数的排列结果：
~~~
int main() {
char test[] = "0123456789";
Permutation(test, 0, 2, sizeof(test) - 1);
}
~~~
# 组合问题
题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。
长度为n的字符串，能构成长度为1的组合、长度为2的组合、……、长度为n的组合。假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：第一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；第二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。
~~~
void Combination(char *string ,int number,vector<char> &result);
void Combination(char *string) {
assert(string != NULL);
vector<char> result;
int i , length = strlen(string);
for(i = 1 ; i <= length ; ++i)
Combination(string , i ,result);
}
//使用vector容器来存放要放入组合的字符
void Combination(char *string ,int number , vector<char> &result) {
assert(string != NULL);
if(number == 0) {
static int num = 1;
printf("第%d个组合\t",num++);
vector<char>::iterator iter = result.begin();
for( ; iter != result.end() ; ++iter)
printf("%c",*iter);
printf("\n");
return ;
}
if(*string == '\0')
return ;
result.push_back(*string);
cout << *string << endl;
Combination(string + 1 , number - 1 , result);
result.pop_back();
Combination(string + 1 , number , result);
}
~~~
### 使用位运算求组合问题
一个长度为n的字符串，它的组合有2^n-1中情况，我们用1 ~ 2^n-1的二进制来表示，每种情况下输出当前位等于1的字符。
~~~
void Combination(char *str)
{
int len=strlen(str);
for(int cur=1; cur < (1<<len); cur++) //遍历所有的情况，1<<len就等于2^len，遍历1 ~ 2^len-1
{
for(int j=0; j < len; j++) //遍历所有的字符
{
if(cur & (1 << j)) //判断哪一位为1，即输出该位
cout << str[j];
}
cout << endl; //一种情况结束
}
}
~~~
# 八皇后问题
八皇后问题：[](http://zhedahht.blog.163.com/blog/static/2541117420114331616329/)
### [程序员面试题精选100题(58)-八皇后问题[算法] ](http://zhedahht.blog.163.com/blog/static/2541117420114331616329/ "阅读全文")
# [经典回溯算法（八皇后问题）](http://www.cnblogs.com/gaoteng/archive/2012/04/11/2442692.html)
参考：[http://blog.sina.com.cn/s/blog_6fb300a30100mvzp.html](http://blog.sina.com.cn/s/blog_6fb300a30100mvzp.html)
[http://dongxicheng.org/structure/permutation-combination/](http://dongxicheng.org/structure/permutation-combination/)
[http://blog.csdn.net/hackbuteer1/article/details/7462447](http://blog.csdn.net/hackbuteer1/article/details/7462447)
[http://www.it165.net/pro/html/201412/28579.html](http://www.it165.net/pro/html/201412/28579.html)
### [程序员面试题精选100题(59)-字符串的组合[算法] ](http://zhedahht.blog.163.com/blog/static/2541117420114172812217/ "阅读全文")
栈和队列的相互模拟
最后更新于：2022-04-01 16:17:52
队列是先进先出的数据结构，栈时先进后出的数据结构，可以使用栈和队列模拟彼此。
# 两个队列模拟栈
使用C++泛型编程，队列使用STL的queue容器适配器。
主要思想：
两个队列模拟栈时，某时刻要么两个队列均为空，要么有一个队列为空。
（1）向栈中push时：如果两个队列均为空，将元素插入某个队列（这里假定插入队列1）；
如果某个队列不为空，将元素push到该队列中即可。
（2）从栈中pop时： 如果两个队列均为空，则函数返回即可；
如果某个队列不为空，将该队列的前n-1个元素出队，并依次插入另一个队列，再将最后一个元素pop（最后一个元素就是要）。
~~~
//test.h
#ifndef TEST_TEST_H
#define TEST_TEST_H
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
template <class T>
class Qstack {
private:
queue<T> queue1;
queue<T> queue2;
public:
void display(); //输出所有元素
void push(const T& value); //向栈中插入
void pop(); //从栈中弹出
};
template<typename T>
void Qstack<T>::display() {
if (queue1.size() > 0) {
queue<T> q1(queue1);
while (q1.size() > 0) {
cout << q1.front() << " ";
q1.pop();
}
}
if (queue2.size() > 0) {
queue<T> q2(queue2);
while (q2.size() > 0) {
cout << q2.front() << " ";
q2.pop();
}
}
cout << endl << endl;
}
//注意这里在类模板外定义其成员函数的写法
template<class T>
void Qstack<T>::push(const T& value) {
if (queue2.empty())
queue1.push(value);
else if (queue1.empty())
queue2.push(value);
else {}
}
//这里的pop操作返回void，当栈为空时什么也不做。
//这和STL中栈适配器pop操作行为一致
template<typename T>
void Qstack<T>::pop() {
if (queue1.size() > 0) {
while (queue1.size() > 1) {
queue2.push(queue1.front());
queue1.pop();
}
queue1.pop();
}
else if (queue2.size() > 0) {
while (queue2.size() > 1) {
queue1.push(queue2.front());
queue2.pop();
}
queue2.pop();
}
else {}
return;
}
#endif
~~~
测试：
~~~
#include "qstack.h"
using namespace std;
int main() {
Qstack<string> s;
s.push("1");
s.push("2");
s.push("3");
s.display();
s.pop();
s.display();
s.push("4");
s.push("5");
s.display();
s.pop();
s.display();
s.pop();
s.display();
}
~~~
# 两个栈模拟队列
使用C++泛型编程，栈使用STL的stack容器适配器。
主要思想：
与“两个队列模拟栈”不同：这个问题中，在某个状态下两个栈可能都不为空。
（1）向队列插入：一律插入stack1中。
（2）从队列取数：如果stack2不为空，直接从stack2中弹出一个元素；
如果stack2为空，那么将stack1中所有元素弹出并插入stack2，然后从stack2中pop一个。
~~~
template <typename T>
class CQueue
{
public:
void display();
// 在队列末尾添加一个结点
void appendTail(const T& node);
// 删除队列的头结点
void deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
template<typename T>
void CQueue<T>::display() {
stack<T> sq1(stack1);
stack<T> sq2(stack2);
while (sq2.size() > 0) {
cout << sq2.top() << " ";
sq2.pop();
}
while (sq1.size() > 0) {
T data = sq1.top();
sq1.pop();
sq2.push(data);
}
while (sq2.size() > 0) {
cout << sq2.top() << " ";
sq2.pop();
}
cout << endl;
}
template<typename T>
void CQueue<T>::appendTail(const T& element)
{
stack1.push(element);
}
template<typename T>
void CQueue<T>::deleteHead()
{
if(stack2.size()<= 0)
{
while(stack1.size()>0)
{
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
if (stack2.size() > 0)
stack2.pop();
return;
}
~~~
《剑指offer》中deleteHead函数返回被删除的元素，我认为没必要，因为STL中queue队列的删除返回就是void。当对空queue进行pop操作时，在VS2010下运行时会提示下图所示内容，但是g++下不会有任何提示，程序正确。
测试：
~~~
int main() {
CQueue<int> cq;
cq.appendTail(1);
cq.appendTail(2);
cq.appendTail(3);
cq.appendTail(4);
cq.display();
cq.deleteHead();
cq.deleteHead();
cq.display();
cq.appendTail(5);
cq.appendTail(6);
cq.display();
}
~~~
生成k个小于n的互不相同的随机数
最后更新于：2022-04-01 16:17:49
《编程珠玑》习题1.4：如果认真考虑了习题3，你将会面对生成小于n且没有重复的k个整数的问题。最简单的方法就是使用前k个正整数。这个极端的数据集合将不会明显的改变位图方法的运行时间，但是可能会歪曲系统排序的运行时间。如何生成位于0至n - 1之间的k个不同的随机顺序的随机整数？尽量使你的程序简短高效。
如下的程序产生1-n的不重复的随机数：
~~~
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void produce (int a[], int n) {
int i;
//对数组a依次赋一个不同的值
for (i = 0; i < n + 1; i++) {
a[i] = i + 1;
}
srand((int)time(0));
//下面的语句用于产生n个不同的随机数，存于数组的0到n-1位中
// i + rand() % (n - i)产生一个范围i到n的随机数
//那么将这个下标的数组数据和以i为下标的数组数据swap肯定不重复
for (i = 0; i < n; i++) {
swap(&a[i], &a[i + rand() % (n - i)]);
}
}
~~~
上面的算法复杂度为O(n);
在文章[Libnids的哈希函数](http://blog.csdn.net/u013074465/article/details/45061605)中，libnids的void init_hash () 函数也提供了一种产生0到11之间不重复随机数的方法，其复杂度为O(n ^ 2).
参考：
[http://blog.chinaunix.net/uid-21228455-id-2406483.html](http://blog.chinaunix.net/uid-21228455-id-2406483.html)
[http://blog.csdn.net/wdzxl198/article/details/12000091](http://blog.csdn.net/wdzxl198/article/details/12000091)
m个苹果放入n个盘子
最后更新于：2022-04-01 16:17:47
# 题目描述
放苹果问题：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
（注：5,1,1和1,1,5是同一种分法）
解题分析：
设f(m,n) 为m个苹果，n个盘子的放法数目，则先对n作讨论，
当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m) 当n<=m：不同的放法可以分成两类：
1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);
2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n) = f(m-n,n).而总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)
递归出口条件说明：
当n=1时，所有苹果都必须放在一个盘子里，所以返回１；
当m==0(没有苹果可放)时，定义为１种放法；
# 递归
~~~
int fun(int m,int n) //m个苹果放在n个盘子中共有几种方法
{
if(m==0||n==1) //因为我们总是让m>=n来求解的，所以m-n>=0,所以让m=0时候结束，如果改为m=1，
return 1; //则可能出现m-n=0的情况从而不能得到正确解
if(n>m)
return fun(m,m);
else
return fun(m,n-1)+fun(m-n,n);
}
~~~
# 动态规划
~~~
//放苹果
int main() {
int apple, plate;
cin >> apple >> plate;
if (apple < 0 || apple > 10 || plate < 1 || plate > 10) {
cout << -1 << endl;
return -1;
}
vector<vector<int> > ivec(11, vector<int>(11, 0));
for (int i = 0; i < 11; i++) {
ivec[0][i] = 1;
ivec[i][1] = 1;
}
for (int i = 1; i <= 10; ++i) {
for (int j = 1; j <= 10; ++j) {
if (j <= i)
ivec[i][j] = ivec[i][j - 1] + ivec[i - j][j];
else
ivec[i][j] = ivec[i][i];
}
}
cout << ivec[apple][plate] << endl;
return 0;
}
~~~
动态规划：计算字符串相似度
最后更新于：2022-04-01 16:17:45
《编程之美》第223页。
# 题目描述
许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：
1.修改一个字符（如把“a”替换为“b”）;
2.增加一个字符（如把“abdd”变为“aebdd”）;
3.删除一个字符（如把“travelling”变为“traveling”）;
比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案，都仅需要一 次 。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度 为1/2=0.5。
给定任意两个字符串，你是否能写出一个算法来计算它们的相似度呢？
# 采用递归方法求解
原文的分析与解法
不难看出，两个字符串的距离肯定不超过它们的长度之和（我们可以通过删除操作把两个串都转化为空串）。虽然这个结论对结果没有帮助，但至少可以知道，任意两个字符串的距离都是有限的。我们还是就住集中考虑如何才能把这个问题转化成规模较小的同样的子问题。如果有两个串A=xabcdae和B=xfdfa，它们的第一个字符是 相同的，只要计算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距离就可以了。但是如果两个串的第一个字符不相同，那么可以进行 如下的操作（lenA和lenB分别是A串和B串的长度）。
1.删除A串的第一个字符，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。
2.删除B串的第一个字符，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
3.修改A串的第一个字符为B串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
4.修改B串的第一个字符为A串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
5.增加B串的第一个字符到A串的第一个字符之前，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
6.增加A串的第一个字符到B串的第一个字符之前，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。
在这个题目中，我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以，可以将上面的6个操作合并为：
1.一步操作之后，再将A[2,...,lenA]和B[1,...,lenB]变成相字符串。
2.一步操作之后，再将A[2,...,lenA]和B[2,...,lenB]变成相字符串。
3.一步操作之后，再将A[1,...,lenA]和B[2,...,lenB]变成相字符串。
通过以上1和6,2和5，3和4的结合操作，最后两个字符串每个对应的字符会相同，但是这三种操作产生的最终的两个字符串是不一样的。我们不知道通过上述的三种结合那种使用的操作次数是最少的。所以我们要比较操作次数来求得最小值。
下面这幅图是摘自编程之美：从中我们可以看出一些信息。
可以看到，在计算的过程中，有索引越界的情况，抓住这个特点，就可以尽早的结束程序，同时还有重复计算的情况，比如(strA, 2, 2, strB, 2, 2).
# 动态规划方法求解
利用二维数组代替函数递归调用。
# 代码
~~~
#include <string>
#include <iostream>
#include <vector>
using namespace std;
//求三个数的最小值
int min(int a, int b, int c) {
if (a > b) {
if (b > c)
return c;
else
return b;
}
if (a > c) {
if (c > b)
return b;
else
return c;
}
if (b > c) {
if (c > a)
return a;
else
return c;
}
}
//使用动态规划求解方法
int StringDistance(string &str1, int start1, int end1,
string &str2, int start2, int end2) {
if (start1 > end1) {
if (start2 > end2)
return 0;
else
return end2 - start2 + 1;
}
if (start2 > end2) {
if (start1 > end1)
return 0;
else
return end1 - start1 + 1;
}
if (str1[start1] == str2[start2])
return StringDistance(str1, start1 + 1, end1, str2, start2 + 1, end2);
else {
int t1 = StringDistance(str1, start1 + 1, end1, str2, start2, end2);
int t2 = StringDistance(str1, start1, end1, str2, start2 + 1, end2);
int t3 = StringDistance(str1, start1 + 1, end1, str2, start2 + 1, end2);
return min(t1, t2, t3) + 1;
}
}
//递归求解方法
int StringDistance(string &str1, string &str2) {
int len1 = str1.length(), len2 = str2.length();
vector<vector<int> > ivec(len1 + 1, vector<int>(len2 + 1));
//下面初始化的含义：
//当str1长度为0时，那么两个字符串的距离就是str2的长度
//同样，当str2长度为0， 那么两个字符串距离就是str1的长度
for (int i = 0; i < len1 + 1; ++i)
ivec[i][0] = i;
for (int i = 0; i < len2 + 1; ++i)
ivec[0][i] = i;
for(int i = 1; i <= len1; ++i) {
for (int j = 1; j <= len2; ++j) {
if (str1[i - 1] == str2[j - 1])
ivec[i][j] = ivec[i - 1][j -1];
else
ivec[i][j] = min(ivec[i][j - 1], ivec[i - 1][j], ivec[i - 1][j - 1]) + 1;
}
}
return ivec[len1][len2];
}
int main() {
string str1, str2;
cin >> str1 >> str2;
//int dis = StringDistance(str1, 0, str1.length() - 1, str2, 0, str2.length() - 1);
int dis = StringDistance(str1, str2);
cout << dis << endl;
}
~~~
[http://blog.csdn.net/zzran/article/details/8274735](http://blog.csdn.net/zzran/article/details/8274735)
字符串合并处理（二进制位的倒序）
最后更新于：2022-04-01 16:17:43
<table id="table1" class="grid grid_tb " border="0" cellpadding="0" cellspacing="0"><tbody><tr><td class="grid_left_td" width="10%">描述: </td><td width="90%"><p>按照指定规则对输入的字符串进行处理。</p><p>详细描述：</p><p>将输入的两个字符串合并。</p><p>对合并后的字符串进行排序，要求为：下标为奇数的字符和下标为偶数的字符分别从小到大排序。这里的下标意思是字符在字符串中的位置。</p><p>对排训后的字符串进行操作，如果字符为‘0’——‘9’或者‘A’——‘F’或者‘a’——‘f’，<span style="color:#FF0000">则对他们所代表的16进制的数进行BIT倒序的操作，并转换为相应的大写字符</span>。如字符为‘4’，为0100b，则翻转后为0010b，也就是2。转换后的字符为‘2’； 如字符为‘7’，为0111b，则翻转后为1110b，也就是e。转换后的字符为大写‘E’。</p><p> </p><p>举例：输入str1为"dec"，str2为"fab"，合并为“decfab”，分别对“dca”和“efb”进行排序，排序后为“abcedf”，转换后为“5D37BF”</p><p>接口设计及说明：</p><p>/*</p><p>功能:字符串处理</p><p>输入:两个字符串,需要异常处理</p><p>输出:合并处理后的字符串，具体要求参考文档</p><p>返回:无</p><p>*/</p><p>void ProcessString(char* str1,char *str2,char * strOutput)</p><p>{</p><p>}</p><p> </p><p> </p> </td></tr><tr><td class="grid_left_td">知识点:</td><td> 字符串,排序,位运算 </td></tr><tr><td class="grid_left_td">题目来源:</td><td> 内部整理 </td></tr><tr><td class="grid_left_td">练习阶段:</td><td> 中级 </td></tr><tr><td class="grid_left_td">运行时间限制:</td><td>10Sec</td></tr><tr><td class="grid_left_td">内存限制:</td><td>128MByte</td></tr><tr><td class="grid_left_td">输入:</td><td> <p>输入两个字符串</p> </td></tr><tr><td class="grid_left_td">输出:</td><td> <p>输出转化后的结果</p> </td></tr><tr><td class="grid_left_td">样例输入:</td><td><pre>dec fab
</pre></td></tr><tr><td class="grid_left_td">样例输出:</td><td><pre>5D37BF
</pre></td></tr></tbody></table>
**关于二进制位的翻转问题参考：[二进制位的翻转](http://blog.csdn.net/u013074465/article/details/45485959)**
根据“二进制位翻转”这篇文章可以得到如下 程序将要使用的、对4位二进制位的翻转，可以如下处理：
~~~
int main() {
unsigned int n;
cin >> n;
n = n & 0xf;
cout << hex << n << endl;
n = ((n & 0x5) << 1) | ((n & 0xa) >> 1);
n = ((n & 0x3) << 2) | ((n & 0xc) >> 2);
cout << n << endl;
}
~~~
上面的程序将形如“1011”的二进制位序列翻转为“1101”。
解题如下：
~~~
#include <string>
//#include <algorithm>
#include <iostream>
//#include <string.h>
//#include <vector>
//#include <cmath>
#include <sstream>
using namespace std;
//变形的快排，对字符串分别排序其奇数下标字符、偶数下标字母
int PartQuickSort(string &str, int pos1, int pos2) {
char pivot = str[pos1];
int low = pos1, high = pos2;
while (high - low > 1) {
while (high - low > 1 && str[high] >= pivot)
high -= 2;
str[low] = str[high];
while (high - low > 1&& str[low] <= pivot)
low += 2;
str[high] = str[low];
}
str[low] = pivot;
return low;
}
void QuickSort(string &str, int pos1, int pos2) {
if (pos2 - pos1 > 1) {
int part = PartQuickSort(str, pos1, pos2);
QuickSort(str, pos1, part - 2);
QuickSort(str, part + 2, pos2);
}
}
//按照题目要求对特定字符翻转其二进制位
void process_str(string &str) {
char ch1, ch2 = 0;
bool flag = true;
int i;
for (i = 0; i < str.size(); i++) {
flag = true;
if (str[i] >= '0' && str[i] <= '9')
ch1 = str[i] - '0';
else if (str[i] >= 'a' && str[i] <= 'f')
ch1 = str[i] - 'a' + 10;
else if (str[i] >= 'A' && str[i] <= 'F')
ch1 = str[i] - 'A' + 10;
else
flag = false;
if (flag) {
//本题要注意这里将二进制位翻转的做法。
//例如11的二进制为1011，翻转后为1101
ch2 = 0;
ch2 |= (ch1 & (1 << 0)) << 3;
ch2 |= (ch1 & (1 << 1)) << 1;
ch2 |= (ch1 & (1 << 2)) >> 1;
ch2 |= (ch1 & (1 << 3)) >> 3;
if (ch2 < 10) {
str[i] = '0' + ch2;
//cout << str[i] << endl;
}
else {
str[i] = 'A' + ch2 - 10;
//cout << str[i] << endl;
}
}
}
}
int main() {
string str, str1, str2;
getline(cin, str);
stringstream stream(str);
stream >> str1 >> str2;
str1 += str2;
str2 = str1;
//分别对字符串的偶数下标、奇数下标排序
if (str1.size() % 2 != 0) {
QuickSort(str1, 0, str1.size() - 1);
QuickSort(str1, 1, str1.size() - 2);
}
else {
QuickSort(str1, 0, str1.size() - 2);
QuickSort(str1, 1, str1.size() - 1);
}
process_str(str1);
cout << str1 << endl;
}
~~~
汽水瓶
最后更新于：2022-04-01 16:17:40
<table id="table1" class="grid grid_tb " border="0" cellpadding="0" cellspacing="0" style="margin:0px; padding:0px; list-style-type:none; border-spacing:0px; border-collapse:collapse; max-width:100%; background-color:rgb(219,222,223); font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif; width:968px; border:0px; empty-cells:show; color:rgb(51,51,51); font-size:14px; line-height:20px"><tbody style="margin:0px; padding:0px; list-style-type:none"><tr style="margin:0px; padding:0px; list-style-type:none; height:26px"><td width="10%" class="grid_left_td" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">描述: </td><td width="90%" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"><p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; list-style-type:none"><span style="margin:0px; padding:0px; list-style-type:none">有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶，最多可以换多少瓶汽水喝？</span><br style="margin:0px; padding:0px; list-style-type:none"/></p> </td></tr><tr style="margin:0px; padding:0px; list-style-type:none; height:26px"><td class="grid_left_td" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">知识点:</td><td style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 循环 </td></tr><tr style="margin:0px; padding:0px; list-style-type:none; height:26px"><td class="grid_left_td" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">题目来源:</td><td style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 内部整理 </td></tr><tr style="margin:0px; padding:0px; list-style-type:none; height:26px"><td class="grid_left_td" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">练习阶段:</td><td style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 中级 </td></tr><tr style="margin:0px; padding:0px; list-style-type:none; height:26px"><td class="grid_left_td" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">运行时间限制:</td><td style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">无限制</td></tr><tr style="margin:0px; padding:0px; list-style-type:none; height:26px"><td class="grid_left_td" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">内存限制:</td><td style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">无限制</td></tr><tr style="margin:0px; padding:0px; list-style-type:none; height:26px"><td class="grid_left_td" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">输入:</td><td style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; list-style-type:none"><span style="margin:0px; padding:0px; list-style-type:none">输入文件最多包含10组测试数据，每个数据占一行，仅包含一个正整数n（1<=n<=100），表示小张手上的空汽水瓶数。n=0表示输入结束，你的程序不应当处理这一行。</span><br style="margin:0px; padding:0px; list-style-type:none"/></p> </td></tr><tr style="margin:0px; padding:0px; list-style-type:none; height:26px"><td class="grid_left_td" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">输出:</td><td style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px; list-style-type:none"><span style="margin:0px; padding:0px; list-style-type:none">对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出0。</span><br style="margin:0px; padding:0px; list-style-type:none"/></p> </td></tr><tr style="margin:0px; padding:0px; list-style-type:none; height:26px"><td class="grid_left_td" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">样例输入:</td><td style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"><pre style="margin-top:0px; margin-bottom:10px; padding:9.5px; list-style-type:none; white-space:pre-wrap; word-wrap:break-word; line-height:1.42857143; overflow:auto; font-family:Menlo,Monaco,Consolas,'Courier New',monospace; font-size:13px; word-break:break-all; background-color:rgb(245,245,245); border:1px solid rgb(204,204,204)">3
10
81
0
</pre></td></tr><tr style="margin:0px; padding:0px; list-style-type:none; height:26px"><td class="grid_left_td" style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)">样例输出:</td><td style="margin:0px; padding:6px 3px 3px; list-style-type:none; word-break:break-all; word-wrap:break-word; font-family:'Microsoft YaHei',Arial,Helvetica,sans-serif!important; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"><pre style="margin-top:0px; margin-bottom:10px; padding:9.5px; list-style-type:none; white-space:pre-wrap; word-wrap:break-word; line-height:1.42857143; overflow:auto; font-family:Menlo,Monaco,Consolas,'Courier New',monospace; font-size:13px; word-break:break-all; background-color:rgb(245,245,245); border:1px solid rgb(204,204,204)">1
5
40
</pre></td></tr></tbody></table>
两种方式处理，注意下面代码中输入不确定的n个数以0结束输入的方法：
~~~
//方法一：找到规律就这么简单n/2
void fun1() {
int n;
//注意这里输入不确定个整数，以0结束的输入方式
while (cin >> n, n) {
if (n < 0)
break;
cout << n / 2 << endl;
}
}
//方法二：
int fun2(int n) {
int remainder = 0;
int divisor = 0;
int count = 0;
while (n / 3) {
divisor = n / 3;
remainder = n % 3;
count += divisor;
n = divisor + remainder;
}
//如果最后还剩两个空瓶子，可以向老板借一个
//空瓶子再买一瓶
if (n % 3 == 2)
count += 1;
return count;
}
int main() {
//fun1();
int n;
while (cin >> n) {
if (n != 0) {
cout << fun2() << endl;
}
else
break;
}
return 0;
}
~~~
称砝码问题
最后更新于：2022-04-01 16:17:38
# 题目描述
有一组砝码，重量互不相等，分别为m1、m2、m3……mn；它们可取的最大数量分别为x1、x2、x3……xn。
现要用这些砝码去称物体的重量,问能称出多少种不同的重量。
Input
测试数据第一行一个整数n（n<=10），表示有多种不同的砝码；
第二行n个整数（中间用空格分隔），m1、m2、m3……mn，分别表示n个砝码的重量；（1<=mi<=20）
第三行n个整数（中间用空格分隔），x1、x2、x3……xn，分别表示n个砝码可取的最大数量。（1<=xi<=20）
Output
每组数据输出仅一行，一个整数，表示利用给定的砝码可以称出的不同的重量数。
注：包括0。
Sample Input
2
1 2
2 1
Sample Output
5
~~~
//称砝码
int main() {
int n;
cin >> n;
int max_wight = 0;
vector<int> nums(n), wights(n);
for (int i = 0; i < n; i++)
cin >> wights[i];
for (int i = 0; i < n; i++) {
cin >> nums[i];
max_wight += wights[i] * nums[i]; //求最大可称重的值
}
//set内是可以称重的值，元素互斥单调增
set<int> s;
s.insert(max_wight);
//进行n次循环；
//对于第i次循环，将set中元素从小到大依次取出，
//减去k * wights[i]，表示少使用k个质量为wights[i]的砝码
//也可以作为可称重的值；只要这个值是大于0的即可。
for (int i = 0; i < n; i++) {
set<int>::iterator iter = s.begin();
while (iter != s.end()) {
for (int k = 1; k <= nums[i] && *iter - k * wights[i] > 0; k++)
s.insert(*iter - k * wights[i]);
iter++;
}
}
s.insert(0);
cout << s.size() << endl;
return 0;
}
~~~
最长递增子序列
最后更新于：2022-04-01 16:17:36
# 最长递增子序列
[http://blog.csdn.net/lisonglisonglisong/article/details/45241965](http://blog.csdn.net/lisonglisonglisong/article/details/45241965)
最长递增子序列（Longest Increasing Subsequence）是指找到一个给定序列的最长子序列的长度，使得子序列中的所有元素单调递增。
例如：{ 3，5，7，1，2，8 } 的 LIS 是 { 3，5，7，8 }，长度为 4。
### 解法一：转化为求最长公共子序列
其实可以把 求最长递增子序列问题 转化为 求最长公共子序列的问题。
- 设数组 { 3， 5， 7， 1， 2， 8 } 为 A
- 对数组 A 排序，排序后的数组为 B = { 1， 2， 3， 5， 7， 8 }。
- 于是，求数组 A 的最长递增子序列，就是求数组 A 与数组 B 的最长公共子序列。
最长公共子序列的求法见《[动态规划DP](http://blog.csdn.net/lisonglisonglisong/article/details/41548557)》。本方法的时间复杂度是
Θ(nlgn)+Θ(n2)=Θ(n2)
### 解法二：动态规划法
虽然解法一也是使用动态规划，但是与解法一不同的是，解法二不进行转化，而是直接在原问题上采用动态规划法。
**最优子结构：**
对于长度为 N 的数组 A[N]={a0,a1,a2,…,an−1}，假设我们想求以ai 结尾的最大递增子序列长度，设为L[i]，那么
L[i]=⎧⎩⎨max(L[j])+1,1,where j<i and A[j]<A[i]otherwise
也就是 j 的范围是 0 到 i–1。这样，想求ai 结尾的最大递增子序列的长度，我们就需要遍历 i 之前的所有位置 j（0到 i-1），找出A[j]<A[i]，计算这些j 中，能产生最大 L[j] 的 j，之后就可以求出L[i]。之后对每一个A[N]中的元素都计算以他们各自结尾的最大递增子序列的长度，这些长度的最大值，就是我们要求的问题——数组A的最大递增子序列的长度。
**重叠子问题：**
根据上述推导式采用递归实现的话，有些子问题会被计算很多次。
**动态规划法：**
综上所述，LIS 问题具有动态规划需要的两个性质，可以使用动态规划求解该问题。设数组 A = { 3，5，7，1，2，8 }，则：
具体的打表方式如下：
- 初始化对角线为 1；
- 对每一个 i，遍历 j（0 到 i-1）：
- 若`A[i] <= A[j]`，置 1。
- 若`A[i] > A[j]`，取第 j 行的最大值加 1。
打完表以后，最后一行的最大值就是最长递增子序列的长度。由于每次都进行遍历，故时间复杂度还是 Θ(n2)。
[](http://blog.csdn.net/lisonglisonglisong/article/details/45241965)
~~~
// LIS 的动态规划方式实现
#include <iostream>
using namespace std;
int getLISLength(int A[], int len) {
//定义一维数组并初始化为1
int* lis = new int[len];
for (int i = 0; i < len; ++i)
lis[i] = 1;
// 计算每个i对应的lis最大值，即打表的过程
for (int i = 1; i < len; ++i)
for (int j = 0; j < i; ++j) // 0到i-1
if ( A[i] > A[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1; // 更新
// 数组中最大的那个，就是最长递增子序列的长度
int maxlis = 0;
for (int i = 0; i < len; ++i)
if ( maxlis < lis[i] )
maxlis = lis[i];
delete [] lis;
return maxlis;
}
~~~
### 解法三：Θ(nlgn)的方案
本解法的具体操作如下：
- 建立一个辅助数组array，依次读取数组元素 x 与数组末尾元素 top比较：
- 如果 x > top，将 x 放到数组末尾；
- 如果 x < top，则二分查找数组中第一个 大于等于x 的数，并用 x 替换它。
遍历结束之后，最长递增序列长度即为栈的大小。
注意c数组的下标代表的是子序列的长度，c数组中的值也是按递增顺序排列的。这才可能用二分查找。
数组array[i]存储的是子序列长度为i的序列最后一个值（该值是该子序列中最大的元素；如果长度为i的序列有多个，那么array[i]存放这类序列最后元素中的最小一个）
~~~
int getLISLength(int num[], int length) {
vector<int> ivec;
for (int i = 0; i < length; ++i) {
if (ivec.size() == 0 || ivec.back() < num[i])
ivec.push_back(num[i]);
else {
int low = 0, high = ivec.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
if (ivec[mid] < num[i])
low = mid + 1;
else
high = mid - 1;
}
ivec[low] = num[i];
}
}
return ivec.size();
}
~~~
特别注意的是：本方法只能用于求最长递增子序列的长度，辅助数组中的序列不是最长递增子序列：
-
例一：原序列为1，5，8，3，6，7
辅助数组为1，5，8，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。
-
例二：原序列为1，5，8，3
则最栈辅助数组为1，3，8。明显这不是最长递增子序列！
# 合唱队问题
<table id="table1" class="grid grid_tb " border="0" cellpadding="0" cellspacing="0"><tbody><tr><td class="grid_left_td" width="10%">描述: </td><td width="90%"><p style="white-space:normal">计算最少出列多少位同学，使得剩下的同学排成合唱队形</p><p style="white-space:normal">说明：</p><p style="white-space:normal"><span style="font-family:'times new roman'">N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 <br/>合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得Ti<T2<......<Ti-1<Ti>Ti+1>......>TK。 <br/> 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 <br/></span></p><p style="white-space:normal"> </p><p><br/></p> </td></tr><tr><td class="grid_left_td">知识点:</td><td> 循环 </td></tr><tr><td class="grid_left_td">题目来源:</td><td> 内部整理 </td></tr><tr><td class="grid_left_td">练习阶段:</td><td> 初级 </td></tr><tr><td class="grid_left_td">运行时间限制:</td><td>无限制</td></tr><tr><td class="grid_left_td">内存限制:</td><td>无限制</td></tr><tr><td class="grid_left_td">输入:</td><td> <p style="white-space:normal">整数N</p><p style="white-space:normal">一行整数，空格隔开，N位同学身高</p><p><br/></p> </td></tr><tr><td class="grid_left_td">输出:</td><td> <p><span style="font-family:'times new roman'">最少需要几位同学出列</span><br/></p> </td></tr><tr><td class="grid_left_td">样例输入:</td><td><pre>8
186 186 150 200 160 130 197 200
</pre></td></tr><tr><td class="grid_left_td">样例输出:</td><td><pre>4
</pre></td></tr></tbody></table>
根据题意可知，我们需要求出一个“中间点”，使得其左边的【最长递增子序列】和其右边的【最长递减子序列】之和最大。
~~~
#include <iostream>
#include <vector>
using namespace std;
int LonggestIncreaseLength(vector<int> &vec) {
vector<int> result(vec.size(), 1);
vector<int> result2(vec.size(), 1);
for (int i = 1; i < vec.size(); i++) {
for (int j = 0; j < i; j++) {
if (vec[i] > vec[j] && result[i] < result[j] + 1)
result[i] = result[j] + 1;
}
}
for (int i = vec.size() - 2; i >= 0; --i) {
for (int j = vec.size() - 1; j > i; --j) {
if (vec[i] > vec[j] && result2[i] < result2[j] + 1)
result2[i] = result2[j] + 1;
}
}
int max = 0;
for (int i = 0; i < vec.size(); i++) {
if (max < result[i] + result2[i])
max = result[i] + result2[i];
}
return vec.size() - max + 1;
}
int main() {
int n;
cin >> n;
if (n <= 0)
return 0;
vector<int> ivec(n);
for (int i = 0; i < n; i++)
cin >> ivec[i];
cout << LonggestIncreaseLength(ivec) << endl;
}
~~~
动态规划：求最长公共子串/最长公共子序列
最后更新于：2022-04-01 16:17:34
# 最长公共子序列和最长公共子串区别
最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。例如X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}那么，{a, 1, 1}是X和Y的最长公共子序列，但不是它们的最长公共字串。
# 一、最长公共子序列
具体的算法思想参考以下文章：
[http://blog.csdn.net/lisonglisonglisong/article/details/41548557](http://blog.csdn.net/lisonglisonglisong/article/details/41548557)
[http://blog.csdn.net/zhongkeli/article/details/8847694](http://blog.csdn.net/zhongkeli/article/details/8847694)
[
](http://blog.csdn.net/zhongkeli/article/details/8847694)
### 只求最长子序列长度
如果仅仅需要知道最长子序列的长度值，代码如下：
~~~
#include <vector>
#include <string>
#include <iostream>
#include <string.h>
#include <sstream>
using namespace std;
//最长公共子串（LCS）
//二维数组veca记录的是两个字符串Xi和Yj的LCS长度
int LCS_length(const string &str1, const string &str2, vector<vector<int> > &veca) {
int i, j;
int biggest = 0;
if (str1 == "" || str2 == "")
return 0;
for (i = 0; i <= str1.length(); i++) {
veca[i][0] = 0;
}
for (j = 0; j <= str2.length(); j++) {
veca[0][j] = 0;
}
for (i = 1; i <= str1.length(); i++) {
for (j = 1; j <= str2.length(); j++) {
if (str1[i - 1] == str2[j - 1]) {
veca[i][j] = veca[i - 1][j - 1] + 1;
}
else {
if (veca[i - 1][j] >= veca[i][j - 1])
veca[i][j] = veca[i - 1][j];
else
veca[i][j] = veca[i][j-1];
}
}
}
return veca[str1.length()][str2.length()];
}
int main() {
string input;
getline(cin, input);
stringstream ss(input);
string str1, str2;
ss >> str1;
ss >> str2;
//将veca初始化为一个二维数组,其行列值分别为str1和str2的长度加1
//二维数组veca记录的是两个字符串Xi和Yj的LCS长度
vector<vector<int> > veca(str1.length() + 1, vector<int>(str2.length() + 1));
cout << LCS_length(str1, str2, veca) << endl;
return 0;
}
~~~
结果：
动态规划解决LCS问题的时间复杂度为O(mn)，这比简单的递归实现要快多了。空间复杂度是O(mn)，因为使用了一个动态规划表。
### 要输出一个LCS的内容
和上面的程序比，只需要多一个二维数组记录在遍历中所选择的子问题的最优解即可。如下程序：
~~~
//输出最长公共子串（LCS）
//二维数组veca记录的是两个字符串Xi和Yj的LCS长度
int LCS_length(const string &str1, const string &str2,
vector<vector<int> > &veca, vector<vector<int> > &vecb) {
int i, j;
int biggest = 0;
if (str1 == "" || str2 == "")
return 0;
for (i = 0; i <= str1.length(); i++) {
veca[i][0] = 0;
}
for (j = 0; j <= str2.length(); j++) {
veca[0][j] = 0;
}
for (i = 1; i <= str1.length(); i++) {
for (j = 1; j <= str2.length(); j++) {
//如果Xi-1 == Yj-1，那么最长子序列为veca[i - 1][j - 1] + 1
//此时将vecb[i][j] = 1表明str1[i-1]是子问题LCS的一个元素
if (str1[i - 1] == str2[j - 1]) {
veca[i][j] = veca[i - 1][j - 1] + 1;
vecb[i][j] = 1;
}
else {
if (veca[i - 1][j] >= veca[i][j - 1]) {
veca[i][j] = veca[i - 1][j];
vecb[i][j] = 2;
}
else {
veca[i][j] = veca[i][j-1];
vecb[i][j] = 3;
}
}
}
}
return veca[str1.length()][str2.length()];
}
//该函数用于输出一个LCS的序列
//这里输出的顺序是先向上寻找，再向左寻找
void PrintOneLCS(vector<vector<int> > &vecb, string &str1, int i, int j) {
if (i == 0 || j == 0)
return;
if (vecb[i][j] == 1) {
PrintOneLCS(vecb, str1, i - 1, j - 1);
cout << str1[i - 1] << " ";
}
else if (vecb[i][j] == 2)
PrintOneLCS(vecb, str1, i -1, j);
else
PrintOneLCS(vecb, str1, i, j - 1);
}
int main() {
string input;
getline(cin, input);
stringstream ss(input);
string str1, str2;
ss >> str1;
ss >> str2;
//将veca初始化为一个二维数组,其行列值分别为str1和str2的长度加1
//二维数组veca记录的是两个字符串Xi和Yj的LCS长度
//二维数组vecb[i][j]记录veca[i][j]时所选择的子问题的最优解
vector<vector<int> > veca(str1.length() + 1, vector<int>(str2.length() + 1));
vector<vector<int> > vecb(str1.length() + 1, vector<int>(str2.length() + 1));
cout << LCS_length(str1, str2, veca, vecb) << endl;
PrintOneLCS(vecb, str1, str1.length(), str2.length());
return 0;
}
~~~
求一个LCS内容也可以不借助辅助二维数组vecb而是用下面小节的方法，
~~~
//该函数用于输出一个LCS的序列，使用下一小节的方法
//这里输出的顺序是先向左寻找，再向上寻找
void PrintOneLCS(string &str1, string &str2, int i, int j,
vector<vector<int> > &veca) {
string lcs_str;
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
lcs_str = str1[i - 1] + lcs_str;
--i;
--j;
}
else {
//如果左边存在LCS就从左边找否则再从右边找
if (veca[i - 1][j] >= veca[i][j - 1])
--i;
else
--j;
}
}
cout << lcs_str << endl;
}
~~~
如下代码：
### 要输出所有LCS的内容
两个字符串对应的最长公共子序列不一定唯一，这个程序输出所有的LCS内容。
基本思想是：
具体参考文章：[http://blog.csdn.net/lisonglisonglisong/article/details/41596309](http://blog.csdn.net/lisonglisonglisong/article/details/41596309)
代码：
~~~
#include <vector>
#include <iomanip>
#include <set>
#include <string>
#include <map>
#include <iostream>
#include <string.h>
#include <sstream>
using namespace std;
set<string> all_lcs; //注意这里要用set去除重复的LCS
//最长公共子串（LCS）
//二维数组veca[i][j]记录的是两个字符串Xi和Yj的LCS长度
int LCS_length(const string &str1, const string &str2, vector<vector<int> > &veca) {
int i, j;
int biggest = 0;
if (str1 == "" || str2 == "")
return 0;
for (i = 0; i <= str1.length(); i++) {
veca[i][0] = 0;
}
for (j = 0; j <= str2.length(); j++) {
veca[0][j] = 0;
}
for (i = 1; i <= str1.length(); i++) {
for (j = 1; j <= str2.length(); j++) {
if (str1[i - 1] == str2[j - 1]) {
veca[i][j] = veca[i - 1][j - 1] + 1;
}
else {
if (veca[i - 1][j] >= veca[i][j - 1])
veca[i][j] = veca[i - 1][j];
else
veca[i][j] = veca[i][j-1];
}
}
}
return veca[str1.length()][str2.length()];
}
//该函数找出所有的LCS的序列，并将其存在vector中
void PrintAllLCS(string &str1, string &str2, int i, int j,
vector<vector<int> > &veca, string lcs_str) {
//注意这里形参lcs_str不可以为引用，这里需要每次调用lcs_str都重新生成一个对象
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
lcs_str = str1[i - 1] + lcs_str; //逆向存放
--i;
--j;
}
else {
if (veca[i - 1][j] > veca[i][j - 1]) //向左走
--i;
else if (veca[i - 1][j] < veca[i][j - 1]) //向上走
--j;
else { //此时向上向右均为LCS的元素
PrintAllLCS(str1, str2, i - 1, j, veca, lcs_str);
PrintAllLCS(str1, str2, i, j - 1, veca, lcs_str);
return;
}
}
}
cout << " " << lcs_str << endl;
all_lcs.insert(lcs_str);
}
int main() {
string input;
getline(cin, input);
stringstream ss(input);
string str1, str2;
ss >> str1;
ss >> str2;
//将veca初始化为一个二维数组,其行列值分别为str1和str2的长度加1
//二维数组veca记录的是两个字符串Xi和Yj的LCS长度
vector<vector<int> > veca(str1.length() + 1, vector<int>(str2.length() + 1));
cout << LCS_length(str1, str2, veca) << endl;
string lcs_str;
PrintAllLCS(str1, str2, str1.length(), str2.length(), veca, lcs_str);
set<string>::iterator iter = all_lcs.begin();
while (iter != all_lcs.end()) {
cout << *iter++ << endl;
}
return 0;
}
~~~
如图所示的两个字符串共有三个LCS。
# 二、最长公共子串
**描述：**
计算两个字符串的最大公共子串（Longest Common Substring）的长度，字符不区分大小写。
**输入：**
输入两个字符串
**输出：**
输出一个整数
**样例输入：**
~~~
asdfas werasdfaswer
~~~
**样例输出：**
~~~
6
~~~
这里的**最大公共字串要求的字串是连续**的。
求字串的方法和求子序列方法类似：
当str1[i] == str2[j]时，子序列长度veca[i][j] = veca[i - 1][j - 1] + 1；只是当str1[i] ！= str2[j]时，veca[i][j]长度要为0，而不是max{veca[i - 1][j], veca[i][j - 1]}。
~~~
#include <vector>
#include <string>
#include <iostream>
#include <string.h>
#include <sstream>
using namespace std;
int LCS_length(const string &str1, const string &str2, vector<vector<int> > &veca) {
int i, j;
int biggest = 0;
if (str1 == "" || str2 == "")
return 0;
for (i = 0; i <= str1.length(); i++) {
veca[i].resize(str2.length() + 1, 0);
}
for (j = 0; j <= str2.length(); j++) {
veca[0][j] = 0;
}
for (i = 1; i <= str1.length(); i++) {
for (j = 1; j <= str2.length(); j++) {
if (str1[i - 1] == str2[j - 1]) {
veca[i][j] = veca[i - 1][j - 1] + 1;
if (veca[i][j] > biggest)
biggest = veca[i][j];
}
else
//可以看出，求最长子串和求最长子序列差别仅仅在这里
veca[i][j] = 0;
}
}
return biggest;
}
int main() {
string input;
getline(cin, input);
stringstream ss(input);
string str1;
ss >> str1;
string str2;
ss >> str2;
vector<vector<int> > veca(str1.length() + 1);
cout << LCS_length(str1, str2, veca) << endl;
return 0;
}
~~~
同样适用求最长子序列的测试数据，得到它们的公共最长子串长度为2，而它们的公共最长子序列长度为4.
# 三、动态规划的其它题目
1、硬币面值组合问题
[http://www.cnblogs.com/python27/archive/2013/09/05/3303721.html](http://www.cnblogs.com/python27/archive/2013/09/05/3303721.html)
2、[最长递增子序列](http://blog.csdn.net/u013074465/article/details/45442067)
除了动态规划，该题还有其他解法。
3、数组最大子数组和的最大值
[http://www.ahathinking.com/archives/120.html](http://www.ahathinking.com/archives/120.html)
3、[动态规划之钢条分割](http://blog.csdn.net/u013074465/article/details/44920979)
4、计算两个字符串的相似度（编程之美）
该文章原理说得比较清楚：[点击打开链接](http://www.cnblogs.com/tianchi/archive/2013/02/25/2886964.html)
这里是代码：[点击打开链接](http://blog.csdn.net/zzran/article/details/8274735)
5、求每一对顶点之间的最短路径：Floyd-Warshall算法
hash函数的基本知识
最后更新于：2022-04-01 16:17:31
一致性hash参考：[一致性哈希](http://blog.csdn.net/u013074465/article/details/46939275)
Hash函数也称为散列表，是一种常用的数据结构。哈希表优点：可以提供快速插入和查找操作，无论有多少数据项，插入与查找只需接近常量的时间：O(1)时间级。而且编程很容易实现。哈希表的缺点：它是基于数组的，数组一旦被创建，就难以拓展；某些哈希表的填充因子（填入的元素个数/哈希表长度)过大，性能会急剧下降。
Hash函数在多个领域均有应用，而在数字签名和数据库实现时又用的最多，比如基于hash的索引，是最好的单值查找索引；同时，在当前数据爆炸的场景下，执行相似item的查找时，在内存受限时，均可以采取LSH（local sensitive hash）进行分段处理。具体用途很多，不赘述，下面介绍一些常用的知识：hash函数本质；简单的hash函数生成法；hash的冲突消解；
一个国外牛人的个人网站，有非常全面的hash算法列表：[http://burtleburtle.net/bob/hash/](http://burtleburtle.net/bob/hash/)
# 1 hash的本质
还可以参考这里[http://blog.csdn.net/u013074465/article/details/40504975](http://blog.csdn.net/u013074465/article/details/40504975)
Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间。在考虑使用Hash函数之前，需要明白它的几个限制：
（1）Hash的主要原理就是把大范围映射到小范围；所以，你输入的实际值的个数必须与小范围相当或者比它更小。不然冲突就会很多。
（2） 由于Hash逼近单向函数；所以，你可以用它来对数据进行加密。
（3）不同的应用对Hash函数有着不同的要求；比如，用于加密的Hash函数主要考虑它和单项函数的差距，而用于查找的Hash函数主要考虑它映射到小范围的冲突率。
Hash函数好坏非评判标准：简单和均匀。
简单指散列函数的计算简单快速；
均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集K随机均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。
# 2 常用hash生成方法
常用的散列函数构造有7种方法，1，直接定址法； 2，数字分析法； 3 ，平方取中法；4，除留余数法；5，相乘取整法；6，伪随机数法；7，折叠法
### （1）直接寻址法
取关键字或关键字的某个线性函数值为散列地址。
即Hash(key) = key 或Hash(key) = a * key + b，其中a,b为常数。
### （2）数字分析法
分析一组数据，比如某班学生的出生年月日发现出生年月日的前几位数字大体相同，这样的话，冲突的几率会很大，但是发现年月日的后几位表示月份和具体日期的数字差别较大，如果用后几位构成散列地址，则冲突的几率会明显降低。因此数字分析法是找出数字的规律，尽可能利用这些数字构造冲突几率低的散列地址。
### （3）平方取中法
具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。
【例】将一组关键字(0100，0110，1010，1001，0111)平方后得 (0010000，0012100，1020100，1002001，0012321)
若取表长为1000，则可取中间的三位数作为散列地址集：
(100，121，201，020，123)。
相应的散列函数用C实现很简单：
~~~
int Hash(int key){ //假设key是4位整数
key *= key;
key /= 100; //先求平方值，后去掉末尾的两位数
return key ％ 1000; //取中间三位数作为散列地址返回
}
~~~
### （4）除余法
该方法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址，即 h(key)=key％m
该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数。
【例】若选m是关键字的基数的幂次，则就等于是选择关键字的最后若干位数字作为地址，而与高位无关。于是高位不同而低位相同的关键字均互为同义词。
【例】若关键字是十进制整数，其基为10，则当m=100时，159，259，359，…，等均互为同义词。
### （5）相乘取整法
该方法包括两个步骤：首先用关键字key乘上某个常数A(0<A<1)，并抽取出key.A的小数部分；然后用m乘以该小数后取整。即：
该方法最大的优点是选取m不再像除余法那样关键。比如，完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用，但对某些值效果会更好。
该函数的C代码为：
~~~
int Hash(int key){
double d=key *A; //不妨设A和m已有定义
return (int)(m*(d-(int)d));//(int)表示强制转换后面的表达式为整数
}
~~~
### （6）随机数法
选择一个随机函数，取关键字的随机函数值为它的散列地址，即
h(key) = random(key)
其中random为伪随机函数，但要保证函数值是在0到m-1之间。
### （7） 折叠法
将关键字分割成位数相同的几个部分（最后一部分位数可以不同），然后取这几个部分的叠加和（舍弃进位）作为哈希地址。
关键字位数很多，而且关键字中每一位数字分布大致均匀时，可以采用折叠法。
# 3 处理hash冲突
### 1)冲突是如何产生的？
上文中谈到，哈希函数是指如何对关键字进行编址的，这里的关键字的范围很广，可视为无限集，如何保证无限集的原数据在编址的时候不会出现重复呢？规则本身无法实现这个目的。
举一个例子，仍然用班级同学做比喻，现有如下同学数据：张三，李四，王五，赵刚，吴露.....
假如我们编址规则为取姓氏中姓的开头字母在字母表的相对位置作为地址，则会产生如下的哈希表
<table rules="all" border="1" cellpadding="3" cellspacing="0"><tbody><tr><td width="35"><span style="font-size:12px">位置</span></td><td width="35"><span style="font-size:12px">字母</span></td><td width="35"><span style="font-size:12px">姓名</span></td><td width="35"><span style="font-size:12px"><br/></span></td></tr><tr><td width="35"><span style="font-size:12px">0</span></td><td width="35"><span style="font-size:12px">a</span></td><td><span style="font-size:12px"><br/></span></td><td><span style="font-size:12px"><br/></span></td></tr><tr><td><span style="font-size:12px">1</span></td><td><span style="font-size:12px">b</span></td><td><span style="font-size:12px"><br/></span></td><td><span style="font-size:12px"><br/></span></td></tr><tr><td><span style="font-size:12px">2</span></td><td><span style="font-size:12px">c</span></td><td><span style="font-size:12px"><br/></span></td><td><span style="font-size:12px"><br/></span></td></tr></tbody></table>
...
<table border="1" cellpadding="3" cellspacing="0"><tbody><tr><td width="35"><span style="font-size:12px">10 </span></td><td width="35"><span style="font-size:12px">L </span></td><td width="35"><span style="font-size:12px">李四</span></td><td width="35"><span style="font-size:12px"><br/></span></td></tr></tbody></table>
...
<table border="1" cellpadding="3" cellspacing="0" style="background-color:#c0c0c0"><tbody><tr><td width="35"><span style="font-size:12px">22</span></td><td width="35"><span style="font-size:12px">W</span></td><td width="100"><span style="font-size:12px">王五，吴露</span></td><td width="35"><span style="font-size:12px"><br/></span></td></tr></tbody></table>
..
<table border="1" cellpadding="3" cellspacing="0" style="background-color:#c0c0c0"><tbody><tr><td width="35"><span style="font-size:12px">25 </span></td><td width="35"><span style="font-size:12px">Z </span></td><td width="100"><span style="font-size:12px">张三，赵刚</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td></tr></tbody></table>
我们注意到，灰色背景标示的两行里面，关键字王五，吴露被编到了同一个位置，关键字张三，赵刚也被编到了同一个位置。老师再拿号来找张三，座位上有两个人，"你们俩谁是张三？"
### 2)如何解决冲突问题
既然不能避免冲突，那么如何解决冲突呢，显然需要附加的步骤。通过这些步骤，以制定更多的规则来管理关键字集合，通常的办法有:
### a)开放地址法
开放地执法有一个公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1，称线性探测再散列。
会出现的问题：一次聚集，即使表相对较空，这样占据的单元也会开始形成一些区块，散列到区块中的任何关键字都要经过多次探测才能解决冲突，然后该关键字又加入到相应块区中。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
称二次探测再散列。
二次探测可以解决线性探测的一次聚集问题，但是会出现二次聚集：散列到同一位置上的那些元素将探测相同的备选单元。
为了解决上述的二次聚集，另一个解决冲突的方法是：双散列
比如选择di = i * Hash2(key)，即发生冲突时，我们将第二个散列函数应用到key并在距离Hash2(key)、 2Hash2(key)、……进行探测。
如果di取值可能为伪随机数列。称伪随机探测再散列。仍然以学生排号作为例子，
现有两名同学，李四，吴用。李四与吴用事先已排好序，现新来一名同学，名字叫王五，对它进行编制
| 10.. | .... | 22 | .. | .. | 25 |
|-----|-----|-----|-----|-----|-----|
| 李四.. | .... | 吴用 | .. | .. | 25 |
赵刚未来之前
<table border="1" cellpadding="3" cellspacing="0"><tbody><tr><td width="60"><span style="font-size:12px">10..</span></td><td width="60"><span style="font-size:12px">..</span></td><td width="60"><span style="font-size:12px">22</span></td><td width="60"><span style="font-size:12px">23</span></td><td width="60"><span style="font-size:12px">25</span></td></tr><tr><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">李四..</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">吴用</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">王五</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td></tr></tbody></table>
(a)线性探测再散列对赵刚进行编址，且di=1
<table border="1" cellpadding="3" cellspacing="0"><tbody><tr><td width="60"><span style="font-size:12px">10...</span></td><td width="60"><span style="font-size:12px">20</span></td><td width="60"><span style="font-size:12px">22</span></td><td width="60"><span style="font-size:12px">..</span></td><td width="60"><span style="font-size:12px">25</span></td></tr><tr><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">李四..</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">王五</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">吴用</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td></tr></tbody></table>
(b)二次探测再散列，且di=-2
<table border="1" cellpadding="3" cellspacing="0"><tbody><tr><td width="60"><span style="font-size:12px">1...</span></td><td width="60"><span style="font-size:12px">10...</span></td><td width="60"><span style="font-size:12px">22</span></td><td width="60"><span style="font-size:12px">..</span></td><td width="60"><span style="font-size:12px">25</span></td></tr><tr><td style="background-color:#c0c0c0"><span style="font-size:12px">王五..</span></td><td style="background-color:#c0c0c0"><span style="font-size:12px">李四..</span></td><td style="background-color:#c0c0c0"><span style="font-size:12px">吴用</span></td><td style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td><td style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td></tr></tbody></table>
(c)伪随机探测再散列,伪随机序列为:5,3,2
### b)再哈希法
当散列表较满时，冲突增加，插入可能失败。于是建立另外一个大约两倍大的散列表（而且使用新的散列函数），扫描原来散列表，计算每个未删除元素的新的散列值，并将其插入到新表中。
缺点：这是非常昂贵的操作，运行时间O(N)，不过再散列不是经常发生，实际效果没那么差
### c)链地址法
将所有关键字为同义词的记录存储在同一线性链表中。如下：
### d.建立一个公共溢出区（比较常见于实际操作中）
假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
经过以上方法，基本可以解决掉hash算法冲突的问题。
还有许多用于散列表的方法，比如散列函数不好或装填因子过大，都会使堆积现象加剧。为了减少堆积的发生，不能像线性探查法那样探查一个顺序的地址序列(相当于顺序查找)，而应使探查序列跳跃式地散列在整个散列表中。衍生出二次探查法，双重散列表法。
参考资料：
http://hunteagle.iteye.com/blog/118551
数据结构（C语言版） 严蔚敏
动态规划之钢条分割
最后更新于：2022-04-01 16:17:29
长度i 1 2 3 4 5 6 7 8 9 10
价格Pi 1 5 8 9 10 17 17 20 24 30
上图分别是长度为i的钢条的价格；那么现在一根长度为n的钢条，求如何切割，使得利润最大？
《算法导论》205页。
如果只求最大利润的值，不需要知道分割过程，有以下两种方法：
~~~
#include "test.h"
#define MAXLEN 11
//****算法导论，动态规划，钢条分割，P205
//自底向上，仅记录最优解结果
int ButtomUpCutRod(int priceList[], int n) {
int highest[MAXLEN] = {-1}; //记录每个长度对应的最优解
highest[0] = 0; //长度为0的最优解（最大利润）为0
int j = 0;
for (j = 1; j <= n; j++) {
int highest_j = -1; //长度为j的最优解
int i;
for (i = 1; i <= j; i++)
//长度为i的最优解为不切割时，或者为切割长度为i的利润加上长度为j-i的最优解
highest_j = max(highest_j, priceList[i] + highest[j - i]);
highest[j] = highest_j; //记录长度为j的最优解值
}
return highest[n];
}
/**********方法二************/
//该函数计算长度为n的钢条的最大利润
int MemorizedCutRod_aux(int priceList[], int n, int highest[]) {
int highest_n = -1;
if (highest[n] >= 0) //如果长度为n的最优解已经被记录了，就直接返回
return highest[n];
if (n == 0) //长度为0的钢条利润为0
highest_n = 0;
else { //还未记录钢条的利润，则计算之
int i;
for (i = 1; i <= n; i++)
//长度为n的钢条最大利润为不切割，或者为切割长度i的利润加上长苏为n-i的最大利润
highest_n = max(highest_n, priceList[i] + MemorizedCutRod_aux(priceList, n-i, highest));
}
highest[n] = highest_n; //记录长度为n的最大利润
return highest_n;
}
//自顶向下，仅记录最优解结果
int MemorizedCutRod(int priceList[], int n) {
int highest[11];
int i;
//初始化最大利润列表
for (i = 0; i < MAXLEN; i++)
highest[i] = -1;
return MemorizedCutRod_aux(priceList, n, highest);
}
~~~
如果不仅要求得最大利润，还要知道如何切割，方法和上面方法很类似，只是需要记录下切割第一段的长度：
~~~
pair<vector<int>, vector<int> > ButtomUpCutRodSolution(vector<int> &priceList, int n) {
vector<int> highest; //每个元素依次记录长度递增的钢条最优解结果
vector<int> solution(priceList.size()); //记录长度为n的钢条的解决方案
int highest_j = -1;
highest.push_back(0); //长度为0的钢条最优解为0
int j;
for (j = 1; j <= n; j++) { //依次求长度为1直到长度为n的钢条的最优解
highest_j = -1;
int i;
for (i = 1; i <= j; i++) { //长度为j的钢条最优解的计算
if (highest_j < priceList[i] + highest[j - i]) {
highest_j = priceList[i] + highest[j - i];
solution[j] = i; //记录切割中取得最优解的切割长度
}
}
highest.push_back(highest_j); //记录长度为j的钢条的最优解
}
return make_pair(highest, solution);
}
//该算法不仅输出最优解，而且给出最优解的一个切割方案
void printSolution(vector<int> &priceList, int n) {
pair<vector<int>, vector<int> > ivec = ButtomUpCutRodSolution(priceList, n);
cout << "highest price3: " << ivec.first.at(n); //输出最优解
vector<int> solu = ivec.second;
cout << " solution: ";
while (n > 0) { //输出解决方案
cout << solu[n] << " ";
n -= solu[n];
}
cout << endl;
vector<int>::iterator iter = solu.begin();
while (iter != solu.end())
cout << *(iter++) << " ";
cout << endl;
cout << endl << endl;
}
//对以上方法的测试：
int main() {
int priceList[] = {0,1, 5, 8, 9,10,17,17,20,24,30};
vector<int> priceVec(priceList, priceList + sizeof(priceList) / sizeof(int));
int n;
while (1) {
cout << "input length: ";
cin >> n;
cout << "highest price: " << ButtomUpCutRod(priceList, n);
cout << " highest price2: " << MemorizedCutRod(priceList, n) << endl;
printSolution(priceVec, n);
}
}
~~~
测试结果：
avl树的C++实现
最后更新于：2022-04-01 16:17:27
这里给出了C++代码的实现。关于AVL树的C语言的实现参见《[AVL树（Adelson-Velskii-Landis tree）](http://blog.csdn.net/u013074465/article/details/44672567)》
~~~
//3avl_tree_c++.h
#ifndef AVL_TREE_cplusplus_H
#define AVL_TREE_cplusplus_H
#include <iostream>
using namespace std;
template <typename Comparable>
class AvlTree
{
public:
AvlTree():root(NULL) {}
AvlTree(const AvlTree &rhs): root(NULL) {
*this = rhs;
}
~AvlTree() {
makeEmpty();
}
const Comparable &findMin() const {
if (isEmpty())
cout << "树为空" << endl;
return findMin(root)->element;
}
const Comparable &findMax() const {
if (isEmpty())
cout << "树为空" << endl;
return findMax(root)->element;
}
bool contains(const Comparable &x) const {
return contains(x, root);
}
bool isEmpty() const {
return root == NULL;
}
void printTree() const {
if (isEmpty())
cout << "Empty tree." << endl;
else {
cout << "先序：";
printTreePreOrder(root);
cout << endl << "中序：";
printTreeInOrder(root);
cout << endl << "后序：";
printTreePostOrder(root);
}
cout << endl;
}
void makeEmpty() {
makeEmpty(root);
}
void insert(const Comparable &x) {
insert(x, root);
}
void remove(const Comparable &x) {
remove(x, root);
}
const AvlTree &operator=(const AvlTree &rhs) {
if (this != &rhs) {
makeEmpty();
root = clone(rhs.root);
}
return this;
}
private:
struct AvlNode
{
Comparable element;
AvlNode *left;
AvlNode *right;
int height;
AvlNode(const Comparable &theElement, AvlNode *l, AvlNode *r, int h = 0):
element(theElement), left(l), right(r), height(h) {}
};
AvlNode *root;
void insert(const Comparable &x, AvlNode* &t) {
if (t == NULL)
t = new AvlNode(x, NULL, NULL);
else if (x < t->element) {
insert(x, t->left);
if (height(t->left) - height(t->right) == 2)
if (x < t->left->element)
rotateWithLeftChild(t);
else
doubleWithLeftChild(t);
}
else if (x > t->element) {
insert(x, t->right);
if (height(t->right) - height(t->left) == 2)
if (t->right->element < x)
rotateWithRightChild(t);
else
doubleWithRightChild(t);
}
else
; //要往树中插入已经存在的元素，什么也不做
t->height = max(height(t->left), height(t->right)) + 1;
}
void remove(const Comparable &x, AvlNode* &t) {
if (t == NULL)
return;
if (x < t->element) {
remove(x, t->left);
if (height(t->right) - height(t->left) == 2) {
if (height(t->right->left) > height(t->right->right))
doubleWithRightChild(t);
else
rotateWithRightChild(t);
}
}
else if (x > t->element) {
if (height(t->left) - height(t->right) == 2) {
if (height(t->left->right) > height(t->left->left))
doubleWithLeftChild(t);
else
rotateWithLeftChild(t);
}
}
else if (t->left && t->right) { //找到要删除的位置，t有两个孩子
t->element = findMin(t->right)->element;
remove(t->element, t->right);
t->height = max(height(t->left), height(t->right)) + 1;
}
else {
AvlNode *oldNode = t;
t = (t->left == NULL) ? t->right : t->left;
delete oldNode;
}
if (t != NULL)
t->height = max(height(t->left), height(t->right)) + 1;
}
AvlNode *findMin(AvlNode *t) const {
if (t == NULL)
return NULL;
if (t->left == NULL)
return t;
return findMin(t->left);
}
AvlNode *findMax(AvlNode *t) const {
//注释部分为递归
//if (t == NULL)
// return NULL;
//if (t->right == NULL)
// return t;
//return findMax(t->right);
//非递归形式
if (t != NULL)
while (t->right != NULL)
t = t->right;
return t;
}
bool contains(const Comparable &x, AvlNode *t) const {
if (t == NULL)
return false;
else if (x < t->element)
return contains(x, t->left);
else if (x > t->element)
return contains(x, t->right);
else
return true;
}
/*
//非迭代操作
bool contains(const Comparable &x, AvlNode *t) {
while (t != NULL) {
if (x < t->element)
t = t->left;
else if (x > t->element)
t = t->right;
else
return true;
}
return false;
}
*/
void makeEmpty(AvlNode* &t) {
if (t != NULL) {
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
void printTreePreOrder(AvlNode *t) const {
if (t != NULL) {
cout << t->element << " ";
printTreePreOrder(t->left);
printTreePreOrder(t->right);
}
}
void printTreeInOrder(AvlNode * t) const {
if (t != NULL) {
printTreeInOrder(t->left);
cout << t->element << " ";
printTreeInOrder(t->right);
}
}
void printTreePostOrder(AvlNode * t) const {
if (t != NULL) {
printTreePostOrder(t->left);
printTreePostOrder(t->right);
cout << t->element << " ";
}
}
AvlNode *clone(AvlNode *t) const {
if (t == NULL)
return NULL;
return new AvlNode(t->element, clone(t->left), clone(t->right));
}
int height(AvlNode *t) const {
return t == NULL ? -1 : t->height;
}
int max(int lhs, int rhs) {
return lhs > rhs ? lhs : rhs;
}
//单旋转，左-左
void rotateWithLeftChild(AvlNode * & k2) {
AvlNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left), height(k2->right)) + 1;
k1->height = max(height(k1->left), height(k1->right)) + 1;
k2 = k1;
}
//单旋转，右-右
void rotateWithRightChild(AvlNode * & k1) {
AvlNode *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(height(k1->left), height(k1->right)) + 1;
k2->height = max(height(k2->left), height(k2->right)) + 1;
k1 = k2;
}
//双旋转，左-右
void doubleWithLeftChild(AvlNode * & k3) {
rotateWithRightChild(k3->left);
rotateWithLeftChild(k3);
}
//双旋转，右-左
void doubleWithRightChild(AvlNode * & k3) {
rotateWithLeftChild(k3->right);
rotateWithRightChild(k3);
}
};
#endif
~~~
测试代码：
~~~
#include "3avl_tree_c++.h"
int main() {
AvlTree<int> tree;
int i = 0;
while (i != 9) {
tree.insert(i++);
}
tree.printTree();
cout << endl << "删除11但11不存在：" << endl;
tree.remove(11);
tree.printTree();
cout << endl << "删除 5和8：" << endl;
tree.remove(5);
tree.remove(8);
tree.printTree();
return 0;
}
~~~
AVL树（Adelson-Velskii-Landis tree）
最后更新于：2022-04-01 16:17:24
AVL树是一个“加上了额外平衡条件”的二叉搜索树。其平衡条件的建立时为了确保树的深度为O(longN)。AVL树要求任何节点左右子树的高度相差不超过1。
插入操作：左-左插入和右-右插入需要单旋转；
左-右插入和右-左插入需要双旋转。
其实，AVL树的插入删除操作和[二叉查找树的操作](http://blog.csdn.net/u013074465/article/details/41699891)类似，只是需要注意调整树的平衡。
# AVL树 C语言实现
删除操作的旋转示意图：
在下面的代码中，插入删除过程中，对树平衡的调整完全可以封装为函数，显得简洁，但懒人我没写成函数。
~~~
//3avl_tree.c
#include "3avl_tree.h"
#include "test.h"
AvlTree MakeEmptyAvlTree(AvlTree avltree) {
if (avltree != NULL) {
MakeEmptyAvlTree(avltree->left);
MakeEmptyAvlTree(avltree->right);
free(avltree);
}
return NULL;
}
Position FindAvlTree(ElementType x, AvlTree avltree) {
if (avltree == NULL)
return NULL;
if (x < avltree->element)
return FindAvlTree(x, avltree->left);
else if (x > avltree->element)
return FindAvlTree(x, avltree->right);
else
return avltree;
}
Position FindMinFromAvlTree(AvlTree avltree) {
if (avltree == NULL)
return NULL;
else if (avltree->left == NULL)
return avltree;
else
return FindMinFromAvlTree(avltree->left);
}
Position FindMaxFromAvlTree(AvlTree avltree) {
if (avltree == NULL)
return NULL;
else if (avltree->right == NULL)
return avltree;
else
return FindMaxFromAvlTree(avltree->right);
}
static int HeightAvlTree(AvlTree avltree) {
if (avltree == NULL)
return -1;
else
return avltree->height;
}
static int Max(int lhs, int rhs) {
return lhs > rhs ? lhs : rhs;
}
//左-左插入，使得k2失去平衡，因此需要在k2处单旋转
static Position SingleRotateWithLeft(Position k2) {
Position k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = Max(HeightAvlTree(k2->left), HeightAvlTree(k2->right)) + 1;
k1->height = Max(HeightAvlTree(k1->left), HeightAvlTree(k1->right)) + 1;
return k1;
}
//右-右插入，使得k1失去平衡，因此需要在k1处单旋转
static Position SigleRotateWithRight(Position k1) {
Position k2;
k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = Max(HeightAvlTree(k1->left), HeightAvlTree(k1->right)) + 1;
k2->height = Max(HeightAvlTree(k2->left), HeightAvlTree(k2->right)) + 1;
return k2;
}
//左-右插入，使得k3失去平衡，因此在k3处双旋转
//双旋转其实是两次单旋转操作
//先对k3的左子树进行一次右-右单旋转操作
//然后对k3进行一次左-左单旋转操作
static Position DoubleRotateWithLeft1(Position k3) { //双旋转，递归
k3->left = SigleRotateWithRight(k3->left);
return SingleRotateWithLeft(k3);
}
static Position DoubleRotateWithLeft2(Position k3) {
Position k1, k2;
k1 = k3->left;
k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k3->left = k2->right;
k2->right = k3;
k1->height = Max(HeightAvlTree(k1->left), HeightAvlTree(k1->right)) + 1;
k3->height = Max(HeightAvlTree(k3->left), HeightAvlTree(k3->right)) + 1;
k2->height = Max(k1->height, k3->height) + 1;
return k2;
}
//右-左插入，使得k1失去平衡，因此在k1处双旋转
//双旋转其实是两次单旋转操作
//先对k1的右子树进行一次左-左单旋转操作
//然后对k1进行一次右-右单旋转操作
static Position DoubleRotateWithRight(Position k1) {
k1->right = SingleRotateWithLeft(k1->right);
return SigleRotateWithRight(k1);
}
AvlTree InsertToAvlTree(ElementType x, AvlTree avltree) {
if (avltree == NULL) { //如果树为空，分配空间，插入节点
avltree = (struct AvlNode*)malloc(sizeof(struct AvlNode));
if (avltree == NULL) {
cout << "malloc failed." << endl;
}
else {
avltree->element = x;
avltree->left = avltree->right = NULL;
}
}
//插入值小于根节点的值，在左子树插入节点
else if (x < avltree->element) {
avltree->left = InsertToAvlTree(x, avltree->left);
//树失去了平衡，对树进行调整，这几个调整平衡的语句可以封装下
if (HeightAvlTree(avltree->left) - HeightAvlTree(avltree->right) == 2) {
if (x < avltree->left->element) //左-左，进行左单旋转
avltree = SingleRotateWithLeft(avltree);
else //左-右，双旋转
avltree = DoubleRotateWithLeft1(avltree);
}
}
//插入值大于根节点的值，在右子树插入节点
else if (x > avltree->element) {
avltree->right = InsertToAvlTree(x, avltree->right);
//树失去了平衡，对树进行调整，这几个调整平衡的语句可以封装下
if (HeightAvlTree(avltree->right) - HeightAvlTree(avltree->left) == 2) {
if (x > avltree->right->element)
avltree = SigleRotateWithRight(avltree); //右-右，单旋转
else //右-左，双旋转
avltree = DoubleRotateWithRight(avltree);
}
}
avltree->height = Max(HeightAvlTree(avltree->left), HeightAvlTree(avltree->right)) + 1;
return avltree;
}
//删除操作类似于二叉树的操作，只是需要将树调整平衡
AvlTree DeleteFromAvlTree(ElementType x, AvlTree avltree) {
Position temp;
if (avltree == NULL)
return NULL;
//在左子树寻找删除位置，删除后可能导致左子树高度变小，可能要调整树
if (x < avltree->element) {
avltree->left = DeleteFromAvlTree(x, avltree->left);
//如果右子树高度比左子树高度超过1，那么需要将树调整平衡，这几个调整平衡的语句可以封装下
if (2 == (HeightAvlTree(avltree->right) - HeightAvlTree(avltree->left))) {
//如果是右-左型，则要进行左单旋、右单旋；即进行如下双旋操作
//否则为右-右型，需要进行左单旋操作
if (HeightAvlTree(avltree->right->left) > HeightAvlTree(avltree->right->right))
avltree = DoubleRotateWithRight(avltree);
else
avltree = SigleRotateWithRight(avltree);
}
}
//在右子树寻找删除位置，删除后可能导致右子树高度变小，可能要调整树
else if (x > avltree->element) {
avltree->right = DeleteFromAvlTree(x, avltree->right);
//这几个调整平衡的语句可以封装下
if (2 == (HeightAvlTree(avltree->left) - HeightAvlTree(avltree->right))) {
if (HeightAvlTree(avltree->left->right) > HeightAvlTree(avltree->left->left))
avltree = DoubleRotateWithLeft1(avltree);
else
avltree = SingleRotateWithLeft(avltree);
}
}
//找到要删除的元素,该节点有两个孩子
//那么将节点的值用右子树中最小的值A替换，然后在右子树中删除A
else if (avltree->left && avltree->right){
avltree->element = (FindMinFromAvlTree(avltree->right))->element;
avltree->right = DeleteFromAvlTree(avltree->element, avltree->right);
}
//找到要删除的节点，该节点为叶子节点或仅有一个孩子
else {
temp = avltree;
if (avltree->left == NULL) //当节点只有右孩子或为叶节点时
avltree = avltree->right;
else if (avltree->right == NULL) //当节点只有左孩子时
avltree = avltree->left;
free(temp);
}
if (avltree)
avltree->height = Max(HeightAvlTree(avltree->right), HeightAvlTree(avltree->left)) + 1;
return avltree;
}
void VisitElement(AvlTree tree) {
cout << tree->element << " ";
}
//先序遍历树
void PreOrderTraversal(AvlTree tree) {
if (tree == NULL)
return;
VisitElement(tree);
PreOrderTraversal(tree->left);
PreOrderTraversal(tree->right);
}
//中序遍历树
void InOrderTraversal(AvlTree tree) {
if (tree == NULL)
return;
InOrderTraversal(tree->left);
VisitElement(tree);
InOrderTraversal(tree->right);
}
int main() {
AvlTree tree = NULL;
tree = MakeEmptyAvlTree(tree);
tree = InsertToAvlTree(1, tree);
tree = InsertToAvlTree(3, tree);
tree = InsertToAvlTree(5, tree);
tree = InsertToAvlTree(122, tree);
tree = InsertToAvlTree(7, tree);
tree = InsertToAvlTree(9, tree);
tree = InsertToAvlTree(11, tree);
tree = InsertToAvlTree(21, tree);
Position min = FindMinFromAvlTree(tree);;
cout << "删除前，树高：" << HeightAvlTree(tree) << endl;
cout << endl << "删除前，先序遍历：" << endl;
PreOrderTraversal(tree);
cout << endl << "删除前，中序遍历：" << endl;
InOrderTraversal(tree);
DeleteFromAvlTree(7, tree);
cout << endl;
cout << "删除后，树高：" << HeightAvlTree(tree) << endl;
cout << endl << "删除后，先序遍历：" << endl;
PreOrderTraversal(tree);
cout << endl << "删除后，中序遍历：" << endl;
InOrderTraversal(tree);
}
~~~
~~~
//3avl_tree.h
typedef int ElementType;
#ifndef TEST_AVL_TREE_H
#define TEST_AVL_TREE_H
struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
struct AvlNode {
ElementType element;
AvlTree left;
AvlTree right;
int height;
};
AvlTree MakeEmptyAvlTree(AvlTree avltree);
Position FindAvlTree(ElementType x, AvlTree avltree);
Position FindMinFromAvlTree(AvlTree avltree);
Position FindMaxFromAvlTree(AvlTree avltree);
AvlTree InsertToAvlTree(ElementType x, AvlTree avltree);
AvlTree DeleteFromAvlTree(ElementType x, AvlTree avltree);
ElementType RetrieveAvlTree(Position pos);
#endif
~~~
程序执行结果：
# [Avl的C++实现](http://blog.csdn.net/u013074465/article/details/44748497)
基础排序算法总结
最后更新于：2022-04-01 16:17:22
# 稳定性概念
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
# [一、冒泡排序](http://blog.csdn.net/u013074465/article/details/44339187)
冒泡排序的普通思路：
比较相邻的两个元素，交换元素使得小元素在前、大元素在后。
第一次排序将对n个元素进行n-1次比较，将最大的元素放到了数组的最后边；
第二次排序将剩下的n-1个元素进行n-2次比较，将第二大的数放在数组的倒数第二个位置；
依次进行该过程；
第n-1趟则所有元素都是有序的，即完成了排序。
改进的冒泡排序：
设置一个标志用来记录某次遍历数组中，有没有发生元素的交换；如果发生了元素的交换，说明数组还没有完全有序；如果没发生元素交换，说明整个数组已经有序，则排序结束。
通过设置这个标志可以减少元素的比较次数。
# [二、插入排序](http://blog.csdn.net/u013074465/article/details/42043665)
思路：
每次将数组右边一个待排序的数据插入到数组左边已经排序的序列中，直到整个数组都是有序的。
某次排序，将数组分为已排序序列A（数组左边部分）和未排序序列B（数组右边部分）；每次排序依次从B序列中取一个元素b，让其依次与A序列的元素比较（依次从A序列的最右一个元素向左开始比较），为数b在A序列中寻找一个合适的插入位置，将b插入A。
由于每次都是将大于b的元素右移动，然后将b放在该位置，因此不会发生相同元素的交换，因此是稳定的。
# [三、希尔排序](http://blog.csdn.net/u013074465/article/details/42043665)
思路：
将数组分割为若干个子序列，每个序列中的元素都是由相隔某个增量的元素组成。
对每个子序列分别进行插入排序；然后依次缩减增量，再次重复上述排序。
直到增量为1后，进行依次排序，这时整个数组就是有序的，排序结束。
希尔排序是对相隔若干距离的数据进行直接插入排序的。
一次插入排序是稳定的，不会改变相同元 素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是**不稳定的。
# [四、选择排序](http://blog.csdn.net/u013074465/article/details/44342373)
思路（假设非递减排序）：
类似于插入排序，将序列分为了有序的和无序的子序列，不过这里不是依次选择一个未排序的元素插入已排序序列；而是找出未排序序列中最小的元素，将其与已经排序的序列紧邻的那个元素交换（初始已排序序列为0）。
例如5，8，5，2，9序列的第一趟排序是将第一个5与2交换，那么，两个5的次序就交换了，所以选择排序不稳定。
# [五、归并排序](http://blog.csdn.net/u013074465/article/details/42043967)
思路：
当一个数组的左部分有序、右部分也有序时，只要将这两部分合并即可完成排序。而如何使得左、右部分分别有序呢？递归使用归并排序即可。
在归并的过程中，主要的操作是合并两个有序的序列，在合并中，如果两个元素相等，不会对它们交换，因此稳定。
# [六、快速排序](http://blog.csdn.net/u013074465/article/details/42083607)
上述链接的文章中给出了详细的思路和过程。
快速排序被认为是所有同数量级(O(nlogn))排序方法中，平均性能最好的。
**时间复杂度：**
但是，如果初始记录序列有序时，以左侧元素为枢纽的快速排序算法将退化为冒泡排序，其时间复杂度为O(n ^ 2)；在初始序列有序或逆序情况下，每次排序需要n * n次比较，因此算法复杂度为O(n ^ 2)。
**空间复杂度：**
快速排序需要一个栈空间来实现递归（即使是[非递归算法](http://blog.csdn.net/u013074465/article/details/42083607#t3)，它也需要一个辅助栈来保存下次带排序数组的下标范围）。若每一趟排序都将记录序列均匀分割为长度接近相等的两个子序列，则平均情况下栈的最大深度为logn + 1（包括最外层参数进栈），但是若每趟排序后，枢纽位置均偏向子序列的一端（初始序列有序或逆序），则为最坏情况，栈的最大深度为n。
# [七、堆排序](http://blog.csdn.net/u013074465/article/details/42043697)
如果要按照非递减顺序排序，那么要使用大根堆；按照非递增顺序排序，要使用小根堆。
假设按照非递减顺序排列，那么排序的思路是：
首先建立一个大根堆；
删除大根堆的根元素（说是删除，其实是利用了堆最后的那个空间来存储该元素，即将根元素与堆尾部元素交换，这样当堆删除完后，那么存储空间就是有序的了）；
每次交换的根元素和尾元素后要进行下滤操作，使得满足大根堆。
排序过程就是删除根元素并上滤的过程，上滤中可能会让相等元素位置改变，因此不稳定。
# 八、线性时间排序
以上将的都是基于比较的排序，时间复杂度上界为O(n ^ 2)， 下界为O(nlogn)。下面介绍几种线性排序：
### 1、基数排序
基数排序是按照低位先排序，然后收集；再按照次低位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优 先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，它在每一位排序中依赖于一个稳定的排序算法，所以基数排序是稳定的排序算法。
给定n个d位数，其中每个数位有k个可能的取值。那么需要d轮排序，所以基数排序耗时为d(n + k)，而d为常数，所以基数排序复杂度为O(n + k)。
### 2、计数排序
假设n个输入元素中每个都是在0到k区间的整数(k是某个整数)。当k = O(n)时，排序的运行时间为O(n)。
### 3、桶排序
假设输入数据服从均匀分布，平均情况下其时间代价为O(n)。和计数排序类似，计数排序假设数据都是一个小区间内的整数，桶排序则假定输入由一个随机过程产生，该过程将元素均匀、独立地分布在[0,1)区间内。
桶排序将[0,1)区间划分为n个相同大小的子区间，称为桶；然后，将n个数分别放入到各个桶中，因为输入数据是均匀分布的，所以不会出现很多数落在一个桶内的情况。为了得到输出结果，先对每个桶中数进行排序（例如，利用插入排序），然后遍历每个桶，按照次序把各个桶内的元素列出来即可。
不借助变量交换两个数
最后更新于：2022-04-01 16:17:20
文章：[不借助if、switch等语句求两个数较大的一个](http://blog.csdn.net/u013074465/article/details/42684559)
交换两个数在排序算法中用的很多：[冒泡排序中](http://blog.csdn.net/u013074465/article/details/44339187) 、[插入排序中](http://blog.csdn.net/u013074465/article/details/42043665)等等。正常的交换两个数是借助一个变量tmp：
~~~
void Swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}
~~~
在面试题中有这样的题目“不借助第三个变量，交换两个数”
~~~
//A方法
void Swap(int &a, int &b) {
a = a + b;
b = a - b;
a = a - b;
}
~~~
~~~
//B方法
void Swap(int &a, int &b) {
a ^= b; b ^= a; a ^= b;
}
~~~
上述的两种方式中，A方法缺点：中当数a或b较大时 a = a + b会发生越界。
方法B的原理：
~~~
a = a ^ b;
b = a ^ b; //那么 b = a ^ b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a，即将a赋值给了b
a = a ^ b; //那么 a = a ^ b = a ^ (a ^ b) = (a ^ a) ^ b = 0 ^ b = b，即实现了将b赋值为a
~~~
以上两种方法的共有bug：
当a、b指向的是同一个数时，即Swap(a, a)时，会发生错误，将a置为了0。但是a等于b的情况下（即a和b不是指向同一个地址时）是不会错误的。
解决方法：
为Swap函数增加判断语句：当a和b相等的时候不交换。
~~~
//A方法
void test(int &a, int &b) {
if (a != b) {
a = a + b;
b = a - b;
a = a - b;
cout << "OK " << endl;
}
}
//B方法
void Swap(int &a, int &b) {
if (a != b) {
a ^= b;
b ^= a;
a ^= b;
}}
~~~
直接选择排序
最后更新于：2022-04-01 16:17:17
直接选择排序和直接插入排序类似，都将数据分为有序的区域和无序的区域。所不同的是直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后（其实是将找到的最小元素与已排序序列紧邻的元素交换，从而使得已排序序列增大1）。
~~~
void Swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}
void SelectSort(int a[], int size) {
int i;
for (i = 0; i < size; ++i) {
int min_index = i;
int j;
for (j = i + 1; j < size; ++j)
if (a[j] < a[min_index])
min_index = j;
Swap(a[i], a[min_index]);
}
}
~~~
该排序算法用到了交换两个数的函数。参考[这里](http://blog.csdn.net/u013074465/article/details/44342629)查看面试题“不借助其他变量，交换两个数”