「算法刷题宝典」必须知道的知识点和技巧

点击蓝字 关注我们

【算法学与练】如期而至，你准备好了吗？

上周，我们在算法刷题群发布了「每日一题」，大家都会做吗？今天，我们来汇总一下上周的算法知识点及题目！错过的小伙伴千万别再忘记刷题啦！

边学边练，yyds！

跟着我一起学算法吧！欢迎你的加入~

01

基础算法——枚举、模拟

枚举算法是我们在日常中使用率最高的一个算法，它的核心思想就是：枚举所有的可能。

枚举法的本质就是从所有候选答案中去搜索正确的解，使用该算法需要满足两个条件：

• 可预先确定候选答案的数量；

• 候选答案的范围在求解之前必须有一个确定的集合。

（图片来源网络：枚举算法的流程图）

枚举的一般形式为：

enum 枚举名
{ 枚举值表 };

举个例子来看看：

enum weekday
{ sun,mou,tue,wed,thu,fri,sat };

该枚举名为weekday，枚举值共有7个，即一周中的七天。

那枚举算法到底好在哪呢？

枚举的算法简单，在局部地方使用效果极佳。但运算量比较大，如果遇到问题规模变大时，循环的阶数越大，执行速度越慢。

当然，并不是所有题目都适合枚举，它在使用中有以下规定：

枚举值是常量，不是变量。

不能在程序中用赋值语句再对它赋值。

例如，对枚举 weekday 的元素，再作以下赋值：sun=5;mon=2;sun=mon; 这都是错误的。

枚举元素本身由系统定义了一个表示序号的数值，从 0 开始顺序定义为 0，1，2……如在 weekday 中，sun 值为 0，mon 值为1， ……sat 值为 6。

练习题来啦！

1、卡片

参考代码

1）C

#include <stdio.h>
int main(void)
{
  int i,t,sum=0;
  for(i=1;;i++)
  {
    for(t=i;t!=0;t/=10)
      if(t%10==1)
        sum++;
    if(sum>=2021)
      goto end;
  }
  end:printf("%d",i);
  return 0;
}

2）C++

#include <iostream>
using namespace std;
 
 
int main()
{
    long int i=0;
    long int sum = 2021,tmp=0;
    long int b=0;
    for(i=1; i<20210; i++) {
        //记住需要一个数把i的值给记下来，因为后面的相除那一个数是发生变化 
        tmp=i;
        while(tmp) {
            b = tmp%10;
            if(b==1 && sum>0) {
                sum-=1;
            }
            tmp/=10;
        }
        if (sum==0) {
            break;
        }
    }
    cout<<i;
    return 0;
}

3）Java

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
 
public class Main {
    public static void main(String[] args) {
        int count=0;
        for (int i = 1; i < 20210; i++) {
            String str=i+"";
            for (int j = 0; j < str.length(); j++) {
                if(str.charAt(j)=='1')
                {
                    count++;
                }
            }
            if(count==2021)
            {
                System.out.println(str);
                break;
            }
        }
        
        scan.close();
    }
}

4）Python

num=0  #用num用来累计用过的数字“1”的次数
for i in range(1,10000):
       num+=str(i).count("1")  #出现过几次1就 给num加上多少
       if num>2021:  #当num数量超过2021时卡牌数量不足
              break
print(i-1)

2、回文日期

参考代码

1）C

//分析：是否合法（年月日）-->不合法，跳过
//                          -->合法--是否是闰年-->分解日期（装入数组）-->判断是否满足回文-->设置变量只打印下一个 
 
 
 
 
#include<stdio.h>
int mon[12]={31,28,31,30,31,30,31,31,30,31,30,31};
int arr[8]={0};
int year,month,day,j,flag=0,temp; 
int legal()//判断是否合法
{
    if(year%400==0)
      mon[1]=29;
    else
      mon[1]=28;
    if(year<1000||year>9999||month<=0||month>12||day>mon[month])
      return 0;
    return 1;
}
int main()
{
  int time;
  scanf("%d",&time);
  for(int i=time+1;i<=99991231;i++)
  {
    year=i/10000;
    month=i/100%100;
    day=i%100;
    if(!legal())
      continue;
    j=0;temp=i;
    while(temp)
    {
        arr[j++]=temp%10;
        temp/=10;
    }
    if(arr[0]==arr[7]&&arr[1]==arr[6]&&arr[2]==arr[5]&&arr[3]==arr[4])
    {
        if(flag==0)
        {
            for(int t=0;t<8;t++)
              printf("%d",arr[t]);
            printf("\n");
            flag=1;
        }
      if(arr[0]==arr[2]&&arr[1]==arr[3])
        {
          for(int t=0;t<8;t++)
              printf("%d",arr[t]);
          break;
      }
     } 
  }
  return 0;
}

