C++知识点（三）

KMP算法

KMP主要解决的就是部分匹配时,原始串上的下标不回溯.只移动模式串在上的位置.
主要就是挖掘模式串上的特点:
如果部分匹配已经在模式串上匹配到了j位置,但此时不匹配了,则说明前面j-1个子串是完全匹配上了.此时我们需要找模式串上从后面的第几位开始到串尾,与模式串的开头部分匹配上.
给出Next的公式

$$Next[j]=前j-1个串的对称程度+1$$

看图2的那个表格,这里模式串的首个下标为1,所以当j-1个字符的串完全不对称时,直接将下标指向第一位.至于Next[1]的值应该是默认为0.

在一些博客中可能会是另外一种形式,不过也是可以的,比如

$$f(j)= \begin{cases} max{m} \ \ \ \ P[0,..,m]=P[j-m,...,j],0≤m≤j\\ -1 \ \ \ \ else \end{cases}$$

Next[j]会是另一种形式

int Next[maxn];
//这里采用next[0]=-1
void getNext(string s)
{
    int m = s.length();
    Next[0] = -1;
    int j = 0;
    int k = -1;
    while( j < m) {
        if (k == -1 || s[j] == s[k])
            Next[++j] = ++k; //第j个和第k个相等就再在对称程度上加1
        else
            k = Next[k];// 看第k个对称程度能不能帮上现在的j
    }
}

Next[j]里面记录的就是如果当前失配了,模式串应该跳到那个位置,使得原始串不动,仍能开始匹配.

循环节问题

经典问题 : 给出一个由某个循环节构成的字符串，要你找出最小的循环节，例如 abababab 最小循环节当是 ab ，而类似 abab 也可以成为它的循环节，但并非最短。

在KMP算法的使用中,首要任务就是获取一个字符串的next数组,我们得明白next数组得含义(最好得方法是自己弄个例子),在这里通俗一点讲,next[k]表示,在模式串的k个字符失配了,然后下一次匹配从next[k]开始(next[k]中保存的是该失配字符的前一个字符在前面出现过的最近一次失配的字符后面的一个字符的位置)

next数组为什么可以用来求重复前缀?且求出的重复前缀是最小的呢?
个人认为，next数组在求解的过程中，用到了KMP的思想，当前失配了，就回溯到上一个next，请见 j=next[j] ，先说个结论，如果到位置 i ，如果有 i%(i-next(i))==0 , 那说明字符串开始循环了，并且循环到 i-1 结束，为什么这样呢？

代码

#include "stdafx.h"
#include <iostream>
#include <vector>
#include<stack>
#include<algorithm>
using namespace std;

vector<int> getNext(string p) {
//优化版本
	int n = p.size(), k = -1, j = 0;
	vector<int> next(n, 0);
	next[0] = -1;
	while (j < n - 1) {
		if (k == -1 || p[j] == p[k]) {
			++k; ++j;
			next[j] = (p[j] != p[k]) ? k : next[k];
		}
		else {
			k = next[k];
		}
	}
	return next;
}


vector<int> getNext(string p) {
//未优化版本
	int n = p.size(), k = -1, j = 0;
	vector<int> next(n, 0);
	next[0] = -1;

	while (j < n - 1) {
		if (k == -1 || p[j] == p[k]) {
			++k; ++j;
			next[j] = k;
		}
		else {
			k = next[k];
		}
	}
	return next;

}


int kmp(string s, string p) {
	int m = s.size(), n = p.size(), i = 0, j = 0;
	vector<int> next = getNext(p);
	while (i < m && j < n) {
		if (j == -1 || s[i] == p[j]) {
			++i; ++j;
		}
		else {
			j = next[j];
		}
	}

	return (j == n) ? i - j : -1;
}

int main() {
	cout << kmp("BBC_ABCDAB_ABCDABCDABDE", "ABCDABD") << endl; // Output: 15
}

参考文献:

1. https://blog.csdn.net/hao_zong_yin/article/details/77455285
2. https://www.cnblogs.com/justPassBy/p/4035361.html
3. https://www.bbsmax.com/R/QV5ZjxvZ5y/
4. https://www.cnblogs.com/Philip-Tell-Truth/p/5183264.html

