美文网首页
PTA刷题总结-Part 1 基础部分

PTA刷题总结-Part 1 基础部分

作者: 苏wisdom | 来源:发表于2020-02-23 13:24 被阅读0次

1. 基础

最近开始在PTA上刷题练手,一边刷,一边整理一些常见的用法出来,加深印象。

这里的内容来源于自己刷题的总结+《算法笔记》+翁恺老师的C语言入门课程+陈越老师的数据结构课程。

这套总结我在持续补充和更新,一篇文章写下来太长了,就拆成了多个部分。

PTA刷题总结-Part 1 基础部分
PTA刷题总结-Part 2 模拟与数学问题
PTA刷题总结-Part 3 数据结构与算法

简书本身不提供自动目录功能。建议大家自己安装一个TamperMonkey,装上简书插件方便阅读,参考简书自动生成文章目录,亲测可用。

image.png

1.1. 数据范围

题目拿到手,要对输入数据的范围有判断。比如题目告诉你第一行输入是不超过10^​9的正整数N,那么你就可以安安心心地选择int类型去接收这个输入数据。如果告诉你的数在 10^10 到 10^18 范围内,就使用long long。如果超过了10^18,就要考虑高精度算法了,模拟加法乘法。碰到浮点型,就无脑使用double就好啦。

以下列出c语言中重要的数据类型在64位机器上的表现

  • int 4字节,32位,范围-2^31~2^31-1,最大值约等于21亿,2x10^9
  • long windows机器上是4字节 同上,unix类型机器上8字节
  • long long 8字节,64位,范围-2^63~2^63-1,最大值约为9x10^18
  • unsigned long long 8字节,64位,不带符号,最大的数2^64-1约为1x10^19
  • float 4字节,32位,实际精度6~7位
  • double 8字节,64位,实际精度15~16位

常用近似值:

  • 2^10 约等于 10^3
  • 2^20 约等于 10^6
  • 2^30 约等于 10^9
  • 2^40 约等于 10^12

1.2. ASCII

ASCII码里的东西大多数都不用记,只需记得小写字母比对应的大写字母大32

A:65
a:97

1.3. 无穷大

const int INF = (1<<30)-1;

1.4. 关于输入输出

刚开始学c, 对sancf()用法不熟,傻傻地读入字符串然后自己去做了一堆分解。后来发现针对数字、日期,可以这么用(题目:7-12 日期格式化 (5分))

#include <stdio.h>

int main(void)
{
    int mm,dd,yyyy=0;
    scanf("%d-%d-%d", &mm,&dd,&yyyy);

    printf("%d-%02d-%02d\n",yyyy,mm,dd);
    return 0;
}

其中printf()里,%02d表示若数字小于2位,则左边补0。

1.5. 变量初始化

变量的初始化想要强调一个点,如果这样初始化int a,b=100;,那么a的值其实是不确定的。对于多个变量的初始化,必须得一个一个去赋值,如int a=100, b=100;

1.6. 数组

如果数组的size较大,超过10^6 ,如int a[1000000];,那么应该写在main函数外面。因为在main函数里申请内存是有限制的,存放在栈区;而在主函数外申请的全局变量,存放在全局数据区,空间较大。

如果要对数组全部赋值为0或者-1,可以使用memset(数组名,值,sizeof(数组名)),使用这个方法需要#include <string.h>

#include <stdio.h>
#include <string.h>
int main(){
    int a[5] = {1,2,3,4,5};
    
    memset(a, 0, sizeof(a));
    for (int i=0;i<5;i++){
        printf("%d ",a[i]);
    }
}

指针数组
一个数组中所有元素都保存的是指针。指针数组最常用在字符串数组中,比如:

char *card[54] = {"S1","S2","S3","S4","S5","S6","S7","S8","S9","S10","S11","S12","S13",
    "H1","H2","H3","H4","H5","H6","H7","H8","H9","H10","H11","H12","H13",
    "C1","C2","C3","C4","C5","C6","C7","C8","C9","C10","C11","C12","C13",
    "D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","D13",
    "J1","J2"};
char *str[3] = {"Monday","Tuesday","Wednesday"};

