1005. K次取反后最大化的数组和
1. LeetCode链接
1005. K 次取反后最大化的数组和 - 力扣(LeetCode)
2. 题目描述
3. 解法
整体来说,就是把负数全部取反,然后如果有剩余反转次数都给绝对值最小的数。
我的解法:先从小到大排序,这个需要分析多种情况。略。
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int i = 0;
int sum = 0;
for (; i < nums.size() && k > 0; i++) {
if (nums[i] >= 0) break;
nums[i] = 0 - nums[i];
sum += nums[i];
k--;
}
if (i != nums.size() && k != 0) {
if (i > 0 && nums[i] > nums[i - 1]) {
i--;
sum -= nums[i];
}
if (k % 2 == 1) nums[i] = 0 - nums[i];
} else if (i == nums.size() && k != 0) {
if (k % 2 == 1) sum -= 2 *nums[nums.size() - 1];
}
for (; i < nums.size(); i++) {
sum += nums[i];
}
return sum;
// k <= nums中的非正数个数
// k > nums中的非正数个数 && 有0
// k > nums中的非正数个数 && no 0
// nums中全是非正数
}
};
简洁方法,直接按照绝对值大小排序。
class Solution {
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), cmp);
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
if(nums[i] < 0 && k > 0) {
nums[i] *= -1;
k--;
}
sum += nums[i];
}
if (k % 2 == 1) sum -= 2 * nums[nums.size() - 1];
return sum;
}
};
134. 加油站
1. LeetCode链接
134. 加油站 - 力扣(LeetCode)
2. 题目描述
3. 解法
整体来说,如果gas的总量 < cost的总量,汽车无论如何都不可能循环一周。否则,必可以循环一周。
我的解法:
1. 判断两个数组总量是否合理。求得存储两数组对应元素差值的数组left(表示,空油箱从i节点出发,到i + 1节点还能剩多少油)。
2. 如果left总和 < 0,直接return -1.
3. 如果left综合 > =0。在left数组上执行类似于LeetCode题目53.最大子序和的操作。首先,记录最大子序的长度len,直到长度与原数组长度相等,return 当前下标;count持续记录连续序列和,如果<0,则刷新len和count。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int count = 0;
vector<int> left;
for (int i = 0; i < gas.size(); i++) {
left.push_back(gas[i] - cost[i]);
}
for (int i : left) count += i;
if (count < 0) return -1;
int len = gas.size();
int i = 0;
count = 0;
while (1) {
if (len == 0) return i;
count += left[i];
len--;
if (count < 0) {
count = 0;
len = gas.size();
}
i = (i + 1) % gas.size();
}
}
};
还有更简单的是,记录累加和初始坐标start,这样可以在一遍遍历后得到答案,而且只需一次遍历。
因为如果在计算局部累加和时,count < 0,则说明其对应累加初始坐标一定不是循环起始点,累加和之间的坐标,也不是!这时,初始化count并记录start。
最后,因为是一次从前到后的完整遍历。判断记录后的累加差值是负数,则return -1。否则,return start。
start之后的是否可能也存在循环起点?因为start到末尾的累加和中,从来没有小于过0,所以,start一定是第一个。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int start = 0;
int count = 0;
int sum = 0;
for (int i = 0; i < gas.size(); i++) {
count += gas[i] - cost[i];
sum += gas[i] - cost[i];
if (count < 0) {
count = 0;
start = i + 1;
}
}
if (sum < 0) return -1;
return start;
}
};
135. 分发糖果
1. LeetCode链接
135. 分发糖果 - 力扣(LeetCode)
2. 题目描述
3. 解法
我的解法:
整体来说,就是每个孩子尽可能拿最少的糖果数量。
一般我们自己解这种题,都是先找极小值;然后,将极小值点设为1(颗糖果),从极小值开始,向左爬升到极大值点,糖果数量依次+1,向右爬升到极大值点,糖果数量一次+1。
编程时,需要先计算完所有极小值点向一侧爬升后,再考虑一起从另一侧爬升。这是因为一个极大值点,两侧各有一个极小值点;左侧极小值点向右爬升得到的糖果数量 和 右侧极小值点向左爬升得到的糖果数量,当前极大值点要取最大值。如果按极小值点先后顺序同时考虑两侧爬升,并不能考虑到这一点。
class Solution {
public:
int candy(vector<int>& ratings) {
int pre = ratings[0];
int cur;
int post = 0;
vector<int> index;
vector<int> candies(ratings.size(), 0); // 记录每个孩子能分发到的最终糖果数量
for (int i = 0; i < ratings.size(); i++) { // 找极小值点,其中判断时,仅考虑非严格递增/递减
if (i == ratings.size() - 1) post = ratings[i];
else post = ratings[i + 1];
cur = ratings[i];
if (pre >= cur && cur <= post) index.push_back(i);
pre = cur;
}
for (int i = 0; i < index.size(); i++) { // 从所有极小值点出发,向左爬升
candies[index[i]] = 1;
int c = 2;
for (int j = index[i] - 1; j >=0; j--) {
if (ratings[j] <= ratings[j + 1]) break;
candies[j] = c;
c++;
}
}
for (int i = 0; i < index.size(); i++) { // 从所有极小值点出发,向右爬升
int c = 2;
for (int j = index[i] + 1; j < ratings.size(); j++) {
if (ratings[j] <= ratings[j - 1]) break;
if (candies[j] > c) break;
candies[j] = c;
c++;
}
}
int sum = 0;
for (int i : candies) sum += i; // 求和
return sum;
}
};
巧妙解法:
局部最优:所有孩子的相邻右孩子如果评分比他高的话+1糖果;所有孩子的相邻左孩子如果评分比他高的话+1糖果。
全局最优:相邻两个孩子评分更高的孩子会获得更多的糖果。
1. 先设置数组记录每个孩子分到的糖果数,设置基数都为1,即每个孩子都分到一个。
2. 从左向右遍历,如果当前孩子评分比前一个高,前一个糖果数+1。
3. 从右向左遍历,如果当前孩子评分比后一个高,取他原本的数/后一个糖果数+1中最大的。
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candies(ratings.size(), 1);
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = max(candies[i], candies[i + 1] + 1);
}
}
int sum = 0;
for (int i : candies) sum += i;
return sum;
}
};