memset

这是C/C++里面的一个初始化函数
目的是将某一块内存中的内容全部设置为指定的值,这个函数通常为新申请的内存做初始化工作.
在C中需要的头文件是C中的
在C++中需要的头文件是C++中的

memset是对字符串的操作

nenset将一段内存空间填入某值
定义函数 void memset(void s,int c,size_t n);
函数说明memset()会将参数s所指的内存区域前n个 子节 以参数c填入,然后返回指向s的指针.在编写程序时,若需要将某一数组作初始化,memset()会相当方便.
返回值 返回指向s的指针
附加说明: 参数c虽声明为int,但必须是unsigned char,所以范围在0到255之间。

int a[10];
memset(a,1,sizeof(a))

注意memset不能用于初始化int数组,这是因为int 由4个字节表示,并且不能得到数组a中整数的期望值。
但我们经常可以看到程序员使用memset将int数组元素设置为0或者-1.

int a[10];
int b[10];
memset(a,0,sizeof(a));
memset(a,-1,sizeof(a));

用整数0初始化是可以的,因为0可以在1字节表示,-1可以表示为所以位中均为1.

常见的问题:

1. 问:为何要用memset置零？memset(&Address,0,sizeof(Address));经常看到这样的用法,其实不用的话,分配数据的时候,剩余的空间也会置零的

2. 问:如下demo是可以的,能把数组中的元素值都设置成字符1

   #include<iostream>
   #include<cstring>
   using namespace std;
   int main(){
   char a[5];
   memset(a,'1',5);
   for(int i=0;i<5;i++){
     cout<<a[i]<<"";
   }
   return 0;
   }

如下程序想把数组中的元素设置成1,却是不可行的

#include<iostream>
#include<cstring>
using namespace std;
int a[5];
memset(a,1,20);\\ 也等价于memset(a,1,sizeof(a))
for(int i=0;i<5;i++){
  cout<<a[i]<<"";
}
return 0;

1. 不想要用for,或是while 循环来初始化int a[5];能做到么？
   答:能做到,但这样是比较麻烦的,memset是最快捷的方法.
   Eg1.

   #include<string.h>
   #include<stdio.h>
   #include<memory.h>
   int main(){
     char buffer[]="Helloword\n";
     printf("Buffer before memset:%s\n",buffer);
     memset(buffer,' * ',strlen(buffer));
     print("Buffer after memset:%s\n",buffer);
     return 0;
   }

Eg2.

int array[5]={1,4,3,5,2};
for(int i=0;i<5;i++){
  cout<<array[i]<<"";
  cout<<endl;
}
输出结果
14352
00000

Eg3

int main(){
int array[5]={1,4,3,5,2};
for(int i=0;i<5;i++){
  cout<<array[i]<<"";  
}
cout<<endl;
memset(array,1,5*sizeof(int));
for(int k=0;k<5;k++){
  cout<<array[k]<<"";
}
cout<<endl;
}

输出结果:
14352
16843009168430091684300916843009

因为memset是以字节为单位就是对array指向的内存的4个字节进行幅值,4个字节合一起就是
00000001000000010000000100000001
就等于16843009168430091684300916843009,就完成了对一个INT元素的赋值了

分治算法

基本思想就是分而治之,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题….直到最后子问题可以简单的直接求解,原问题的解即子问题的合并.这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅里叶变换.

基本思想

将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之.
分支策略:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模较小),则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些问题,然后将各子问题的解合并得到原问题的解.这种算法设计策略叫做分治法

分治法适用的情况

分治法所能解决的问题一般具有以下几个特征:
1)该问题的规模缩小到一定的程度就可以容易地解决
2)该问题可以分解为若干个规模较小地相同问题,即该问题具有最优子结构性质
3)利用该问题分解出地子问题地解可以合并为该问题地解;
4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题.

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

分治法的基本步骤