2）C++

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
      int i,n,a,b,c,d,e,f,g,h;
    int j=0;
    scanf("%d",&n);
    for(i=n+1;i<=89991231;i++)
    {
        a = i%10;
        b = (i/10)%10;
        c = (i/100)%10;
        d = (i/1000)%10;
        e = (i/10000)%10;
        f = (i/100000)%10;
        g = (i/1000000)%10;
        h = (i/10000000)%10;
        if((a==h)&&(b==g)&&(c==f)&&(d==e))
        {
            if(j==0)
            {
                printf("%d\n",i);
                j++;
            }
 
 
        }
        if((a==h)&&(b==g)&&(c==f)&&(d==e)&&(a==c)&&(b==d))
        {
            printf("%d",i);
            break;
        }
    }
  return 0;
}

3）Java

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
 
public class Main {
   public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int data = sc.nextInt();
    huiwenriqi(data);
    ABhuiwenriqi(data);
    sc.close();
}
public static void huiwenriqi(int n) {
    for (int i = n+1; i <= 89991231; i++) {
        String str = i+"";
        char[] ch = str.toCharArray();
        char a = ch[0], b = ch[1], c = ch[2], d = ch[3],e = ch[4],f = ch[5],g = ch[6],h = ch[7];
        if(a==h&&b==g&&c==f&&d==e) {
            System.out.println(ch);
            break;
        }
}
}
public static void ABhuiwenriqi(int n) {
    for (int i = n+1; i <= 89991231; i++) {
        String str = i+"";
        char[] ch = str.toCharArray();
        char a = ch[0], b = ch[1], c = ch[2], d = ch[3],e = ch[4],f = ch[5],g = ch[6],h = ch[7];
        if(a==c&&c==f&&f==h&&b==d&&d==e&&e==g) {
            System.out.println(ch);
            break;
        }
}
    
}
}

4）Python

import datetime #导入日期库
 
 
idate=input()
y=int(idate[:4])           #取出输入的年月日
m=int(idate[4:6])
d=int(idate[6:])
dd=datetime.date(y,m,d)   #将输入的表示日期的字符串转换成日期
flag=True                 #回文日期只输出一次
 
 
for n in range(9999999):
  dd=dd+datetime.timedelta(days=1)     #日期不断增加1天
  sd=str(dd).replace('-','')           #将日期中的-去掉
  
  if sd[:]==sd[::-1]:                  #判断日期是否是回文
    if flag:
      print(int(sd))                   #输出回文日期
      flag=False                       #下次不输出回文日期
    if sd[0]==sd[2]==sd[5]==sd[7] and sd[1]==sd[3]==sd[4]==sd[6]: #判断是否是ABABBABA类型
      print(int(sd))
      break

3、赢球票

参考代码

1）C

#include <stdio.h>
#include <stdlib.h>
int a[102]={0},b[102]={0},N,i,max=0,j,sum=0,k,h,m,max1=0,l;
void dat()
{
  for(i=0,sum=0,j=1;j<=max;)
  {
     if(a[i]<0)
    {
      i=0;
    } 
    if(a[i]==j)
    {
      sum=sum+j;
      j=1;
      
      for(k=i;a[k+1]!=0;k++)
      {
        a[k]=a[k+1];
      }
      continue;
    }
    i++;j++;
  }
 
 
  if(max1<=sum)
    max1=sum;
}
int main(int argc, char *argv[])
{
 
 
  scanf("%d",&N);
  for(i=0;i<N;i++)
  {
    scanf("%d",&b[i]);
    max=max>=b[i]?max:b[i];
  }
  b[i]=-1;
  for(h=0;h<N;h++)
  {
    m=b[0];
    for(i=0;i<N-1;i++)
    {
      b[i]=b[i+1];
    }
    b[N-1]=m;
    for(l=0;l<N+1;l++)
        a[l]=b[l];    
   dat();
  }
 
 
  printf("%d\n",max1);
  return 0;
}

