持续更新中（思路写在代码注释里）
1、最长回文串
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
class Solution { //出现次数为偶数的字符，可以全部用在回文数上； //出现次数为奇数的字符，其中最多的字符可以放在回文数中间，其它的字符可以减去一个（取偶数个），放在回文数里 public int longestPalindrome(String s) { int[] count = new int[128]; //记录下每个字符出现的次数 for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); count[c]++; } int ans = 0; for (int v: count) { //这个小技巧可以使 偶数不变，奇数-1 ans += v / 2 * 2; if (v % 2 == 1 && ans % 2 == 0) { ans++; } } return ans; } }
2、分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 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.
提示：
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
（1）解法一：穷举，找出每个饼干所能满足的最大的小孩
class Solution { public static int findContentChildren(int[] g, int[] s) { ArrayList<Integer> as = new ArrayList<>(); //用来存放挑选出来的胃口小于当前饼干尺寸的小孩胃口 ArrayList<Integer> gs = new ArrayList<>(); //用来储存饥饿的小孩 int count = 0; //用来统计喂饱的小孩数量 //遍历g，将数据存储到gs中 for(int g1 : g) { gs.add(g1); } for(int i=0; i<s.length; i++) { for(int g2 : gs) { //如果小孩胃口小于饼干尺寸，就放入as中 if(s[i] >= g2) { as.add(g2); } } //没有小孩满足，直接跳过后面的操作 if(as.isEmpty()) continue; int big = as.get(0); for(int g3 : as) { //贪心，找出能够满足的胃口最大的小孩 if(g3 > big) { big = g3; } } count++; //将满足的小孩从饥饿列表中删除 gs.remove(gs.indexOf(big)); as.clear(); } return count; } }
（2）解法二：先将两个数组排序，再对应分配，效率会变高
class Solution { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int numOfChildren = g.length, numOfCookies = s.length; int count = 0; //记录喂饱的孩子数量 //s和g任意一个遍历完成，即结束。代表着要么孩子都已喂饱，要么饼干已经用完 for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) { //跳过不能满足小孩的饼干 while (j < numOfCookies && g[i] > s[j]) { j++; } if (j < numOfCookies) { count++; } } return count; } }
3、种花问题
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 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
提示：
1 <= flowerbed.length <= 2 * 104
flowerbed[i] 为 0 或 1
flowerbed 中不存在相邻的两朵花
0 <= n <= flowerbed.length
class Solution { public static boolean canPlaceFlowers(int[] flowerbed, int n) { int count = 1; //用来记录连续出现的0的个数 int []sum = new int[20000]; //用来保存连续出现的0的个数 int index = 0; //sum数列的索引 int result = 0; //最终可以变为1的个数 //考虑只有一个0的情况 if(flowerbed.length == 1 && flowerbed[0] == 0 && n==1) { return true; } for(int i=1; i<flowerbed.length; i++) { //如果当前是0，前面也是0 if(flowerbed[i] == 0 && flowerbed[i-1] == 0) { count++; } else if(flowerbed[i] == 1 && flowerbed[i-1] == 0){ //如果当前是1，前面是0，记录下此时的count值，再把count重置 sum[index++] = count; count=1; } //考虑开头有两个以上的0 if(i==1 && flowerbed[0]==0 &&flowerbed[1]==0) { count++; } //考虑结尾有两个以上的0 if(i==flowerbed.length-2 && flowerbed[i]==0 && flowerbed[i+1]==0) { count++; } //结尾为0时，保存count值 if(i==flowerbed.length-1 && flowerbed[i]==0) { sum[index++] = count; } } //可以变为1的个数 for(int i=0; i<index; i++) { sum[i] = (sum[i]-1)/2; } for(int i=0; i<index; i++) { result = result+sum[i]; } return (result>=n) ? true:false; } }
4、验证回文字符串I
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: s = "aba"
输出: true
示例 2:
输入: s = "abca"
输出: true
解释: 你可以删除c字符。
示例 3:
输入: s = "abc"
输出: false
提示:
1 <= s.length <= 105
s 由小写英文字母组成
不能用二重循环暴力枚举，超时。
class Solution { public static void main(String[] args) { String s = "abacca"; System.out.println(validPalindrome(s)); } public static boolean validPalindrome(String s) { int i = 0; int j = s.length() - 1; //如果s本身是回文串，直接返回true if (isHuiwen(s, i, j)) { return true; } while(i < j) { if(s.charAt(i) == s.charAt(j)) { i++; j--; } else { //如果i和j对应的字符不一致，则i向右跳过该字符（或j向左跳过该字符），继续判断，若仍有字符不一样，则不满足题目要求 return isHuiwen(s, i+1, j) || isHuiwen(s, i, j-1); } } return true; } //判断字符串s在索引i到j之间的子串是否为回文串 public static boolean isHuiwen(String s, int i, int j) { while(i < j) { if(s.charAt(i) == s.charAt(j)) { i++; j--; } else { return false; } } return true; } }
5、柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
示例 3：
输入：bills = [5,5,10]
输出：true
示例 4：
输入：bills = [10,10]
输出：false
提示：
1 <= bills.length <= 105
bills[i] 不是 5 就是 10 或是 20
class Solution { public static boolean lemonadeChange(int[] bills) { int count5 = 0; //记录手中5元的数量 int count10 = 0; //记录手中10元的数量 for(int i=0; i<bills.length; i++) { //如果给的是5元，直接收下 if(bills[i] == 5) { count5++; } else if(bills[i] == 10) { //如果给的是10元 //如果有5元，找零 if(count5 > 0) { count5--; count10++; } else { //如果没5元，则不能满足 return false; } } else { //如果顾客给的是20元 //贪心，优先考虑给出一张10元和一张5元 if(count5>0 && count10>0) { count5--; count10--; } else if(count5 >= 3) { //有三张5元也行 count5 = count5-3; } else { return false; } } } return true; } }