分治法再每一层递归上都有三个步骤:
step1. 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
step2. 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
step3. 合并:将各个子问题的解合并为原问题的解

分治法的复杂性分析

一个分治法将规模为n的问题分成k各规模为n/m的子问题去解.设分解阈值$n_0$=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merage将k个子问题的解合并为原问题的解用f(n)个单位时间.用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:

$$T(n)=kT(\frac{n}{m})+f(n)$$

通过迭代法求得方程的解:
递归方程及其解只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由n等于m方幂时T(n)的值可以估计T(n)的增长速度。

可适用分治法求解的一些经典问题

1. 二分搜索
2. 大整数乘法
3. Strassen矩阵乘法
4. 棋盘覆盖
5. 合并排序
6. 快速排序
7. 线性时间选择
8. 最接近点对问题
9. 循环赛日程表
10. 汉诺塔

    依据分治法设计程序时的思维过程

    实际就是类似于数学归纳法,找到解决本问题的求解方程公式,然后根据方程公式设计递归程序
11. 一定是先找到最小问题规模时的求解方法
12. 然后考虑随着问题的规模增大时的求解方法
13. 找到求解的递归函数式后(各种规模或因子),设计递归程序即可.

经典示例——大数相乘

$$XY=(A×10^{\frac{n}{2}}+B)(C×10^{\frac{n}{2}}+D)=AC×10^n+(AD+BC)×10^{\frac{n}{2}}+BD$$

注意我们这里取得大数X、是再理想情况下,即X与Y的位数一致,且$n=2^m,m=1,2,3,..,k$

算法分析

