害，昨天和今天在搞数据结构的报告，后面应该也会把哈夫曼的大作业写上来。
今天认识认识贪心算法。(｡･?･)ﾉ
给你一个由 小写英文字母 组成的字符串 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了，结果都忘了转化数组了
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 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;
}
}
给定长度为 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;
}
}
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 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++大佬的防御式编程，茅塞顿开，对啊，这不跟哨兵异曲同工之妙嘛。