[关闭]
@donghanyuan0609 2020-04-18T14:26:23.000000Z 字数 3377 阅读 196

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

2020年4月18日 19:00

易错语法篇

  1. while (scanf("%d%d%d%d", &n, &x, &y, &k) != EOF); // !!!
  2. {
  3.     y = (y + n - x + k) % 7;
  4.     switch (y) {
  5.         // code here ......
  6.     }
  7. }
  9. for (int i = 0 ; i < n; i++);
  10. {
  11.     // code here
  12. }
  1. for (i = 0; i < m; i++)
  2. {
  3.     // ......
  4.     for (i = 1; i < m; i++) // for j
  5.     {
  7.     }
  8. }
  1. #include <stdio.h>
  2. typedef long long ll; // 这样比较方便

换行符的坑

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

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

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

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

  1. Hello world
  1. H e l l o SPACE w o r l d \n 
  2. H e l l o SPACE w o r l d \r \n

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

指针篇

指针的基础再回顾

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

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

为什么要交换指针

一列整数的最大值怎么求

  1. 8
  2. 1 10 2 8 7 11 3 6
  1. int n, x, i; 
  2. int max = 0;
  3. scanf("%d", &n);
  4. for (i = 0; i < n; i++) {
  5.     scanf("%d", &x);
  6.     if (x > max) max = x;
  7. }

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

  1. char buf[10005], longest[10005];
  2. int max_len = 0, len;
  3. while (gets(buf) != NULL) {
  4.     len = strlen(buf);
  5.     if (len > max_len) {
  6.         strcpy(longest, buf); // Time cost
  7.         max_len = len;
  8.     }
  9. }

为什么用PPT上的指针写法

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

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

变量的交换

  1. tmp = in_line;
  2. in_line = longest;
  3. longest = tmp;
  5. t = x; x = y; y = t;

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

  1. // 遍历一个字符串
  3. // 数组方式
  4. // l = strlen(s);
  5. for (i = 0; s[i] ; i++) {
  6.     putchar(s[i]);
  7. }
  9. // 指针方式
  10. char *p = s;
  11. p[0] = 's'; *(s + 1) = '1';
  12. for (p = s; *p; p++) {
  13.     putchar(*p);
  14. }
  16. // 区间的反转(指针)

上机题目篇

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

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

算，循环遍。
算，循环遍。
算，循环遍。
算，循环遍。
。。。。。。
算，循环遍。

  1. #define MOD 1000003
  2. int fact[1000005] = {1}, sum[1000005] = {1};
  3. int main()
  4. {
  5.     // 先预处理再输入
  6.     for (i = 1; i <= 1000000; i++)
  7.     {
  8.         fact[i] = (1LL * fact[i - 1] * i) % MOD;
  9.         sum[i] = (sum[i - 1] + fact[i]) % MOD;
  10.     }
  11.     scanf("%d", &q);
  12.     while (q--)
  13.     {
  14.         scanf("%d", &n);
  15.         printf("%d\n", sum[n]);
  16.     }
  17. }

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

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

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

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

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

  2. // 红组：排序(所有相同的值连在一起)
  3. // 统计最长的连续相等片段的长度
  5. // 假设红组已经排完序了
  6. int cnt = 0, max_red = 0, ans_red = 0;
  7. // cnt: 以当前元素结尾的最长相等连续段的长度
  8. for (i = 1; i <= m; i++)
  9. {
  10.     if (i > 1 && red[i] == red[i - 1])
  11.         cnt++;
  12.     else 
  13.         cnt = 1;
  15.     if (cnt > max_red)
  16.         max_red = cnt, ans_red = red[i];
  17. }
  20. // 黑组
  21. for (i = 1; i <= n; i++)
  22. {
  23.     scanf("%d", &x);
  24.     cnt_black[x]++;
  25.     if (cnt_black[x] > max) {
  27.     }
  28.     else if (cnt_black[x] == max) {
  30.     }
  31. }
  32. for (i = 1; i <= 1000; i++) {
  33.     if (cnt_black[x] >= max) // 更新最大值
  34. }

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

- 空间的力量：散列

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

坑多！
Hint多

输入

\r:我没存在感吗？

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

找子串

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

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

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

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

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

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

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

区间反转：

  1. void rev(char *s, char *t)
  2. {
  3.     char tmp;
  4.     for (; s < t; s++, t--) // s, t始终指向区间的对称位置
  5.     {
  6.         tmp = *s;
  7.         *s = *t;
  8.         *t = tmp;
  9.     }
  10. }

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

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

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

输入

又是\r惹的祸

  1. char a[1005][1005];
  3. for (i = 0; i < n; i++){
  4.     for (j = 0; j < n; j++)
  5.         a[i][j] = getchar();
  6.     //getchar(); // \n or \r\n
  7.     while (getchar() != '\n');
  8. }

以前的知识点回顾篇

数组的应用

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

置换的分解，Taylor Swift

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

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

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

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

递归怎么想

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

递归和循环的关系

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

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

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

记忆化(性能优化)

  1. 求组合数

位运算巩固

动态规划?

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

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注