C语言答疑串讲 2020-4-18

2020年4月18日 19:00

易错语法篇

• for, while的括号后面手滑加了分号

while (scanf("%d%d%d%d", &n, &x, &y, &k) != EOF); // !!!
{
    y = (y + n - x + k) % 7;
    switch (y) {
        // code here ......
    }
}
for (int i = 0 ; i < n; i++);
{
    // code here
}

• 有多层循环或多个循环变量时i, j写混（内层外层循环都用了同一个i，或者是内层循环一会儿写成i一会儿写成j）

for (i = 0; i < m; i++)
{
    // ......
    for (i = 1; i < m; i++) // for j
    {
    }
}

• 数组那点事（全局！别正好开n个！）

• 数据范围的坑！（K题long long记住了吗）

#include <stdio.h>
typedef long long ll; // 这样比较方便

换行符的坑

再认识一下这位"罪魁祸首" - \r

windows中，换行符是CR+LF("\r\n"), 在windows系统中体现不出来

用getchar逐个字符读取，只能读到一个'\n'，识别不到'\r'。

在linux系统(OJ评测机)中，默认的换行符是"\n"，'\r'会被当做一个普通的字符(分隔符)。会占一个字符长度！

Hello world

H e l l o SPACE w o r l d \n 
H e l l o SPACE w o r l d \r \n

用gets或者fgets有影响，用scanf("%s", s)无影响。
在windows系统中（本地调试）察觉不到，但提交到OJ上会有影响。

指针篇

指针的基础再回顾

int a = 1, *p = &a; // 指针的定义
int b = 2;
p = &b; 
*p = 3; // b = 3;
// 指针和数组名
char str[1005], *ps;
// 数组名就是首地址
str == &str[0]
ps = str;
printf("%s", ps);
puts(ps);
char s[105] = "hello", *p = "world";
s[0] = 'b'; p = "cprogramming";

课堂例题：最长的一行句子

为什么要交换指针

一列整数的最大值怎么求

8
1 10 2 8 7 11 3 6

int n, x, i; 
int max = 0;
scanf("%d", &n);
for (i = 0; i < n; i++) {
    scanf("%d", &x);
    if (x > max) max = x;
}

类似的方法求长度最长的字符串

char buf[10005], longest[10005];
int max_len = 0, len;
while (gets(buf) != NULL) {
    len = strlen(buf);
    if (len > max_len) {
        strcpy(longest, buf); // Time cost
        max_len = len;
    }
}

为什么用PPT上的指针写法

两个数组在任何时刻：其中一个数组负责接受新的输入，另一个数组负责存储最长串。
两个数组没有本质的区别。
省去strcpy传递的过程。

任何时刻，总有一个指针指向存储最长串的数组，另一个指针指向的数组用于接受新的输入。

变量的交换

tmp = in_line;
in_line = longest;
longest = tmp;
t = x; x = y; y = t;

数组与指针在字符串问题的应用

// 遍历一个字符串
// 数组方式
// l = strlen(s);
for (i = 0; s[i] ; i++) {
    putchar(s[i]);
}
// 指针方式
char *p = s;
p[0] = 's'; *(s + 1) = '1';
for (p = s; *p; p++) {
    putchar(*p);
}
// 区间的反转(指针)

上机题目篇

求阶乘 - 预处理(性能优化)

排除重复的计算
第一遍算$4!$，循环4遍。
第二遍算$10!$，循环10遍

算$10^6!$，循环$10^6$遍。
算$10^6!$，循环$10^6$遍。
算$10^6!$，循环$10^6$遍。
算$10^6!$，循环$10^6$遍。
。。。。。。
算$10^6!$，循环$10^6$遍。

#define MOD 1000003
int fact[1000005] = {1}, sum[1000005] = {1};
int main()
{
    // 先预处理再输入
    for (i = 1; i <= 1000000; i++)
    {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
        sum[i] = (sum[i - 1] + fact[i]) % MOD;
    }
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d", &n);
        printf("%d\n", sum[n]);
    }
}

