leetCode进阶算法题+解析（五十一）
根据字符出现频率排序
题目：给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
"tree"
输出:
"eert"
解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:
输入:
"cccaaa"
输出:
"cccaaa"
解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:
输入:
"Aabb"
输出:
"bbAa"
解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。
思路：这个题，简直就是送分。我现在的想法就是把字符串转化成数组，下标代表字符，数值代表出现的次数。因为没有任何时间空间要求，我不知道这个字符串是不是只有大小写字母，先暂定52位数组。去 实现下试试。
我踏马果然太天真，看题目中没说只包含大小写字母就不应该试这个运气，不过问题不大，仍然很简单，简单的改造一下就行。附上我第一版本的代码截图，毕竟辛苦写的：
只包含字母大小写答案
好了，正确答案出来了：
class Solution {
public String frequencySort(String s) {
StringBuffer[] d = new StringBuffer[134];
for (int i = 0;i<d.length;i++) {
d[i] = new StringBuffer();
}
for(char c : s.toCharArray()) {
d[c].append(c);
}
Arrays.sort(d, new Comparator<StringBuffer>() {
@Override
public int compare(StringBuffer o1, StringBuffer o2) {
if(o1.length()<o2.length()) return 1;
if(o1.length()>o2.length()) return -1;
return 0;
}
});
StringBuffer sb = new StringBuffer();
for(StringBuffer ss:d){
sb.append(ss);
}
return sb.toString();
}
}
其实就是把字典下标改成了134，因为char最大133.别的没啥改动。我个人感觉优化的空间就是如果是空StringBuffer就不要参与排序浪费性能了，这里加一个集合，所有非空的才放进去会好一点吧，不过因为比较麻烦，所以我就不写了，直接去看性能排行第一的代码了。
class Solution {
public String frequencySort(String s) {
int[] letters = new int[128];
char[] a = s.toCharArray();
for (char c : a) {
letters[c]++;
}
int curr = 0;
int len = s.length();
while(curr < len){
int max = 0;
char c = 0;
// 遍历找出最大的次数
for(int i = 0 ; i < 128 ; ++i) {
if(letters[i] > max) {
max = letters[i];
c = (char) i;
}
}
while(letters[c] > 0){
a[curr] = c;
letters[c]--;
curr++;
}
}
return new String(a);
}
}
处于能看懂，灵机一动也可能想到的范围，因为这个题比较简单所以就不多说了，下一题。
用最少数量的箭引爆气球
题目：在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。
一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
Example:
输入:
[[10,16], [2,8], [1,6], [7,12]]
输出:
2
解释:
对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。
思路：这个题真的看了n遍才看懂，然後觉得题意还算是好理解，但是这个叙述真的一眼难尽。读懂题目后有隐隐约约的思路。首先第一步就是排序，从开始最小排序，然後再取最小值范围内end最小的，当下一个开始值大于这个end说明到这里要重新 定点了，暂时这个是很模糊的想法，我去代码试试。
只能说这个题比我想得要简单的多，说真的我觉得题目描述吓到我了，直接贴代码，一次通过的：
class Solution {
public int findMinArrowShots(int[][] points) {
if(points == null || points.length == 0) return 0;
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0]>o2[0]) return 1;
if(o1[0]<o2[0]) return -1;
return 0;
}
});
int res = 1;
int start = points[0][0];
int end = points[0][1];
for(int[] i:points){
if(i[0]<=end){//开始不大于最小的结束，有共同区间，不用单独写
end = Math.min(end,i[1]);
}else{//开始大于最小的结束，要从新开始定点
start = i[0];
end = i[1];
res++;
}
}
return res;
}
}
其实我之前的思路是对的，就是判断有没有共同区间，然後判断要不要重新定点。这个性能超过百分之八十多，我去看看性能排行第一的代码:
class Solution {
public int findMinArrowShots(int[][] points) {
if (points == null || points.length == 0) return 0;
//这种写法排序比用lambda快
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
int count = 1, end = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] <= end) {
continue;
}
count++;
end = points[i][1];
}
return count;
}
}
思路差不多，只不过处理的更加优雅，而且看了人家的代码才发现我这个start确实是没用到。不过我改了下比较大小的步骤提交性能立刻就上来了，附个图下一题。
性能超过百分之九十七
四数相加2
题目：给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
例如:
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
思路:题目居然还说为了使问题简单化？我忍不住笑出了声。反正继续说这道题吧。我个人的感觉就是笛卡尔积。其实就是a中和b中的每个计算，再和c中的每个计算，再和d中的每个计算。如果结果是0则答案+1.这个题目中说整数是有范围的，所以还可以剪个枝。我不知道会不会超时，但是我觉得单纯的实现绝对是可以的。我直接去写代码了。
我这个嘴简直是开光了，没啥说的，反正就是超时，附个截图：
超时截图
好吧，我看的答案，四层循环拆开两个，然後直接贴代码（我没想到能有重复的数字）：
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer, Integer> map = new HashMap<>();
for(int a : A){
for(int b : B){
map.put(a + b , map.getOrDefault(a + b, 0) + 1);
}
}
int sum = 0;
for(int a : C){
for(int b : D){
if(map.containsKey(0 - a - b)){
sum += map.get(0 -a - b);
}
}
}
return sum;
}
}
怎么说呢，我觉得这个题的考点，就是性能优化?不多解释了，没啥好说的，下一题了。
132模式
题目：给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
注意：n 的值小于15000。
示例1:
输入: [1, 2, 3, 4]
输出: False
解释: 序列中不存在132模式的子序列。
示例 2:
输入: [3, 1, 4, 2]
输出: True
解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
示例 3:
输入: [-1, 3, 2, 0]
输出: True
解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].
思路：这个题我不知道是不是我想的太简单了，两次遍历，从前往后最小值，从后往前最小值。然後遍历每一个元素，判断前后小于当前值则true，不然继续往下遍历。我去实现了。
额，实现了是实现了，但是性能一言难尽，没超时我就觉得挺神奇了，先贴代码：
class Solution {
public boolean find132pattern(int[] nums) {
int len = nums.length;
int[] front = new int[len];
front[0] = nums[0];
for(int i = 1;i<len;i++){
front[i] = Math.min(front[i-1],nums[i]);
}
for(int i = 1;i<len-1;i++){
//接下来判断是不是1.2模式
if(nums[i]>front[i-1] && nums[i]>nums[i+1]) {
for(int j = i+1;j<len;j++) {
if(nums[j]<nums[i] && nums[j]>front[i-1]) return true;
}
}
}
return false;
}
}
在做的时候其实我大大小小调了很多次，才有现在的代码。之前想的是前后做两个数组都存最小值，但是后来才明白这个132的意思是1要小于2，反正现在是对付实现了虽然性能不行。我 甚至觉得好像不用front这个数组也可以实现了。我再去试试。
class Solution {
public boolean find132pattern(int[] nums) {
int len = nums.length;
if(len<3) return false;
int min = nums[0];
for(int i = 1;i<len-1;i++){
min = Math.min(min,nums[i-1]);
//接下来判断是不是1.2模式
if(nums[i]>min && nums[i]>nums[i+1]) {
for(int j = i+1;j<len;j++) {
if(nums[j]<nums[i] && nums[j]>min) return true;
}
}
}
return false;
}
}
又优化了一次，还是不行，我还是直接看性能排行第一的代码吧。
我直接贴代码：
public class Solution {
public boolean find132pattern(int[] nums) {
if (nums.length < 3)
return false;
int[] min = new int[nums.length];
min[0] = nums[0];
for (int i = 1; i < nums.length; i++)
min[i] = Math.min(min[i - 1], nums[i]);
for (int j = nums.length - 1, k = nums.length; j >= 0; j--) {
if (nums[j] > min[j]) {
while (k < nums.length && nums[k] <= min[j])
k++;
if (k < nums.length && nums[k] < nums[j])
return true;
nums[--k] = nums[j];
}
}
return false;
}
}
我总觉得和我最开始的思路差不多，但是性能差的就有点多了，反正不多说了，下一题。
环形数组循环
题目：给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数，则向前移动 k 个索引。相反，如果是负数 (-k)，则向后移动 k 个索引。因为数组是环形的，所以可以假设最后一个元素的下一个元素是第一个元素，而第一个元素的前一个元素是最后一个元素。
确定 nums 中是否存在循环（或周期）。循环必须在相同的索引处开始和结束并且循环长度 > 1。此外，一个循环中的所有运动都必须沿着同一方向进行。换句话说，一个循环中不能同时包括向前的运动和向后的运动。
示例 1：
输入：[2,-1,1,2,2]
输出：true
解释：存在循环，按索引 0 -> 2 -> 3 -> 0 。循环长度为 3 。
示例 2：
输入：[-1,2]
输出：false
解释：按索引 1 -> 1 -> 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。
示例 3:
输入：[-2,1,-1,-2,-2]
输出：false
解释：按索引 1 -> 2 -> 1 -> ... 的运动无法构成循环，因为按索引 1 -> 2 的运动是向前的运动，而按索引 2 -> 1 的运动是向后的运动。一个循环中的所有运动都必须沿着同一方向进行。
思路:这个题怎么说呢，首先读了好几遍题目，然後第一反应就是从第一个元素开始往下顺着走，至于判断是不是环是要用标记的办法。如果走到重复的点说明到了循环，不过题目说一个不是环，还有环中方向要相同。所以还是要标记一下每个元素的正负。反正是有思路，我去代码实现下试试。
本来以为挺简单的，屁颠屁颠写完了才发现题意都没理解。我本来以为一定是从第0个元素开始，然后测试案例给我一个重击：3,1,2成立，就说明是可以从任何元素开始的。因为理解错误所以最开始的思路要从头开始写了，我再理理思路。
死乞白赖把答案写出来了，性能一言难尽、但是起码ac了：
class Solution {
public boolean circularArrayLoop(int[] nums) {
if(nums==null || nums.length<2) return false;
for(int i = 0;i<nums.length;i++) {
Set<Integer> set = new HashSet<Integer>();
int v = nums[i]>0?1:-1;//1是往前， -1 是往后
int idx = i;
while(!set.contains(idx)) {
set.add(idx);
int n = nums[idx];
//nums中只包含正整数和负整数，不存在0
if(n>0) {
//当前元素是正数，上一个是负数，所以此路不通
if(v == -1) break;
idx = (idx+n)%nums.length;
}else {
//当前元素是负数，上一个是整数，所以此路不通
if(v == 1) break;
idx = idx+n>=0?idx+n:(idx+n)%nums.length+nums.length;
}
if(set.size()>1 && idx == i) return true;
}
}
return false;
}
}
然后性能不好我也能理解，毕竟我一开始的思路只是从头开始，这个题其实我觉得我的代码中还有可进步的，但是我有点懒得想了，直接看性能排行第一的代码吧：
class Solution {
int max, len;
public boolean circularArrayLoop(int[] nums) {
this.len = nums.length;
this.max = 1000 * len;
for (int i = 0; i < len; i++) {
int slow = i, fast = i;
int slowLast, fastLast;
while (true) {
slowLast = slow;
slow = getNextIndex(nums, slow);
if (nums[slow] == 0 || nums[slow] * nums[slowLast] < 0 || slow == slowLast) {
setZero(nums, i);
break;
}
fastLast = fast;
fast = getNextIndex(nums, fast);
if (nums[fast] == 0 || nums[fast] * nums[fastLast] < 0 || fast == fastLast) {
setZero(nums, i);
break;
}
fastLast = fast;
fast = getNextIndex(nums, fast);
if (nums[fast] == 0 || nums[fast] * nums[fastLast] < 0 || fast == fastLast) {
setZero(nums, i);
break;
}
if (slow == fast) {
return true;
}
}
}
return false;
}
public void setZero(int[] nums, int i) {
int j;
while (true) {
j = getNextIndex(nums, i);
if (nums[j] == 0 || nums[i] * nums[j] < 0) {
nums[i] = 0;
break;
}
nums[i] = 0;
i = j;
}
}
public int getNextIndex(int[] nums, int fast) {
return (nums[fast] + fast + max) % len;
}
}
啧啧，人家这个代码量，我简单看了下，用的快慢指针，之前做链表的时候经常用，能理解，但是我自己反正是没想到。而且这个还涉及到了正负数不能一起算，反正是挺复杂的，有兴趣的自己仔细看看吧。
这篇笔记就到这里了，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！说个题外话，一直以来一起刷题的微信群里，一个小姐姐今天收到了微软的offer，她在群里说了一句，付出总会有回报的，我觉得挺好的。也希望大家都能这样！java技术交流群130031711，欢迎各位踊跃加入！
