LeetCode75 Day2

1431.拥有最多糖果的孩子

给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。

示例 1：

1
2
3
4
5
6
7
8
输入：candies = [2,3,5,1,3], extraCandies = 3
输出：[true,true,true,false,true] 
解释：
孩子 1 有 2 个糖果，如果他得到所有额外的糖果（3个），那么他总共有 5 个糖果，他将成为拥有最多糖果的孩子。
孩子 2 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。
孩子 3 有 5 个糖果，他已经是拥有最多糖果的孩子。
孩子 4 有 1 个糖果，即使他得到所有额外的糖果，他也只有 4 个糖果，无法成为拥有糖果最多的孩子。
孩子 5 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。

示例 2：

1
2
3
输入：candies = [4,2,1,1,2], extraCandies = 1
输出：[true,false,false,false,false] 
解释：只有 1 个额外糖果，所以不管额外糖果给谁，只有孩子 1 可以成为拥有糖果最多的孩子。

示例 3：

1
2
输入：candies = [12,1,12], extraCandies = 10
输出：[true,false,true]

提示：

  • 2 <= candies.length <= 100
  • 1 <= candies[i] <= 100
  • 1 <= extraCandies <= 50
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool* kidsWithCandies(int* candies, int candiesSize, int extraCandies, int* returnSize){
    bool *res = (bool *)malloc(candiesSize * sizeof(bool));
    if (res == NULL) {
        return NULL;
    }

    int maxNum = 0;
    *returnSize = 0;
    for (int i = 0; i < candiesSize; ++i) {
        maxNum = maxNum >= candies[i] ? maxNum : candies[i];
    }

    for (int i = 0; i < candiesSize; ++i) {  
        res[(*returnSize)++] = candies[i] + extraCandies >= maxNum ? true : false;
    }

    return res;
}

作者：程序员小熊
链接：https://leetcode.cn/problems/kids-with-the-greatest-number-of-candies/solutions/350142/1431-yong-you-zui-duo-tang-guo-de-hai-zi-c-yu-yan/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  1. 首先，函数接受四个参数：candies 数组表示每个孩子拥有的糖果数量，candiesSize 表示数组的长度，extraCandies 表示额外的糖果数量，returnSize 是一个指向整数的指针，用于存储返回的布尔数组的长度。
  2. 使用 malloc 函数动态分配了一个布尔数组 res，其长度为 candiesSize。如果分配失败，则返回 NULL。
  3. 使用变量 maxNum 记录数组 candies 中的最大值，初始化为 0。
  4. 使用循环遍历数组 candies，找到其中的最大值，并将其赋值给变量 maxNum。
  5. 使用循环遍历数组 candies，对于每个孩子，判断其拥有的糖果数量加上额外的糖果数量是否大于等于最大糖果数量 maxNum。如果是，则表示这个孩子拥有的糖果数量加上额外的糖果数量足以使其成为拥有最多糖果的孩子，将对应位置的布尔数组 res 设为 true；否则设为 false。
  6. 在循环结束后，将 returnSize 的值设为布尔数组 res 的长度，并返回 res。

这段代码的主要逻辑是通过遍历数组两次，第一次找出最大糖果数量，第二次判断每个孩子是否拥有超过其他孩子的糖果数量。最终返回一个布尔数组，其中 true 表示拥有超过其他孩子的糖果数量，false 表示没有。

在上述代码中，res 指针确实指向了一个动态分配的布尔数组，但是需要注意的是，这个布尔数组的实际空间是在堆内存中分配的，而不是在代码中显式地定义的。

具体来说，malloc 函数会在堆内存中动态分配一块连续的内存空间，大小为 candiesSize * sizeof(bool) 字节，用于存储布尔数组的各个元素。这个内存空间的地址会被返回给 res 指针变量，因此 res 指针指向的就是这个分配好的内存空间的起始地址。

在代码中并没有显式地声明布尔数组的名称，因为它是通过动态内存分配而来的，不需要像静态数组一样提前声明。这种情况下，我们只需要使用指针变量 res 来操作和访问这个布尔数组即可，而无需使用数组名称。

605.种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

示例 1：

1
2
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2：

1
2
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

提示：

  • 1 <= flowerbed.length <= 2 * 104
  • flowerbed[i] 为 0 或 1
  • flowerbed 中不存在相邻的两朵花
  • 0 <= n <= flowerbed.length
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {
    int newFlowerbedSize = flowerbedSize + 2;
    int *newFlowerbed = (int*)malloc(newFlowerbedSize * sizeof(int));
    newFlowerbed[0] = 0;
    for (int i = 0; i < flowerbedSize; i++) {
        newFlowerbed[i + 1] = flowerbed[i];
    }
    newFlowerbed[newFlowerbedSize - 1] = 0; //组成新的数组，两边各加一个‘0’
    for(int i=1; i < newFlowerbedSize-1; i++){ //这样就不用考虑当i=0时，i-1<0超出数组边界的问题。
        if(newFlowerbed[i-1]==0 && newFlowerbed[i]==0 && newFlowerbed[i+1]==0){ 
            newFlowerbed[i]=1;
            n-=1;
        }
    }
    if(n<=0){
        return true;
    }
    else{
        return false;
    }
}

官方题解中使用贪心算法理解起来太复杂，从题目讨论中发现“Harrytsz”的防御式编程思想：在 flowerbed 数组两端各增加一个 0， 这样处理的好处在于不用考虑边界条件，任意位置处只要连续出现三个 0 就可以栽上一棵花。

