科软机试日常 - leetcode注意事项与C语言技巧

分类:热门推荐日期:2024-04-12浏览:1评论:0

目录

  • 一、科软机试注意事项
  • 二、leetcode注意事项
    • 1. returnSize和returnColumnSize
    • 2. 其他注意事项
    • 三、C语言小技巧
      • 1. 数组初始化
      • 2. 功能强大的sprintf函数和sscanf函数
      • 3. 快速排序库函数
      • 4. 二分查找库函数
      • 5.哈希表
      • 6.栈
      • 7.队列
      • 8.其他
        • 8.1 判断字符是否是数字
        • 8.2 整型最大值
        • 四、力扣常见报错
        • 总结

          一、科软机试注意事项

          • 在待完成的注释处写代码完成函数，main函数中的printf用于测试
          • 函数中不要加注释，否则会随机报错，你找半天都找不出哪里出错
          • 好好检查for循环和递归，死循环死递归直接卡2分钟把你心态搞崩
          • oi赛制，按照测试用例给分，一道题5个测试用例，一个用例5分，考试时不会告诉你提交的代码通过几个用例，只能自己调试
          • 只要时间复杂度不是太过分（指数级别）,则一般能拿全分
          • 能不能加头文件，不好说，有人说能有人说不能，个人觉得只要在线编译能通过就能用

            二、leetcode注意事项

            1. returnSize和returnColumnSize

            • 如果返回值是一个一维数组的话，必定出现returnSize，它是一个int类型的指针，其指向的地址单元保存了数组中元素个数，*returnSize = 2表示返回值数组中元素的个数为2
            • 如果返回值是一个二维数组的话，就必定同时出现returnSize和returnColumnSizes，returnSize是一个一级指针，其指向的地址保存的内容是二维数组的行数，returnColumnSizes是一个一维指针数组，保存返回值中各行的一维数组中元素个数
            • returnColumnSize不能用memset赋值，而且用for循环赋值时(*returnColumnSizes)必须加括号 
              *returnSize = 3;	//二维数组行数为3
*returnColumnSizes = (int*)malloc(3*sizeof(int));	//需要3个单元来记录各行元素个数
(*returnColumnSizes)[0] = 2;	//二维数组第0行有2个元素
(*returnColumnSizes)[1] = 3;	//第1行有3个元素
(*returnColumnSizes)[2] = 4;	//第2行有4个元素

              2. 其他注意事项

              • 一定要注意输入元素为NULL等情况，我经常在这里犯错
              • 链表最后一个节点的next指针置为NULL，否则会报错
              • 在循环中定义数组（静态），编译器不会重复创建这个数组，因此不用担心内存爆炸的问题
              • leetcode中返回的数组必须使用动态分配内存的数组，也就是必须要malloc
              • 在开始编码前要考虑到各种极端情况（如爆int），所以我默认都定义long long类型就不容易出错哈哈哈，或者习惯上把减法放在加法前面
              • 整数最大值为INT_MAX = 0x7FFFFFFF，最小值为INT_MIN = 0x80000000，学过计算机组成原理应该容易理解
              • 字符串一定要记得有’\0‘，反斜杠0
              • 全局变量必须在main函数中初始化，不要在外面初始化
              • 数组的拷贝：int* arr1 和arr2，拷贝arr2到arr1不是直接给arr1赋值（浅拷贝），而是将arr2的元素挨个赋值给arr1，或者用memcpy(arr1,arr2,sizeof(arr2)/sizeof(int))的方式
              • printf(“%d”,fmin(INT_MIN, INT_MAX));打印结果为0，因为fmim返回double类型

                三、C语言小技巧

                1. 数组初始化

                将数组元素都置0

                #include/*
注意别踩坑：
1.sizeof里面的数组只能是静态数组！！！
2.如果是用malloc分配内存的数组，malloc参数怎么写这里第三个参数就怎么写
3.稍不注意，直接buffer overflow
*/
int buf[255];
memset(buf, 0, sizeof(buf));//静态数组初始化
int* buf2 = (int*)malloc(255*sizeof(int));
memset(buf2,0,255*sizeof(int));//动态数组初始化

                坑2： memset是按照一个字节一个字节赋值的，赋值char类型的数据永远不会出错，但是如果赋值超过1个字节的数据则有可能出现读取错误，因此初始化非char类型数组时，只能赋值为0或-1

                2. 功能强大的sprintf函数和sscanf函数

                #includechar str[200];
