hot100|双指针|C语言

283. 移动零 – 力扣（LeetCode）

前后双指针

void moveZeroes(int* nums, int numsSize) {
    // 前后双指针
    int left=0,right=0;
    // 非零元素前移
    while(right<numsSize){
        if(nums[right]!=0){
            nums[left++]=nums[right];
        }
        ++right;
    }
    // 置零
    while(left<numsSize){
        nums[left++]=0;
    }
    return;
}

11. 盛最多水的容器 – 力扣（LeetCode）

相向双指针 贪心

int maxArea(int* height, int heightSize) {
    // 相向双指针
    int left=0,right=heightSize-1;
    int res=INT_MIN;
    while(left<right){
        int cur=(right-left)
            *fmin(height[left],height[right]);
        if(cur>res){
            res=cur;    
        }
        // 贪心
        // 每次移动短板 容量才有可能变大
        if(height[left]<height[right]){
            ++left;
        }else{
            --right;
        }
    }
    return res;
}

15. 三数之和 – 力扣（LeetCode）

相向双指针 快速排序 贪心 去重 剪枝 C语言内存分配

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

// 交换
void swap(int *a,int *b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
    return;
}

// 快排
void quickSort(int *nums,int left,int right){
    if(left>=right) return;
    int i=left,j=right;
    int p=nums[left];
    while(i<j){
        while(i<j && nums[j]>=p) --j;
        while(i<j && nums[i]<=p) ++i;
        if(i<j) swap(&nums[i],&nums[j]);
    }
    swap(&nums[left],&nums[i]);
    quickSort(nums,left,i-1);
    quickSort(nums,i+1,right);
    return;
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 边界处理
    if(numsSize<3){
        *returnSize=0;
        return NULL;
    }
    // 快速排序
    quickSort(nums,0,numsSize-1);
    // 预分配内存
    int **result=(int **)malloc(20000*sizeof(int *));
    *returnColumnSizes=(int *)malloc(20000*sizeof(int));
    int cnt=0;
    // 固定第一个数
    for(int i=0;i<numsSize-2;++i){
        // 剪枝
        if(nums[i]>0){
            break;
        }
        // 去重 第一个数
        if(i>0 && nums[i]==nums[i-1]){
            continue;
        }
        int target=-nums[i];
        // 相向双指针
        int left=i+1;
        int right=numsSize-1;
        while(left<right){
            int sum=nums[left]+nums[right];
            // 保存结果
            if(target==sum){
                result[cnt]=(int *)malloc(3*sizeof(int));
                result[cnt][0]=nums[i];
                result[cnt][1]=nums[left];
                result[cnt][2]=nums[right];
                (*returnColumnSizes)[cnt]=3;
                ++cnt;
            // 去重
            // 左指针
            while(left<right && nums[left]==nums[left+1]){
                ++left;
            }
            // 右指针
            while(left<right && nums[right]==nums[right-1]){
                --right;
            }
            ++left;
            --right;
            }else if(sum<target){
                ++left;
            }else{
                --right;
            }
        }
    }
    // 调整内存
    *returnSize=cnt;
    if(cnt>0){
        result=(int **)realloc(result,cnt*sizeof(int *));
        *returnColumnSizes=(int *)
                    realloc(*returnColumnSizes,cnt*sizeof(int));
    }else{
        free(result);
        free(*returnColumnSizes);
        result=NULL;
        *returnColumnSizes=NULL;
    }
    return result;
}

42. 接雨水 – 力扣（LeetCode）

相向双指针 贪心

int trap(int* height, int heightSize) {
    if(heightSize<=2){
        return 0;
    }
    // 相向双指针
    int res=0;
    int left=0,right=heightSize-1;
    int preMax=0,sufMax=0;
    while(left<right){
        // 贪心 短板对应的微分桶容积可确定
        preMax=fmax(preMax,height[left]);
        sufMax=fmax(sufMax,height[right]);
        if(preMax<sufMax){
            res+=preMax-height[left++];
        }else{
            res+=sufMax-height[right--];
        }
    }
    return res;
}