## 1005.K次取反后最大化的数组和 #### 思路

1. 首先将整个数组按照绝对值的大小从大到小排列
2. 当有反转次数并且为负数时，反转负数
3. 如果反转次数有剩余，那么反转绝对值最小的数，即排序后的数组尾数。

#### 实现

``````class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int result = 0;
sort(nums.begin(), nums.end(), cmp);
for(int i = 0 ; i < nums.size()-1; i++) {
if(nums[i] < 0 && k > 0) {
result += -nums[i];
k--;
}
else {
result += nums[i];
}
cout << result << endl;
}
if( k >=1 && k % 2 == 1) {
result += -nums[nums.size() - 1];
}
else {
result += nums[nums.size() - 1];
}

return result;

}
bool static cmp(int a, int b) {
return abs(a) > abs(b);
}
};
``````

#### 复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

## 134.加油站 #### 实现

``````class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& 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) {
curSum = 0;
start = i + 1;
}
}
if(totalSum < 0) return -1;
return start;
}
};
``````

• 时间复杂度：O(n)
• 空间复杂度：O(1)

## 135. 分发糖果 #### 思路

1. 考虑右边孩子比左边孩子优秀的情况‘
2. 考虑左边孩子比右边孩子优秀的情况

#### 实现

``````class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyCount(ratings.size(), 1);
for(int i = 0; i < ratings.size() - 1; i++) {
if(ratings[i+1] > ratings[i]) candyCount[i+1] = candyCount[i] + 1;
//cout << candyCount[i] <<endl;
}
for(int i = ratings.size() - 2; i >= 0; i--) {
if(ratings[i] > ratings[i+1]) candyCount[i] = max(candyCount[i], candyCount[i+1] + 1);
//cout<<candyCount[i]<<endl;
}
int result = 0;
for(auto a : candyCount)  result += a;
return result;
}
};
``````

#### 复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
{"ft_lang_label":"__label__zh","ft_lang_prob":0.60895276,"math_prob":0.9983616,"size":2251,"snap":"2023-40-2023-50","text_gpt3_token_len":1367,"char_repetition_ratio":0.11927014,"word_repetition_ratio":0.073426574,"special_character_ratio":0.33807197,"punctuation_ratio":0.19059406,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.988944,"pos_list":[0,1,2,3,4,5,6],"im_url_duplicate_count":[null,1,null,1,null,1,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-11T05:55:04Z\",\"WARC-Record-ID\":\"<urn:uuid:2d69b7af-9c6e-4c2e-b31d-9cb210ba28c3>\",\"Content-Length\":\"31334\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:5dddc018-8454-4c62-9032-15fe9de80658>\",\"WARC-Concurrent-To\":\"<urn:uuid:d7330855-dd65-4ca7-8355-e8c7abbd822b>\",\"WARC-IP-Address\":\"39.99.242.93\",\"WARC-Target-URI\":\"https://www.sucaidaohang.com/23713.html\",\"WARC-Payload-Digest\":\"sha1:OH5IONIO26EQ6FZVW2OHQMHGKXDIATWE\",\"WARC-Block-Digest\":\"sha1:2EQI2JM7FAHUUHCF52YLMNVQIEIQDIK7\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679103558.93_warc_CC-MAIN-20231211045204-20231211075204-00775.warc.gz\"}"}