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

2020-02-23 本文已影响0人苏wisdom

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;
}