LeetCode day30

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++大佬的防御式编程，茅塞顿开，对啊，这不跟哨兵异曲同工之妙嘛。