2）C++

#include <iostream>
#include <algorithm> 
#include <string>
#include <cstring>
#include <queue>
#include <utility>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque> 
 
 
#define io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define x first
#define y second
 
 
using namespace std;
 
 
const int N = 110,  M = 400010;
typedef long long LL;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PII;
 
 
int n, m;
unordered_set<int> s;
int a[N];
 
 
int main()
{
    io;
    int maxn = 0, res = 0;
    cin >> n;
    rep(i, 0, n - 1)
    cin >> a[i], res += a[i];
    rep(i, 0, n - 1)
    {
        s.clear();
        int cnt = 1;
        int j = i;
        int sum = 0; 
        int k = 0;
        while(j != -1)
        {
            k ++;
            if(k > 50000) break;
            j = j % n;
            //cout << a[j] << " " << cnt;
            if(s.find(a[j]) != s.end())
            {
                //cout << " ?" <<endl; 
                j ++;
            //    if(cnt == n) break;
                continue;
            }
            else
            {
                //cout << " !";
                if(cnt == a[j])
                {
                    //cout << "?\n";
                    s.insert(cnt);
          sum += cnt;
                    cnt = 1;
                    
                }
                else 
                {
                    cnt ++;
                //    cout << "!\n";
                }
                j ++;
            }
            if(cnt > n) break;
            if(sum == res)
            {
                cout << sum << endl;
                return 0;
            }
        }
        maxn = max(maxn, sum);
    }
    cout << maxn;
    return 0;    
}

3）Java

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
 
public class Main {
   static int num;
    static int msize=0;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        num=sc.nextInt();
        int[] arr=new int[num];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=sc.nextInt();
        }
        for (int i = 1; i <= num; i++) {
            msize+=i;
        }
        for (int i = 0; i < arr.length; i++) {
            barr=new boolean[num];
            P(arr,i,1,0);
            if(maxsize==msize)break;
        }
        System.out.println(maxsize);
    }
    static int maxsize=0;
    static boolean[] barr;
    public static void P(int[] arr,int k,int i,int size) {
        if(i>num||size==msize) {
            if(size>maxsize)maxsize=size;
            return;
        }
        if(barr[k]) {
            P(arr,k+1<arr.length?k+1:0,i,size);
            return;
        }
        if(arr[k]==i) {
            barr[k]=true;
            P(arr,k+1<arr.length?k+1:0,1,size+arr[k]);
        }else {
            P(arr,k+1<arr.length?k+1:0,i+1,size);
        }
    }
}

4）Python

import os
import sys
 
 
# 请在此输入您的代码
def f(n,nums):
    ans = 0
    for m in range(n):    #控制次数    n个数有n种顺序读数，每一个数可以打头阵
        tmp = nums[m:] + nums[:m]    #重新拼接数组   
        j = 0   #数数，起点
        while j < max(tmp):    #数的数比最大值还大，就跳出去，无法全部卡片收取
            for i,v in enumerate(tmp,1+j):
                if v == i:
                    j = 0
                    if len(tmp)==1:    #只有一个，直接return出来
                        return cnt   
                    elif v == tmp[-1]:   #只剩一个，不好切片，所以用[:-1]
                        tmp = tmp[:-1]
                    else:
                        r = tmp.index(v)    #i已经不能用，已经再转圈计数了，所以用拼接的数组的索引
                        tmp = tmp[r+1:] + tmp[:r]                      
                    break
            else:
                j = i  #转圈的i索引记录下来
        ans = max(ans, cnt - sum(tmp))
    return ans
 
 
n = int(input())
nums = [int(i) for i in input().split()]
cnt = sum(nums)
print(f(n,nums))

02

算法基础——前缀和、差分

前缀和（Prefix Sum）的定义为：对于一个给定的数列 A，它的前缀和数列 S 是通过递推能求出来得部分和。

例如：A = {1, 2, 3, 4, 5}，S = {1, 3, 6, 10, 15}，即：Sn = a1 + a2 + a3 + … + an，类似于数列的前 N 项和。

差分，相当于前缀和的逆运算。