其中

  • str是一个二级指针,类型是char **
  • *str是一个一级指针,类型是char *,指向一个字符串如"Monday",保存着该字符串的地址。也可以使用*(str+i)或者str[i]指向数组中第i个字符串
  • **str是具体的字符,如字符'M' , **(arr+1)T

1.7. math.h 常用函数

  • double fabs(double x) 浮点数取绝对值
  • double floor(double x) 向下取整
  • double ceil(double x) 向上取整
  • double pow(double x, double p) x^p, 注意,在计算水仙花数的题目中,发现pow(x,n)会超时,而换成for循环去做乘法竟然不会。
  • double sqrt(double x) 平方根
  • double log(double x) 以自然数为底的对数。若要以2为底,使用log(x)/log(2) 注意x 不能为0或者负数

下面这个取绝对值的函数常常被误认为是math.h中的,其实他在stdlib.h中

  • int abs(int x) 整数取绝对值

1.8. string.h 常用函数

  • int len = strlen(str); 字符串长度
  • int cmp = strcmp(str1, str2); 比较字典序
  • strcpy(des, src); 将src复制给des,包括\0
  • strcat(des, src); 将src接到des后面
  • char *p = strchr(str,c)从左到右找到字符c第一次出现的位置,返回指针,若没找到返回NULL
  • char *p = strrchr(str,c)从右到左找到字符c第一次出现的位置,返回指针,若没找到返回NULL
  • char *p = strstr(str1,str2)从左到右找到字符串str2在str1中第一次出现的位置,返回指针,若没找到返回NULL
  • memset(a, 0, sizeof(a)); 数组数据全部置为0

题目:7-53 删除字符串中的子串 (20分)

#include <stdio.h>
#include <string.h>
char s1[81];
char s2[81];
char t[81];
int main(){
    gets(s1);
    gets(s2);

    int len2 = strlen(s2);
    char *p;
    while (p = strstr(s1, s2)){
       *p = '\0';
       strcat(t, s1);
       strcat(t, p+len2);
       strcpy(s1, t);
       t[0] = '\0';
    }
    printf("%s", s1);
    return 0;
}

1.9. 字符串的输入

如果能够使用C++进行字符串的读入的话,是再好不过了。不过PTA有的题目只能以C编译。
c语言中字符串的输入
一般使用gets()标准函数读入一行字符串,而scanf("%s",str)虽然也能读入字符串,但是会在空格处断开,除非使用正则,挺麻烦的。

#include <stdio.h>
#include <string.h>
char str[100000];
int main(){
    gets(str); // 读取含有空格的字符串
    int len = strlen(str); 
    return 0;
}

c++语言中字符串的输入
cin>>str也可以读入字符串,但是遇到空格就不读了,要注意。

#include <iostream>
#include <string>
using namespace std;
int main(){
    string str;
    getline(cin, str); // 读入一整行,包括空格
    int len = str.length();
    return 0;
}

1.10. stdio.h中的 sscanf 和 sprntf

处理字符串的利器。

sscanf 是“从左至右”,将str里的内容灌到了整型变量n中。

#include <stdio.h>

int main(){
    int n;
    char str[100] = "00123";
    sscanf(str, "%d", &n);
    printf("%d\n", n);
    return 0;
}
#include <stdio.h>

int main(){
    int n;
    double db;
    char str[100] = "2048:3.14,hello", str2[100];
    sscanf(str, "%d:%lf,%s", &n,&db,str2);
    printf("n = %d, db = %.2lf, str = %s\n", n,db, str);
    return 0;
}

sprntf 是“从右至左”

#include <stdio.h>

int main(){
    int n = 2333;
    char str[100];
    sprintf(str, "%d", n);
    printf("%s\n", str);
    return 0;
}
#include <stdio.h>

int main(){
    int n = 12;
    double db = 3.14;
    char str[100] , str2[100] = "Hello";
    sprintf(str, "%d:%lf,%s", n,db,str2);
    printf("str = %s\n", str);
    return 0;
}

相关文章

网友评论

      本文标题:PTA刷题总结-Part 1 基础部分

      本文链接:https://www.haomeiwen.com/subject/qpfjqhtx.html