1. 首先将X和Y分成A,B,C,D
2. 此时将X和Y的乘积转化为(1)式,把问题转化为求解因式分解的值
   在(1)式中,我们一共需要进行4次n/2的乘法(AC2次,AD、BC各一次)和3次加法,因而该算法的时间复杂度为: $$T(n)=4×T(\frac{n}{2})+\theta(n)$$ 通过master定理可以求得$T(n)=\theta(n^2)$
   但我们再来看看,我们是否可以用加法来换乘法?因为多一个加法操作,也是常数项,对事件复杂度没有影响,如果减少一个乘法则不同.
   (1)式化为: $$XY=AC×10^n+((A-B)(D-C)+AC+BD)×10^{\frac{n}{2}}+BD$$ 现在时间复杂度为$T(n)=3×T(\frac{n}{2})+\theta(n)$,通过master定理求得,$T(n)=O(n^{log_2(3)})$

   #include <iostream>
   #include <string>
   #include <sstream>
   
   using namespace std;
   
   string multi(string A, string B); //计算大整数相乘
   string Plus(string q, string w, string e, string r); //计算大整数相加
   stringstream ss;
   
   int main() {
       string A, B;
   
       while (cin >> A >> B) {
           cout << multi(A, B) << endl;
       }
       return 0;
   }
   
   string multi(string A, string B) {
       int len_A = A.length();
       int len_B = B.length();
       if (len_A == 1) {
           if (len_B == 1) { //最基本的情况：A和B都是一位数，把A、B从string转为int（我这里用的stringstream），然后相乘后转回为string型return回去。
               ss << A;
               int a;
               ss >> a;
               ss.clear();
               ss << B;
               int b;
               ss >> b;
               ss.clear();
               ss << b*a;
               string str_out;
               ss >> str_out;
               ss.clear();
               return str_out;
           }
           else {  //A是个位数，B不是的情况下，按照分治的思想把B分开分别与A相乘。
               string B1, B2;
               B1 = B.substr(0, len_B / 2);
               B2 = B.substr(len_B / 2);
               string AB1 = multi(A, B1);
               string AB2 = multi(A, B2);
               if (AB2.length() > B2.length()) {
                   string str = AB2.substr(0, 1);
                   ss << str;
                   int ab2;
                   ss >> ab2;
                   ss.clear();
                   ss << AB1;
                   int ab1;
                   ss >> ab1;
                   ss.clear();
                   ss << ab1 + ab2;
                   ss >> AB1;
                   ss.clear();
                   return AB1 + AB2.substr(1);
               }
               else
                   return AB1 + AB2;
           }
       }
       else {
           if (len_B == 1) {  //B是个位数，A不是的情况与上述A是个位数B不是的情况相同。
               string A1, A2;
               A1 = A.substr(0, len_A / 2);
               A2 = A.substr(len_A / 2);
               string A1B = multi(A1, B);
               string A2B = multi(A2, B);
               if (A2B.length() > A2.length()) {
                   string str = A2B.substr(0, 1);
                   ss << str;
                   int a2b;
                   ss >> a2b;
                   ss.clear();
                   ss << A1B;
                   int a1b;
                   ss >> a1b;
                   ss.clear();
                   ss << a1b + a2b;
                   ss >> A1B;
                   ss.clear();
                   return A1B + A2B.substr(1);
               }
               else {
                   return A1B + A2B;
               }
           }
           else {  //A和B都不是个位数，就按照上述方法分治就可以了，只是为了最后相加的时候方便，把返回的四个部分都用0凑成了位数相同的。
               string A1, A2, B1, B2;
               A1 = A.substr(0, len_A / 2);
               A2 = A.substr(len_A / 2);
               B1 = B.substr(0, len_B / 2);
               B2 = B.substr(len_B / 2);
               string part1_ = multi(A1, B1);
               string part1_0(A2.length()+B2.length(), '0');
               part1_ = part1_ + part1_0;
               string part2_ = multi(A2, B2);
               string part2_00(part1_.length() - part2_.length(), '0');
               part2_ = part2_00 + part2_;
               string part3_ = multi(A1, B2);
               string part3_0(A2.length(), '0');
               part3_ = part3_ + part3_0;
               string part3_00(part1_.length() - part3_.length(), '0');
               part3_ = part3_00 + part3_;
               string part4_ = multi(A2, B1);
               string part4_0(B2.length(), '0');
               part4_ = part4_ + part4_0;
               string part4_00(part1_.length() - part4_.length(), '0');
               part4_ = part4_00 + part4_;
               return Plus(part1_, part2_, part3_, part4_);
           }
       }
   }
   
   string Plus(string q, string w, string e, string r) { //大整数相加
       int len_q = q.length();
       string y, out;
       int a, b, c, d;
       for (int i = 1; i <= len_q; i++) {
           ss << q.substr(len_q - i, 1);
           ss >> a;
           ss.clear();
           ss << w.substr(len_q - i, 1);
           ss >> b;
           ss.clear();
           ss << e.substr(len_q - i, 1);
           ss >> c;
           ss.clear();
           ss << r.substr(len_q - i, 1);
           ss >> d;
           ss.clear();
           ss << a + b + c + d;
           ss >> y;
           ss.clear();
           if (i == 1)
               out = y;
           else if (out.length() > i - 1) {
               ss << out.substr(0, 1);
               ss >> a;
               ss.clear();
               ss << y;
               ss >> b;
               ss.clear();
               ss << a + b;
               ss >> y;
               ss.clear();
               out = y + out.substr(1);
           }
           else {
               out = y + out;
           }
       }
       return out;
   }

经典示例——棋盘覆盖

就是用一个特殊方块和4种三个方块构成的L型骨牌来覆盖$2^k×2^k$的棋盘,注意必须是$2^k×2^k$,否则若是一个奇数×奇数的就不能保证一个L型骨块再一个子棋盘中,而且奇数×奇数也不方便二分.(主要还是前面一个理由,分治法不一定必须要是二分的).

input sample

2
2
0 0
8
2 2

output sample

CASE:1
0  1  
1  1  
CASE:2
3  3  4  4  8  8  9  9  
3  2  2  4  8  7  7  9  
5  2  0  6  10 10 7  11
5  5  6  6  1  10 11 11
13 13 14 1  1  18 19 19
13 12 14 14 18 18 17 19
15 12 12 16 20 17 17 21
15 15 16 16 20 20 21 21

