LeetCode day30
害，昨天和今天在搞數據結構的報告，后面應該也會把哈夫曼的大作業寫上來。
今天認識認識貪心算法。(｡･?･)ﾉ
2697. 字典序最小回文串
給你一個由 小寫英文字母 組成的字符串 s ，你可以對其執行一些操作。在一步操作中，你可以用其他小寫英文字母 替換 s 中的一個字符。
請你執行 盡可能少的操作 ，使 s 變成一個 回文串 。如果執行 最少 操作次數的方案不止一種，則只需選取 字典序最小 的方案。
對于兩個長度相同的字符串 a 和 b ，在 a 和 b 出現不同的第一個位置，如果該位置上 a 中對應字母比 b 中對應字母在字母表中出現順序更早，則認為 a 的字典序比 b 的字典序要小。
返回最終的回文字符串。
示例 1：
輸入：s = "egcfe"
輸出："efcfe"
解釋：將 "egcfe" 變成回文字符串的最小操作次數為 1 ，修改 1 次得到的字典序最小回文字符串是 "efcfe"，只需將 'g' 改為 'f' 。
示例 2：
輸入：s = "abcd"
輸出："abba"
解釋：將 "abcd" 變成回文字符串的最小操作次數為 2 ，修改 2 次得到的字典序最小回文字符串是 "abba" 。
示例 3：
輸入：s = "seven"
輸出："neven"
解釋：將 "seven" 變成回文字符串的最小操作次數為 1 ，修改 1 次得到的字典序最小回文字符串是 "neven" 。
class Solution {public String makeSmallestPalindrome(String s) {int len=s.length();int ans=0;StringBuffer temp=new StringBuffer();String curr = new StringBuffer(s).reverse().toString();for(int i=0;i<len;i++){if(curr.charAt(i)!=s.charAt(i)){if(curr.charAt(i)>s.charAt(i)){temp.append(s.charAt(i));continue;}else{temp.append(curr.charAt(i));continue;}}temp.append(curr.charAt(i));}return String.valueOf(temp);}}
class Solution {
public:string makeSmallestPalindrome(string s) {string curr=s;reverse(s.begin(),s.end());for(int i=0;i<curr.length();i++){if(curr[i]>s[i]){curr[i]=s[i];}}return curr;}
};
先直接暴力做了？還有就是我以為c++會快，結果慢了一倍？？？？
class Solution {public String makeSmallestPalindrome(String s) {char[]temp=s.toCharArray();int len=temp.length;int l=0,r=len-1;while(l<r){char min=(char)Math.min(temp[l],temp[r]);temp[l++]=temp[r--]=min;}return String.valueOf(temp);}
}
額。我當時詬病Java應該比c++慢，就是因為String比較用charAt，但是做了還交換不了，就跑去cpp了，結果都忘了轉化數組了
455. 分發餅干
假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。
對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值。
示例 1:
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應該輸出1。
示例 2:
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數量和尺寸都足以讓所有孩子滿足。
所以你應該輸出2.
能喂飽一個是一個，吐舌~
class Solution {public int findContentChildren(int[] g, int[] s) {if(s.length==0){return 0;}Arrays.sort(g);Arrays.sort(s);int len1=g.length;int len2=s.length;int j=0;int ans=0;for(int i=0;i<len1;i++){if(j==len2){return ans;}while(j<len2){if(g[i]<=s[j++]){ans++;break;} }}return ans;}
}
561. 數組拆分
給定長度為 2n 的整數數組 nums ，你的任務是將這些數分成 n 對, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得從 1 到 n 的 min(ai, bi) 總和最大。
返回該 最大總和 。
示例 1：
輸入：nums = [1,4,3,2]
輸出：4
解釋：所有可能的分法（忽略元素順序）為：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大總和為 4
示例 2：
輸入：nums = [6,2,6,5,1,2]
輸出：9
解釋：最優的分法為 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9
那自然是貪心起來，大數只能跟大數匹配，不然浪費，可不能下等馬和上等馬pk
class Solution {public int arrayPairSum(int[] nums) {Arrays.sort(nums);int sum=0;for(int i=0;i<nums.length;i+=2){sum+=nums[i];}return sum;}
}
605. 種花問題
假設有一個很長的花壇，一部分地塊種植了花，另一部分卻沒有。可是，花不能種植在相鄰的地塊上，它們會爭奪水源，兩者都會死去。
給你一個整數數組 flowerbed 表示花壇，由若干 0 和 1 組成，其中 0 表示沒種植花，1 表示種植了花。另有一個數 n ，能否在不打破種植規則的情況下種入 n 朵花？能則返回 true ，不能則返回 false 。
示例 1：
輸入：flowerbed = [1,0,0,0,1], n = 1
輸出：true
示例 2：
輸入：flowerbed = [1,0,0,0,1], n = 2
輸出：false
解答錯誤
120 / 129 個通過的測試用例
官方題解
輸入
flowerbed =
[0,1,0]
n =
1添加到測試用例
輸出
true
預期結果
false
那有特么這樣的啊，我給你費力想怎么種更多，你倒好，直接搗亂
class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {if(n==0){return true;}if(flowerbed.length<3){int temp=0;for(int x:flowerbed){temp+=x;}if(temp==1){return false;}return n<=1;}int count=0;for(int i=1;i<flowerbed.length-1;i++){if(flowerbed[0]==0&&flowerbed[1]==0){flowerbed[0]=1;count++;}if(flowerbed[flowerbed.length-1]==0&&flowerbed[flowerbed.length-2]==0){flowerbed[flowerbed.length-1]=1;count++;}if(flowerbed[i-1]==0&&flowerbed[i+1]==0&&flowerbed[i]!=1){flowerbed[i]=1;count++;}}return n<=count;
}}
日內瓦，面向測試案例編程，我真的吐了啊這玩意.
class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int len=flowerbed.length;int[]curr=new int[len+2];curr[0]=0;curr[len+1]=0;System.arraycopy(flowerbed, 0, curr, 1, len);int ans=0;for(int i=1;i<curr.length-1;i++){if(curr[i]==0&&curr[i-1]==0&&curr[i+1]==0){i++;ans++;}}return n<=ans;}
}害，瞄了瞄評論區，看到一眼C++大佬的防御式編程，茅塞頓開，對啊，這不跟哨兵異曲同工之妙嘛。