他的代码是Python写的，比较简洁

1
2
3
4
5
6
7
8
class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
        tmp = [0]+flowerbed+[0]
        for i in range(1, len(tmp)-1):
            if tmp[i-1] == 0 and tmp[i] == 0 and tmp[i+1] == 0:
                tmp[i] = 1  # 在 i 处栽上花
                n -= 1   
       return n <= 0   # n 小于等于 0 ，表示可以栽完花

我在这边试着用C语言进行了重写，麻烦的重点就在于怎么让数组两边都加一个0，最开始是直接用变长数组（在一些编译器中，允许使用变量来定义数组的大小），后来想想C 语言的标准规范中不支持在数组定义时使用变量来指定数组的大小，还是使用动态内存分配函数 malloc，如下所示：

1
int *newFlowerbed = (int*)malloc(newFlowerbedSize * sizeof(int));

其实一般在用动态内存分配的时候，要加一些检测判断，如下：

1
2
3
4
5
6
7
   if (newFlowerbed == NULL) {
       // 内存分配失败处理
       return false;
   }

// 释放动态分配的内存
   free(newFlowerbed);

上述代码可以通过检测，就是执行用时分布还不够好。

image-20240330230124758

345.反转字符串中的元音字母

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

示例 1：

1
2
输入：s = "hello"
输出："holle"

示例 2：

1
2
输入：s = "leetcode"
输出："leotcede"

提示：

  • 1 <= s.length <= 3 * 105
  • s 由 可打印的 ASCII 字符组成

根据讨论区的“Ticstc”大佬的解释说题目的意思，是把a、e、i、o、u这几个字母按顺序存起来，最后这些存起来的字符串整体反转插入到原数组中，并不是相邻的两两交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
char vowel[] = "aeiouAEIOU";

bool isVowel(char ch) {
    for (int i = 0; vowel[i]; i++) {
        if (vowel[i] == ch) {
            return true;
        }
    }
    return false;
};

char* reverseVowels(char* s) {
    int n = strlen(s);
    int i = 0, j = n - 1;
    while (i < j) {
        while (i < n && !isVowel(s[i])) {
            ++i;
        }
        while (j > 0 && !isVowel(s[j])) {
            --j;
        }
        if (i < j) {
            char* tmp = s[i];
            s[i] = s[j], s[j] = tmp;
            ++i;
            --j;
        }
    }
    return s;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/reverse-vowels-of-a-string/solutions/944385/fan-zhuan-zi-fu-chuan-zhong-de-yuan-yin-2bmos/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这段代码实现了一个函数 reverseVowels，其作用是将输入字符串 s 中的元音字母反转，其他字符保持不变。函数中用到了一个辅助函数 isVowel 来判断一个字符是否为元音字母。

  1. vowel[] 数组定义了所有的元音字母，包括小写和大写。这个数组用于在 isVowel 函数中检查一个字符是否为元音字母。

  2. isVowel 函数接收一个字符 ch 作为输入，在一个循环中遍历 vowel[] 数组，如果 ch 等于 vowel[i] 中的任何一个元素，则返回 true，表示该字符是一个元音字母。如果循环结束时仍然没有找到相等的元音字母，则返回 false。

  3. reverseVowels 函数首先获取输入字符串 s 的长度 n，然后初始化两个指针 i 和 j，分别指向字符串的起始和末尾。

  4. 使用 while 循环来对字符串进行遍历。在循环中，首先检查 i 指向的字符是否为元音字母，如果不是，则 i 向后移动，直到找到一个元音字母为止；类似地，检查 j 指向的字符是否为元音字母，如果不是，则 j 向前移动，直到找到一个元音字母为止。

  5. 如果 i 小于 j，说明找到了一对需要交换的元音字母，将它们进行交换，并且 i 向后移动一步，j 向前移动一步，以继续寻找下一对需要交换的元音字母。

  6. 当 i >= j 时，表示已经遍历完整个字符串，此时完成了元音字母的反转操作，函数返回原始字符串 s 的指针。

注意事项：

  • 交换字符的语句 char* tmp = s[i]; s[i] = s[j], s[j] = tmp; 可能会引发编译器的警告或错误，因为 tmp 是一个字符指针，而 s[i] 和 s[j] 是字符。正确的做法应该是交换字符而不是交换指针，可以修改为 char tmp = s[i]; s[i] = s[j], s[j] = tmp;。

  • 在这段代码中，++i 和 --j 是分别对变量 i 和 j 进行递增和递减操作。而 i++ 是先取 i 的当前值，然后再将 i 的值加 1。

    这里使用 ++i 和 --j 的原因是它们与 i++ 和 j-- 在这个上下文中的效果是一样的，但是它们的性能稍微更好一些。这是因为 ++i 和 --j 是“前缀递增”和“前缀递减”操作符，它们直接修改了变量的值，并返回这个修改后的值。相比之下，i++ 和 j-- 是“后缀递增”和“后缀递减”操作符，它们会先返回变量当前的值，然后再修改这个变量的值。

    在这种情况下，无论是使用 ++i 还是 i++ 都不会影响代码的功能，因为这里只是简单地递增或递减 i 和 j 的值。然而，使用 ++i 和 --j 可以避免不必要的内存分配和拷贝，因为它们直接在原始变量上进行操作，而不需要为返回值创建一个临时变量。

    所以，在 C 或 C++ 中，建议在不需要后缀操作符的情况下尽可能使用前缀操作符，以获得更好的性能。