数据结构与算法笔记 | 杂项

在刷算法题的时候, 不仅需要算法正确, 还要注意一些小的坑点, 才能保证程序结果的准确无误.

long占几字节

这个是不固定的，根据操作系数和处理器位数不同而不同，比如我的64位Archlinux上是8字节的，64位Win10上是4字节的。
但是通常来说int是4字节，long long是8字节。所以在刷题时 long 是不被建议使用的。
所以如果想使用固定8字节，一般用 long long 或者更进一步使用 int64_t

#include <stdint.h>
typedef int64_t ll;
typedef uint64_t ull;

想使用固定4字节，一般用int或者更进一步使用 int32_t

#include <stdint.h>
typedef int32_t int;
typedef uint32_t uint;

输入输出重定向

./a.out < in > out

输入重定向也可以用管道的方式：

cat in | ./a.out

OJ 的运算能力

以LeetCode为例，下面的算法在约 1x10^7 处（10930287）超时

typedef long long ll;

class Solution {
public:
    int findIntegers(int n) {
        int ans = 1;
        for(ll i = 1; i <= n; ++i) {
            if((i & i<<1) == 0) {
                ans ++;
            }
        }
        return ans;
    }
};

OJ中的坑

输入输出类

这是最容易犯的一类错误.

比如OJ说输入是 a seperate line, 即使在样例输入中的字符串中间没有空格, 也不能保证 OJ 上的例子中字符串中间也是没有空格的. 所以这个时候如果用 scanf 读取可能只能读到一个片段, 应该用 fgets 或者是 getline.

例: UVA-10405: https://vjudge.net/problem/UVA-10405

还有输入的组数问题，比如下面的描述：

There are a lot of cases. In each case, there is an integer N representing the number of integers to find.

INPUT:

3
2 3 4

这种情况下要用 while(scanf("%d", &N) != EOF) 去读取。因为有多个cases，样例中只是展示了一个case。
例 HDU 2.1.2：http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=2&sectionid=1&problemid=2

而下面的描述：

输入数据的第一行为一个正整数T，表示测试数据的组数。然后是T组数据…

INPUT:

2
26501/6335 18468/42
29359/11479 15725/19170

这种情况下要用 scanf("%d", &T); 读取，使用上一种读取方式反而可能会出现 Time Limit Exceeded(读取超时) 或 Output Limit Exceeded(读取空行导致死循环输出) 的错误。
例 HDU 2.1.3：http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=2&sectionid=1&problemid=3

合法数据类

牛客网上有一道求树的高度的题, 明明说是一棵合法的二叉树, 可是在输入数据中却包含了不合法的多叉树情况. 这是需要忽略三叉之后的情况.

https://www.nowcoder.com/activity/oj?title=%E6%A0%91%E7%9A%84%E9%AB%98%E5%BA%A6&page=1

读题不仔细类

PAT Advanced 1002: A+B for polynomials

题目中明确说了NK到N1的指数范围是非负的, 但是我误以为系数a的范围也是非负的. 导致第二个测试点一直过不去… 其实系数的范围可正也可负.

生活常识类

排名问题

PAT Advanced 1012: The Best Rank
给A B C三人排名时如果分数 A = B > C, 那么排名为 1,1,3

题目描述不清类

PAT 1032 Sharing

题目中明明说了, The address of a node is a 5-digit positive integer. 可是实际上包含五位全部为 0 的合法地址… 也就是说在判定链表是否结束的时候, 使用 (next > 0) 是不行的, 要用 (next >= 0). 也许是出题人理解的 positive integer 和我们有点不太一样…

PAT 1038 Recover the Smallest Number

题目中说最后结果不能是0, 实际上有0的数据. 我在代码里写了一行测试

For(i,N){
    scanf("%s", segments[i]);
    if (atoi(segments[i]) == 0) {--i;--N;}
}
if (N==0) {puts("0"); return 1;}

结果果然产生了非零返回… 让我很是气愤.

针对C语言全局变量的坑

C语言对全局变量会初始化为0，但对于LeetCode这样的在线做题网站，一个函数可能调用多次，在调用下一次的时候全局变量就已经不是0了，所以全局变量还是要在函数当中重新初始化赋值。