0616刷题
LeetCode 55. 跳跃游戏 LeetCode 55. 跳跃游戏思路：贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。
而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。
如果cover大于等于了终点下标，直接return true就可以了。
class Solution {
public:
bool canJump(vector& nums) {
int cover = 0;
if (nums.size() == 1) return true; // 只有一个元素，就是能达到
for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
cover = max(i + nums[i], cover);
if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
}
return false;
}
};
注意得是cover范围以内的。
理解：开头就是0的案例[0,2,3]和[1,0,1,0]
LeetCode 45. 跳跃游戏 II LeetCode 45. 跳跃游戏 II// 版本二
class Solution {
public:
int jump(vector& nums) {
int curDistance = 0; // 当前覆盖的最远距离下标
int ans = 0; // 记录走的最大步数
int nextDistance = 0; // 下一步覆盖的最远距离下标
for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在
nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标
if (i == curDistance) { // 遇到当前覆盖的最远距离下标
curDistance = nextDistance; // 更新当前覆盖的最远距离下标
ans++;
}
}
return ans;
}
};
在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。
LeetCode 1005. K 次取反后最大化的数组和 LeetCode 1005. K 次取反后最大化的数组和 自己写的垃圾方法：直接暴力class Solution {
public:
int largestSumAfterKNegations(vector& nums, int k) {
sort(nums.begin(),nums.end());
int sum=0;
int low=0;
while(k>nums.size())
{
k=k-2;
}
for(int i=0;i
if(k>0)
{
if(nums[i]<0)
{
low=i;
nums[i]=-nums[i];
k--;
}
else if(nums[i]>=0&&k%2==1)
{
if(nums[i]>=nums[low]) nums[low]=-nums[low];
else nums[i]=-nums[i];
k=0;
}
else if(nums[i]>=0&&k%2==0) k=0;
}
}
for(int i=0;i
sum+=nums[i];
}
return sum;
}
};
较为好的贪心算法：
思路基本相同，但是最开始的数据处理上面，没有考虑到直接按照绝对值大小进行排序
class Solution {
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
public:
int largestSumAfterKNegations(vector& nums, int k) {
sort(nums.begin(), nums.end(), cmp); // 第一步
for (int i = 0; i < nums.size(); i++) { // 第二步
if (nums[i] < 0 && k > 0) {
nums[i] *= -1;
k--;
}
}
if (k % 2 == 1) nums[nums.size() - 1] *= -1; // 第三步
int result = 0;
for (auto& num : nums) result += num; // 第四步
return result;
}
};
贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
局部最优可以推出全局最优。
那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。
那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了），全局最优：整个 数组和 达到最大。
那么本题的解题步骤为：
- 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
- 第二步：从前向后遍历，遇到负数将其变为正数，同时K–
- 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
- 第四步：求和
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = 0; i < gas.size(); i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0
start = i + 1; // 起始位置更新为i+1
curSum = 0; // curSum从0开始
}
}
if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
return start;
}
};
自己没写出来
扩展gas和cost数组，进行sum，小于0则break。
//wrong answer
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
int sum=0;
int count=gas.size();
int size=gas.size();
int result=0;
for(int i=0;i
sum+=gas[i]-cost[i];
}
if(sum<0) return -1;
for(int i=0;i
gas.push_back(gas[i]);
cost.push_back(cost[i]);
}
//1 2 3 4 5 //1 2 3 4 5
//3 4 5 1 2 //3 4 5 1 2
int j;
for(int i=0;i
sum=0;
j=i;
while(count--)
{
sum=sum+gas[j]-cost[j];
j++;
if(sum<0)
{
break;
}
}
if(count==0&&sum>=0) return i;
}
// if(count==0) return result;
return -1;
}
};
