1. 加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -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 升汽油。 因此，无论怎样，你都不可能绕环路行驶一周。
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int index = 0; int sum = 0; int csum = 0; for (int i = 0; i < gas.size(); i++) { int temp = gas[i] - cost[i]; sum += temp; if (csum > 0) { csum += gas[i] - cost[i]; } else { csum = gas[i] - cost[i]; index = i; } } return sum >= 0 ? index : -1; } }; int main() { Solution s; vector<int> gas = {1,2,3,4,5}, cost = {3,4,5,1,2}; cout << s.canCompleteCircuit(gas, cost) << endl; gas = {2,3,4}, cost = {3,4,3}; cout << s.canCompleteCircuit(gas, cost) << endl; return 0; }
输出：
3
-1
2. 拼接最大数
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
示例 1:
输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]
示例 2:
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]
示例 3:
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<int> maxNumber(vector<int> &nums1, vector<int> &nums2, int k) { vector<int> ans; const int n1 = nums1.size(); const int n2 = nums2.size(); for (int k1 = 0; k1 <= k; ++k1) { const int k2 = k - k1; if (k1 > n1 || k2 > n2) { continue; } ans = max(ans, maxNumber(maxNumber(nums1, k1), maxNumber(nums2, k2))); } return ans; } private: vector<int> maxNumber(const vector<int> &nums, const int k) { if (k == 0) { return {}; } vector<int> ans; int to_pop = nums.size() - k; for (const int num : nums) { while (!ans.empty() && num > ans.back() && to_pop-- > 0) { ans.pop_back(); } ans.push_back(num); } ans.resize(k); return ans; } vector<int> maxNumber(const vector<int> &nums1, const vector<int> &nums2) { vector<int> ans; auto s1 = nums1.cbegin(); auto e1 = nums1.cend(); auto s2 = nums2.cbegin(); auto e2 = nums2.cend(); while (s1 != e1 || s2 != e2) { ans.push_back(lexicographical_compare(s1, e1, s2, e2) ? *s2++ : *s1++); } return ans; } }; int main() { Solution s; vector<int> res, nums1 = {3, 4, 6, 5}, nums2 = {9, 1, 2, 5, 8, 3}; int k = 5; res = s.maxNumber(nums1, nums2, k); copy(res.begin(), res.end(), ostream_iterator<int>(cout," ")); cout << endl; nums1 = {6, 7}, nums2 = {6, 0, 4}; res = s.maxNumber(nums1, nums2, k); copy(res.begin(), res.end(), ostream_iterator<int>(cout," ")); cout << endl; nums1 = {3, 9}, nums2 = {8, 9}, k=3; res = s.maxNumber(nums1, nums2, k); copy(res.begin(), res.end(), ostream_iterator<int>(cout," ")); return 0; }
输出：
9 8 6 5 3
6 7 6 0 4
9 8 9
3. 下一个排列
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1:
输入:
nums = [1, 2, 3]
输出:
[1, 3, 2]
示例 2:
输入:
nums = [3, 2, 1]
输出:
[1, 2, 3]
示例 3:
输入:
nums = [1, 1, 5]
输出:
[1, 5, 1]
示例 4:
输入:
nums1 = [1]
输出:
[1]
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: void nextPermutation(vector<int>& nums) { int n = nums.size(), i = n - 2, j = n - 1; while (i >= 0 && nums[i] >= nums[i + 1]) --i; if (i >= 0) { while (nums[j] <= nums[i]) --j; swap(nums[i], nums[j]); } reverse(nums.begin() + i + 1, nums.end()); } }; int main() { Solution s; vector<int> nums = {1, 2, 3}; s.nextPermutation(nums); copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," ")); cout << endl; nums = {3, 2, 1}; s.nextPermutation(nums); copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," ")); cout << endl; nums = {1, 1, 5}; s.nextPermutation(nums); copy(nums.begin(), nums.end(), ostream_iterator<int>(cout," ")); cout << endl; return 0; }
输出：
1 3 2
1 2 3
1 5 1
附录
排列与组合
是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。
基本原理
⑴加法原理和分类计数法
⒈加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+m3+…+mn种不同方法。
⒉第一类办法的方法属于集合A1，第二类办法的方法属于集合A2，……，第n类办法的方法属于集合An，那么完成这件事的方法属于集合A1UA2U…UAn。
⒊分类的要求 ：每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同（即分类不重）；完成此任务的任何一种方法，都属于某一类（即分类不漏）。
⑵乘法原理和分步计数法
⒈ 乘法原理：
做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N=m1×m2×m3×…×mn种不同的方法。
⒉合理分步的要求
任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不同。
3.与后来的离散型随机变量也有密切相关。
著名问题
计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。
地图着色问题
对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。
船夫过河问题
船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。
中国邮差问题
由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。
任务分配问题
有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？这是线性规划的问题。
