1005.K次取反後最大化的數組和
力扣題目連結
思路
方法一
- 兩次貪心
- 第一次，局部最優：将絕對值最大的負數變為正數，目前數值達到最大，全局最優：整個數組和達到最大
- 第二次，局部最優：隻找數值最小的正整數進行反轉，目前數值可以達到最大，全局最優：整個數組和達到最大
本題的解題步驟為：
- 第一步：将數組按照絕對值大小從大到小排序，注意要按照絕對值的大小
- 第二步：從前向後周遊，遇到負數将其變為正數，同時k–
- 第三步：如果k還大于0，那麼反複轉變數值最小的元素，将K用完
-
- 剩餘取反次數為偶數：不用取反
- 剩餘取反次數為奇數：此時從目前數值中取一個絕對值最小值進行取反，得到最終的取反數組。
- 第四步：求和
方法二
- 利用哈希桶排序
- 将數組通過哈希升序排序
- 對負數進行取反（注意取反細節，目前指向負數的個數會出現小于需要取反的個數k的情況）
- 剩餘取反次數為偶數：不用取反
- 剩餘取反次數為奇數：此時從目前數值中取一個絕對值最小值進行取反，得到最終的取反數組。
- 求和可以在過程中進行也可以在最後求和
代碼
方法一
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);
//對負數進行取反
for(int i=0;i<nums.size();i++){
if(nums[i]<0&&k>0){
nums[i]*=-1;
k--;
}
if(k==0) break;
}
//如果剩餘的k為奇數，取反絕對值最小的數
if(k%2==1) nums[nums.size()-1]*=-1;
//求和
int ans=0;
for(int i=0;i<nums.size();i++)
ans+=nums[i];
return ans;
}
};
- 時間複雜度
O(nlogn)
- 空間複雜度
O(1)
方法二
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
unordered_map<int,int> map;
int ans=0;
//哈希-桶排序
for(int i=0;i<nums.size();i++){
map[nums[i]]++; //key=數的大小，value=大小為key的數的個數
ans+=nums[i];//求和
}
//對負數進行取反
for(int i=-100;i<0;i++){
if(map[i]){
int ops=min(k,map[i]);//處理需要取反的個數k小于目前負數i的個數的情況
ans+=(-i)*ops*2;
map[-i]+=ops; //取反ops個負數i
k-=ops;
map[i]-=ops; //map[i]剩餘map[i]-ops個負數
}
if(k==0) break;
}
//如果剩餘的k為奇數，減去反絕對值最小的數的兩倍
for(int i=0;k%2==1&&i<=100;i++){
if(map[i]){
ans-=i*2;
break;
}
}
return ans;
}
};
- 時間複雜度
O(n+C)
- 空間複雜度
O(C)
134.加油站
力扣題目連結
思路
1. 暴力解
- for循環控制從頭到尾周遊數組
- while循環模拟跑一圈
2. 貪心1
- 情況一：如果總油量減總消耗小于0，那麼一定跑不完一圈。
- 情況二：從0開始累加沒有出現負數，說明從0出發能夠到達終點。
- 情況三：如果累加的最小值是負數，從後往前看，哪個節點能夠填平這個負數，哪個節點就是出發節點。
- 下面是針對情況三的改進（以下總油量都是指每個加油站的剩餘量rest[i]=gas[i] - cost[i]相加）：因為總油量大于0且正向逐個相加中出現了最大負數，說明在這個站點之後的各站點的總油量為整數且必然大于等于最大負數的絕對值，是以最大負數的下一站就是出發節點。（假設從最大負數的下一站x到終點經過了z，因為x能到達終點，那麼x到達z的油量一定是大于等于0的，可以推出從x出發到終點的剩餘油量必然大于從[x,終點]之間的任意點出發到達終點的剩餘油量。由于題目設定隻有唯一解，如果x結點不是出發節點，[x,終點]之間的結點必然也不是出發節點，是以x結點就是出發節點）。
3. 貪心2
- 如果總油量減總消耗大于0，一定能跑完一圈
- 每個加油站的剩餘量rest[i]為gas[i] - cost[i]
- i從0開始累加rest[i]，和記為curSum，一旦curSum小于零，說明[0, i]區間都不能作為起始位置，起始位置從i+1算起，再從0計算curSum（原理和2類似，如果從x到達不了y，那麼從中間任意一點都到不了y，是以可以從i+1算起）
- 從i+1出發，若直到n-1都滿足total>=0，則i+1是可行的出發點。（原理和2類似，x到終點的剩餘油量一定大于中間點z到終點的剩餘油量，由于有解且是唯一解，如果從x都無法跑完一圈，就不可能從其它點跑完一圈，是以x就是解）
4. 方法三（我的樸素解法）
- 首先，求出每個加油站的剩餘油量gas[i] - cost[i]和總剩餘油量
- 如果總剩餘油量小于0，那麼一定跑不完一圈。
- 當總剩餘油量大于0時，一定能跑完一圈。觀察每個加油站的剩餘油量可以發現，尋找一個起始位置，累計從這個起始位置跑一圈的過程中剩餘油量能否一直為正數，如果能，則說明從該位置出發能跑完一圈。代碼思路參考最大子序和，其實就是求定長連續數之和，sum記錄累計剩餘油量和，count記錄目前經過的站點數
- 周遊數組
- 如果sum<0，則sum和count清零重新累計，否則累計sum+=下一個站點油量和count++
- 當count==站點數時，說明成功跑完一圈，傳回起始位置
代碼
1. 暴力解
class Solution {
public:
//暴力法
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
for(int i=0;i<gas.size();i++){
int rest=gas[i]-cost[i]; //開到下一站的剩餘油量
int index=(i+1)%gas.size(); //下一站下标
while(rest>0&&index!=i){
rest+=gas[index]-cost[index];
index=(index+1)%gas.size();
}
//如果到達終點且油量>=0
if(rest>=0&&index==i) return i;
}
return -1;
}
};
- 時間複雜度
O(n^2)
- 空間複雜度
O(1)
2. 貪心1
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum=0; //總剩餘油量
int min=INT_MAX; //最小值
int index=0; //最小值下标
for(int i=0;i<gas.size();i++){
curSum+=gas[i]-cost[i];
if(min>curSum){
min=curSum;
index=i;
}
}
//如果總剩餘油量小于0，說明跑不完一圈
if(curSum<0) return -1;
//如果在到達終點的過程中沒有出現負數，說明從0站點可以到達終點
if(min>=0) return 0;
//傳回最小值的下一位
return index+1;
}
};
- 時間複雜度
O(n)
- 空間複雜度
O(1)
2. 貪心2
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum=0;
int total=0;
int start=0;
for(int i=0;i<gas.size();i++){
curSum+=gas[i]-cost[i];
total+=gas[i]-cost[i];
//如果目前累計剩餘油量小于0，到達不了終點，清零，從i+1重新計算
if(curSum<0){
curSum=0;
start=i+1;
}
}
if(total>=0) return start;
//總剩餘油量小于0
return -1;
}
};
- 時間複雜度
O(n)
- 空間複雜度
O(1)
方法三：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int ans=0;
//計算每個站點的剩餘油量
for(int i=0;i<gas.size();i++){
gas[i]-=cost[i];
ans+=gas[i]; //總油量
}
//如果總剩餘油量小于0，那麼一定跑不完一圈
if(ans<0) return -1;
int sum=0,count=0,res;
for(int i=0;;i=(i+1)%gas.size()){
sum+=gas[i];
count++;
if(sum<0){ //清零，重新計數
sum=0;
count=0;
}
//跑完一圈，傳回起始位置
if(count==gas.size()){
res=(i+1)%gas.size();
break;
}
}
return res;
}
};
- 時間複雜度
O(n)
- 空間複雜度
O(1)
135.分發糖果
力扣題目連結
思路
兩次周遊
- 一次是從左到右周遊，隻比較右邊孩子評分比左邊大的情況。
- 右比左大，右=左+1，否則為1
- 一次是從右到左周遊，隻比較左邊孩子評分比右邊大的情況
- 左比右大且左的糖果小于右，左=右+1
代碼
兩次周遊
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> res(ratings.size());
res[0]=1;
//向右周遊
for(int i=1;i<ratings.size();i++){
if(ratings[i]>ratings[i-1]) res[i]=res[i-1]+1;
else res[i]=1;
}
//向左周遊
for(int i=ratings.size()-1;i>0;i--){
if(ratings[i-1]>ratings[i]&&res[i-1]<=res[i]) res[i-1]=res[i]+1;
}
//求和
int sum=0;
for(int i=0;i<ratings.size();i++)
sum+=res[i];
return sum;
}
};
- 時間複雜度
O(n)
- 空間複雜度
O(n)
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)