LeetCode入门(C)

LeetCode题解

欢迎补充。

函数的使用

1. LeetCode参数名的含义：
   1. int* nums，表示nums[]数组。
   2. int numsSize，表示nums数组第一维的大小。
      • 在C中，指针无法得出数组长度，因此需要numsSize辅助。
      • 见：stackoverflow热门问题（二）- 如何确定C的数组的大小
   3. int* returnSize，表示作为函数返回值的数组的第一维大小。
      • 如果返回的数组长度为2，则需要*returnSize = 2
        • 否则输出会是 ]，正确输出应该是 [num1, num2]
      • 同理，例如int** returnColumnSizes，就是指第一维中每个数组元素的长度。
2. 函数中必须的结构：
   1. 返回值为数组的，*returnSize需要赋值，类似的，形如*returnXXX的指针均需赋值，否则输出会有问题。
   2. 有返回值的，函数结尾必须要有return result;
      • 否则报错：error: control reaches end of non-void function

数组/链表指针的使用

1. 定义一个int类型的指针array：
   • int* array;
   • 一般定义指针来分配数组，可根据输入定义不同大小的数组，且可使用realloc()改变数组空间大小。
     • int array[2]的数组大小不可改变，且int array[n]是非法的。
     • 未分配空间且为指向数组的指针无法被当做数组使用，会报错。
2. 为array指针分配长度为n的空间：
   • array = malloc(sizeof(int) * n);
   • malloc()用来分配空间，参数为空间大小。
   • sizeof()用来获得某类型占用空间的大小。
   • 所以，上面的代码，实际上就是用malloc()函数，给array指针分配n个int类型的空间。
3. array数组指针的使用：
   1. array[i]，如数组一样使用。
   2. *(array + i)，效果如上。
   3. i[array]，比较奇怪，但的确能用。
      • 见stackoverflow热门问题（一）-为什么数组的a[5] == 5[a]？
   4. *array++ / *++array，可以用于遍历一个数组，指针将指向停下来的地址。
4. 为array数组指针增加空间：
   • array = realloc(array, sizeof(int) * (arraySize + newSize));
     • 其中，arraySize表示array原本的数组长度，newSize表示新增加的长度。
   • realloc()能在原本的地址上，改变指针占用的空间。
     • 即用了这个函数，地址不会改变，但可以增加或减少空间。
   • realloc()只能用在malloc()分配的函数，不能用于int array[]。
   • 但它用在LeetCode时会造成大量内存消耗。
5. 访问*node结点内容时，需要先判断结点非空：
   • 如node->next->value = 1;，需要改成if(node && node->next) node->next->value = 1;
     • 否则报错：member access within null pointer of type 'struct ListNode'

错误信息

1. error: control reaches end of non-void function
   • 函数结尾需要加上return语句。
   • 见函数的使用-第二点。
2. error: member access within null pointer of type 'struct ListNode'
   • 访问指针结点时需要先对其判空。
   • 见数组/链表指针的使用-第五点。
3. error: AddressSanitizer: heap-buffer-overflow on address...
   1. 指针申请的空间小了。
      • 可以将申请的空间改的特别大，如果不再提示，说明是空间申请有问题。
   2. 越界访问了。
      • 可以对每次访问该指针的语句后，加上一个printf输出相关信息，来判断错误位置。
      • 如果输出了太多行，显示不全，就加个判断，只输出特定位置的信息。
4. 这里暂时只提到了几个典型的，欢迎补充。

提高效率排名

1. 多提交几遍。
   • 看似愚蠢但非常有效的方法。
2. 不使用realloc函数动态分配空间。
   • 见数组/链表指针的使用-第四点。
3. 改进算法。这个就得多看了，这里举几个简单算法思想：
   1. 二分法：搜索有序数组的时候可以用，根据中间值与目标值的大小情况，进行下一次的搜索。
      • 见：二分搜索及其于不同场景的应用(C/Java/Python)
   2. 双指针：头部设一个指针，尾部设一个指针，向中间移动。
      • 或者两个指针都在头部，向尾部移动。
      • 或者两个指针同时移动，这个也被叫做滑动窗口。
      • 见：“双指针”的搜索结果 - MWHLS' blog
   3. 原地操作：不增设额外空间，直接在传参的数组空间上操作。
      • 做完题的时候，可以看一下对新分配空间的使用，能否迁移到参数的数组中。
      • 见：LeetCode-中等-71-简化路径-栈/双指针/原地解决(C)
   4. 排序：对无序数组排序完再用二分法。
      • 见：快速排序-递归/分治法(C/Java/Python)
      • 即便要求的是数组下标，也可以设一个保存数组下标数组，然后根据其对应值来排序。
      • 见：LeetCode-困难-42-接雨水-双指针/快速排序(C)

文章推荐

1. C语言二级字符串指针的使用(函数传参/长度获取/空间分配)