设 a[N] 是我们的目标数组，b[N] 是我们的差分数组，则它们的关系是：

a1 = b1，a2 = b1 + b2，a3 = b1 + b2 + b3，…，an = b1 + b2 + … + bn，也就是说数组 a 是 数组 b 的前缀和。

假如我们想要在数组 a 的 [l, r] 范围内每个元素都加上 c ,可以考虑迭代方式加上 c ，但是时间复杂度是 O(n)。

利用数组 a 的差分数组 b 就可以这样做到：

b[l] += c;

b[r + 1] -= c;

a 是 b 的前缀和，也就是说 b 中的每一个元素累加起来就是 a 中的元素，如果在 b 数组的某个位置加上 c ，a 是 b 的累加，那么从 a[l] 到 a[r] 中的每一个数都相当于加上了 c。

练习题来啦！

1、小明的彩灯

参考代码

1）C

#include <stdio.h>
#include <stdlib.h>
 
 
#define  N 500005
long long arr[N];//原数组
long long  diff[N];//差分数组
 
 
int main(int argc, char *argv[])
{
    // 请在此输入您的代码
    int n, q,i=0;
    scanf("%d %d",&n,&q);
    while(++i<=n){
        scanf("%lld",&arr[i]);
        diff[i]=arr[i]-arr[i-1];///构造差分数组
    }
 
 
    while(q--){
        long long  l,r,x;
        scanf("%lld %lld %lld",&l,&r,&x);
        diff[l]+=x;///对差分数组的两个端点进行修改
        if(r+1>=N)
          continue;
        diff[r+1]-=x;
    }
 
 
    ///区间修改已完成，开始还原数组
    for(i=1;i<=n;i++){
        diff [i]=diff[i]+diff[i-1];//还原修改后的数组
        if(diff [i]>=0)
            printf("%lld ",diff [i]);
        else
            printf("0 ");
    }
    return 0;
}

2）C++

#include <iostream>
const int maxn=500005;
long long N[maxn]={0};
long long b[maxn]={0};
using namespace std;
int main()
{
  int P,Q;
  cin>>P>>Q;
  for(int i=1;i<=P;i++){
    cin>>N[i];
    b[i]=N[i]-N[i-1];//定义差分和数组
  }
  while(Q>0){
    long long l,r,x;
    cin>>l>>r>>x;
    b[l]+=x;
    b[r+1]-=x;//对两端进行操作
    Q--;
  }
  for(int i=1;i<=P;i++){
    N[i]=b[i]+N[i-1];//最后回归原来数组 
    if(N[i]<0){
      cout<<0<<" ";
    }else
    cout<<N[i]<<" ";
  }
  return 0;
}

3）Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
 
 
public class Main {
 
 
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        StreamTokenizer sc=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        sc.nextToken();
        int n=(int)sc.nval;
        sc.nextToken();
        int q=(int)sc.nval;
        long a[]=new long[n+1];
        long b[]=new long[n+1];
        for(int i=1;i<=n;i++){
            sc.nextToken();
            a[i]=(long)sc.nval;
            b[i]=a[i]-a[i-1];
        }
        for(int i=0;i<q;i++) {
            sc.nextToken();
            int l=(int)sc.nval;
            sc.nextToken();
            int r=(int)sc.nval;
            sc.nextToken();
            long c=(long)sc.nval;
            b[l]+=c;
            if(r<n)b[r+1]-=c;
        }
        for(int j=1;j<=n;j++)a[j]=a[j-1]+b[j];
        for(int i=1;i<=n;i++){
            if(a[i]<0)a[i]=0;
            System.out.print(a[i]+" ");
        }
    }
}

4）Python

import os
import sys
 
 
N, Q = map(int, input().split())
a = list(map(int, input().split()))
op = [0 for _ in range(N+1)]
for _ in range(Q):
  l, r, x = map(int, input().split())
  op[l-1] += x
  op[r] -= x
 
 
for i in range(1, N):
  op[i]+= op[i-1]
print(' '.join(str(max(a[i] + op[i], 0)) for i in range(N)))

上周算法学与练就到这了，但「每日一题」仍在【算法刷题群】中继续，如想算法刷题，欢迎加入【算法刷题群】，期待你的到来！（ps：回复【算法】可获取更详细的算法题解~）