char 和 char 比较要使用单引号' ' string 和 string 比较要使用" "
这种先处理局部再处理整体代码会比较复杂 ，先处理整体再处理局部比较好
以下是可以使用
reverse的常见容器：
顺序容器
std::vector：最常用的动态数组，支持随机访问迭代器，reverse可以高效反转其元素。std::deque：双端队列，支持随机访问，可直接使用reverse。std::array：固定大小数组，同样支持随机访问迭代器。std::string：字符串本质是字符序列，支持随机访问，可反转字符顺序（如"abc"反转为"cba"）。其他支持随机访问的结构
- 原生数组：如
int arr[] = {1,2,3}，可通过指针作为迭代器使用reverse(arr, arr + 3)。不能直接使用
reverse的容器：
std::list、std::forward_list等链表容器不支持随机访问迭代器，但其自身提供了成员函数reverse()来实现反转（效率更高，因为链表反转无需交换元素，只需调整指针）
1. 两数之和
已解答
相关企业
提示
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hashtable;
int n = nums.size();
for(int i=0;i<n;i++)
{
auto it = hashtable.find(nums[i]);
if(it != hashtable.end())
{
return {it->second,i};
}
hashtable[target-nums[i]] = i;
}
return {0,0};
}
};
// target = i + num;
// target - i = 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 中。
有一个数组走到头了，就不要在访问和移动指针
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
cur = nums2[p2--];
} else if (p2 == -1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
}
};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 <= 1000 <= nums[i] <= 500 <= val <= 100
优化双指针解法，right位于末尾，换位后right右侧的元素都是被换走的无效元素，故结束条件是left >= right. 而且left就是k.
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0, right = nums.size();
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
};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] <= 104nums已按升序排列
slow 和 fast 分别为慢指针和快指针，其中慢指针表示处理出的数组的长度，快指针表示已经检查过的数组的长度，即 nums[fast] 表示待检查的第一个元素 slow和fast之间为需要被覆盖的元素。
条件合法始fast 的元素覆盖掉slow
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n <= 2) {
return n;
}
int slow = 2, fast = 2;
while (fast < n) {
if (nums[slow - 2] != nums[fast]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
};
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
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
pair<int, int> mp(nums[0], 1);
for (int i = 1; i < n; i++) {
if (mp.second == 0) {
mp = {nums[i], 1};
continue;
}
if (nums[i] == mp.first) {
mp.second++;
} else {
mp.second--;
}
}
return mp.first;
}
};无需中间变量交换两个数的写法
public void swap(int[] nums, int i, int j) {
if (i == j) {
return;
}
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
}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) 的 原地 算法解决这个问题吗？
注意0到k-1 是在左侧
class Solution {
public:
void reverse(vector<int>& nums, int start, int end) {
while (start < end) {
swap(nums[start], nums[end]);
start++;
end--;
}
}
void rotate(vector<int>& nums, int k) {
k %= nums.size();
reverse(nums, 0, nums.size() - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.size() - 1);
}
};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 <= 1050 <= prices[i] <= 104
找到一条上升曲线最长的曲线
class Solution {
public:
int maxProfit(vector<int>& prices) {
int inf = 1e9;
int minprice = inf, maxprofit = 0;
for (int price: prices) {
maxprofit = max(maxprofit, price - minprice);
minprice = min(price, minprice);
}
return maxprofit;
}
};
122. 买卖股票的最佳时机 II
给你一个整数数组 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] <= 10
将所有上升的曲线累加就行
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
int n = prices.size();
for (int i = 1; i < n; ++i) {
ans += max(0, prices[i] - prices[i - 1]);
}
return ans;
}
};
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 <= 1040 <= nums[i] <= 105- 实时维护最远可以到达的位置 使用x+nums[x] 更新 最远可以到达的位置。最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int rightmost = 0;
for (int i = 0; i < n; ++i) {
if (i <= rightmost) {
rightmost = max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
}
return false;
}
};
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 <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]
维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。
class Solution {
public:
int jump(vector<int>& nums) {
int maxPos = 0, n = nums.size(), end = 0, step = 0;
for (int i = 0; i < n - 1; ++i) {
maxPos = max(maxPos, i + nums[i]);
if (i == end) {
end = maxPos;
++step;
}
}
return step;
}
};
如果不保证一定有解，需要对最大边界进行判断，当maxPos < i,永远也不可能到达数组末尾
class Solution {
public:
int jump(vector<int>& nums) {
int maxPos = 0, n = nums.size(), end = 0, step = 0;
for (int i = 0; i < n - 1; ++i) {
if (maxPos >= i) {
maxPos = max(maxPos, i + nums[i]);
if (i == end) {
end = maxPos;
++step;
}
}
}
return step;
}
};
274. 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.length1 <= n <= 50000 <= citations[i] <= 1000
翻译：数组中有h个不小于h的值，求最大的h
计数排序
时间复杂度O(n)
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size(), tot = 0;
vector<int> counter(n + 1);
for (int i = 0; i < n; i++) {
if (citations[i] >= n) {
counter[n]++;
} else {
counter[citations[i]]++;
}
}
for (int i = n; i >= 0; i--) {
tot += counter[i];
if (tot >= i) {
return i;
}
}
return 0;
}
};
二分搜索统计
假设数组是[1,3,2,3,100]（5 篇论文）：
- 当
mid=3时，扫描数组发现≥3 的元素有 3、3、100 →cnt=3。因为3≥3，说明 “h=3” 是可能的（至少有 3 篇满足）。 - 当
mid=4时，扫描数组发现≥4 的元素只有 100 →cnt=1。因为1<4，说明 “h=4” 不可能（凑不够 4 篇）。
通过这样的统计，我们才能判断 “当前猜测的 mid 是否符合 H 指数的条件”，进而调整二分搜索的范围
mid = (left + right +1 )>>1;
left = mid;
right = mid -1;
class Solution {
public:
int hIndex(vector<int>& citations) {
int left=0,right=citations.size();
int mid=0,cnt=0;
while(left<right){
// +1 防止死循环
mid=(left+right+1)>>1;
cnt=0;
for(int i=0;i<citations.size();i++){
if(citations[i]>=mid){
cnt++;
}
}
if(cnt>=mid){
// 要找的答案在 [mid,right] 区间内
left=mid;
}else{
// 要找的答案在 [0,mid) 区间内
right=mid-1;
}
}
return left;
}
};
380. O(1) 时间插入、删除和获取随机元素
实现RandomizedSet 类：
RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
方法一：变长数组 + 哈希表
这道题要求实现一个类，满足插入、删除和获取随机元素操作的平均时间复杂度为 O(1)。
变长数组可以在 O(1) 的时间内完成获取随机元素操作，但是由于无法在 O(1) 的时间内判断元素是否存在，因此不能在 O(1) 的时间内完成插入和删除操作。哈希表可以在 O(1) 的时间内完成插入和删除操作，但是由于无法根据下标定位到特定元素，因此不能在 O(1) 的时间内完成获取随机元素操作。为了满足插入、删除和获取随机元素操作的时间复杂度都是 O(1)，需要将变长数组和哈希表结合，变长数组中存储元素，哈希表中存储每个元素在变长数组中的下标。
插入操作时，首先判断 val 是否在哈希表中，如果已经存在则返回 false，如果不存在则插入 val，操作如下：
在变长数组的末尾添加 val；
在添加 val 之前的变长数组长度为 val 所在下标 index，将 val 和下标 index 存入哈希表；
返回 true。
删除操作时，首先判断 val 是否在哈希表中，如果不存在则返回 false，如果存在则删除 val，操作如下：
从哈希表中获得 val 的下标 index；
将变长数组的最后一个元素 last 移动到下标 index 处，在哈希表中将 last 的下标更新为 index；
在变长数组中删除最后一个元素，在哈希表中删除 val；
返回 true。
删除操作的重点在于将变长数组的最后一个元素移动到待删除元素的下标处，然后删除变长数组的最后一个元素。该操作的时间复杂度是 O(1)，且可以保证在删除操作之后变长数组中的所有元素的下标都连续，方便插入操作和获取随机元素操作。
获取随机元素操作时，由于变长数组中的所有元素的下标都连续，因此随机选取一个下标，返回变长数组中该下标处的元素
class RandomizedSet {
public:
RandomizedSet() {
srand((unsigned)time(NULL));
}
bool insert(int val) {
if (indices.count(val)) {
return false;
}
int index = nums.size();
nums.emplace_back(val);
indices[val] = index;
return true;
}
bool remove(int val) {
if (!indices.count(val)) {
return false;
}
int index = indices[val];
int last = nums.back();
nums[index] = last;
indices[last] = index;
nums.pop_back();
indices.erase(val);
return true;
}
int getRandom() {
int randomIndex = rand()%nums.size();
return nums[randomIndex];
}
private:
vector<int> nums;
unordered_map<int, int> indices;
};
238. 除自身以外数组的乘积
给你一个整数数组 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
输入 保证 数组 answer[i] 在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
先把 answer 作为方法一的 L 数组。
这种方法的唯一变化就是我们没有构造 R 数组。而是用一个遍历来跟踪右边元素的乘积。并更新数组 answer[i]=answer[i]∗R。然后 R 更新为 R=R∗nums[i]，其中变量 R 表示的就是索引右侧数字的乘积。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int length = nums.size();
vector<int> answer(length);
// answer[i] 表示索引 i 左侧所有元素的乘积
// 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
answer[0] = 1;
for (int i = 1; i < length; i++) {
answer[i] = nums[i - 1] * answer[i - 1];
}
// R 为右侧所有元素的乘积
// 刚开始右边没有元素，所以 R = 1
int R = 1;
for (int i = length - 1; i >= 0; i--) {
// 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
answer[i] = answer[i] * R;
// R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
R *= nums[i];
}
return answer;
}
};
给定两个整数数组 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 升汽油。 因此，无论怎样，你都不可能绕环路行驶一周。
提示:
n == gas.length == cost.length1 <= n <= 1050 <= gas[i], cost[i] <= 104- 输入保证答案唯一。
i = i + cnt +1 的本质 就是x能到达y但不能到达y+1，实际上说明了：x与y之间的任意一个点（设为k）的不可能比x还“富裕”，因为x能到达k，则一定说明x到达k的时候一定油量是有余或者刚好的，不能是亏欠的；那么如果x都到达不了，“白手起家”的k就更不可能了。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int i = 0;
while (i < n) {
int sumOfGas = 0, sumOfCost = 0;
int cnt = 0;
while (cnt < n) {
int j = (i + cnt) % n;
sumOfGas += gas[j];
sumOfCost += cost[j];
if (sumOfCost > sumOfGas) {
break;
}
cnt++;
}
if (cnt == n) {
return i;
} else {
i = i + cnt + 1;
}
}
return -1;
}
};
135. 分发糖果
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 * 10
我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理。
左规则：当 ratings[i−1]<ratings[i] 时，i 号学生的糖果数量将比 i−1 号孩子的糖果数量多。
右规则：当 ratings[i]>ratings[i+1] 时，i 号学生的糖果数量将比 i+1 号孩子的糖果数量多。
我们遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。
ret += max(left[i],right);
两次遍历
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> left(n);
for (int i = 0; i < n; i++) {
if (i > 0 && ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
} else {
left[i] = 1;
}
}
int right = 0, ret = 0;
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1 && ratings[i] > ratings[i + 1]) {
right++;
} else {
right = 1;
}
ret += max(left[i], right);
}
return ret;
}
};
常数空间遍历
if(inc = dec) dec++;
假设评分序列是 [1, 3, 5, 4, 3, 2]
- 递增阶段：
1→3→5，inc会逐渐变为 3（对应糖果数：1, 2, 3）。 - 递减阶段：
5→4→3→2，dec会从 1 开始增加：- 4 比 5 小：
dec=1（糖果数：2） - 3 比 4 小：
dec=2（糖果数：1） - 2 比 3 小：
dec=3（此时dec == inc，触发dec++，dec变为 4）
- 4 比 5 小：
为什么要dec++？
- 原递增序列的最后一个元素（5）的糖果数是 3（由
inc=3决定）。 - 当递减序列长度达到 3 时（4,3,2），按规则它们的糖果数应该是 2,1,0，但 0 违反 “至少 1 颗”，且 5 的糖果数（3）需要比 4 的糖果数（2）多，这没问题。
- 但当递减序列长度等于递增序列长度时（都是 3），此时递减序列的第一个元素（4）的糖果数（2）和递增序列的倒数第二个元素（3）的糖果数（2）相等，而 4 的评分比 3 高（5>4 但 4>3），这没问题？不，更深层的问题是：
若dec不增加，递增序列的最后一个元素（5）的糖果数（3）会等于递减序列延伸后的某个位置的糖果数，导致需要 “再额外加 1 颗” 才能满足规则。
简单说：当dec == inc时，说明递减序列已经 “追上” 递增序列的长度，此时需要将递增序列的最后一个元素也纳入递减序列的计数中（相当于给它多 1 颗糖），否则会出现糖果数不足的冲突。dec++就是通过增加递减序列的计数，在累加总糖果时把这部分额外的糖果算进去，确保规则成立。
- 依据前面总结的规律，我们可以提出本题的解法。我们从左到右枚举每一个同学，记前一个同学分得的糖果数量为 pre：
- 如果当前同学比上一个同学评分高，说明我们就在最近的递增序列中，直接分配给该同学 pre+1 个糖果即可。
- 否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，并把该同学所在的递减序列中所有的同学都再多分配一个糖果，以保证糖果数量还是满足条件。
- 我们无需显式地额外分配糖果，只需要记录当前的递减序列长度，即可知道需要额外分配的糖果数量。
- 同时注意当当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中。
- 这样，我们只要记录当前递减序列的长度 dec，最近的递增序列的长度 inc 和前一个同学分得的糖果数量 pre 即可。
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
int ret = 1;
int inc = 1, dec = 0, pre = 1;
for (int i = 1; i < n; i++) {
if (ratings[i] >= ratings[i - 1]) {
dec = 0;
pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
ret += pre;
inc = pre;
} else {
dec++;
if (dec == inc) {
dec++;
}
ret += dec;
pre = 1;
}
}
return ret;
}
};
42. 接雨水
已解答
困难
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5] 输出：9
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
动态规划
如果已经知道每个位置两边的最大高度，则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。
创建两个长度为 n 的数组 leftMax 和 rightMax。对于 0≤i<n，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度，rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。
显然，leftMax[0]=height[0]，rightMax[n−1]=height[n−1]。两个数组的其余元素的计算如下：
当 1≤i≤n−1 时，leftMax[i]=max(leftMax[i−1],height[i])；
当 0≤i≤n−2 时，rightMax[i]=max(rightMax[i+1],height[i])。
因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值，反向遍历数组 height 得到数组 rightMax 的每个元素值。
在得到数组 leftMax 和 rightMax 的每个元素值之后，对于 0≤i<n，下标 i 处能接的雨水量等于 min(leftMax[i],rightMax[i])−height[i]。遍历每个下标位置即可得到能接的雨水总量。
动态规划做法可以由下图体现。
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n == 0) {
return 0;
}
vector<int> leftMax(n);
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = max(leftMax[i - 1], height[i]);
}
vector<int> rightMax(n);
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
};
双指针（直接看这个解法）
当两个指针没有相遇时，进行如下操作：
使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；
如果 height[left]<height[right]，则必有 leftMax<rightMax，下标 left 处能接的雨水量等于 leftMax−height[left]，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）；
如果 height[left]≥height[right]，则必有 leftMax≥rightMax，下标 right 处能接的雨水量等于 rightMax−height[right]，将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减 1（即向左移动一位）。
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
int left = 0, right = height.size() - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = max(leftMax, height[left]);
rightMax = max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
};
13. 罗马数字转整数
罗马数字包含以下七种字符: 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 <= 15s仅含字符('I', 'V', 'X', 'L', 'C', 'D', 'M')- 题目数据保证
s是一个有效的罗马数字，且表示整数在范围[1, 3999]内 - 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
- IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
- 关于罗马数字的详尽书写规则，可以参考 罗马数字 - 百度百科。
i < n - 1 && value < symbolValues[s[i + 1]
本位比下一位要小，那么这个本位是要被减去的 防止越界 i < n-1
class Solution {
private:
unordered_map<char, int> symbolValues = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000},
};
public:
int romanToInt(string s) {
int ans = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
int value = symbolValues[s[i]];
if (i < n - 1 && value < symbolValues[s[i + 1]]) {
ans -= value;
} else {
ans += value;
}
}
return ans;
}
};
12. 整数转罗马数字
七个不同的符号代表罗马数字，其值如下：
| 符号 | 值 |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：
- 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
- 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (
V) 减 1 (I):IV，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。 - 只有 10 的次方（
I,X,C,M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。
给定一个整数，将其转换为罗马数字。
示例 1：
输入：num = 3749
输出： "MMMDCCXLIX"
解释：
3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M) 700 = DCC 由于 500 (D) + 100 (C) + 100 (C) 40 = XL 由于 50 (L) 减 10 (X) 9 = IX 由于 10 (X) 减 1 (I) 注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位
示例 2：
输入：num = 58
输出："LVIII"
解释：
50 = L 8 = VIII
示例 3：
输入：num = 1994
输出："MCMXCIV"
解释：
1000 = M 900 = CM 90 = XC 4 = IV
提示：
1 <= num <= 3999
模拟
引用遍历使用技巧
std::map<std::string, int> mp = { {"a", 1}, {"b", 3} };
// 使用引用（&）遍历，才能修改原容器元素
for (auto &a : mp) { // 注意这里的 &
a.first = "k"; // 修改键（字符串类型匹配）
a.second = 4; //
}const pair<int, string> valueSymbols[] = {
{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"},
};
class Solution {
public:
string intToRoman(int num) {
string roman;
for (const auto &[value, symbol] : valueSymbols) {
while (num >= value) {
num -= value;
roman += symbol;
}
if (num == 0) {
break;
}
}
return roman;
}
};
硬编码 空间换时间
直接哈希每一位的取值
58. 最后一个单词的长度
给你一个字符串 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 <= 104s仅有英文字母和空格' '组成s中至少存在一个单词
给你一个字符串 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 <= 104s包含英文大小写字母、数字和空格' 's中 至少存在一个 单词
进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
#include <algorithm>
#include <string>
using namespace std;
class Solution {
public:
string reverseWords(string s) {
// 1. 反转整个字符串
reverse(s.begin(), s.end());
int n = s.size();
int idx = 0; // 记录当前有效字符的位置
for (int start = 0; start < n; ++start) {
if (s[start] == ' ') continue; // 跳过空格
// 非空格字符：先加空格（除了第一个单词）
if (idx != 0) s[idx++] = ' ';
// 复制整个单词到当前位置
int end = start;
while (end < n && s[end] != ' ')
s[idx++] = s[end++];
// 反转当前单词
reverse(s.begin() + idx - (end - start), s.begin() + idx);
start = end; // 移动到下一个空格或结尾
}
// 截断多余字符并返回
s.resize(idx);
return s;
}
};
这种先处理局部再处理整体代码会比较复杂 ，先处理整体再处理局部比较好
碰到一个新字符串 begin 不动 ，end 找到末尾然后停下，反转begin 和 end 之间
碰到空格 begin = ++end
处理好后，整体再翻转一遍 删除多余空格
6. 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 <= 1000s由英文字母（小写和大写）、','和'.'组成1 <= numRows <= 1000
class Solution {
public:
string convert(string s, int numRows) {
int n = s.length(), r = numRows;
if (r == 1 || r >= n) {
return s;
}
string ans;
int t = r * 2 - 2;
for (int i = 0; i < r; ++i) { // 枚举矩阵的行
for (int j = 0; j + i < n; j += t) { // 枚举每个周期的起始下标
ans += s[j + i]; // 当前周期的第一个字符
if (0 < i && i < r - 1 && j + t - i < n) {
ans += s[j + t - i]; // 当前周期的第二个字符
}
}
}
return ans;
}
};
