hot100|普通数组|C语言

53. 最大子数组和 – 力扣（LeetCode）

贪心

int maxSubArray(int* nums, int numsSize) {
    if(numsSize==1){
        return nums[0];
    }
    // 贪心
    int res=INT_MIN;
    int sumCur=0;
    for(int i=0;i<numsSize;++i){
        sumCur+=nums[i];
        res=fmax(res,sumCur);
        // 舍弃为负数的前缀和
        sumCur=fmax(sumCur,0);
    }
    return res;
}

56. 合并区间 – 力扣（LeetCode）

排序 内存管理

待补充

189. 轮转数组 – 力扣（LeetCode）

分解为基本操作：循环移位->三次逆置

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

// 逆置
void reverse(int *nums,int left,int right){
    while(left<right){
        swap(&nums[left++],&nums[right--]);
    }
    return;
}

void rotate(int* nums, int numsSize, int k) {
    if(numsSize==1){
        return;
    }
    // 易错 处理k>n
    k=k%numsSize;
    // 三次逆置实现循环右移
    reverse(nums,0,numsSize-1);
    reverse(nums,0,k-1);
    reverse(nums,k,numsSize-1);
    return;
}

238. 除了自身以外数组的乘积 – 力扣（LeetCode）

预处理：前缀与后缀乘积列表

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    *returnSize=numsSize;
    // 内存分配
    int *res=(int *)malloc((*returnSize)*sizeof(int));
    if(res==NULL){
        *returnSize=0;
        return NULL;
    }
    // 预处理：后缀乘积列表
    res[numsSize-1]=1;
    for(int i=numsSize-2;i>=0;--i){
        res[i]=res[i+1]*nums[i+1];
    }
    // 求除了自身外数组的乘积
    int mulLeft=1;
    for(int i=0;i<numsSize;++i){
        res[i]*=mulLeft;
        mulLeft*=nums[i];
    }

    return res;
}

预处理：后缀乘积列表

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    *returnSize=numsSize;
    // 内存分配
    int *res=(int *)malloc((*returnSize)*sizeof(int));
    if(res==NULL){
        *returnSize=0;
        return NULL;
    }
    // 预处理：后缀乘积列表
    res[numsSize-1]=1;
    for(int i=numsSize-2;i>=0;--i){
        res[i]=res[i+1]*nums[i+1];
    }
    // 求除了自身外数组的乘积
    int mulLeft=1;
    for(int i=0;i<numsSize;++i){
        res[i]*=mulLeft;
        mulLeft*=nums[i];
    }

    return res;
}

41. 缺失的第一个正数 – 力扣（LeetCode）

哈希表

int firstMissingPositive(int* nums, int numsSize) {
    // 哈希表
    int isExist[numsSize+2];
    for(int i=0;i<numsSize+2;++i){
        isExist[i]=0;
    }
    for(int i=0;i<numsSize;++i){
        int cur=nums[i];
        if(cur>=1 && cur<numsSize+2){
            isExist[cur]=1;
        }
    }
    int res;
    for(int i=1;i<numsSize+2;++i){
        if(isExist[i]==0){
            res=i;
            break;
        }
    }
    return res;
}

原地置换

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

int firstMissingPositive(int* nums, int numsSize) {
    // 原地置换
    for(int i=0;i<numsSize;++i){
        while(nums[i]>0 && nums[i]<=numsSize
                && nums[nums[i]-1]!=nums[i]){
            swap(&nums[i],&nums[nums[i]-1]);
        }
    }
    int res=numsSize+1;
    for(int i=0;i<numsSize;++i){
        if(nums[i]!=i+1){
            res=i+1;
            break;
        }
    }
    return res;
}