2019-01-27 第三天 (#134, #274, #275
#134 Gas Station
题目地址：https://leetcode.com/problems/gas-station/
这题和array真的有关系吗……
这题我自己没做出来，看的答案。
为了方便，我们把两个数组相减，gas-cost之后得到的新数组为remain；
而对这个数组从左往右求和，使得部分和最小的下标再+1就是出发点。
用数学语言描述大概就是：
若
remain[0] + remain[1] + ... + remain[i]
最小，则出发点下标为[i+1]。
考虑到他给出来的数组组合只能产生唯一解，我们需要证明从[i+1]出发的所有部分和都不小于0，即：
remain[i+1] >=0
remain[i+1] + remain[i+2] >= 0
...
remain[i+1] + ... + remain[n-1] >=0
remain[i+1] + ... + remain[n-1] + remain[0] >=0
remain[i+1] + ... + remain[n-1] + remain[0] + remain[1] >=0
...
remain[i+1] + ... + remain[n-1] + remain[0] + ... + remain[i-1] >= 0
（即此解成立）就能证明此处为最优解。
证明如下：
首先，由于
remain[0] + remain[1] + ... + remain[i]
最小，
由
remain[0] + ... + remain[i] + remain[i+1] > remain[0] + remain[1] + ... + remain[i]
得
remain[i+1] >=0
同理，我们可得
remain[i+1] >=0
remain[i+1] + remain[i+2] >= 0
...
remain[i+1] + ... + remain[n-1] >=0
然后同样是根据
remain[0] + remain[1] + ... + remain[i]
最小，我们有
remain[0] + remain[1] + ... + remain[j] > remain[0] + remain[1] + ... + remain[i]
(此处j<i），而
remain[0] + remain[1] + ... + remain[i] + remain[i+1] + ... + remain[n-1] > 0
(由于解存在）
故
remain[0] + remain[1] + ... + remain[j] + remain[i+1] + ... + remain[n-1] > 0
等式得证。
实现本身很简单，如下：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int smallest = gas.at(0) - cost.at(0);
int startpoint = 1;
int total = 0;
for(int i = 0; i < gas.size(); i++){
total += gas.at(i) - cost.at(i);
if(total < smallest){
smallest = total;
startpoint = i+1;
}
}
if(total < 0)
return -1;
else if(startpoint == gas.size())
return 0;
else
return startpoint;
}
};
时间复杂度为O(n)，空间复杂度O(1)。
#274 H-Index
题目地址：https://leetcode.com/problems/h-index/
题目本身挺简单，对数组逆向排序一次，然后遍历数组，判断当前的下标是否大于引用数，如果大于引用数就让影响因子等于下标，退出循环。
class Solution {
public:
bool static comp(int a, int b){
return (a>b);
}
int hIndex(vector<int>& citations) {
int index = citations.size();
sort(citations.begin(), citations.end(), comp);
for(int i = 0; i < citations.size(); i++){
if(i >= citations.at(i)){
index = i;
break;
}
}
return index;
}
};
有两个问题要注意：
一个问题是要注意当数组内的所有引用数都大于数组长度的时候，这个时候影响因子应该取数组长度。这个问题可以在初始化的时候解决。
第二个是要std::sort()函数接受的comp必须要是函数指针或者是对象（cplusplus.com原文：This can either be a function pointer or a function object.）在这里定义comp的时候要加上static，否则编译不能通过。
时间复杂度是O(nlogn)（排序算法复杂度），空间复杂度O(1)。太久没做需要排序的题咯。
275 H-Index II
题目地址：https://leetcode.com/problems/h-index-ii/
待续，看完知乎的帖子再说。
更新：
彻底复习+学习了一边二分查找法/分叉搜索法(Binary Search)，现在的解法应该来自于C++标准库里<algorithm>的写法，只有一个判断条件和一个+1/-1操作，左开右闭区间，能够应对存在复数个所需值的情形，还避免了溢出。代码如下：
class Solution {
public:
int hIndex(vector<int>& citations) {
int front = 0, end = citations.size();
int index, mid;
while(front < end){
mid = front + (end - front) / 2; // avoid overflow
index = citations.size() - mid;
if(citations.at(mid) < index)
front = mid + 1;
else
end = mid;
}
index = citations.size() - front;
return index;
}
};
首先要明确这道题到底要干什么：
对于引用数citations和文章数index，需要找到在所有引用数不小于文章数citations >= index情况下的最小引用数citations，并返回这个最小引用数对应的文章数index。
确实有点绕：我们要找的是引用数，但是实际返回的是文章数。
换言之这是一个寻找引用数下界的问题，用这种写法正好（上界的结果和下界也只差1而已）。
要注意的是这种写法最后的mid并不是寻找结果，first或者last才是，而且这个时候first == last。
时间复杂度O(logN)，空间复杂度O(1)。
