【Leecode 随笔】C语言版看了不后悔系列持续更新中。。。

🌈你好呀！我是 山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨

题目一：旋转数组的最小数字

题目描述：

给定一个按非递减顺序排列的数组的一个旋转，编写一个函数来找到旋转数组中的最小元素。你可以假设数组中不存在重复元素。

题目分析：

这个问题可以通过二分查找算法来解决，尽管数组被旋转，但我们可以利用数组的有序性。在旋转点之前的元素都大于旋转点之后的元素。通过比较中间元素与其右侧元素的大小，我们可以确定最小元素是在中间元素的左侧还是右侧。

解题思路：

初始化左右指针，left = 0, right = n-1。
进入循环，当left < right时执行：
计算中间索引 mid = left + (right - left) / 2。
如果arr[mid] > arr[right]，说明最小元素在mid的右侧，更新left = mid + 1。
如果arr[mid] < arr[right]，说明最小元素在mid的左侧或者就是mid本身，更新right = mid。
当循环结束时，left == right，此时就找到了最小元素。

示例代码：

#include <stdio.h>  
  
int findMin(int* nums, int numsSize) {  
    int left = 0, right = numsSize - 1;  
    while (left < right) {  
        int mid = left + (right - left) / 2;  
        if (nums[mid] > nums[right]) {  
            left = mid + 1;  
        } else {  
            right = mid;  
        }  
    }  
    return nums[left];  
}  
  
int main() {  
    int nums[] = {4, 5, 6, 7, 0, 1, 2};  
    int numsSize = sizeof(nums) / sizeof(nums[0]);  
    int min = findMin(nums, numsSize);  
    printf("The minimum element is: %d\n", min);  
    return 0;  
}

题目二：三数之和

题目描述：

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

题目分析：

这个问题可以通过双指针法解决。首先，对数组进行排序，然后固定一个数，利用双指针在剩余数组中查找两个数之和为相反数。

解题思路：

对数组进行排序。
遍历数组，对于每个元素nums[i]：
如果当前元素大于0，由于数组已排序，则后面的元素都大于0，不可能存在三数之和为0，直接返回结果。
如果当前元素与上一个元素相同，则跳过，以避免重复解。
设置两个指针left = i + 1, right = n - 1，在[left, right]范围内查找满足nums[i] + nums[left] + nums[right] = 0的解。
如果三数之和大于0，则移动右指针right向左。
如果三数之和小于0，则移动左指针left向右。
如果找到满足条件的解，则保存结果，并移动left和right指针，同时跳过重复元素。

示例代码：

#include <stdio.h>  
#include <stdlib.h>  
  
int cmp(const void *a, const void *b) {  
    return (*(int *)a - *(int *)b);  
}  
  
void threeSum(int* nums, int numsSize, int** returnSize, int** returnColumnSizes, int** result) {  
    *returnSize = 0;  
    if (numsSize < 3) return;  
    qsort(nums, numsSize, sizeof(int), cmp);  
    int left, right;  
    for (int i = 0; i < numsSize - 2; i++) {  
        if (nums[i] > 0) break;  
        if (i > 0 && nums[i] == nums[i - 1]) continue;  
        left = i + 1;  
        right = numsSize - 1;  
        while (left < right) {  
            int sum = nums[i] + nums[left] + nums[right];  
            if (sum == 0) {  
                result[*returnSize] = (int *)malloc(3 * sizeof(int));  
                result[*returnSize][0] = nums[i];  
                result[*returnSize][1] = nums[left];  
                result[*returnSize][2] = nums[right];  
                (*returnColumnSizes)[*returnSize] = 3;  
                (*returnSize)++;  
                while (left < right && nums[left] == nums[left + 1]) left++;  
                while (left < right && nums[right] == nums[right - 1]) right--;  
                left++;  
                right--;  
            } else if (sum < 0) {  
                left++;  
            } else {  
                right--;  
            }  
        }  
    }  
}  
  
int main() {  
    int nums[] = {-1, 0, 1, 2, -1, -4};  
    int numsSize = sizeof(nums) / sizeof(nums[0]);  
    int returnSize, *returnColumnSizes = malloc(1000 * sizeof(int));  
    int **result = malloc(1000 * sizeof(int *));  
    threeSum(nums, numsSize, &returnSize, &returnColumnSizes, &result);  
    for (int i = 0; i < returnSize; i++) {  
        for (int j = 0; j < returnColumnSizes[i]; j++) {  
            printf("%d ", result[i][j]);  
        }  
        printf("\n");  
    }  
    // 释放动态分配的内存  
    // ...  
    return 0;  
}

题目三：接雨水

题目描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

题目分析：

这个问题可以通过双指针法解决。关键在于，对于每个位置，我们需要找到其左边和右边的最高柱子，然后计算该位置能接多少雨水。为了避免重复计算，我们可以从两边向中间移动指针，同时记录当前遇到的最大高度。

解题思路：

初始化左右指针 left = 0, right = n-1，以及两个变量来记录左右指针遇到的最大高度。
进入循环，当left < right时执行：
如果左边最大高度小于右边最大高度，说明左边边界限制了当前位置的水量，更新left，并计算水量。
否则，更新right，并计算水量。
更新左右指针遇到的最大高度。
循环结束时，累加的水量即为结果。

示例代码：

#include <stdio.h>  
  
int trap(int* height, int heightSize) {  
    if (heightSize == 0) return 0;  
    int left = 0, right = heightSize - 1;  
    int leftMax = 0, rightMax = 0;  
    int water = 0;  
    while (left < right) {  
        if (height[left] < height[right]) {  
            if (height[left] >= leftMax) {  
                leftMax = height[left];  
            } else {  
                water += leftMax - height[left];  
            }  
            left++;  
        } else {  
            if (height[right] >= rightMax) {  
                rightMax = height[right];  
            } else {  
                water += rightMax - height[right];  
            }  
            right--;  
        }  
    }  
    return water;  
}  
  
int main() {  
    int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};  
    int heightSize = sizeof(height) / sizeof(height[0]);  
    int water = trap(height, heightSize);  
    printf("The amount of trapped water is: %d\n", water);  
    return 0;  
}

---

✨ 这就是今天要分享给大家的全部内容了，我们下期再见！😊
🏠 我在CSDN等你哦！我的主页😍

原文地址：https://blog.csdn.net/shiranyyds/article/details/142629103

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！