hot100|技巧|C语言

作者

每道题的题解将包含两类可直接通过评测的代码：

一类是暴力解 / 过渡优化解（适配初次解题时无法直接想到最优解的场景），另一类是最优解。

136. 只出现一次的数字 – 力扣（LeetCode）

1.快速排序

// 交换
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[i],&nums[left]);
    quickSort(nums,left,i-1);
    quickSort(nums,i+1,right);
    return;
}

int singleNumber(int* nums, int numsSize) {
    if(numsSize==1){
        return nums[0];
    }
    // 快速排序
    quickSort(nums,0,numsSize-1);
    // 只出现一次的数字是最值
    if(nums[0]!=nums[1] && nums[1]==nums[2]){
        return nums[0];
    }else if(nums[numsSize-1]!=nums[numsSize-2]
            && nums[numsSize-2]==nums[numsSize-3]){
        return nums[numsSize-1];
    }
    // 只出现一次的数字不是最值
    int res;
    for(int i=1;i<=numsSize-2;++i){
        if(nums[i-1]!=nums[i] && nums[i]!=nums[i+1]){
            res=nums[i];
            break;
        }
    }
    return res;
}

2.位运算

int singleNumber(int* nums, int numsSize) {
    int res=0;
    // 位运算
    for(int i=0;i<numsSize;++i){
        res^=nums[i];
    }
    return res;
}

169. 多数元素 – 力扣（LeetCode）

1.快速排序（需要剪枝等优化）

// 交换函数（不变）
void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}

// 三数取中法：选左、中、右的中位数作为基准值，避免极端情况退化
int medianOfThree(int *nums, int left, int right) {
    int mid = left + (right - left) / 2;
    // 调整顺序：让nums[left] <= nums[mid] <= nums[right]
    if (nums[left] > nums[mid]) swap(&nums[left], &nums[mid]);
    if (nums[left] > nums[right]) swap(&nums[left], &nums[right]);
    if (nums[mid] > nums[right]) swap(&nums[mid], &nums[right]);
    // 把中位数放到left位置（作为基准值）
    swap(&nums[left], &nums[mid]);
    return nums[left];
}

// 快速选择：找数组中第k小的元素（k从0开始）
int quickSelect(int *nums, int left, int right, int k) {
    if (left == right) return nums[left]; // 只有一个元素，直接返回
    
    // 优化1：三数取中法选基准值（替代原左边界基准值）
    int p = medianOfThree(nums, left, right);
    int i = left, j = right;
    
    // 快排分区逻辑（不变）
    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[i], &nums[left]); // 基准值归位
    
    // 优化2：只递归处理包含k的一侧（无需处理两侧）
    if (i == k) {
        return nums[i]; // 找到第k小元素，直接返回
    } else if (i < k) {
        return quickSelect(nums, i+1, right, k); // 目标在右侧，递归右侧
    } else {
        return quickSelect(nums, left, i-1, k); // 目标在左侧，递归左侧
    }
}

int majorityElement(int* nums, int numsSize) {
    if (numsSize == 1) return nums[0];
    // 找第numsSize/2小的元素（即中位数，就是多数元素）
    int k = numsSize / 2;
    return quickSelect(nums, 0, numsSize-1, k);
}

2.贪心/Moore投票法

int majorityElement(int* nums, int numsSize) {
    if(numsSize==1){
        return nums[0];
    }
    //  贪心 Moore投票法
    int res;
    int tmp=nums[0];
    int cnt=0;
    for(int i=0;i<numsSize;++i){
        if(tmp==nums[i]){
            ++cnt;
        }else{
            --cnt;
        }
        if(cnt<0){
            cnt=0;
            tmp=nums[i];
        }
    }
    res=tmp;
    return res;
}

75. 颜色分类 – 力扣（LeetCode）

1.哈希表

void sortColors(int* nums, int numsSize) {
    // 哈希表
    int cnt[3]={0};
    for(int i=0;i<numsSize;++i){
        ++cnt[nums[i]];
    }
    // 更新
    int idx=0;
    for(int i=1;i<=cnt[0];++i){
        nums[idx++]=0;
    }
    for(int i=1;i<=cnt[1];++i){
        nums[idx++]=1;
    }
    for(int i=1;i<=cnt[2];++i){
        nums[idx++]=2;
    }
    return;
}

2.相向双指针

// 交换
void swap(int *x,int *y){
    int tmp=*x;
    *x=*y;
    *y=tmp;
}

void sortColors(int* nums, int numsSize) {
    // 相向双指针
    int left=0;
    int right=numsSize-1;
    for(int i=0;i<=right;++i){
        while(i<=right && nums[i]==2){
            swap(&nums[i],&nums[right--]);
        }
        if(nums[i]==0){
            swap(&nums[i],&nums[left++]);
        }
    }
}

31. 下一个排列 – 力扣（LeetCode）

1.八股题

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

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

void nextPermutation(int* nums, int numsSize) {
    // 从后向前查找第一个顺序对a[i]<a[i+1] 
    int i=numsSize-2;
    while(i>=0 && nums[i]>=nums[i+1]){
        --i;
    }
    // 从后向前查找第一个较大数a[j]>a[i]
    if(i>=0){
        int j=numsSize-1;
        while(j>=0&&nums[i]>=nums[j]){
            --j;
        }
        // 交换a[i]与a[j]
        swap(&nums[i],&nums[j]);
    }
    // 反转a[i+1]~a[n-1]
    reverse(nums,i+1,numsSize-1);

    return;
}

287. 寻找重复数 – 力扣（LeetCode）

1.哈希表

int findDuplicate(int* nums, int numsSize) {
    if(numsSize==1){
        return nums[0];
    }
    // 哈希表
    int *cnt=(int *)calloc(numsSize,sizeof(int));
    if(cnt==NULL){
        return -1;
    }
    for(int i=0;i<numsSize;++i){
        ++cnt[nums[i]];
    }

    int res;
    for(int i=1;i<=numsSize-1;++i){
        if(cnt[i]>1){
            res=i;
        }
    }
    return res;
}

2.快慢双指针

int findDuplicate(int* nums, int numsSize) {
    // 快慢双指针
    int slow=0,fast=0;
    do{
        slow=nums[slow];
        fast=nums[nums[fast]];
    }while(slow!=fast);
    int res=0;
    while(slow!=res){
        slow=nums[slow];
        res=nums[res];
    }
    return res;
}

发表评论