LeetCode-面试经典150题

共计 19673 个字符，预计需要花费 50 分钟才能阅读完成。

1. 合并两个有序数组

给你两个按  非递减顺序   排列的整数数组  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)  的算法解决此问题吗？

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {for (int i = 0; i < n; i++) {nums1[i + m] = nums2[i];
        }
        sort(nums1.begin(),nums1.end());
    }
};

2. 移除元素

给你一个数组  nums 和一个值  val，你需要  原地   移除所有数值等于  val  的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用  O(1)  额外空间并  原地  修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

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

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

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

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

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

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

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

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {for(int i = 0;i<nums.size();i++) {if(nums[i] == val) {nums.erase( nums.begin() + i);
               i--;
            }
        }
        return nums.size();}
};

3. 删除有序数组的重复项

给你一个  非严格递增排列   的数组  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  已按  非严格递增  排列

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
        return nums.size();}
};

4. 删除有序数组中的重复项 二

给你一个有序数组  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  已按升序排列

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        for(int n : nums) {if (i < 2 || n > nums[i-2])
                nums[i++] = n;
        }
        return i;
    }
};

5. 多数元素

给定一个大小为  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) 的算法解决此问题。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> mp;
        int num = nums.size() / 2;
        int ans;
        for(int i = 0;i<nums.size();i++) {mp[nums[i]] += 1;
        }

        for(const auto& i : mp) {if(i.second > num) {
                ans = i.first;
                break;
            }
        }
        return ans;
    }
};

6. 轮转数组

给定一个整数数组  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)  的  原地  算法解决这个问题吗？

class Solution {
public:
    void rotate(vector<int>& nums, int k) {int n = nums.size();
        vector<int> num1(n);
        if(k == 0) return;
        for(int i = 0;i<n;i++) {num1[(i + k) % n] = nums[i];
        }
        nums.assign(num1.begin(),num1.end());
    }
};

7. 买卖股票的最佳时机

给定一个数组  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

class Solution {
public:
    int maxProfit(vector<int>& prices) {// 暴力法(超时)
        // int min = prices[0],n = prices.size(),ans = 0;
        // for(int i = 0;i<n;i++) {//     min = prices[i];
        //     for(int j = i + 1;j<n;j++) {//         if(prices[j] > min && prices[j] - min > ans) {//             ans = prices[j] - min;
        //         }
        //     }
        // }
        // return ans;

        // 一次遍历（每次对比最大利益和最小值）:
        int inf = 1e9;
        int minPrice = inf,maxProfit = 0;
        for(int price:prices) {maxProfit = max(maxProfit,price - minPrice);
            minPrice = min(price,minPrice);
        }
        return maxProfit;
    }
};

8. 买卖股票的最佳时机 二

给你一个整数数组  prices ，其中  prices[i]  表示某支股票第  i  天的价格。

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

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

示例 1：

