Leetcode 面试经典150题

1 *88. 合并两个有序数组(可跳转)

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

进阶*：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

解法1：(时间复杂度O(m+n)，空间复杂度O(1))

/*************************************************************************
        > File Name: 1.merge.c
        > Author:ZhangNan 
        > Mail:1470161695@qq.com 
        > Created Time: Mon 28 Oct 2024 10:38:38 AM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int *nums3 = (int *)calloc(nums1Size, sizeof(int));                 // 申请空间
    int k = 0;                                                          // 记录 nums1 数组的下标
    int i = 0;                                                          // 记录 nums1 数组的下标
    int j = 0;                                                          // 记录 nums2 数组的下标
    while(i < m && j < n){
        if(nums1[i] <= nums2[j]) {                                      // 若 nums1[i] 小于等于 nums2[j]
            nums3[k++] = nums1[i++];                                    // 则将 nums1[i] 放入 nums3 数组
        }
        else {
            nums3[k++] = nums2[j++];                                    // 否则将 nums2[j] 放入 nums3 数组
        }
    }
    while(i < m){
        nums3[k++]= nums1[i++];                                         // 若 nums1 数组遍历完，则将 nums1 剩余元素放入 nums3 数组
    }
    while(j < n){
        nums3[k++]= nums2[j++];                                         // 若 nums2 数组遍历完，则将 nums2 剩余元素放入 nums3 数组
    }

    for(int i = 0; i < nums1Size; i++) {
        nums1[i] = nums3[i];                                            // 将 nums3 数组中的元素复制到 nums1 数组中
    } 
    free(nums3);                                                        // 释放 nums3 数组空间
    return ;
}

int main () {
    int n = 3;
    int m = 3;
    int nums1[3] = {1, 2, 4};
    int nums2[3] = {2, 5, 6};
    int nums1Size = m + n;
    int nums2Size = n;
    merge(nums1, nums1Size, m, nums2, nums2Size, n);               
    for(int i = 0; i < nums1Size; i++) {      
        printf("%d,", nums1[i]);                                     // 输出合并后的数组
    }
    printf("\n");
    return 0;
}

---

2 *27. 移除元素(可跳转)

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = […]; // 输入数组
int val = …; // 要移除的值
int[] expectedNums = […]; // 长度正确的预期答案。
// 它以不等于 val 的值排序。
int k = removeElement(nums, val); // 调用你的实现
assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,,]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,,,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

解法1：(时间复杂度O(n)，空间复杂度O(1))

/*************************************************************************
        > File Name: 3.removeElement.c
        > Author:ZhangNan 
        > Mail:1470161695@qq.com 
        > Created Time: Tue 29 Oct 2024 08:54:11 AM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>

int removeElement(int* nums, int numsSize, int val) {
    int n = 0;
    int i = -1;
    int *nums1 = (int *)calloc(numsSize, sizeof(int));                // 申请空间
    while(++i < numsSize){
        if(nums[i] == val) continue;                                  // 若 nums[i] 等于 val，则跳过
        else {
            nums1[n] = nums[i];                                       // 否则将 nums[i] 放入 nums1 数组
            n++;
        }
    }
    for(int i = 0; i < n; i++){
        nums[i] = nums1[i];                                           // 将 nums1 数组中的元素复制到 nums 数组中
    }
    return n; 
}

int main() {
    int num[8] = {0, 1, 2, 2, 3, 0, 4, 2};
    int numsSize = 8;
    int val = 2;
    int a = removeElement(num, numsSize, val);
    for(int i = 0; i < numsSize - a; i++) {
        printf("%d,", num[i]);
    }
    printf("k = %d\n", a);
    return 0;
}

3 *26. 删除排序数组中的重复项(可跳转)

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确>的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 非严格递增 排列

解法1：(时间复杂度O(n)，空间复杂度O(1))

/*************************************************************************
        > File Name: 4.removeDuplicates.c
        > Author:ZhangNan 
        > Mail:1470161695@qq.com 
        > Created Time: Wed 30 Oct 2024 10:22:36 AM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>

int removeDuplicates(int* nums, int numsSize) {
    int i = 0;
    int n = 0;
    //int *nums1 = (int *)calloc(numsSize, sizeof(int));
    while(i < numsSize) {
        nums[n++] = nums[i++];
        while(i < numsSize) {
            if(nums[n - 1] == nums[i + 1] && i + 1 <= numsSize){
                i++;
            }
            else{
                break;
            }
        }
    }
    /*for(int j = 0; j < n; j++) {
        nums[j] = nums1[j];
    }*/
    return n;
}

