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

admin 2022年5月24日00:53:09评论16 views字数 8718阅读29分3秒阅读模式
「算法刷题宝典」必须知道的知识点和技巧
点击蓝字 关注我们
「算法刷题宝典」必须知道的知识点和技巧

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


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


边学边练,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时卡牌数量不足              breakprint(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("%dn",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("%dn",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 osimport 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 500005long 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 osimport 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:回复【算法】可获取更详细的算法题解~


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

原文始发于微信公众号(蓝桥云课精选):「算法刷题宝典」必须知道的知识点和技巧

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年5月24日00:53:09
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   「算法刷题宝典」必须知道的知识点和技巧http://cn-sec.com/archives/1043390.html

发表评论

匿名网友 填写信息