输入：prices = [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 * 104
• 0 <= prices[i] <= 104

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 动态规划 
        // int n = prices.size();
        // int dp0 = 0, dp1 = -prices[0];
        // for (int i = 1; i < n; ++i) {//     int newDp0 = max(dp0, dp1 + prices[i]);
        //     int newDp1 = max(dp1, dp0 - prices[i]);
        //     dp0 = newDp0;
        //     dp1 = newDp1;
        // }
        // return dp0;

        // 贪心
        int n = prices.size(),ans = 0;
        for (int i = 1; i < n; ++i) {ans += max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
};

9. 跳跃游戏

给你一个非负整数数组  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 <= 104
• 0 <= nums[i] <= 105

class Solution {
public:
    bool canJump(vector<int>& nums) {int n = nums.size();
        // 方法一：// int cur = nums[0],i = 1;
        // for(;cur != 0 && i < nums.size();i++) {
        //     cur--;
        //     if(cur < nums[i]) cur = nums[i];
        // }
        // return i == nums.size();

        // 方法二：int k = 0;
            for(int i = 0;i<nums.size();i++) {if(i > k) return false;
                k = max(k,i + nums[i]);
            }
            return true;
    }
};

10. 跳跃游戏 二

给定一个长度为  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 <= 104
• 0 <= nums[i] <= 1000
• 题目保证可以到达  nums[n-1]

class Solution {
public:
    int jump(vector<int>& nums) {
        // 贪心
        int n = nums.size();
        int cur = nums[0],cnt = 0,maxPosition = 0,end = 0;
        for(int i = 0;i < n - 1;i++) {maxPosition = max(maxPosition, i + nums[i]);
            if(i == end) {
                end = maxPosition;
                cnt++;
            }
        }
        return cnt;
    }
};

11. H 指数

给你一个整数数组  citations ，其中  citations[i]  表示研究者的第  i  篇论文被引用的次数。计算并返回该研究者的  h 指数。

根据维基百科上  h 指数的定义 ：h  代表“高引用次数”，一名科研人员的  h  指数   是指他（她）至少发表了  h  篇论文，并且  至少  有  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

class Solution {
public:
    int hIndex(vector<int>& citations) {
        // 方法一：// int ans;
        // sort(citations.begin(),citations.end());
        // for(int i = 0;i < citations.size();i++){//   int  h = citations.size() - i ;
        //     if(citations[i] >= h) {
        //         ans = h;
        //         break;
        //     }
        // }
        // return ans;
        // 二分法：int left = 0, right = citations.size();
        int mid = 0, cnt = 0;
        while (left < right) {
            // 取数组中间值位运算
            // mid = (left + right + 1) >> 1;
            // mid = left + (right - left) / 2;
            mid = left + (right - left >> 1);
            cnt = 0;
            for (int i = 0; i < citations.size(); i++) {if (citations[i] >= mid)
                    cnt++;
            }
            if (cnt >= mid) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

12. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet  类：

• RandomizedSet()  初始化  RandomizedSet  对象
• bool insert(int val)  当元素  val  不存在时，向集合中插入该项，并返回  true ；否则，返回  false 。
• bool remove(int val)  当元素  val  存在时，从集合中移除该项，并返回  true ；否则，返回  false 。
• int getRandom()  随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有  相同的概率  被返回。

你必须实现类的所有函数，并满足每个函数的  平均  时间复杂度为  O(1) 。

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出

[null, true, false, true, 2, true, false, 2]

解释 RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // 向集合中插入 1。返回 true 表示 1 被成功地插入。randomizedSet.remove(2); // 返回 false，表示集合中不存在 2。randomizedSet.insert(2); // 向集合中插入 2。返回 true。集合现在包含 [1,2]。randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2。randomizedSet.remove(1); // 从集合中移除 1，返回 true。集合现在包含 [2]。randomizedSet.insert(2); // 2 已在集合中，所以返回 false。randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2。

提示：

• -231 <= val <= 231 - 1
• 最多调用  insert、remove  和  getRandom  函数  2 * 105  次
• 在调用  getRandom  方法时，数据结构中  至少存在一个  元素。

class RandomizedSet {
private:
    unordered_map<int, int> mp;
    vector<int> arr;
public:
    RandomizedSet() {}

    bool insert(int val) {if (mp.find(val) == mp.end()) {mp.insert({val,val});
            arr.push_back(val);
            return true;
        } else
            return false;
    }

    bool remove(int val) {auto indexx = find(arr.begin(),arr.end(),val);
        if(indexx == arr.end()) {return false;}
        int n = mp.erase(val);
        arr.erase(indexx);
        return n > 0 ? true : false;
    }

    int getRandom() {int n = arr.size();
        // 随机索引 random
        int indexx = rand() % n ;
        return arr[indexx];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

13. 除自身以外数组的乘积

给你一个整数数组  nums，返回  数组  answer ，其中  answer[i]  等于  nums  中除  nums[i]  之外其余各元素的乘积 。

题目数据  保证   数组  nums 之中任意元素的全部前缀元素和后缀的乘积都在   32 位  整数范围内。

请  不要使用除法，且在  O(n)  时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 保证   数组  nums 之中任意元素的全部前缀元素和后缀的乘积都在   32 位  整数范围内

进阶：你可以在  O(1)  的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组  不被视为  额外空间。）

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // 方法一（超时）// vector<int> arr;
        // for(int i  = 0;i<nums.size();i++) {
        //     int sum = 1;
        //     for(int j = 0;j<nums.size();j++) {//         if(j == i) continue;
        //         else {//             sum *= nums[j];
        //         }
        //     }
        //     arr.push_back(sum);
        // }
        // return arr;



        // 方法二：// 求每个前缀
        vector<int> ans(nums.size());
        ans[0] = 1;
        for(int i = 1; i <nums.size();i++) {ans[i] = ans[i - 1] * nums[i - 1];
        }
        // 求每个位置的后缀
        int R = 1;
        for(int i = nums.size() - 1;i >= 0;i--) {ans[i] = ans[i] * R;
            R *= nums[i];
        }
        return ans;

    } 
};

14. 加油站

在一条环路上有  n  个加油站，其中第  i  个加油站有汽油  gas[i] 升。

你有一辆油箱容量无限的的汽车，从第  i  个加油站开往第  i+1  个加油站需要消耗汽油  cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组  gas  和  cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回  -1 。如果存在解，则  保证   它是   唯一  的。

示例  1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站 (索引为 3 处) 出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。因此，3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。我们从 2 号加油站出发，可以获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。因此，无论怎样，你都不可能绕环路行驶一周。

提示:

• gas.length == n
• cost.length == n
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // 方法一（超时）// vector<int> arr;
        // int n = gas.size();
        // for(int i = 0;i<n;i++) { // 最多 n 趟
        //      int havee  = 0,costs = 0,L = 0,cnt = 0,indexx = i; // L 是否轮转过
        //      bool flag = true;
        //     while(cnt < n) {//         havee += gas[indexx];
        //         costs += cost[indexx];
        //         if(havee < costs) {
        //             flag = false;
        //             break;
        //         }
        //         cnt++,indexx++;
        //         if(indexx >= n && L == 0) {
        //           indexx = indexx % n;
        //             L++;
        //         }
               
        //     }
        //     if(flag == true) {
        //         return i;
        //     }
        // }
        // return -1;

        // 方法二
        int totalCost = 0,totalGas = 0,start = 0,tank = 0;
        for(int i = 0;i < gas.size();i++) {totalCost += cost[i];
            totalGas += gas[i];
            tank += gas[i] - cost[i];
            if(tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return totalGas >= totalCost ? start : -1;
        // return totalGas < totalCost ? -1 : start;
    }
};

15. 分发糖果

n  个孩子站成一排。给你一个整数数组  ratings  表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到  1  个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的  最少糖果数目 。

示例  1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例  2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= ratings[i] <= 2 * 104

class Solution {
public:
    int candy(vector<int>& ratings) {int n = ratings.size();
        vector<int> candys(n, 1);
        // 确保右侧大于左侧
        for (int i = 1; i < n; i++) {if (ratings[i] > ratings[i - 1])
                candys[i] = candys[i - 1] + 1;
        }

        //
        for (int i = n - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candys[i] = max(candys[i], candys[i + 1] + 1);
            }
        }
        int sum = 0;
        for(auto cur:candys) {sum += cur;}
        return sum;
    }
};

16. 接雨水（没做出来）

17. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D  和  M。

字符            数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字  2  写做  II ，即为两个并列的 1。12  写做  XII ，即为  X + II 。 27  写做   XXVII, 即为  XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做  IIII，而是  IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4。同样地，数字 9 表示为  IX。这个特殊的规则只适用于以下六种情况：

• I  可以放在  V (5) 和  X (10) 的左边，来表示 4 和 9。
• X  可以放在  L (50) 和  C (100) 的左边，来表示 40 和  90。 
• C  可以放在  D (500) 和  M (1000) 的左边，来表示  400 和  900。

给定一个罗马数字，将其转换成整数。

示例  1:

输入: s = "III"
输出: 3

示例  2:

输入: s = "IV"
输出: 4

示例  3:

输入: s = "IX"
输出: 9

示例  4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例  5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

• 1 <= s.length <= 15
• s  仅含字符  ('I', 'V', 'X', 'L', 'C', 'D', 'M')
• 题目数据保证  s  是一个有效的罗马数字，且表示整数在范围  [1, 3999]  内
• 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
• IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX。
• 关于罗马数字的详尽书写规则，可以参考  罗马数字 – Mathematics 。

class Solution {
public:
    int romanToInt(string s) {int nums = 0,len = s.length();
        for(int i = 0; i < len; i++){if(s[i] == 'V') nums += 5;
            if(s[i] == 'L') nums += 50;
            if(s[i] == 'D') nums += 500;
            if(s[i] == 'M') nums += 1000;
            if(s[i] == 'I'){if(s[i+1] == 'V' || s[i+1] == 'X')
                   nums -= 1;
                else
                    nums += 1;
            }
            if(s[i] == 'X'){if(s[i+1] == 'L' || s[i+1] == 'C')
                    nums -= 10;
                else
                    nums += 10;
            }
            if(s[i] == 'C'){if(s[i+1] == 'D' || s[i+1] == 'M')
                    nums -= 100;
                else
                    nums += 100;
            }
        }
        return nums;
    }
};

18. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D  和  M。

字符            数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做  II ，即为两个并列的 1。12 写做  XII ，即为  X + II 。27 写做   XXVII, 即为  XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做  IIII，而是  IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4。同样地，数字 9 表示为  IX。这个特殊的规则只适用于以下六种情况：

• I  可以放在  V (5) 和  X (10) 的左边，来表示 4 和 9。
• X  可以放在  L (50) 和  C (100) 的左边，来表示 40 和  90。 
• C  可以放在  D (500) 和  M (1000) 的左边，来表示  400 和  900。

给你一个整数，将其转为罗马数字。

示例  1:

输入: num = 3
输出: "III"

示例  2:

输入: num = 4
输出: "IV"

示例  3:

输入: num = 9
输出: "IX"

示例  4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例  5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

• 1 <= num <= 3999

class Solution {
public:
    string intToRoman(int num) {
        vector<pair<int, string>> romanMap = {{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"}, {100, "C"},
            {90, "XC"},  {50, "L"},   {40, "XL"}, {10, "X"},   {9, "IX"},
            {5, "V"},    {4, "IV"},   {1, "I"}};
        string s = "";
        for(const auto& pair:romanMap) {while(num >= pair.first) {
                s += pair.second;
                num -= pair.first;
            }
        }
        return s;
    }
};

19. 最后一个单词的长度

给你一个字符串  s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中  最后一个  单词的长度。

单词  是指仅由字母组成、不包含任何空格字符的最大

子字符串。

示例 1：

输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。

示例 2：

输入：s = "fly me   to   the moon"
输出：4
解释：最后一个单词是“moon”，长度为 4。

示例 3：

输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

提示：

• 1 <= s.length <= 104
• s  仅有英文字母和空格  ' '  组成
• s  中至少存在一个单词

class Solution {
public:
    int lengthOfLastWord(string s) {
        int cnt = 0;
        for(int i = s.length() - 1;i>=0;i--) {if(s[i] == ' ' && cnt != 0) {break;} else {cnt += s[i] == ' ' ? 0 : 1; 
            }
        }
        return cnt;
    }
};

20. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串  ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]  仅由小写英文字母组成

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {int n = strs.size();
        if(n < 1) return "";
        string s = strs[0];
        for(int i = 1;i < n;i++) {
            string s1;
            for(int j = 0;j<strs[i].length();j++) {if(strs[i][j] != s[j]) {break;} else {s1 += strs[i][j];
                }
            }
            s =  s1;
        }
        return s.length() > 0 ? s : "";} 
};

21. 反转字符串中的单词

给你一个字符串  s ，请你反转字符串中  单词  的顺序。

单词   是由非空格字符组成的字符串。s  中使用至少一个空格将字符串中的   单词  分隔开。

返回  单词   顺序颠倒且   单词  之间用单个空格连接的结果字符串。

注意：输入字符串  s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = " hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 104
• s  包含英文大小写字母、数字和空格  ' '
• s  中  至少存在一个  单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用  O(1)  额外空间复杂度的  原地  解法。

class Solution {

22. Z 字形变换

将一个给定字符串  s  根据给定的行数  numRows ，以从上往下、从左到右进行  Z 字形排列。

比如输入字符串为  "PAYPALISHIRING"  行数为  3  时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、',' 和 '.' 组成
• 1 <= numRows <= 1000

class Solution {
public:
    string convert(string s, int numRows) {if(numRows < 2) return s;
        vector<string> str(numRows);
        int i = 0,flag = -1;
        for(char cur : s) {str[i].push_back(cur);
            // 两边转角处调转方向
            if(i == 0 || i == numRows - 1) flag = -flag;
            i += flag;
        }
        string sum;
        for(string cur : str) {sum += cur;}
        return sum;
    }
};

23. 找出字符串第一个匹配的下标

给你两个字符串  haystack  和  needle ，请你在  haystack  字符串中找出  needle  字符串的第一个匹配项的下标（下标从 0 开始）。如果  needle  不是  haystack  的一部分，则返回   -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0，所以返回 0。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1。

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

class Solution {
public:
    int strStr(string haystack, string needle) {for(int i = 0;i<haystack.length();i++) {if(haystack[i] == needle[0]) {
                bool flag = true;
                for(int j = 1;j<needle.length();j++) {if(haystack[i+j] != needle[j]) {
                        flag = false;
                        break;
                    }
                }
               
                if(flag)  return i;
            }
        }
        return -1;
    }
};

24. 左右对齐（不会做）

25. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个  回文串 。

字母和数字都属于字母数字字符。

给你一个字符串  s，如果它是  回文串 ，返回  true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 ""。由于空字符串正着反着读都一样，所以是回文串。

提示：

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

class Solution {
public:
    bool isPalindrome(string s) {
        string ans1;
        for(char c:s) {if(isalnum(c)){ans1 += tolower(c);
            }
        }
        string ans2(ans1.rbegin(),ans1.rend());
        return ans1 == ans2;
    }
};

26. 判断子序列

给定字符串  s  和  t ，判断  s  是否为  t  的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是 "abcde" 的一个子序列，而 "aec" 不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10 亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢  @pbrother  添加此问题并且创建所有测试用例。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

class Solution {
public:
    bool isSubsequence(string s, string t) {int n = t.length();
        int indexx = 0;
        for(auto& c:t) {if(c == s[indexx]) indexx++;    
        }
        return indexx == s.length();}
};

27. 两数之和 二 – 输入有序数组

给你一个下标从  1  开始的整数数组  numbers ，该数组已按   非递减顺序排列   ，请你从数组中找出满足相加之和等于目标数  target  的两个数。如果设这两个数分别是  numbers[index1]  和  numbers[index2] ，则  1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组  [index1, index2]  的形式返回这两个整数的下标  index1 和 index2。

你可以假设每个输入  只对应唯一的答案  ，而且你   不可以  重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9。因此 index1 = 1, index2 = 2。返回 [1, 2]。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6。因此 index1 = 1, index2 = 3。返回 [1, 3]。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1。因此 index1 = 1, index2 = 2。返回 [1, 2]。

提示：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 非递减顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {vector<int> ans(2);
        // 双指针
        int left = 0,right = numbers.size() - 1;
        while(numbers[left] + numbers[right] != target && right > left) {if(numbers[left] + numbers[right] < target) left++;
            else if(numbers[left] + numbers[right] > target) right--;
            else break;
        }
        ans[0] = left + 1;ans[1] = right + 1;
        return ans;
    }
};