每日题目-1.2：每日一题+41+42
1. 每日一题390：消除游戏
题目
列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：
从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
给你整数 n ，返回 arr 最后剩下的数字。
输入：n = 9
输出：6
解释：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]
输入：n = 1
输出：1
1 <= n <= 10^9
思路
约瑟夫问题。约瑟夫用dp做。
一开始从左往右删，之后从右往左删以此类推。可以发现每次删除假设删前数为n则删除的个数为int(n / 2)。
我们用f(n)代表将1-n先从左到右再从右到左遍历最后剩下来的数字，用g(n)代表将1-n先从右到左，再从左到右遍历最后剩下来的数字。
可以发现有如下规律：
1是初始状态。
2假设初始数组是[1,2,3,4,5,6]，最终剩下来的数字是f(6)，经过第一轮从左到右遍历后剩下来的是[2,4,6]，恰好是2 * [1,2,3]，但是这时候我们开始要从右侧开始遍历了，最终剩下来的数字是g(3)，我们可以发现f(6)=2∗g(3)。如果初始数组长度为奇数得到的结果是一样的。
3假设f(n)最终留下来的是从左到右的第k个数字，可以发现g(n)和f(n)的操作是对称的，剩下来的是从右到左的第k个数字，二者相加之和为n+1。
最终结果推得公式有：
代码
class Solution {
public:
int lastRemaining(int n) {
if(n == 1) return 1;
return 2 * (n / 2 + 1 - lastRemaining(n / 2));
}
};
2. 41: 组合总和
题目
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
输入：nums = [1,2,0]
输出：3
输入：nums = [3,4,-1,1]
输出：2
输入：nums = [7,8,9,11,12]
输出：1
1 <= nums.length <= 5 * 10^5
-2^31 <= nums[i] <= 2^31 - 1
思路
哈希表可以实现复杂度o(n)。但要求常数级空间。
使用桶排序可满足常数级空间：1出现在nums[0]上，2在nums[1]上，…，n在nums[n-1]上，其他的非正数不管。例如[3,4,-1,1]将被排序为[1,-1,3,4]
在操作前先遍历整个数组除了INT_MIN以外的数全部减一，保证之后的数swap时能满足nums[i] == i。
遍历nums，找到第一个不在应在位置上的1到n的数，并返回i + 1，如果最后没有则返回n + 1。例如，排序后的[1,-1,3,4]中第一个 nums[i] != i的是数字1。
复杂度
代码中第二层while循环，每循环一次，会将一个数放在正确的位置上，所以总共最多执行 n 次，所以总时间复杂度O(n)。
代码
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 1;
for(int i = 0; i < n; i++)
if(nums[i] != INT_MIN) nums[i] --;
for(int i = 0; i < n; i++){
while(nums[i] >= 0 && nums[i] < n && nums[i] != i && nums[i] != nums[nums[i]])
swap(nums[i], nums[nums[i]]);
}
for(int i = 0; i < n; i++)
if(nums[i] != i) return i + 1;
return n + 1;
}
};
3. 42: 接雨水
题目
给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。
输入：height = [4,2,0,3,2,5]
输出：9
n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5
思路
单调栈做法。
代码
class Solution {
public:
int trap(vector<int>& height) {
stack<int> sta;
int res = 0;
for(int i = 0; i < height.size(); i++){
int last = 0;
while(sta.size() && height[sta.top()] <= height[i]){
res += (height[sta.top()] - last) * (i - sta.top() - 1);
last = height[sta.top()];
sta.pop();
}
if(sta.size()) res += (height[i] - last) * (i - sta.top() - 1);
sta.push(i);
}
return res;
}
};```