用分治法处理:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 10000
int board[N][N];//棋盘的布局
int team;//用方块覆盖，相当于分组
int loc;//key(x,y)的方位（返回值为1、2、3、4分别指1、2、3、4象限）
int witk(int m,int x,int y,int a,int b){//where is the key(x,y)?  m为棋盘的边长，x，y为黑点的坐标，a，b为棋盘左上角的坐标，
    int n;
    n=m/2;
    if(x<n+a&&y>=n+b)
        return 1;
    else if(x<n+a&&y<n+b)
        return 2;
    else if(x>=n+a&&y<n+b)
        return 3;
    else if(x>=n+a&&y>=n+b)
        return 4;
}
void cover(int m,int a,int b){
    int i;
    int j;
    int x,y;
    int n;
    if(m==2){//若m==2，直接覆盖
        for(i=a;i<m+a;i++)
            for(j=b;j<m+b;j++)
                if(board[i][j]==-1)
                    board[i][j]=team;
        team++;
    }
    else{//m>2
        for(i=a;i<m+a;i++){//找出黑点的位置x，y
            for(j=b;j<m+b;j++)
                if(board[i][j]!=-1){
                    x=i;
                    y=j;
                }
        }
        n=m/2;
        loc=witk(m,x,y,a,b);//where is the key(x,y)?
        for(i=a+n-1;i<=a+n;i++)//遍历棋盘中部四个格，判断其方位，若不和黑点在同一个方位则将其覆盖；
            for(j=b+n-1;j<=b+n;j++)
                if(witk(m,i,j,a,b)!=loc)
                    board[i][j]=team;
        team++;
        cover(n,a,b);//覆盖四个分区域，递归调用
        cover(n,a,b+n);
        cover(n,a+n,b);
        cover(n,a+n,b+n);
    }
}
int main(){
    int i,j,k;
    int n,m;
    int x,y;
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    scanf("%d",&n);
    for(i=0;i<n;i++){
        team=1;
        memset(board,-1,sizeof(board));//将棋盘全部置为-1
        scanf("%d%d%d",&m,&x,&y);
        board[x+1][y+1]=0;
        cover(m,1,1);
        printf("CASE:%d\n",i+1);
        for(j=1;j<=m;j++){
            for(k=1;k<=m;k++)
                printf("%-3d",board[j][k]);
            printf("\n");
        }
    }
    return 0;
}

55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

一开始的时候采用的是回溯法,貌似有个测试样例时间超了,确实回溯法容易超时和超内存.细想了一下如果这里采用回溯的方法的话,大致时间复杂度是$O(n^2)$.况且这里要求的只是bool,还没有要求具体的路径.
一定要注意,这里的信息是最大jump,也就是说哪怕没有跳到最后一个数据,而是超过最后一个数据仍在后续是有可能达到最后一个数据的.
所以开始统计每个位置能达到的最大的位置,如果有位置x能跳到超过数组大小的位置则必定能达到最后一个位置,但是有一种可能是达不到这个x的位置,所以x有变成了我们的目标位置以此迭代进行下去.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==0){
            return true;
        }
        vector<int> path;
        for(int i=0;i<nums.size();i++){
            path.push_back(nums[i]+i);
        }

        int target=nums.size()-1;
        for(int i=path.size()-2;i>=0;i--){
            if(path[i]>=target){
                target=i;
            }
        }
        if(target==0)
        {
            return true;
        }
        else{
            return false;
        }    
    }
};

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool cmp(Interval a,Interval b){
        return a.start<b.start;
    }
    vector<Interval> merge(vector<Interval>& ins) {
    vector<Interval> res;
    if (ins.empty())
        return res;

    sort(ins,cmp);

    res.push_back(ins[0]);
    for (int i = 1; i < ins.size(); i++) {
        if (res.back().end < ins[i].start) res.push_back(ins[i]);
        else
            res.back().end = max(res.back().end, ins[i].end);
    }
    return res;
}
};

一开始的想法就是先排序然后再找合并,但是不敢写,有点怕爆内存,下次要敢想敢做!!!!!

---

P.S.
vector.empty() :返回bool,反馈是否为空

vector.back():表示数组中最后一个元素.