精华内容
下载资源
问答
  • 前缀和是指某序列的前n项和,可以把它理解为数学上的数列的前n项和(对于维数组的前缀和) ** ** 前缀和算法有什么好处? 先来了解这样个问题: 输入个长度为n的整数序列。接下来再输入m个询问,每个询问...

    1、前缀和

    前缀和是指某序列的前n项和,可以把它理解为数学上的数列的前n项和,而差分可以看成前缀和的逆运算。合理的使用前缀和与差分,可以将某些复杂的问题简单化。


    加粗样式

    2、前缀和算法有什么好处?

    先来了解这样一个问题:

    输入一个长度为n的整数序列。接下来再输入m个询问,每个询问输入一对l, r。对于每个询问,输出原序列中从第l个数到第r个数的和。

    我们很容易想出暴力解法,遍历区间求和。

    代码如下:

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    while(m--)
    {
        int l,r;
        int sum=0;
        scanf("%d%d",&l,&r);
        for(int i=l;i<=r;i++)
        { 
            sum+=a[i];
        }
        printf("%d\n",sum);
    }
    

    这样的时间复杂度为O(n*m),如果nm的数据量稍微大一点就有可能超时,而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(n+m),大大提高了运算效率。

    具体做法:

    首先做一个预处理,定义一个sum[]数组,sum[i]代表a数组中前i个数的和。

    求前缀和运算:

    const int N=1e5+10;
    int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
    for(int i=1;i<=n;i++)
    { 
        sum[i]=sum[i-1]+a[i];   
    }
    

    然后查询操作:

     scanf("%d%d",&l,&r);
     printf("%d\n", sum[r]-sum[l-1]);
    

    对于每次查询,只需执行sum[r]-sum[l-1] ,时间复杂度为O(1)

    原理

    sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r];
    sum[l-1]=a[1]+a[2]+a[3]+a[l-1];
    sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];

    图解
    在这里插入图片描述
    这样,对于每个询问,只需要执行 sum[r]-sum[l-1]。输出原序列中从第l个数到第r个数的和的时间复杂度变成了O(1)

    我们把它叫做一维前缀和

    总结:

    练习一道题目
    输入一个长度为n的整数序列。
    接下来再输入m个询问,每个询问输入一对l, r。
    对于每个询问,输出原序列中从第l个数到第r个数的和。
    输入格式
    第一行包含两个整数n和m。
    第二行包含n个整数,表示整数数列。
    接下来m行,每行包含两个整数l和r,表示一个询问的区间范围。
    输出格式
    共m行,每行输出一个询问的结果。
    数据范围
    1≤l≤r≤n,
    1≤n,m≤100000,
    −1000≤数列中元素的值≤1000
    输入样例:
    5 3
    2 1 3 6 4
    1 2
    1 3
    2 4
    输出样例:
    3
    6
    10
    代码:

    #include <iostream>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int a[N], s[N];
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
        for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化
    
        while (m -- )
        {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", s[r] - s[l - 1]); // 区间和的计算
        }
    
        return 0;
    }
    

    3、二维前缀和

    如果数组变成了二维数组怎么办呢?

    先给出问题:

    输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

    同一维前缀和一样,我们先来定义一个二维数组s[][], s[i][j]表示二维数组中,左上角(1,1)到右下角( i,j )所包围的矩阵元素的和。接下来推导二维前缀和的公式。

    先看一张图:

    紫色面积是指(1,1)左上角到(i,j-1)右下角的矩形面积, 绿色面积是指(1,1)左上角到(i-1, j )右下角的矩形面积。每一个颜色的矩形面积都代表了它所包围元素的和。
    在这里插入图片描述
    从图中我们很容易看出,整个外围蓝色矩形面积s[i][j] = 绿色面积s[i-1][j] + 紫色面积s[i][j-1] - 重复加的红色的面积s[i-1][j-1]+小方块的面积a[i][j];

    因此得出二维前缀和预处理公式

    s[i] [j] = s[i-1][j] + s[i][j-1 ] + a[i] [j] - s[i-1][ j-1]

    接下来回归问题去求以(x1,y1)为左上角和以(x2,y2)为右下角的矩阵的元素的和。

    如图:

    紫色面积是指 ( 1,1 )左上角到(x1-1,y2)右下角的矩形面积 ,黄色面积是指(1,1)左上角到(x2,y1-1)右下角的矩形面积;

    不难推出:
    在这里插入图片描述

    绿色矩形的面积 = 整个外围面积s[x2, y2] - 黄色面积s[x2, y1 - 1] - 紫色面积s[x1 - 1, y2] + 重复减去的红色面积 s[x1 - 1, y1 - 1]

    因此二维前缀和的结论为:

    (x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
    s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]

    总结:

    练习一道完整题目:
    输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。

    对于每个询问输出子矩阵中所有数的和。

    输入格式
    第一行包含三个整数n,m,q。

    接下来n行,每行包含m个整数,表示整数矩阵。

    接下来q行,每行包含四个整数x1, y1, x2, y2,表示一组询问。

    输出格式
    共q行,每行输出一个询问的结果。

    数据范围
    1≤n,m≤1000,
    1≤q≤200000,
    1≤x1≤x2≤n,
    1≤y1≤y2≤m,
    −1000≤矩阵内元素的值≤1000
    输入样例:
    3 4 3
    1 7 2 4
    3 6 2 8
    2 1 2 3
    1 1 2 2
    2 1 3 4
    1 3 3 4
    输出样例:
    17
    27
    21

    代码:

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=1010;
    int a[N][N],s[N][N];
    int main()
    {
        int n,m,q;
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
           scanf("%d",&a[i][j]);
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
            s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
        while(q--)
        {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
        }
        return 0;
    }
    

    4、差分


    在这里插入图片描述

    5、一维差分

    类似于数学中的求导和积分,差分可以看成前缀和的逆运算。

    差分数组:

    首先给定一个原数组aa[1], a[2], a[3],,,,,, a[n];

    然后我们构造一个数组bb[1] ,b[2] , b[3],,,,,, b[i];

    使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]

    也就是说,a数组是b数组的前缀和数组,反过来我们把b数组叫做a数组的差分数组。换句话说,每一个a[i]都是b数组中从头开始的一段区间和。

    考虑如何构造差分b数组?

    最为直接的方法

    如下:

    a[0 ]= 0;

    b[1] = a[1] - a[0];

    b[2] = a[2] - a[1];

    b[3] =a [3] - a[2];

    ........

    b[n] = a[n] - a[n-1];

    图示:

    我们只要有b数组,通过前缀和运算,就可以在O(n) 的时间内得到a数组 。

    知道了差分数组有什么用呢? 别着急,慢慢往下看。

    话说有这么一个问题:

    给定区间[l ,r ],让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c;

    暴力做法是for循环lr区间,时间复杂度O(n),如果我们需要对原数组执行m次这样的操作,时间复杂度就会变成O(n*m)。有没有更高效的做法吗? 考虑差分做法,(差分数组派上用场了)。

    始终要记得,a数组是b数组的前缀和数组,比如对b数组的b[i]的修改,会影响到a数组中从a[i]及往后的每一个数。

    首先让差分b数组中的 b[l] + c ,通过前缀和运算,a数组变成 a[l] + c ,a[l+1] + c,,,,,, a[n] + c;

    然后我们打个补丁,b[r+1] - c, 通过前缀和运算,a数组变成 a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c;

    为啥还要打个补丁?

    我们画个图理解一下这个公式的由来:
    在这里插入图片描述
    b[l] + c,效果使得a数组中 a[l]及以后的数都加上了c(红色部分),但我们只要求lr区间加上c, 因此还需要执行 b[r+1] - c,让a数组中a[r+1]及往后的区间再减去c(绿色部分),这样对于a[r] 以后区间的数相当于没有发生改变。

    因此我们得出一维差分结论:给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组bb[l] + = c, b[r+1] - = c。时间复杂度为O(1), 大大提高了效率。

    总结:
    在这里插入图片描述

    题目练习: AcWing 797. 差分

    输入一个长度为n的整数序列。
    接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。
    请你输出进行完所有操作后的序列。
    输入格式
    第一行包含两个整数n和m。
    第二行包含n个整数,表示整数序列。
    接下来m行,每行包含三个整数l,r,c,表示一个操作。
    输出格式
    共一行,包含n个整数,表示最终序列。
    数据范围
    1≤n,m≤100000,
    1≤l≤r≤n,
    −1000≤c≤1000,
    −1000≤整数序列中元素的值≤1000
    输入样例:
    6 3
    1 2 2 1 2 1
    1 3 1
    3 5 1
    1 6 1
    输出样例:
    3 4 5 3 4 2
    AC代码

    //差分 时间复杂度 o(m)
    #include<iostream>
    using namespace std;
    const int N=1e5+10;
    int a[N],b[N]; 
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) 
        {
            scanf("%d",&a[i]);
            b[i]=a[i]-a[i-1];      //构建差分数组
        }
        int l,r,c;
        while(m--)
        {
            scanf("%d%d%d",&l,&r,&c);
            b[l]+=c;     //表示将序列中[l, r]之间的每个数加上c
            b[r+1]-=c;
        }
        for(int i=1;i<=n;i++) 
        {
            b[i]+=b[i-1];  //求前缀和运算
            printf("%d ",b[i]);
        }
        return 0;
    }
    

    6、二维差分

    如果扩展到二维,我们需要让二维数组被选中的子矩阵中的每个元素的值加上c,是否也可以达到O(1)的时间复杂度。答案是可以的,考虑二维差分

    a[][]数组是b[][]数组的前缀和数组,那么b[][]a[][]的差分数组

    原数组: a[i][j]

    我们去构造差分数组: b[i][j]

    使得a数组中a[i][j]b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和。

    如何构造b数组呢?

    其实关于差分数组,我们并不用考虑其构造方法,因为我们使用差分操作在对原数组进行修改的过程中,实际上就可以构造出差分数组。

    同一维差分,我们构造二维差分数组目的是为了 让原二维数组a中所选中子矩阵中的每一个元素加上c的操作,可以由O(n*n)的时间复杂度优化成O(1)

    已知原数组a中被选中的子矩阵为 以(x1,y1)为左上角,以(x2,y2)为右下角所围成的矩形区域;

    始终要记得,a数组是b数组的前缀和数组,比如对b数组的b[i][j]的修改,会影响到a数组中从a[i][j]及往后的每一个数。

    假定我们已经构造好了b数组,类比一维差分,我们执行以下操作
    来使被选中的子矩阵中的每个元素的值加上c

    b[x1][y1] + = c;

    b[x1,][y2+1] - = c;

    b[x2+1][y1] - = c;

    b[x2+1][y2+1] + = c;

    每次对b数组执行以上操作,等价于:

    for(int i=x1;i<=x2;i++)
      for(int j=y1;j<=y2;j++)
        a[i][j]+=c;
    

    我们画个图去理解一下这个过程:

    b[x1][ y1 ] +=c ; 对应图1 ,让整个a数组中蓝色矩形面积的元素都加上了c
    b[x1,][y2+1]-=c ; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c,使其内元素不发生改变。
    b[x2+1][y1]- =c ; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c,使其内元素不发生改变。
    b[x2+1][y2+1]+=c; 对应图4,让整个a数组中红色矩形面积的元素再加上c,红色内的相当于被减了两次,再加上一次c,才能使其恢复。
    在这里插入图片描述
    我们将上述操作封装成一个插入函数:

    void insert(int x1,int y1,int x2,int y2,int c)
    {     //对b数组执行插入操作,等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=c;
    }
    

    我们可以先假想a数组为空,那么b数组一开始也为空,但是实际上a数组并不为空,因此我们每次让以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 c=a[i][j],等价于原数组a(i,j)(i,j)范围内 加上了 a[i][j] ,因此执行n*m次插入操作,就成功构建了差分b数组.

    这叫做曲线救国。

    代码如下:

      for(int i=1;i<=n;i++)
      {
          for(int j=1;j<=m;j++)
          {
              insert(i,j,i,j,a[i][j]);    //构建差分数组
          }
      }
    

    当然关于二维差分操作也有直接的构造方法,公式如下:

    b[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]

    二维差分数组的构造同一维差分思维相同,因次在这里就不再展开叙述了。

    总结:

    在这里插入图片描述

    题目练习: AcWing 798. 差分矩阵
    输入一个n行m列的整数矩阵,再输入q个操作,每个操作包含五个整数x1, y1, x2, y2, c,其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。
    每个操作都要将选中的子矩阵中的每个元素的值加上c。
    请你将进行完所有操作后的矩阵输出。
    输入格式
    第一行包含整数n,m,q。
    接下来n行,每行包含m个整数,表示整数矩阵。
    接下来q行,每行包含5个整数x1, y1, x2, y2, c,表示一个操作。
    输出格式
    共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。
    数据范围
    1≤n,m≤1000,
    1≤q≤100000,
    1≤x1≤x2≤n,
    1≤y1≤y2≤m,
    −1000≤c≤1000,
    −1000≤矩阵内元素的值≤1000
    输入样例:
    3 4 3
    1 2 2 1
    3 2 2 1
    1 1 1 1
    1 1 2 2 1
    1 3 2 3 2
    3 1 3 4 1
    输出样例:
    2 3 4 1
    4 3 4 1
    2 2 2 2
    AC代码:

    include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=1e3+10;
    int a[N][N],b[N][N];
    void insert(int x1,int y1,int x2,int y2,int c)
    {
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=c;
    }
    int main()
    {
      int n,m,q;
      cin>>n>>m>>q;  
      for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
        cin>>a[i][j];
      for(int i=1;i<=n;i++)
      {
          for(int j=1;j<=m;j++)
          {
              insert(i,j,i,j,a[i][j]);    //构建差分数组
          }
      }
      while(q--)
      {
          int x1,y1,x2,y2,c;
          cin>>x1>>y1>>x2>>y2>>c;
          insert(x1,y1,x2,y2,c);
      }
      for(int i=1;i<=n;i++)
      {
          for(int j=1;j<=m;j++)
          {
              b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
          }
      }
      for(int i=1;i<=n;i++)
      {
          for(int j=1;j<=m;j++)
          {
              printf("%d ",b[i][j]);
          }
          printf("\n");
      }
      return 0;
    }
    

    如果我的文章对你有帮助,请点点关注,你的关注是对我创作的最大支持。
    在这里插入图片描述

    如果你对【前缀和与差分】算法还有疑问的话,欢迎加入我们,一起交流学习!!!

    在这里插入图片描述

    展开全文
  • 注:下面前缀有多重意思的,我都是分开写的,所以你看到有重复的,并不是我搞错了! 要看使用示例,去看该百度文库中的内容:https://wenku.baidu.com/view/02f225482b160b4e767fcfb6 序号 “ - ”表

    说明

    个人拙见:单词基本上都是由前缀词根后缀然后结合词性组成,所以,只要花大量时间死记硬背的吧前缀词根后缀都背熟以后,结合词性翻译或使用该单词,效率比直接被单词或 通过文章背单词效率高很多。

    完整前缀(138个)

    注:下面一个前缀有多重意思的,我都是分开写的,所以你看到有重复的,并不是我搞错了!
    要看使用示例,去看该百度文库中的内容:史上最全英语前缀大全

    序号“ - ”表示单词位置解释
    1a-加在单词或词根前面, 表示 不,无,非
    2a-加在单词前, 表示 在…, …的
    3ab-, abs-加在词根前,表示 相反,变坏,离去 等
    4ab-, ac-, ad-, af-, ag-, an-, ap-, ar-, as-, at-等加在同辅音字母词根前,表示 一再 等加强意
    5ad-加在单词或词根前, 表示 做…, 加强…
    6amphi-表示 两个、两种
    7an-在词根前, 表示 不,无
    8ana-表示 错误,在旁边,分开
    9ante-表示 前面,先
    10anti-表示 反对,相反
    11apo-表示 离开,远离
    12auto-表示 自动、自已
    13be-构成动词,表示 使…成为
    14be-构成一些介词
    15bene-表示 善, 好
    16bi-表示 二个, 两
    17by-表示 在旁边,副的
    18cata-表示 向下,相反,离开
    19circum-表示 环绕,周围
    20co-表示 共同 ,通常放元音词根前
    21col-, cor-在同辅音词根前, 表示 共同
    22com-, con-表示 共同
    23contra-表示 反对,相反
    24counter-表示 反对,相反
    25de-表示 去掉,变坏,离开,变慢,向下 等
    26de-表示 使…成为, 加强 等
    27deca-表示 十
    28deci-表示 十分之一
    29demi-表示 半
    30di-表示 二个,双
    31di-表示 使…变成,分开,离开
    32dia-表示 穿过,二者之间
    33dif-和辅音重复表示 不,否定,分开
    34dis-表示 不,消失掉
    35dis-表示 分开,分离
    36dys-表示 坏,不良
    37e-, ef-表示 出,出来,
    38em-, en-表示 进入… 之中,包围
    39em-,en-表示 使… 进入状态
    40endo-表示 内部
    41epi-表示 在…上,在…周围,在…后面
    42eu-表示 好,优秀
    43ex-表示 出,出去
    44ex-表示 前面的,前任的
    45exo-表示 外部的,外面
    46extra-表示 以外的,超过的
    47fore-表示 前面,预先
    48hecto-表示 百,许多
    49hemi-表示 半
    50hepta-表示 七
    51hetero-表示 异类,异种
    52hexa-表示 六
    53holo-表示 全部
    54homo-表示 同类的
    55hyper-表示 超过,太多
    56hypo-表示 下面,次等
    57il-, ir-辅音重复表示 不,无
    58il-,ir-表示 使…成为,进入
    59im-, in-表示 不,无,非
    60im-,in-表示 向内,进入
    61inter-表示 在… 之间,相互
    62intra-表示 在内,内部
    63intro-表示 向内,入内
    64iso-表示 等, 同
    65kilo-表示 一千
    66macro-表示 宏传, 大
    67mal-; male表示 坏,恶
    68meta-表示 超过, 改变
    69micro-表示 微,小
    70milli-表示 千,千分之一
    71mini-表示 小
    72mis-表示 错误,坏
    73mono-表示 单个,一个
    74mono-表示 单个,一个
    75neo-表示 新的
    76non-表示 不,非
    77ob-表示 逆,倒,加强意义
    78octa-表示 八 ; 亦作octo
    79omni-表示 全部,到处
    80out-示 超过,过度
    81out-表示 出去,过时
    82over-表示 过度,过份
    83over-表示 翻转
    84over-表示 在… 之上
    85paleo-表示 古,旧
    86pan-表示 广泛的
    87para-表示 半,类似,辅助
    88para-表示 旁边
    89para-表示 降落伞
    90pen-表示 近似,差不多
    91penta-表示 五
    92per-表示 贯穿,自始至终
    93per-表示 假,坏
    94peri-表示 周围,靠近
    95poly-表示 多
    96post-表示 在后面
    97post-表示 邮件,邮政
    98pre-表示 …前的,预先
    99pro-表示 赞同,亲…
    100pro-表示 向前,在前
    101pro-表示 很多…
    102proto-表示 原始…
    103pseudo-表示 假,伪
    104quadri-,quadru-表示 四
    105quasi-表示 类似,准
    106re-表示 向后,相反
    107re-表示 一再,重新
    108retro-表示 向后,倒退
    109se-表示 分开,离开,区别开
    110semi-表示 半
    111sept-,septi-表示 七
    112sex-, sexi-表示 六
    113step-表示 后,继或前夫(妻)所生
    114stereo-表示 立体
    115sub-表示 在下面,次一等,副手
    116sub-表示 接近,靠近
    117suc-, suf-, sup-, sur-等辅音重复表示 在…下面
    118super-表示 在…上面
    119super-表示 超级,超过,过度
    120supra-表示 超…
    121sur-辅音不重复表示 超过,在上面
    122sus-表示 在… 下面
    123sym-, syn-表示 共同,相同
    124tetra-表示 四
    125trans-表示 横过,越过
    126trans-表示 变换,改变’;转移
    127tri-表示 三
    128twi-表示 二、两
    129ultra-表示 极端
    130ultra-表示 超出,超过
    131un-表示 不,无,非,没有
    132un-表示 打开,解开,弄出
    133under-表示 在…下,在…之内
    134under-表示 不足,不够
    135under-表示 副手 3
    136uni-表示 一个、单一
    137vice-表示 副
    138with-表示 向后,相反

    常用前缀

    常用个屁,全部前缀也不过才138个,138个前缀都想摸鱼,怎么记成千上万个单词?

    展开全文
  • 、示例 示例 1: 输入: ["flower","flow...令最长公共前缀 ans 的值为第个字符串,进行初始化; 遍历后面的字符串,依次将其与 ans 进行比较,两两找出公共前缀,最终结果即为最长公共前缀; 如果查找过程中出现了 an

    一、示例

    示例 1:

    输入: ["flower","flow","flight"]
    输出: "fl"
    

    示例 2:

    输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀。
    

    二、说明

    所有输入只包含小写字母 a-z 。

    三、解题思路

    1. 当字符串数组长度为 0 时则公共前缀为空,直接返回;
    2. 令最长公共前缀 ans 的值为第一个字符串,进行初始化;
    3. 遍历后面的字符串,依次将其与 ans 进行比较,两两找出公共前缀,最终结果即为最长公共前缀;
    4. 如果查找过程中出现了 ans 为空的情况,则公共前缀不存在直接返回

    时间复杂度:O(n^2)

    四、Demo

    class Solution {
        public static void main(String[] args) {
            String[] strs = new String[]{"flower", "flow", "flight"};
            System.out.println(Solution.longestCommonPrefix(strs));
        }
    
        public static String longestCommonPrefix(String[] strs) {
            // 判断是否有空字符串
            if (strs.length == 0) {
                return "";
            }
            String ans = strs[0];
            for (int i = 1; i < strs.length; i++) {
                int j = 0;
                for (; j < ans.length() && j < strs[i].length(); j++) {
                    if (ans.charAt(j) != strs[i].charAt(j)) {
                        break;
                    }
                }
                ans = ans.substring(0, j);
                // 判断共同前缀是否为空
                if (ans.equals("")) {
                    return ans;
                }
            }
            return ans;
        }
    }
    

    五、图解

    在这里插入图片描述

    展开全文
  • 维(差分+前缀和)应用

    千次阅读 2020-04-18 09:47:57
    为了抵御攻击,地球人派出了 A × B × C 艘战舰,在太空中排成个 A 层 B 行 C 列的立方体。其中,第i 层第 j 行第 k 列的战舰(记为战舰 (i, j, k))的生命值为 d(i, j, k)。三体人将会对地球发起 m 轮...

    Description:三体攻击

    三体人将对地球发起攻击。
    为了抵御攻击,地球人派出了 A × B × C 艘战舰,在太空中排成一个 A 层 B 行 C 列的立方体。其中,第i 层第 j 行第 k 列的战舰(记为战舰 (i, j, k))的生命值为 d(i, j, k)。三体人将会对地球发起 m 轮“立方体攻击”,每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。
    具体地,第 t 轮攻击用 7 个参数lat, rat, lbt, rbt, lct, rct, ht 描述;所有满足
    i ∈ [lat, rat],j ∈ [lbt, rbt],k ∈ [lct, rct] 的战舰 (i, j, k) 会受到 ht的伤害。
    如果一个战舰累计受到的总伤害超过其防御力,那么这个战舰会爆炸。
    地球指挥官希望你能告诉他,第一艘爆炸的战舰是在哪一轮攻击后爆炸的。

    思路1:暴力求解

    暴力求解的方法是依次进行每一轮攻击,然后更新攻击范围内的战舰的生命值,当第t轮某一个战舰的血量小于0,那么直接返回 t.

    思路2:二分+差分+前缀和

    利用二分,第一次连续攻击m/2轮,然后判断战舰的生命值,如果此时没有战舰爆炸,那么再往后攻击m/4轮;如果此时有战舰爆炸,那么往前恢复m/4轮。不断二分,直到找到是在第几轮攻击时导致战舰爆炸。
    那么怎么实现连续攻击m/2轮?
    利用差分数组,再求前缀和

    一、前缀和的概念:

    例如,给出一组数 arr[ 1 , 2 , 3 , 4 , 5 ]
    其前缀和 Sn[ 1, 3 , 6 , 10 , 15 ]
    即 Sn[i] = Sn[i-1] + arr[i];

    二、前缀和的特点:

    1. O(N)的时间维护
      例如,arr[2] += 3;
      则Sn[ 1, 3 , 6+3 , 10+3 , 15+3 ]
    2. O(1)的时间获取区间和
      例如,求在 [2,4] 的区间内数值和
      即 Sn[4] - Sn[1] = 15 - 3 = 12

    三、一维差分数组+前缀和:

    在这里插入图片描述

    四、二维差分数组+前缀和:
    在这里插入图片描述
    五、三维差分数组+前缀和:

    1、三维差分数组
    在这里插入图片描述
    给定三个角的坐标la , ra , lb , rb , lc , rc和攻击力h
    正面四个
    arr[lc][lb][la] += h;
    arr[rc+1][lb][la] -= h;
    arr[lc][lb][ra+1] -= h;
    arr[rc+1][lb][ra+1] += h;
    左面补两个
    arr[lc][rb+1][la] -= h;
    arr[lc][rb+1][ra+1] += h;
    上面再补两个
    arr[rc+1][rb+1][la] += h;
    arr[rc+1][rb+1][ra+1] -= h;
    2、三维前缀和
    在这里插入图片描述
    画的很乱,建议各位自己试着画一画。
    arr[i][j][k] += arr[i][j-1][k]; //后方
    arr[i][j][k] += arr[i-1][j][k];//左侧
    arr[i][j][k] += arr[i][j][k-1]; //下方
    arr[i][j][k] -= arr[i-1][j-1][k]; //左后
    arr[i][j][k] -= arr[i-1][j][k-1]; //左下
    arr[i][j][k] -= arr[i][j-1][k-1]; //后下
    arr[i][j][k] += arr[i-1][j-1][k-1]; //左后下

    六、算法实现

    1. 暴力求解
        private static int[] arr;
        private static int[][] attacks;
        private static int A,B,C,m;
        public static void main(String[] args) {
            Scanner cin = new Scanner(System.in);
            A = cin.nextInt();
            B = cin.nextInt();
            C = cin.nextInt();
            m = cin.nextInt();
            arr = new int[(A+1)*(B+1)*(C+1)];
            attacks = new int[m+1][7];
            //初始化战舰生命值
            for (int i = 1;i < A+1;i++){
                for (int j = 1;j < B+1;j++){
                    for (int k = 1;k < C+1;k++){
                        arr[getIndex(i,j,k)] = cin.nextInt();
                    }
                }
            }
    
            //执行攻击
            for (int k = 1; k < m+1; k++) {
                for (int m = 0;m < 7;m++) //读入攻击信息。
                    attacks[k][m] = cin.nextInt();
    
                for (int i = attacks[k][0];i <= attacks[k][1];i++){
                    for (int j = attacks[k][2]; j <= attacks[k][3]; j++) {
                        for (int l = attacks[k][4]; l <= attacks[k][5]; l++) {
                            arr[getIndex(i,j,l)] -= attacks[k][6];
                            if (arr[getIndex(i,j,l)] < 0) {
                                System.out.println();
                                System.out.println(k);
                                return;
                            }
                        }
                    }
                }
            }
    
        }
    
        static int getIndex(int i, int j, int k){
            return (((i-1)*(B+1)+(j-1))*(C+1)+k);
        }
    
    1. 二分+差分+前缀和
    private static int A, B, C, a, b, c, m;
        private static int[][] attack;//攻击
        private static int[] diff;//差分数组
    
        public static void main(String[] args) {
            Scanner cin = new Scanner(System.in);
            A = cin.nextInt();
            B = cin.nextInt();
            C = cin.nextInt();
            m = cin.nextInt();
            a = A + 1;
            b = B + 1;
            c = C + 1;
            attack = new int[m + 1][7];//m次攻击
            diff = new int[a * b * c];//差分数组(也是战舰生命值数组)
    
            cin.nextLine();//吃掉换行符
            //战舰生命值初始化(相当于给战舰回血)
            for (int i = 1; i < a; i++) {
                for (int j = 1; j < b; j++) {
                    for (int k = 1; k < c; k++) {
                        op(i, i, j, j, k, k, cin.nextInt());
                    }
                }
            }
    
            cin.nextLine();
            //输入每轮攻击范围和强度
            for (int i = 1; i <= m; i++) {
                for (int j = 0; j < 7; j++) {
                    attack[i][j] = cin.nextInt();
                }
                cin.nextLine();
            }
    
            //二分攻击
            int l = 1, r = m, mid, lastMid = 0;
            while (l < r) {
                mid = (l + r) >> 1;
                if (mid > lastMid) {//说明战舰还没爆炸,需要继续进攻
                    for (int i = lastMid + 1; i <= mid; i++)
                        op(attack[i][0], attack[i][1], attack[i][2], attack[i][3], attack[i][4], attack[i][5], -attack[i][6]);
                }
                if (mid < lastMid) {//说明已经有战舰爆炸,需要撤销进攻
                    for (int i = mid + 1; i <= lastMid; i++)
                        op(attack[i][0], attack[i][1], attack[i][2], attack[i][3], attack[i][4], attack[i][5], attack[i][6]);
                }
                if (check())
                    r = mid;
                else
                    l = mid + 1;
                lastMid = mid;
            }
    
            System.out.println(r);
        }
    
        static boolean check() {//求前缀和
            int[] temp = new int[a * b * c];
            System.arraycopy(diff, 0, temp, 0, a * b * c);
            for (int i = 1; i < a; i++) {
                for (int j = 1; j < b; j++) {
                    for (int k = 1; k < c; k++) {
                        if (j - 1 > 1)
                            diff[getIndex(i, j, k)] += diff[getIndex(i, j - 1, k)];
                        if (k - 1 > 1)
                            diff[getIndex(i, j, k)] += diff[getIndex(i, j, k - 1)];
                        if (i - 1 > 1)
                            diff[getIndex(i, j, k)] += diff[getIndex(i - 1, j, k)];
                        if (i - 1 > 1 && j - 1 > 1)
                            diff[getIndex(i, j, k)] -= diff[getIndex(i - 1, j - 1, k)];
                        if (i - 1 > 1 && k - 1 > 1)
                            diff[getIndex(i, j, k)] -= diff[getIndex(i - 1, j, k - 1)];
                        if (j - 1 > 1 && k - 1 > 1)
                            diff[getIndex(i, j, k)] -= diff[getIndex(i, j - 1, k - 1)];
                        if (i - 1 > 1 && j - 1 > 1 && k - 1 > 1)
                            diff[getIndex(i, j, k)] += diff[getIndex(i - 1, j - 1, k - 1)];
    
                        if (diff[getIndex(i, j, k)] < 0)//如果当前战舰爆炸了
                            return true;
                    }
                }
            }
            return false;//所有战舰都没爆炸
        }
    
        static int getIndex(int i, int j, int k) {
            return (((i - 1) * (B + 1) + (j - 1)) * (C + 1) + k);
        }
    
        static void op(int la, int ra, int lb, int rb, int lc, int rc, int m) {
            //正面
            diff[getIndex(la, lb, lc)] += m;
            if (rb + 1 < b)
                diff[getIndex(la, rb + 1, lc)] -= m;
            if (ra + 1 < a)
                diff[getIndex(ra + 1, lb, lc)] -= m;
            if (ra + 1 < a && rb + 1 < b)
                diff[getIndex(ra + 1, rb + 1, lc)] += m;
            //左面
            if (rc + 1 < c)
                diff[getIndex(la, lb, rc + 1)] -= m;
            if (ra + 1 < a && rc + 1 < c)
                diff[getIndex(ra + 1, lb, rc + 1)] += m;
            //上面
            if (ra + 1 < a && rb + 1 < b && rc + 1 < c)
                diff[getIndex(ra + 1, rb + 1, rc + 1)] -= m;
            if (rb + 1 < b && rc + 1 < c)
                diff[getIndex(la, rb + 1, rc + 1)] += m;
        }
    
    展开全文
  • 在nginx配置文件中中设置了 location /api/ 时 浏览器访问 /api/test 反向代理后实际还是/api/test ... proxy_pass http://localhost:12345; } 修改为如下location: location ^~/api/ { proxy_pass http://
  • 个问题很重要,需要立即引起注意: ①到1994年,一半以上的B类地址已被分配。预计,B类地址空间大约在1995年将被用尽 ②32位的IPv4地址被认为不足以应付Internet在21世纪初的预期规模 ③全球性路由表的条目数...
  • ES的简单前缀提示搜索(Movies案例) 要根据电影的名字做前缀搜索,前缀搜索的字段属性应该要使用 completion, 这个时候需要我们自定义mapping,但是mapping定义过于复杂。...第步,获取mapping信息: GET
  • 、最左前缀原则 最左前缀原则的定义 、索引下推 、小结 、引入 在开始这篇文章之前,首先明确个概念,聚集索引的B+树的每个节点就是个索引页,索引页会根据先前规定好的度数来决定个索引页放...
  • 、Tmux 是什么? 1.1 会话与进程 命令行的典型使用方式是,打开个终端窗口(terminal window,以下简称"窗口"),在里面输入命令。用户与计算机的这种临时的交互,称为次"会话"(session) 。 会话的个重要...
  • 比如我有个url为127.0.0.1:443/jh-12345zxc要反向代理到127.0.0.1:9443/jh-12345zxc要如何配置?
  • redis-cli -h 89.30.245.11 -p 6379 -a 12345 keys "bkdx:qjdx:*" |xargsredis-cli -h 89.30.245.11 -p 6379 -a 12345 del {}\;
  • volatile与lock前缀指令

    万次阅读 多人点赞 2016-08-17 23:48:51
    当CPU要读取个数据时,首先从级缓存中查找,如果没有再从级缓存中查找,如果还是没有再从级缓存中或内存中查找。一般来说每级缓存的命中率大概都有80%左右,也就是说全部数据量的80%都可以在级缓存中找到...
  • 前缀和与差分(c++)

    2020-07-15 09:16:51
    前缀和 基本思想 原数组:a1 a2 a3 …an 前缀和:si = a1 + a2 + a3 + …+ ai (s[0] = 0 例如:[1, 10] s = s10 - s0) 1.求si for(int i = 1; i <= n;.../*前缀和 —— 模板题 AcWing 795.
  • 前缀编码定义: (字符集中)任一编码都不是其它字符的编码的前缀 (字符集中)任一编码都不是其它字符的编码的前缀 (字符集中)任一编码都不是其它...第步:看A中的第个数1,看看其他数有没有1开头的。没有。 ...
  • 2、本文对于斐波拉契数列的前缀和以及多次求前缀和的方法进行一定的分析,得出了转移矩阵的一般形式。 3、编写公式开始是在AxMath进行的书写,写完以后发现好像不能直接将原文本导出(只有LaTex文本文件),故下面...
  • 前缀表达式的值

    万次阅读 多人点赞 2018-05-25 21:08:57
    7-1 求前缀表达式的值(20 分)算术表达式有前缀表示法、中缀...输入格式:输入在行内给出不超过30个字符的前缀表达式,只包含+、-、*、\以及运算数,不同对象(运算数、运算符号)之间以空格分隔。输出格式:输...
  • 、概述 我有个需求是需要邮箱登录的, mysql> select f1, f2 from SUser where email='xxx'; 我们知道,如果不在 email 上建立索引,那么将会走全表扫描。 于是,我们有两种建立方式  -mysql> ...
  • ​ volatile主要就是保证线程之间对单一变量的有序性和防止指令的重排序,本篇博文在于深入到操作系统的角度来解释什么是volatile关键字以及其如何实现对个变量的代码有序性。 引入 引入1 单例模式下的volatile 要...
  • 前缀和与差分数组前缀前缀和 对于 a1, a2, a3, a4, a5, a6, … 前缀和 Si = a1 + a2 + a3 + a4 +…+ ai,S0 = 0 其中,[l, r] 区间的前缀和为:Sr - S(l-1) 非
  • 、转换思路 转换思路为将输入的中缀表达式字符串从右往左扫描(字符前后加#号),遇到数字直接输出,遇到操作符比较优先级。 栈顶优先级低,入栈; 栈顶优先级高,出栈并且输出; 优先级相等(即左右括号),出栈(不...
  • 后缀表达式、前缀表达式

    千次阅读 2017-10-18 23:10:32
    后缀表达式和前缀表达式是什么呢?  前缀表达式:不包括括号的算术表达式,将运算符写在前面,操作数写在后面的表达式。为纪念其发明者波兰数学家Jan Lukasiewcz,也称“波兰式”。  后缀表达式:不包括括号,...
  • 前缀列表简介

    2015-03-11 12:38:24
    前缀列表的特点:(1)、可以增量修改,我们知道对于普通访问控制列表,我们不能删除该列表中的某个条目,如果想删除列表中的某个条目只能将该访问列表全部删除,而前缀列表中,个条目可以单独地删除或添加。...
  • 今天突然看到自己的个小笔记是关于spring配置文件前缀的总结,心血来潮就详细的写写吧=。= 啥?你问我spring是啥?对不起,咱们不认识=。=哈哈 做java的小伙伴对spring可谓是再熟不过了,那可是所谓的大头龙哈,...
  • ,通过创建唯一性索引,可以保证数据库表中每行数据的唯一性。 第,可以大大加快数据的检索速度,这也是创建索引的最主要的原因。 第,可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有...
  • 给出个电话列表,如果列表中存在其中个号码是另个号码的前缀情况,那么就称这个电话列表是不兼容的。 假设电话列表如下: ·Emergency 911 ·Alice 97 625 999 ·Bob 91 12 54 26 在此例中,报警电话号码...
  • 前缀树实现剪枝

    2021-09-16 13:12:33
    前缀树之前,反手个dfs爆搜,超时了,考虑剪枝,其实很多时间都浪费在从开始就不可能实现的单词上了,所以简简单单在深搜之前判断一下单词中的字母是不是每个都在图里出现过,偷鸡过了。 前缀树其实作用就是...
  • 霍夫曼编码是种不等长非前缀编码方式,于1951年由MIT的霍夫曼提出。 用于对串数字/符号编码获取最短的结果,获取最大的压缩效率。 特点:不等长、非前缀 等长式编码 等长编码,意思是对出现的元素采用相同位数的...
  • 中缀,后缀,前缀表达式转换前言中缀转后缀方法举例例1: A + B * (C - D)- E / F转换步骤手算(应用考试)后缀转中缀方法例: ABCD - * + E F / -中缀转前缀步骤 前言 中缀表达式转后缀表达式,后缀表达式转中缀...
  • 维差分 典型例题:差分矩阵 题目: 输入个n行m列的整数矩阵,再输入q个操作,每个操作包含个整数x1, y1, x2, y2, c。 其中(x1, y1)和(x2, y2)表示个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的...
  • 例如:user_12345abcd acct_23lksjdg3受其API中Stripe前缀ID的启发。 :rocket:安装将此行添加到应用程序的Gemfile中:gem'prefixed_ids':memo:用法将has_prefix_id:my_prefix添加到模型中以自动生成前缀ID。 类User...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 107,287
精华内容 42,914
关键字:

一二三四五的前缀