//sprintf和printf效果一样，只不过一个输出到控制台，一个输出到数组中
//结合两函数可以轻松实现进制转换与字符串与数字之间转换
//注意C语言没有二进制的格式化方法，转为2进制需要自己写了
sprintf(str,"%d",12345); //12345转为10进制字符串
sprintf(str,"%x",1234); //转16进制
sprintf(str,"%o",1234); //转8进制
sprintf(str,"%d",0b10000000);	//2进制转10进制
//sscanf函数和scanf效果一样，只不过一个是键盘读入数据一个是从字符串读入数据
int dest;
char* str= "123";
//sprintf是将第三个参数转换后送给第一个参数，sscanf参数是将第一个参数转换送送给第三个参数
//和scanf一样要加&，不然报错！！！
sscanf(str,"%d",&dest);
//二者区别就像printf和scanf的区别

                感谢好友的补充：

                • 对于超出整型范围的字符串的字符串，sscanf会将该字符串转换为该整型类型的最大值或最小值

                  3. 快速排序库函数

                  • 快速排序时间复杂度为 O ( n l o g 2 n ) O(nlog_2 n) O(nlog2​n)
                  • cmp比较函数需要自己写 
                    #include//cmp比较函数需要自己写！
/*
形参为void*的意思是能接收所有类型的数据
返回值将void*强制转换为(int*)然后*(int*)是指针指向的值
a - b是升序排序，b - a是降序排序
*/
/**
 *写成这样唯一不好的一点是：如果a-b的值超出int范围了
 *排序就会失败（改long long没用，qsort只接受返回值为
 *int类型的函数）
*/
int cmp(const void* a, const void* b){ return *((int*)a) - *((int*)b);
}
//这样写就可以避免溢出问题，是一个完美的排序函数，降序只需要将大于号改成小于号
int cmp(const void* a,const void* b){return !(*(int*)a==*(int*)b) && *(int*)a > *(int*)b ? 1 : -1;
}
int arr[] = {-5,-3,6,0,0,-4,6,7,-9};
qsort(arr, len, sizeof(int), cmp);
                    • 扩展：成绩按从低到高排序，如果成绩相同则按学号大小排序
                    • 提交网址：成绩排序（清华大学复试上机题） 
                      #include #includestruct stu { int id;
    int score;
};
int cmp(struct stu* s1, struct stu* s2){ if((*s1).score==(*s2).score){ return (*s1).id-(*s2).id;
    }
    return (*s1).score - (*s2).score;
}
int main() { int n;
    struct stu* s;
    while (scanf("%d", &n) != EOF) { s = (struct stu*)malloc(n * sizeof(struct stu));
        int i, j;
        for (i = 0; i < n; i++)
            scanf("%d %d", &s[i].id, &s[i].score);
        qsort(s,n,sizeof(struct stu),cmp);
        for(i=0;i printf("%d %d\n",s[i].id,s[i].score);
        }
    }
    return 0;
}

                      4. 二分查找库函数

                      #include#include //bsearch函数是stdlib头文件中的函数
//和qsort的cmp一模一样
int cmp(const void* a, const void* b){ return *(int*)a - *(int*)b;
}
/*
参数一：目标值的地址
参数二：数组首地址
参数三：要查找的长度
参数四：函数指针cmp
返回值：目标值的地址，用该地址减去数组首地址就是目标值的下标，若目标值不存在则返回NULL
注意：数组必须有序，刷力扣时尽量少用库函数，避免知其然而不知其所以然
*/
int main() { int nums[] = {123, 145, 512, 627, 800, 933,0};
  int key = 512;
  int len = 6;
  int* index = bsearch(&key,nums,len,sizeof(int),cmp);
  if(index)
    printf("%d\n",index-nums);
  return 0;
}

                      //自己写也很简单，不要太迷恋库函数
