LeetCode刷题总结（C语⾔版）
编程总结
每每刷完⼀道题后，其思想和精妙之处没有地⽅记录，本篇博客⽤以记录刷题过程中的遇到的算法和技巧001. 两数之和
给定⼀个整数数组 nums 和⼀个⽬标值 target，请你在该数组中出和为⽬标值的两个整数。
你可以假设每种输⼊只会对应⼀个答案。但是，你不能重复利⽤这个数组中同样的元素。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
typedef struct{
int value;
int pos;
}num_data_t;
//use qsort to sort this nums array
int struct_cmp(const void*arr1,const void*arr2)
{
num_data_t *arr1_tmp =(num_data_t *)arr1;
num_data_t *arr2_tmp =(num_data_t *)arr2;
return(arr1_tmp->value - arr2_tmp->value);
}
int*twoSum(int* nums,int numsSize,int target,int* returnSize){
int*result =NULL;
num_data_t *num_data =NULL;
int left =0;
int right =0;
num_data =(num_data_t *)malloc(numsSize *sizeof(num_data_t));
if(num_data ==NULL){
return result;
}
for(int i =0; i < numsSize; i++){
num_data[i].value = nums[i];
num_data[i].pos  = i;
}
//0. due to need to return position in nums, so arrange a structure
/
/1. sort this nums array
qsort(num_data, numsSize,sizeof(num_data_t), struct_cmp);
left =0;
right = numsSize -1;
//2. use two pointer, and move the left pointer if sums less than targets
while(left < right){
if(num_data[left].value + num_data[right].value > target){
right--;
}
else if(num_data[left].value + num_data[right].value < target){
left++;
}
else if(num_data[left].value + num_data[right].value == target){
result =(int*)malloc(2*sizeof(int));
result[0]= num_data[left].pos;
result[1]= num_data[right].pos;
free(num_data);
*returnSize =2;
return result;
}
}
return result;
}
此题利⽤了qsort先排好顺序后，使⽤移动左右两个指针来进⾏查，当前仅是到⼀对满⾜条件的数组⽽已。算法思想在于，当和⼩于target时，移动left指针，当和⼤于target时，移动right指针，while循环条件是left < right（对撞指针）。
**统计⼀个数中⼆进制表⽰0或者1出现的个数⽅法
075. 颜⾊分类法：
给定⼀个包含红⾊、⽩⾊和蓝⾊，⼀共 n 个元素的数组，原地对它们进⾏排序，使得相同颜⾊的元素相邻，并按照红⾊、⽩⾊、蓝⾊顺序排列。
此题中，我们使⽤整数 0、 1 和 2 分别表⽰红⾊、⽩⾊和蓝⾊
本题由于是特殊 0 1 2 处理即可，可以不使⽤qsort来进⾏排序。具体做法是先使⽤桶排序对 0 1 2 的数进⾏计算，然后在nums上直接进⾏填数，时间复杂度是：O(n)，需要遍历⼀次数组，空间复杂度为
O(K)级别，K为3（即需要⼀个桶来对整数0-2进⾏排序，本题使⽤count[2]这样⼀个数组）
void sortColors(int*nums,int numsSize){
int count[3]={0};
int i =0;
int j =0;
// 借助桶排序，计算有多少个0/1/2
for(i =0; i < numsSize; i++){
if(nums[i]>2){
printf("inputs error");
}
count[nums[i]]++;
}
//将计算好后的0-1-2的个数，回填⾄nums数组
for(i =0; i < count[0]; i++){
nums[j]=0;
j++;
}
for(i =0; i < count[1]; i++){
nums[j]=1;
j++;
}
for(i =0; i < count[2]; i++){
nums[j]=2;
j++;
}
}
283. 移动零
给定⼀个数组 nums，编写⼀个函数将所有 0 移动到数组的末尾，同时保持⾮零元素的相对顺序。
输⼊: [0,1,0,3,12]
输出: [1,3,12,0,0]
//法⼀：将数组⾮零值拷贝⾄⼀个新的数组，时间复杂度：O(n)，空间复杂度:O(n)
//法⼆：[0.......k)为存放⾮零的位置, [k,numsSize]为存放0
void moveZeroes(int*nums,int numsSize){
int k =0;//[0.......k)为存放⾮零的位置, [k,numsSize]为存放0
int i =0;
//遍历⼀次数组，将⾮零值都移动到[0,k)⾥
for(i =0; i < numsSize; i++){
if(nums[i]!=0){
c语言编程小游戏
nums[k]= nums[i];
k++;
}
}
//将超过k值的，赋值为0，[k, numsSize] 为0
for(i = k; i < numsSize; i++){
nums[i]=0;
}
return;
}
125. 验证回⽂串
给定⼀个字符串，验证它是否是回⽂串，只考虑字母和数字字符，可以忽略字母的⼤⼩写。
说明：本题中，我们将空字符串定义为有效的回⽂串。
⽰例 1:
输⼊: “A man, a plan, a canal: Panama”
输出: true
⽰例 2:
输⼊: “race a car”
输出: false
解题思路，利⽤对撞指针，不过由于需要处理字符，可以先处理好⼤写字母转换为⼩写后和空格后，再利⽤对撞指针处理即可。580. 连续⼦区间和
题⽬描述
给⼀串含有c个正整数的数组, 求出有多少个下标的连续区间, 它们的和⼤于等于x。
解答要求
时间限制：1000ms, 内存限制：64MB
输⼊
第⼀⾏两个整数c x（0 < c <= 1000000, 0 <= x <= 100000000)
第⼆⾏有c个正整数（每个正整数⼩于等于100)。
输出
输出⼀个整数，表⽰所求的个数。
样例
输⼊样例 1 复制
3 6
2 4 7
输出样例 1
4
本题是利⽤双指针来实现，思路清晰， 但是 index1 和 index2 都只需要遍历⼀次即可，不需要回退，只要涵盖了回退操作，都不是最优解。另外，注意如果是 输出数字，有可能需要输出%ld的情况。
printf("%ld", result);
unsigned long calcSum1(unsigned int*num,unsigned int n,unsigned int m)
{
unsigned int  index1 =0;
unsigned int  index2 =0;
unsigned long sum  = num[0];
unsigned long count  =0;
unsigned long result  =0;
// 最直接能想到的⽅法：遍历两次数组 O(n^2)，但是其中有很多可以优化的地⽅
for(index1 =0; index1 <= n; index1++){
count =0;
count = num[index1];
for(index2 = index1 +1; index2 <= n; index2++){
if(count >= m){
result++;
}
count = count + num[index2];
}
}
return result;
}
unsigned long calcSum2(unsigned int*num,unsigned int n,unsigned int m)
{
unsigned int  index1 =0;
unsigned int  index2 =0;
unsigned long sum  = num[0];
unsigned long count  =0;
unsigned long result  =0;
for(index1 =0; index1 <= n; index1++){
count =0;
count = num[index1];
for(index2 = index1 +1; index2 <= n; index2++){
if(count >= m){
// 优化1：如果到了超过m的index2 由于数组都是正数，后续数可以不⽤再遍历，直接退出即可                result = result + n - index2 +1;
break;
}
count = count + num[index2];
}
}
return result;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。