int main () {
    int arr[10] = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    int numsSize = 10;
    int n = removeDuplicates(arr, numsSize);
    for(int i = 0; i < n; i++) {
        printf("%d,", arr[i]);
    }
    printf("n = %d\n", n);
    printf("\n");
    return 0;
}

---

4 **80. 删除有序数组中的重复项 II(可跳转)

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以 「引用」 方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按升序排列

解法1：(时间复杂度O(n) 空间复杂度O(1))

#include <stdio.h>
#include <stdlib.h>

int removeDuplicates(int* nums, int numsSize) {
    int i = 0;
    int n = 0;
    while(i < numsSize) {
        nums[n++] = nums[i++];
        while(i + 1 < numsSize) {
            if(nums[n - 1] == nums[i + 1]){
                i++;
            }
            else{
                break;
            }
        }
    }
    return n;
}

int main () {
    int arr[6] = {1, 1, 1, 2, 2, 3};
    int numsSize = 6;
    int n = removeDuplicates(arr, numsSize);
    for(int i = 0; i < n; i++) {
        printf("%d,", arr[i]);
    }
    printf("n = %d\n", n);
    printf("\n");
    return 0;
}

5 *169. 多数元素(可跳转)

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

如上思路解法1：(时间复杂度O(n) 空间复杂度O(1))

思路解析：

出于“多数元素”特殊性质，考虑以下情形：给定的数组如果存在“多数元素”，那么从这个数组中拿走两个不同的元素，新的数组一定仍然具有相同的“多数元素”。因为如果拿掉两个非“多数元素”，原本的“多数元素”占比就更多了，而拿走一个“多数元素”和一个其他元素，由于拿走的元素中“多数元素”和其他元素之比为1:1，原本为x:1，其中x>1，因此剩余部分“多数元素”仍比其他元素多。

基于以上想法，以：7, 7, 5, 7, 5, 1 , 5, 7 , 5, 5, 7, 7 , 7, 7, 7, 7这一组数为例，分析下列过程：

遍历数组：

第一个数字为7，它有可能就是我们要寻找的“多数元素”，不妨先假定他就是“多数元素”，声明一个变量candidate赋值为7来表示它就是我们目前假定的“多数元素”，设置一个新变量count为1，用以表示candidate确实是“多数元素”的一种“可能性大小”。

第二个数字为7，与candidate相等，这表明“7就是“多数元素”的可能性增大了”，将count值加一。

下一个数字为5，与candidate不相等，根据我们上述的分析，拿掉两个不相等的元素后，数组仍然具有相同的“多数元素”，可以理解为，把5与前面的candidate中的某一个一同拿掉后，剩下的数组与原数组的“多数元素”一样。因此我们将count值减一，表示取出目前的候选者与另外某一元素，这俩个取出的元素对“多数元素”的取值已经不再有任何影响，原数组的“多数元素”不变。可见，此candidate是“多数元素”的“可能性”变小了。

依此类推，下一个数字为7，将count加一，此时其值为2。

接下来两个数字分别为5和1， 这样count减一再减一，值变为0。也就是说，此时的“多数元素”取值可能情形与遍历开始时完全一样了：3个7和3个其他数相当于拿出数组的三对不同元素，剩下的数组“多数元素”和原数组相同。

下一个数字为5，由于此时count为0，在此后任何一个数字是“多数元素”的“可能性”都相同，因此我们不妨设置第一个遇到的数“5”为新的candidate，count设置为1，继续重复上述过程。

可见，随后count又减一、加一、加一、减一、减一，变为0，下一个数为7，重新将candidate赋值为7，并最终遍历完整个数组且count最终为4，此过程中未再次减小至0，最终的candidate就是我们需要找的“多数元素”，因为遍历完后相当于将所有的非最终candidate的数每个都和candidate这个数组队删除，上面所说的“可能性大小”变量count的实际含义就是成对拿走元素后剩下的candidate的个数，此候选者自然就是要求的“多数元素”了。

#include<stdio.h>