易错点：不要使用递归（SIGSEGV）

递归层次过深，改成循环！！！！！

红黑歌合战 - 时间和空间的神秘力量

Key: 红组用排序，黑组用散列(数组计数)

红组个数少但是数据元素比较分散，
黑组数据个数多，但是数值相对集中

// 红组：排序(所有相同的值连在一起)
// 统计最长的连续相等片段的长度
// 假设红组已经排完序了
int cnt = 0, max_red = 0, ans_red = 0;
// cnt: 以当前元素结尾的最长相等连续段的长度
for (i = 1; i <= m; i++)
{
    if (i > 1 && red[i] == red[i - 1])
        cnt++;
    else 
        cnt = 1;
    if (cnt > max_red)
        max_red = cnt, ans_red = red[i];
}
// 黑组
for (i = 1; i <= n; i++)
{
    scanf("%d", &x);
    cnt_black[x]++;
    if (cnt_black[x] > max) {
    }
    else if (cnt_black[x] == max) {
    }
}
for (i = 1; i <= 1000; i++) {
    if (cnt_black[x] >= max) // 更新最大值
}

小结：
- 时间的力量：排序

- 空间的力量：散列

名字的愤怒 - 字符串替换(经典！)

坑多！
Hint多

输入

\r:我没存在感吗？

gets(s);
// 去掉末尾的第一个分号
int l = strlen(s);
while (s[--l] != ';');
s[l] = 0;

找子串

只需要将替换的位置输出即可，不需要真正在原处替换

strstr函数：若匹配：则返回匹配位置(首字符的地址)；若不匹配，则返回NULL。

匹配到了，直接输出要换成的新串；
如果没匹配：原样输出

char *slow = s, *fast = s;
while ((fast = strstr(slow, a)) != NULL) {
    while (slow < fast) putchar(*(slow++)); // 当前位置到匹配点之间
    printf("%s", b); // 输出替换为的串b
    slow += len_a; // 直接跳过要匹配的串a
}
while (*slow) putchar(*(slow++));
putchar(';');

魔镜 - 字符串区间翻转(基本操作必会！)

• 找到单词的分界
• 区间反转

单词开头：自己是字母，并且要么在句首要么上一个不是字母
单词结尾：自己是字母，要么下一个字符不是字母(字符串结尾是'\0')

用指针或下标变量标记单词的开头(或者结尾)

区间反转：

void rev(char *s, char *t)
{
    char tmp;
    for (; s < t; s++, t--) // s, t始终指向区间的对称位置
    {
        tmp = *s;
        *s = *t;
        *t = tmp;
    }
}

爱的魔力转圈圈 - 剥洋葱壳、由繁到简

先转外圈，再将边界向里各退缩一格。

可以用递归来做，也可以用循环来做。

输入

又是\r惹的祸

char a[1005][1005];
for (i = 0; i < n; i++){
    for (j = 0; j < n; j++)
        a[i][j] = getchar();
    //getchar(); // \n or \r\n
    while (getchar() != '\n');
}

以前的知识点回顾篇

数组的应用

散列 - vis, cnt, ... 都是他

• 甄医生
• 水水的多项式加法

置换的分解，Taylor Swift

for (j = i; j != n; j = next[j])
    vis[j] = 1;

什么时候没必要用数组 - 迭代

只需要知道当前的状态和上一个状态的关系，不需要知道更早的状态

由s[i - 1]推s[i]

递归怎么想

把一个大问题分解成类似的小问题

递归和循环的关系

求最大公约数，求阶乘，汉诺塔

层次比较深但是不分叉的递归，能否直接循环搞定？

可以迭代的问题（这个勇者很菜，斐波那契，求阶乘，公约数）

记忆化(性能优化)

求组合数

位运算巩固

• 按位与(取出某些位的值)，按位或(将某些位设定为1)，按位非的作用
• 原码反码补码
• w位数

动态规划?

• 这个勇者很菜
• 硬币的组合

当前状态怎么由之前已有的(数据规模比较小的)状态得到