int search(int* nums, int numsSize, int target) {int left = 0, right = numsSize - 1;
	while(left<=right){int mid = (right-left)/2 + left;	//避免爆int
		if(nums[mid]==target)
			return mid;
		else if(nums[mid]>target)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
}

                      5.哈希表

                      在leetcode中经常需要用到用到键值对索引的情况，但是C语言中并没有哈希表的数据结构，但是可以用数组下标来模拟

                      int hashTable[130];
memset(hashTable, 0, sizeof(hashTable);	//注意#includehashTable['A'] = 1;		//就像<'A', 1>键值对一样

                      6.栈

                      leetcode中dfs、括号匹配、中缀表达式转后缀表达式问题中经常需要使用到栈，但是C语言中没有栈这个数据结构，但是我们可以用数组来模拟

                      int stack[10005];	//容量尽可能定义大一点
int top = 0;		//栈顶元素
stack[top++] = 2;	//将2压入栈
int tmp = stack[--top];//弹栈

                      7.队列

                      leetcode中bfs等题目中需要用到队列，C语言中也没有队列这个数据结构，和栈一样，我们仍然可以用数组来模拟

                      int queue[10005];
int front = 0, rear = 0;
queue[rear++] = 2;	//入队
int tmp = queue[front++];//出队

                      8.其他

                      8.1 判断字符是否是数字

                      #includeint isdigit(int c);	//如果c是数字，则返回非0整数，否则返回0
//记不住直接这样写
if(ch>='0'&&ch<='9')

                      8.2 整型最大值

                      注意：int范围和long范围一样，在机试中一定要用long long类型

                      #include#includeint M1 = INT_MAX;
int m1 = INT_MIN;	//其他类型同理
long long mm1 = LONG_LONG_MAX;
//也可以这么写，注意有的编译器可能会报错，报错的话把后面的H去掉
int M2 = 0x7fffffffH;
int m2 = 0x80000000H;
int main(){printf("%d\n",M1);
	printf("%d\n",m1);
	printf("%ld\n",LONG_MAX);
	printf("%lld\n",mm1);
	return 0;
}

                      四、力扣常见报错

                      错误提示1：

                      ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6160000002d8 at pc 0x556c2692357e bp 0x7ffca71fc0d0 sp 0x7ffca71fc0c0

                      调试：科软机试只能用printf查看自己程序哪里错了，所以要多写printf，可以很快找到自己的程序哪里出错了

                      错误原因：使用了未分配的空间，数组越界。

                      • 数组定义的空间不够大，导致越界，我还使用了sizeof(arr)导致错上加错，要注意sizeof()只能求静态数组的空间大小，malloc分配内存的数组sizeof()统一会返回8。
                      • memset函数报错，memset(arr,0 ,sizeof(arr);，如果arr是静态数组就可以这么初始化，如果这个arr是malloc动态分配内存的数组，sizeof默认返回8，所以就报数组越界错了，第三个参数最好是前面malloc里面怎么写这个就怎么写
                      • int* ans = (int*)malloc(len1*sizeof(char));sizeof里面int误写成char

                        错误提示2：

                        Line 25: Char 39: runtime error: store to address 0x62e00059e040 with insufficient space for an object of type 'struct TreeNode *' [solution.c]

                        错误原因：给数组分配的内存空间不够

                        • (struct TreeNode**)malloc(10000*sizeof(int));把sizeof(struct TreeNode*)写成了sizeof(int)，导致分配的内存空间不够

                          错误提示3：

                          Line 26: Char 17: runtime error: shift exponent -1 is negative [solution.c]

                          错误原因：位运算移位的位数只能是非负整数

                          • 2<<0 - 1，由于位运算优先级非常低，该表达式会优先进行减法运算，因此导致移位负数，因此需要给位运算加括号，改成 (2<<0) - 1

                            错误提示4：

                            Line 96: Char 17: runtime error: member access within misaligned address 0xbebebebebebebebe for type 'struct TreeNode', which requires 8 byte alignment [TreeNode.c] 0xbebebebebebebebe: note: pointer points here

                            错误原因： 二叉树节点左子树与右子树没有初始化为NULL，或链表末尾没有指向NULL

                            错误提示5：

                            AddressSanitizer:DEADLYSIGNAL ==21==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x7ff25e341149 bp 0x7ffd63421960 sp 0x7ffd63421260 T0)

                            错误原因： scanf或者sscanf没加&

                            错误提示6

                            测试样例单独测试都能通过，但是放到一起测试却显示报错

                            错误原因： 代码中有全局变量没有初始化，或者没有写*returnSize = 0;

                            总结

                            本文主要是使用纯C编程完成leetcode中题目的小技巧和注意事项。暂时先更新这么多了，更多细节需要等我慢慢踩坑

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号