C刷题:LeetCode刷题踩坑常见BUG总结

作者:来知晓
公众号:来知晓
刷题交流QQ群:444172041

Git项目地址LeetCodeUsingC刷题笔记

本文主要记录使用C语言刷LeetCode题目时,经常出现的一些bug错误,便于快速定位排查以及提高正确编码意识,欢迎大家参考并补充。更专业的内容可以查阅书籍《C缺陷和陷阱》。

常见坑点


  • 数组下标越界,下标改变后用前务必保证在有效范围内,防止越界或为负
  • 代码理解错误,特别涉及到对参考的代码自己实现时,对原代码功能理解错误,需要仔细和扎实的基础
  • 使用双指针时,经常误用 left - right 作为长度, 最好使用 end - start 命名更清晰
  • 注意运算溢出,使用 int mid = start + (end - start) / 2;
  • 特别注意有符号数和无符号数相减,最好避免

debug技巧


  • 必会快捷键,运行调试:Ctrl + ',提交代码:Ctrl + enter
  • 参考别人代码实现时,重要的是先搞懂思路,弄清每步操作到底是在干啥,自己再用代码去复现,才能更高效地实现
  • 如果有正确的参考代码,先观察正确代码的关键点和数值,再对比有问题的代码对应的变量,找到差异点,从而定位出问题
  • 不清楚哪段代码有问题,可以用二分法,把代码块分段,按代码段查看对应阶段结果是否正确,不断细分缩小,找到问题代码
  • 熟练的打断点,添加变量和表达式观察
  • 实在看不出来,就缓缓,说不定第二天再看,脑子跳出来再回看时一下就能看出问题

刷题经验


  • 能排序的先排序再处理,不断简化问题,缩小问题规模,便于摸清问题规律
  • 注意转化题意,将复杂问题等价转换成简单数学问题
  • 实在无思路时,先暴力再优化,根据题意用最简单的暴力解决二维for解决

代码分析


数组下标越界

// while (hash[s2[left] - 'a'] == 0 && left < right) { // 问题代码
while (left < right && hash[s2[left] - 'a'] == 0) {
    // 数组下标先判范围再引用,否则可能越界

代码理解错误,不深入,陷入定势思维错误:

// 参考表达
if (hash[s[right]]-- > 0) {
   
    notFitNum--;
}

// 错误转化,陷入定势思维
if (hash[s[right]] > 0) {
    
    notFitNum--;
    hash[s[right]]--;
} 

// 正确转化
if (hash[s[right]] > 0) {
   
    notFitNum--;
}
hash[s[right]]--; 

以上参考代码里,if判断时,先执行 hash[s[right]] > 0 判断 并且不管结果真假,hash[s[right]]--都会执行自减。而自己却大意的理解为if判断为真后才做自减。


对C++的STL函数不熟悉

// while (valid == need.size()) { // size表示的键个数, 如字符串 aa, 则键只有1个,值为2 
   while (valid == lenT) {
              // 而我以为就是t的长度,用lenT代替了,遇到重复字符串就有问题,lenT则为 aa 的长度,为2 

need为无序map,size函数实际返回无序map中有效的键个数,而自己错误理解为所有键的值之和。


注意有符号数和无符号数相减,涉及到C语言整型提升规则:

int a = 6;
unsigned int b = 5;
if (b - a < 0) {
   
	...
}

分析:以为b - a-1,预期会进入到if语句内,实际if判断时不会成立。因为C语言在不同类型运算时,两者占同一级bit位数时,此处都占32位,有符号会提升为无符号数,也即b - a的结果-1(0x 8000 0001)会被视为无符号数,按解析成超大正数2147483649,而UINT_MAX = 2^32 - 1 = 4294967295)。


ascii字符和数字之间的相互转换

int tmp = a[posA] - '0' + b[posB] - '0' + carry;
res.push_back(tmp % 2 + '0'); 				    // + ‘0’ ,又强制转换成了字符 
res.append((char) tmp % 2 + '0'); 				//注意转换成字符,否则res字符串出来全是空白

// IntToChar
int val = 9;
char ch = 9 + '0';

// CharToInt
char ch = '9';
int val = ch - '0';

常见报错


报错:==43==ERROR AddressSanitizer: heap-buffer-overflow on address…

  • 一般都是下标越界的问题,注意检查下标引用。
  • 对于可能越界的情况,务必要先判断在范围内,再引用。
  • j--时,s[j]引用,j是否小于零。i++时,s[i]是否超出长度。
  • 可能是动态申请的空间大小不足,引用时越界。

报错:AddressSanitizer:DEADLYSIGNAL,详细如下

===42====ERROR:AddressSanitizer: SEGV on unknown address xx. 
The signal is caused by a READ memory access.

分析:可能有如下几点问题

  1. 越界,数组引用超越了左右边界
  2. 无限递归,代码无法正常结束返回
  3. 函数入参及出参返回处理错误

举例详细分析见博客《LeetCode报错:AddressSanitizer:DEADLYSIGNAL详细分析与解决》。

参考资料


  1. 【LeetCode攻略】使用LeetCode刷题时你必须注意的几个点
  2. 【精华帖】关于leetcode刷题详细介绍