int majorityElement(int* nums, int numsSize) {
    int count = 0;
    int num = nums[0];
    for(int i = 0; i < numsSize; i++) {
        if(nums[i] == num) {
            count++;
        }
        else{
            count--;
        }
        if(count == 0) {
            num = nums[i + 1];
        }
    }
    return num;
}

int main(){
    int arr1[7] = {2, 2, 1, 1, 1, 2, 2};
    int numsSize = 7;
    int num1 = majorityElement(arr1, numsSize);
    printf("majorityElement = %d\n", num1);

    int arr2[11] = {1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 2};
    numsSize = 11;
    num1 = majorityElement(arr2, numsSize);
    printf("majorityElement = %d\n", num1);

    return 0;
}

6 **189. 轮转数组(可跳转)

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

进阶：

• 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

解法1：(时间复杂度O(n) 空间复杂度O(1))

#include<stdio.h>

void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
    if (k <= numsSize && numsSize != 1) {
        for (int i = 0, j = numsSize - 1; i < j; i++, j--) {
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
        for (int i = 0, j = k - 1; i < j; i++, j--) {
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
        for (int i = k, j = numsSize - 1; i < j; i++, j--) {
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
    }
}

int main() {
    int arr[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int numsSize = 11;
    int k = 4;
    rotate(arr, numsSize, k);
    for(int i = 0; i < numsSize; i++) {
        printf("%d,", arr[i]);
    }
    printf("\n");
    return 0;
}

解法2：(时间复杂度O(n) 空间复杂度O(k))

#include<stdio.h>

void rotate(int* nums, int numsSize, int k) {
    int arr[k];
    for(int i = 0; i < k; i++) {
        arr[i] = nums[numsSize  - k + i];
    }
    for(int i = 0; i < k; i++) {
        printf("%d", arr[i]);
    }
    printf("\n");
    for(int j = numsSize - k; j > 0; j--) {
        nums[j + k - 1] = nums[j - 1]; 
    }
    for(int i = 0; i < k; i++) {
        nums[i] = arr[i];
    }
}

int main() {
    int arr[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int numsSize = 11;
    int k = 4;
    rotate(arr, numsSize, k);
    for(int i = 0; i < numsSize; i++) {
        printf("%d,", arr[i]);
    }
    printf("\n");
    return 0;
}

---

7 *121. 买卖股票的最佳时机(可跳转)

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

解法1：(解算时间过长，不推荐)

问题所在：

1. 效率低下：

使用了两个嵌套的 for 循环，时间复杂度是 O(n^2)。对于较大的输入数组，这会导致性能问题。

2. 命名不明确：

变量名 min 用于表示最大利润，这可能导致混淆。更好的命名可以使代码更易读，比如将 min 改为 maxProfit。

3. 初始值设置不当：

int min = 0; 会导致如果没有找到利润，返回值可能仍为 0，而这并不代表没有利润的情况。建议将初始值设置为一个很小的数，如 INT_MIN。

1. 没有处理边界情况：

没有检查 pricesSize 是否小于 2，可能导致不必要的计算或访问越界。

int maxProfit(int* prices, int pricesSize) {
    int min = 0;                                        //定义一个最小值
    int k = 0;                                          //保存最大利润值
    for(int i = 0; i < pricesSize; i++) {  
        for(int j = pricesSize - 1; j > i; j--) {       //遍历数组，找出最小值
            k = prices[j] - prices[i];                  //计算当前读取值和最小值之间的利润值
            if(min < k) min = k;                        //更新最小值
        }
    }
    return min;
}

解法2：(时间复杂度O(n) 空间复杂度O(1))

算法思路：

1. 初始化：

min_price 设置为无穷大，以确保第一个价格会更新它。
max_profit 初始化为 0，因为在未进行任何交易时没有利润。

2. 遍历价格：

对于每个股票价格，检查是否比当前的 min_price 更低。如果是，则更新 min_price。
计算当前价格减去 min_price 的利润，并更新 max_profit 为当前利润和之前最大利润中的较大值。

3. 返回结果：

最后返回 max_profit，即最大利润。

int maxProfit(int* prices, int pricesSize) {
    int min_price = INT_MAX;                   //定义一个最大值的price
    int max_profit = 0;                        //保存最大的利润值
    for (int i = 0; i < pricesSize; i++) {
        if (prices[i] < min_price) {           //更新最小的price
            min_price = prices[i];
        }
        int profit = prices[i] - min_price;    //计算当前读取值和最小值之间的利润值
        if (profit > max_profit) {             //更新最大的利润值
            max_profit = profit;
        }
    }
    return max_profit;                         //返回最大的利润值
}

8 **122. 买卖股票的最佳时机 II(可跳转)

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：[7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

提示：

• 1 <= prices.length <= 3 * 10 ^ 4
• 0 <= prices[i] <= 10 ^ 4

解法1：(时间复杂度O(n) 空间复杂度O(1))

算法思路：

1. 初始化：

创建一个变量 total_profit 来记录累计的利润。

2. 遍历价格：

从第二天开始遍历价格数组，检查当前价格是否高于前一天的价格。

3. 计算利润：

如果当前价格高于前一天的价格，表示可以在前一天买入并在今天卖出，累加这个利润到 total_profit 中。

4. 返回结果：

最后返回 total_profit，即最大利润。

int maxProfit(int* prices, int pricesSize) {
    int min_price = prices[0];                   //定义一个最小的price
    int max_profit = 0;                          //保存最大的利润值
    for (int i = 1; i < pricesSize; i++) {
        if (prices[i] < min_price) {             //更新最小的price
            min_price = prices[i];
        }
        int profit = prices[i] - min_price;      //计算当前读取值和最小值之间的利润值
        if (profit > max_profit) {               //更新最大的利润值
            max_profit = profit;
        }
    }
    return max_profit;                           //返回最大的利润值
}

9 **55. 跳跃游戏(可跳转)

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

题目理解：

这个题，能够用到的数据有 当前位置的最大步数(数组内的值) ，以及表示当前位置的数组下标 和 需要跳过的数组长度 。

题目要求判断是否可以跳过这个数组：

1.通过分析，不能跳过这个数组的情况只有一种，那就是数组内一个值为0，而且其前面的值呈-1递减的情况。(即 … 6, 5, 4, 3, 2, 1, 0, …)，此种情况，6前面的值还不能大于6，因为如果大于6，那么就可以直接跳过这整段递减数列，不用考虑此处的0。

按照这种思路来写代码，1.首先需要判断数组中存在一段差为1的递减数列且最后值为0，2.如要判断这段数列前面的最大步数不会大于数列的最左段的最大值……凡此种种就很复杂，所以，这样来理解没问题，但是照着这个逻辑去写代码就很复杂。

2.换个思路，将这三个值的关系画出，我们发现的三个值中间有一个很为微妙的关系：

比如：
numsSize = 5
下标:   0  1  2  3  4             0  1  2  3  4
数组1: {3, 2, 1, 0, 4}    数组2: {5, 2, 1, 0, 4}

很容易发现，下标 + 最大步数 和 0 值处的 下标 以及 数组长度减一 关系。
例如： 在数组1中，0值(下标3)之前的任何 下标 加上 最大步数 都等于0值的下标，即跳不过去；数组2模拟了一下思路1的情况，可以参照理解。
然后结合这个关系，我们可以整理一下转为代码逻辑：

return 1 的条件：整段数组中的 数组下标 + 最大步数 大于或者等于 数组长度减一 时
return 0 的条件：当遇到 0 时，0 前面的所有 下标 加 最大步数 都小于 0值处的下标 或者 遍历完整个数组还是没能 return 1 的时候
结合以上两个条件， 我们需要一个max_num整型来记录 最远距离(等价于下标加上最大步数) ，然后遍历数组，对于每个位置，计算当前位置能跳跃的最远距离，并更新 max_num ，如果 max_num 超过数组长度减一，则说明可以到达最后一个位置，返回 true ，否则，如果当前面的步数大于当前位置，可以跳过，否则，如果当前位置不能跳，则返回 false 。

解法1：( 时间复杂度O(n) 空间复杂度O(1) )

算法思路：

1. 初始化：

创建一个变量 max_num 来记录当前能跳跃的最远距离。

2. 遍历数组：

对于每个位置，计算当前位置能跳跃的最远距离，并更新 max_num 。

3. 判断是否到达最后一个位置：

如果 max_num 超过数组长度减一，则说明可以到达最后一个位置，返回 true 。

4. 返回结果：

如果遍历完都不能到达最后一个位置，返回 false 。

bool canJump(int* nums, int numsSize) {
    int max_num = INT_MIN;
    for (int i = 0; i < numsSize; i++) {
        if (max_num < nums[i] + i) max_num = nums[i] + i;        //更新最大的跳跃距离
        if (max_num >= numsSize - 1) return 1;                   //可以到达最后一个位置，返回true
        else if(max_num > i) continue;                           //当前面的步数大于当前位置下标，可以跳过
        else if(nums[i] == 0) return 0;                          //当前位置不能跳，则返回false
    }
    return 0;                                                    //遍历完都不能到达最后一个位置，返回false
}

解法1(GPT逻辑优化后)：( 时间复杂度O(n) 空间复杂度O(1) )

变量 maxReachable：用于记录当前能够到达的最远位置。

逻辑判断：

如果当前索引 i 超过 maxReachable，说明无法到达这个位置，返回 false。
更新 maxReachable 为 maxReachable 和 i + nums[i] 的较大值。
如果 maxReachable 达到或超过最后一个位置，返回 true。
返回值：如果遍历结束后仍未能到达最后的位置，返回 false。

bool canJump(int* nums, int numsSize) {
    int maxReachable = 0; // 当前能够到达的最远位置

    for (int i = 0; i < numsSize; i++) {
        // 如果当前索引超出了可达的最远位置，返回 false
        if (i > maxReachable) {
            return false;
        }
        // 更新最远可达位置
        maxReachable = (maxReachable > i + nums[i]) ? maxReachable : (i + nums[i]);
        
        // 如果能够到达最后一个位置，返回 true
        if (maxReachable >= numsSize - 1) {
            return true;
        }
    }
    
    return false; // 遍历完后仍无法到达最后位置
}

10 ** 45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

11 ** 274. H 指数

数组中有 h 个不小于 h 的值，求最大的 h 。

示例 1：

输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：

输入：citations = [1,3,1]
输出：1

提示：

• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000

题目理解：

此处的可用数据有 表示引用次数的catations数组值、表示最大论文数的数组长度。

2024/11/05 的思路：
(这种方法有点呆，算法的时间复杂度不好，空间复杂度虽然为O(1)，但是内存占用还是较大，但是是我一下就能想到的方法，所以就先记录下来了)

在这里为了求出所谓的 H指数，首先从 极端值 找一下灵感

极端情况：
{1} H = 1
{2, 2} H = 2
{3, 3, 3} H = 3
{4, 4, 4, 4} H = 4
......

明显可以看出，当一段 数组内部的元素值 都大于等于 数组长度 时，数组的长度就是最大的 H指数 。
因此我们可以确定 H指数 可以从 数组的长度开始递减，当遇到不符合条件时，H指数 减一，这个可以变动的数组长度我们姑且称其为 Size 。
此处的 Size 是个标杆，是理想的 H指数 ，对于条件判断来说，也就是数组内大于这个值(被引用的次数)的元素个数要大于这个值(发表的文档篇数)
可以发现在进行 数组内元素 和 Size 进行比较的时候，我们需要进行一此数组遍历，所以时间复杂度是 O(n) 。

比如： {1, 3, 4, 4, 2}
Size = 5
令 大于等于 Size 的元素个数 = nums；
递推的顺序来推一下：
1、Size = 5
nums = 0

2、Size = 4
nums = 2

3、Size = 3
nums = 3

满足条件退出，此时 H指数 = 3

而不符合的条件就是，当这段数组中存在元素的值小于数组的值(或者更一般的情况就是，数组中此时大于等于 Size 的元素个数累计小于 Size )

解法1：( 时间复杂度O(n^2) 空间复杂度O(1) )

int hIndex(int* citations, int citationsSize) {
    int count = 0;                                    // 记录大于等于 理想 H指数 的元素个数
    for (int i = citationsSize; i > 0; i--) {         // i 代表理想 H指数，从 citationsSize 开始递减
        count = 0;                                    // 重置 count
        for (int j = 0; j < citationsSize; j++) {
            if (citations[j] >= i) count++;           // 满足条件时，count 加一
        }
        if (count >= i) {                             // 符合条件时，返回 H指数
            count = i;                                // 记录 H指数
            break;                                    // 退出循环
        }
    }
    return count;
}