01.整數(shù)替換
題目鏈接：https://leetcode.cn/problems/integer-replacement/
給定一個正整數(shù) n ，你可以做如下操作：
- 如果
n是偶數(shù)，則用n / 2替換n。 - 如果
n是奇數(shù)，則可以用n + 1或n - 1替換n。
返回 n 變?yōu)?1 所需的 最小替換次數(shù) 。
示例 1：
輸入：n = 8
輸出：3
解釋：8 -> 4 -> 2 -> 1
示例 2：
輸入：n = 7
輸出：4
解釋：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1
示例 3：
輸入：n = 4
輸出：2
提示：
1 <= n <= 2^31 - 1
思路
這里我們要求得最小次數(shù)，要進(jìn)行具體的分析討論，首先偶數(shù)只有一種情況，所以不必討論，若是奇數(shù)則分為一下三種情況：
1、n>1且n%3==1的時候，二進(jìn)制位后是……01，最優(yōu)的方式應(yīng)該選擇-1，這樣就可以把末尾的1去掉
2、n>3且n%3==3的時候，二進(jìn)制位后是……11，最優(yōu)的方式應(yīng)是選擇+1，這樣后續(xù)均為連續(xù)0，能夠更快趨近1
3、n==3時，變成1最優(yōu)操作數(shù)為2
代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-842754.html
class Solution {
public:
int integerReplacement(int n) {
int ret=0;
while(n>1){
if(n%2==0){
ret++;
n/=2;
}
else
{
if(n==3){
ret+=2;
n=1;
}
else if(n%4==1){
ret+=2;
n/=2;
}else{
ret+=2;
n=n/2+1;
}
}
}
return ret;
}
};
02.俄羅斯套娃信封問題
題目鏈接：https://leetcode.cn/problems/russian-doll-envelopes/
給你一個二維整數(shù)數(shù)組 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 個信封的寬度和高度。
當(dāng)另一個信封的寬度和高度都比這個信封大的時候，這個信封就可以放進(jìn)另一個信封里，如同俄羅斯套娃一樣。
請計算 最多能有多少個 信封能組成一組“俄羅斯套娃”信封（即可以把一個信封放到另一個信封里面）。
注意：不允許旋轉(zhuǎn)信封。
示例 1：
輸入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
輸出：3
解釋：最多信封的個數(shù)為 3, 組合為: [2,3] => [5,4] => [6,7]。
示例 2：
輸入：envelopes = [[1,1],[1,1],[1,1]]
輸出：1
提示：
1 <= envelopes.length <= 105envelopes[i].length == 21 <= wi, hi <= 105
思路
重寫排序+貪心+二分的思想：
我們先按照左端點不同時升序排序，左端點相同時按右端點降序排序，這樣我們只需要考慮右端點，再使用貪心+二分就可以很好的解決這個問題
代碼
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(),envelopes.end(),[&](const vector<int>& v1,const vector<int>& v2){
return v1[0]!=v2[0]?v1[0]<v2[0]:v1[1]>v2[1];
});
vector<int> ret;
ret.push_back(envelopes[0][1]);
for(int i=1;i<envelopes.size();i++){
int b=envelopes[i][1];
if(b>ret.back()) ret.push_back(b);
else{
int left=0,right=ret.size()-1;
while(left<right){
int mid=(left+right)/2;
if(ret[mid]>=b) right=mid;
else left=mid+1;
}
ret[left]=b;
}
}
return ret.size();
}
};
03.可被三整除的最大和
題目鏈接：https://leetcode.cn/problems/greatest-sum-divisible-by-three/
給你一個整數(shù)數(shù)組 nums，請你找出并返回能被三整除的元素最大和。
示例 1：
輸入：nums = [3,6,5,1,8]
輸出：18
解釋：選出數(shù)字 3, 6, 1 和 8，它們的和是 18（可被 3 整除的最大和）。
示例 2：
輸入：nums = [4]
輸出：0
解釋：4 不能被 3 整除，所以無法選出數(shù)字，返回 0。
示例 3：
輸入：nums = [1,2,3,4,4]
輸出：12
解釋：選出數(shù)字 1, 3, 4 以及 4，它們的和是 12（可被 3 整除的最大和）。
提示：
1 <= nums.length <= 4 * 10^41 <= nums[i] <= 10^4
思路
首先我們先將所有的值累加起來，那么就會有下面三種情況
1、剛好是3的倍數(shù)，那么直接返回即可。
2、是3的倍數(shù)多1，那么我們找出除3的數(shù)中余1的最小的一個數(shù)，用總和減去與除3的數(shù)中余2的最小的兩個數(shù)，找出最大值即為所需
3、是3的倍數(shù)多2，那么我們找出除3的數(shù)中余2的最小的一個數(shù)，用總和減去與除3的數(shù)中余1的最小的兩個數(shù)，找出最大值即為所需
代碼
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
const int INF=0x3f3f3f3f;
int sum=0,x1=INF,x2=INF,y1=INF,y2=INF;
for(int& x:nums){
sum+=x;
if(x%3==1){
if(x<x1) x2=x1,x1=x;
else if(x<x2) x2=x;
}else if(x%3==2){
if(x<y1) y2=y1,y1=x;
else if(x<y2) y2=x;
}
}
if(sum%3==0) return sum;
else if(sum%3==1) return max(sum - x1,sum-y1-y2);
else return max(sum-y1,sum-x1-x2);
}
};
04.距離相等的條形碼
題目鏈接：https://leetcode.cn/problems/distant-barcodes/
在一個倉庫里，有一排條形碼，其中第 i 個條形碼為 barcodes[i]。
請你重新排列這些條形碼，使其中任意兩個相鄰的條形碼不能相等。 你可以返回任何滿足該要求的答案，此題保證存在答案。
示例 1：
輸入：barcodes = [1,1,1,2,2,2]
輸出：[2,1,2,1,2,1]
示例 2：
輸入：barcodes = [1,1,1,1,2,2,3,3]
輸出：[1,3,1,3,2,1,2,1]
提示：
1 <= barcodes.length <= 100001 <= barcodes[i] <= 10000
思路
首先題目要求保證存在答案，我們只需將出現(xiàn)次數(shù)最多的那個數(shù)兩兩相隔放置，剩下的數(shù)接著兩兩相隔放置即可，關(guān)于剩下的數(shù)為什么也可以直接兩兩放置，這是因為我們可以通過鴿巢定理推出只有出現(xiàn)最多的數(shù)才會影響到相隔，而我們解決了出現(xiàn)次數(shù)最大的數(shù)，所以剩下的數(shù)只要繼續(xù)按照兩兩相隔的順序繼續(xù)放置即可。
代碼
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
unordered_map<int,int> hash;
int maxval=0,maxCount=0;
for(int& x:barcodes){
if(maxCount<++hash[x]){
maxCount=hash[x];
maxval=x;
}
}
int n=barcodes.size(),index=0;
vector<int> ret(n);
for(int i=0;i<maxCount;i++){
ret[index]=maxval;
index+=2;
}
hash.erase(maxval);
for(auto& [x,y]:hash){
for(int i=0;i<y;i++){
if(index>=n) index=1;
ret[index]=x;
index+=2;
}
}
return ret;
}
};
05.重構(gòu)字符串
題目鏈接：https://leetcode.cn/problems/reorganize-string/
給定一個字符串 s ，檢查是否能重新排布其中的字母，使得兩相鄰的字符不同。
返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。
示例 1:
輸入: s = "aab"
輸出: "aba"
示例 2:
輸入: s = "aaab"
輸出: ""
提示:
1 <= s.length <= 500-
s只包含小寫字母
思路
這一題和上一題思路基本一致，但需要注意的是，這一題并沒有說一定有解，所以這里我們需要給出不符合的判斷，其余代碼類似上一題。文章來源：http://www.zghlxwxcb.cn/news/detail-842754.html
代碼
class Solution {
public:
string reorganizeString(string s) {
int hash[26]={0};
char maxChar=' ';
int maxCount=0;
for(char& ch:s){
if(maxCount<++hash[ch-'a']){
maxChar=ch;
maxCount=hash[ch-'a'];
}
}
int n=s.size();
if(maxCount>(n+1)/2) return "";
string ret(n,' ');
int index=0;
for(int i=0;i<maxCount;i++){
ret[index]=maxChar;
index+=2;
}
hash[maxChar-'a']=0;
for(int i=0;i<26;i++){
for(int j=0;j<hash[i];j++){
if(index>=n) index=1;
ret[index]='a'+i;
index+=2;
}
}
return ret;
}
};
到了這里，關(guān)于算法沉淀——貪心算法七（leetcode真題剖析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
