总结

1：用s.charAt()比较字符是否等于或者不等于某个字符的时候，要用单引号，双引号这个错误就太low了

s.charAt(i) != ' '

二维数组排序

Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});

list转数组

return merged.toArray(new int[merged.size()][]);

Arrays.sort实现降序排序

注意：如果需要改变默认的排列方式，不能使用基本类型（int，char等）定义变量，而应该用对应的类

优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。对垒中的元素达到默认的大小之后，再压入元素就会进行判断，如果满足压入条件，就会弹出队首元素

实际上是一个堆（不指定Comparator时默认为最小堆），通过传入自定义的Comparator函数可以实现大顶堆。

如果使用默认的小根堆，那么队列中维护的就是比堆顶更大的元素，如果要插入的数比堆顶大，那么用这个数替换堆顶，同时把堆顶弹出，然后优先队列会重新调整这个小根堆，如果要插入的数比堆顶小，那么这个数不能插入队列中

下面这样定义的时候传入比较器，那么我们的优先对垒就是一个大顶堆

PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) ->b - a);

如果使用大根堆，那么队列中维护的就是比堆顶更小的元素，如果要插入的数比堆顶小，那么用这个数替换堆顶，同时把堆顶弹出，然后优先队列会重新调整这个大根堆，如果要插入的数比堆顶大小，那么这个数不能插入队列中

1 9. 回文数

就是这个数把最高位当做个位，第二高位当做百位，酱紫，求出来的数应该等于原来的数

class Solution {public boolean isPalindrome(int x) {int sum=0; int k=1;int temp=x;int count=0;Stack<Integer>stack=new Stack();while(x!=0){int a=x%10;x=x/10;stack.push(a); }while(!stack.empty()){int p=stack.pop();sum=p*k+sum;k=k*10;}System.out.println(sum);if(temp<0) sum=-sum;return sum==temp;} } class Solution {public boolean isPalindrome(int x) {// 特殊情况：// 如上所述，当 x < 0 时，x 不是回文数。// 同样地，如果数字的最后一位是 0，为了使该数字为回文，// 则其第一位数字也应该是 0// 只有 0 满足这一属性if (x < 0 || (x % 10 == 0 && x != 0)) {return false;}int revertedNumber = 0;while (x > revertedNumber) {revertedNumber = revertedNumber * 10 + x % 10;x /= 10;}// 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。// 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，// 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。return x == revertedNumber || x == revertedNumber / 10;} }作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/palindrome-number/solution/hui-wen-shu-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2 11. 盛最多水的容器

暴力超时

class Solution {public int maxArea(int[] height) {int max=0;for(int i=0;i<height.length;i++){for(int j=0;j<height.length;j++){max=Math.max(max,Math.min(height[i],height[j])*Math.abs(i-j));}}return max;} }

4 165. 比较版本号

7 453. 最小操作次数使数组元素相等

给定一个长度为 n 的 非空 整数数组，每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。

解题：对原数组进行排序，每次将最小的元素加到和最大的元素相等，那么每一次加完之后，最小的元素都是nums[0],而最大的元素从最后一个元素依次往前移(因为倒数第二个元素加完之后肯定是大于大数第一个元素的)，直到nums[1]

class Solution {public int minMoves(int[] nums) {int move=0;Arrays.sort(nums);int min=nums[0];for(int i=nums.length-1;i>=1;i--){move+=nums[i]-nums[0]; } return move; } }

思路2 ：动态规划
把大问题拆分成小问题，每次把2个数移动成相同的

C++ 动态规化

数组

1 27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解题思路，前后双指针，左指针指向等于val的数，右指针指向不等于val的数，两者交换，然后后移左指针，前移右指针，直到右指针小于左指针

class Solution {public int removeElement(int[] nums, int val) {int i=0;int j=nums.length-1;while(i<=j){while(i<=j&&nums[j]==val){j--;}while(i<=j&&nums[i]!=val){i++;}if(i<=j){ nums[i]=nums[j];i++;j--;} }return j+1;} }

从后往前覆盖

class Solution {public int removeElement(int[] nums, int val) {int left=0;for(int right=0;right<nums.length;right++){if(nums[right]!=val)nums[left++]=nums[right];}return left;} } class Solution {public int removeElement(int[] nums, int val) {int left = 0;int right = nums.length;while (left < right) {if (nums[left] == val) {nums[left] = nums[right - 1];right--;} else {left++;}}return left;} }

2 66. 加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

我的解题思路

class Solution {public int[] plusOne(int[] digits) {int carry=0;int n=digits.length;int num[]=new int[n+1];for(int i=n-1;i>=0;i--){int temp=digits[i]+carry;if(i==n-1)temp=temp+1;carry=temp/10;digits[i]=temp%10;num[i+1]=temp%10;}if(carry==1){num[0]=1;}return carry==1?num:digits;} }

只要+1求余数，余数不等于0，说明没有进位，直接返回。如果余数等于0，说明有进位，遍历前一个数字，加1再求余数，以此循环。如果for循环都遍历完了，说明最高位也有进位，则重新建立一个数组，初始化为0，将第一位设置为1就可以了，因为，99、999之类的数字加一为100、1000

class Solution {public int[] plusOne(int[] digits) {for (int i = digits.length - 1; i >= 0; i--) {digits[i]++;digits[i] = digits[i] % 10;if (digits[i] != 0) return digits;}digits = new int[digits.length + 1];digits[0] = 1;return digits;} }作者：yhhzw 链接：https://leetcode-cn.com/problems/plus-one/solution/java-shu-xue-jie-ti-by-yhhzw/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3 26. 删除有序数组中的重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成

输入：nums = [1,1,2]
输出：2, nums = [1,2]

双指针，i指向前面没有重复元素的位置，j向后遍历，把非重复元素前移

class Solution {public int removeDuplicates(int[] nums) {int i=0;int j=1;while(j<nums.length){while(j<nums.length&&nums[j]==nums[i]){j++;}if(j<nums.length){nums[i+1]=nums[j];i++;} }return i+1;} }

真的是优雅啊啊啊

class Solution {public int removeDuplicates(int[] nums) {int i = 0;for(int j=1;j<nums.length;j++){if(nums[i] != nums[j]){nums[++i] = nums[j];}}return ++i;} }

4 56. 合并区间

解题思路：先排序，然后遍历比较当前区间的左右的值和已经放入list中的左右的值的大小的关系，先比较左区间，再比较右区间

class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0) {return new int[0][2];}Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});List<int[]> merged = new ArrayList<int[]>();for (int i = 0; i < intervals.length; ++i) {int L = intervals[i][0], R = intervals[i][1];if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {merged.add(new int[]{L, R});} else {merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);}}return merged.toArray(new int[merged.size()][]);} }

5 870. 优势洗牌 (田忌赛马问题)

给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列，使其相对于 B 的优势最大化。

示例 1：

输入：A = [2,7,11,15], B = [1,10,4,11]
输出：[2,11,7,15]

示例 2：

输入：A = [12,24,8,32], B = [13,25,32,11]
输出：[24,32,8,12]

解题思路，类似田忌赛马，如果田忌的最快的马比齐威王最快的马快，就直接干掉齐威王的马
如果田忌的最快的马没有齐威王的最快的马快，就用田忌最弱的马消耗掉齐威王的最快的马。

参考：604，贪心算法解优势洗牌-田忌赛马问题

class Solution {public int[] advantageCount(int[] nums1, int[] nums2) {Arrays.sort(nums1); int len=nums2.length;PriorityQueue<int[]>queue=new PriorityQueue<>((a,b)->b[0]-a[0]);for(int i=0;i<len;i++){queue.add(new int[]{nums2[i],i});//建立大根堆}int res[]=new int[len];int left=0;int right=len-1;while(!queue.isEmpty()){int arr[]=queue.poll();int val=arr[0];int index=arr[1]; res[index]=nums1[right]>val?nums1[right--]:nums1[left++];}return res; } }

用最大堆是为了让最大的数在堆最上面。然后需要记录每一个数的原来的索引
PriorityQueue默认是最小堆，所以需要重写比较器

6 414. 第三大的数

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

参考：Java：三变量表示第一二三大数，一次遍历，更新三变量

class Solution {public int thirdMax(int[] nums) {int n=nums.length;if(n==1) return nums[0];if(n==2) return Math.max(nums[0],nums[1]);long max1= Long .MIN_VALUE;long max2=Long.MIN_VALUE;long max3=Long.MIN_VALUE;for(int i=0;i<n;i++){if(nums[i]==max1||nums[i]==max2) continue;if(nums[i]>max1) {max3=max2;max2=max1;max1=nums[i];}else if(nums[i]>max2){max3=max2;max2=nums[i];}else if(nums[i]>max3){max3=nums[i];}}return max3==Long.MIN_VALUE?(int)max1:(int)max3;//但是如果恰好第3大的就是Integer.MIN_VALUE，就不好处理了，所以，我们取float} }

7 581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]
输出：0

示例 3：

输入：nums = [1]
输出：0

思路1：排序找相同的左右边界

class Solution {public int findUnsortedSubarray(int[] nums) {int temp[]=nums.clone();Arrays.sort(temp);int left=0;int right=nums.length-1;while(left<=right&&nums[left]==temp[left])left++;//注意有序的时候left会超边界while(right>left&&nums[right]==temp[right]) right--;return right-left+1;//注意有序的时候left会超边界，right-left=-1,+1=0没毛病} }

注意数组复制的方法，还号可以是 System.arraycopy，Arrays.copyOf

class Solution {public int findUnsortedSubarray(int[] nums) {//int temp[]=nums.clone();// int temp[]=Arrays.copyOf(nums,nums.length);int temp[]=new int[nums.length];System.arraycopy(nums, 0, temp, 0, nums.length);Arrays.sort(temp);int left=0;int right=nums.length-1;while(left<=right&&nums[left]==temp[left])left++;//注意有序的时候left会超边界while(right>left&&nums[right]==temp[right]) right--;return right-left+1;//注意有序的时候left会超边界，right-left=-1,+1=0没毛病} }

思路2 单调栈找左右边界
解法思路：利用单调栈，从左往右扫一遍找到左边界，再从右往左扫一遍找到右边界，两者相减即可。

class Solution {public int findUnsortedSubarray(int[] nums) {// 单调栈从前往后遍历一遍可得到左边界// 单调栈从后往前遍历一遍可得到右边界Deque<Integer> stack = new ArrayDeque<>();int left = nums.length;for (int i = 0; i < nums.length; i++) {while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {left = Math.min(left, stack.pop());}stack.push(i);}stack.clear();int right = -1;for (int i = nums.length - 1; i >= 0; i--) {while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {right = Math.max(right, stack.pop());}stack.push(i);}return right - left > 0 ? right - left + 1 : 0;} }作者：tong-zhu 链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/kan-tong-ge-shua-ti-jian-dan-yi-li-jie-d-2ci3/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 int findUnsortedSubarray(vector<int>& nums) {int n = nums.size();int small = nums[n - 1], big = nums[0];int l = -1, r = -2;for (int i = n - 1; i >= 0; -- i) {small = min(small, nums[i]);if (nums[i] > small) l = i;}for (int i = 0; i < n; ++ i) {big = max(big, nums[i]);if (nums[i] < big) r = i;}return r - l + 1;}

class Solution {public int findUnsortedSubarray(int[] nums) {int n = nums.length;int maxn = Integer.MIN_VALUE, right = -1;int minn = Integer.MAX_VALUE, left = -1;for (int i = 0; i < n; i++) {if (maxn > nums[i]) {right = i;} else {maxn = nums[i];}if (minn < nums[n - i - 1]) {left = n - i - 1;} else {minn = nums[n - i - 1];}}return right == -1 ? 0 : right - left + 1;} }

8 628. 三个数的最大乘积

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

输入：nums = [1,2,3]
输出：6

示例 2：

输入：nums = [1,2,3,4]
输出：24

示例 3：

输入：nums = [-1,-2,-3]
输出：-6

解题思路1 排序，最开始还在想着三数之和那种解法，帧数傻

class Solution {public int maximumProduct(int[] nums) {Arrays.sort(nums);int max=Integer.MIN_VALUE;int n=nums.length;//取两负一正，或者3正if(n==3) return nums[0]*nums[1]*nums[2];return Math.max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]);// for(int i=0;i<n;i++){// if(i>0&&nums[i]==nums[i-1]) continue;// int L=i+1;int R=n-1;// while(L<R){// int temp1=nums[L];// int temp2=nums[R];// if(nums[i]*temp1*temp2>max){// max=nums[i]*temp1*temp2;// }// max=Math.max(max,nums[i]*temp1*temp2);// while(L<R&&nums[++L]==temp1);// L++;// while(L<R&&nums[--R]==temp2); //R--;// }// }// return max;} }

方法二：线性扫描
找到最大的三个数和最小的两个数

class Solution {public int maximumProduct(int[] nums) {// 最小的和第二小的int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;// 最大的、第二大的和第三大的int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;for (int x : nums) {if (x < min1) {min2 = min1;min1 = x;} else if (x < min2) {min2 = x;}if (x > max1) {max3 = max2;max2 = max1;max1 = x;} else if (x > max2) {max3 = max2;max2 = x;} else if (x > max3) {max3 = x;}}return Math.max(min1 * min2 * max1, max1 * max2 * max3);} }作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/maximum-product-of-three-numbers/solution/san-ge-shu-de-zui-da-cheng-ji-by-leetcod-t9sb/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

9 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

10 643. 子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1
输出：5.00000

解题思路1：暴力枚举，超时

class Solution {public double findMaxAverage(int[] nums, int k) {int n=nums.length;double max=Integer.MIN_VALUE;for(int i=0;i<=n-k;i++){max=Math.max(max,calAv(nums,i, k));}return max;}public double calAv(int arr[],int start,int k){double sum=0;for(int i=start;i<start+k;i++){sum+=arr[i];}return sum/k;} }

相当于利用队列，每次弹出一个元素，然后压入一个元素，改变sum的大小

class Solution {public double findMaxAverage(int[] nums, int k) {int n=nums.length;double sum=0.0;double avg=0.0;for(int i=0;i<k;i++){sum+=nums[i];}avg=sum/k;for(int i=1;i<=n-k;i++){sum=sum-nums[i-1]+nums[i+k-1];avg=Math.max(avg,sum/k);}return avg;} }

记录最大的sum就好啊，为什么每次要计算呢，浪费时间

class Solution {public double findMaxAverage(int[] nums, int k) {int n=nums.length;double sum=0.0;double avg=0.0;double max=0.0;for(int i=0;i<k;i++){sum+=nums[i];}max=sum;for(int i=1;i<=n-k;i++){ sum=sum-nums[i-1]+nums[i+k-1];max=Math.max(max,sum);}return max/k;} }

这个更快，我们以每一个窗口的最后一个元素为标杆啊。。。。。我前面的写法是以每一个窗口的第一个元素为标杆

class Solution {public double findMaxAverage(int[] nums, int k) {int len = nums.length;int count = 0;for(int i = 0;i < k;i++){count += nums[i];}int sumMax = count;for(int j = k;j < len;j++){count = count - nums[j-k] + nums[j];sumMax = (sumMax > count) ? sumMax : count;}return 1.0 * sumMax / k;} }

11 665. 非递减数列

给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

12 674. 最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

class Solution {public int findLengthOfLCIS(int[] nums) {int n=nums.length;int dp[]=new int[n];dp[0]=1;int max=1;for(int i=1;i<n;i++){dp[i]=nums[i]>nums[i-1]?dp[i-1]+1:1;max=Math.max(max,dp[i]);}return max;} }

双指针

1 58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

解题思路，双指针，右指针从尾遍历，指向单数第一个不为空格的字符，左指针从右指针的前一个开始遍历，指向右指针前面第一个空格，然后right-left就是所求

class Solution {public int lengthOfLastWord(String s) {int right=s.length()-1;int left=0;while(right>=0&&s.charAt(right)==' '){right--;}left=right-1;while(left>=0&&s.charAt(left)!=' '){left--;}return right-left;} }

思路2，直接计数字符个数

class Solution {public int lengthOfLastWord(String s) { int count = 0;for (int i = s.length() - 1; i >= 0; i--){if (s.charAt(i) != ' ') count++; //检测到字母if (s.charAt(i) == ' ' && count != 0) break; //记完末单词碰到空格就退出，同时解决末单词后面还有空格的情况（"a "）}return count;} }

2 69. x 的平方根

class Solution {public int mySqrt(int x) {if(x<=1) return x;int left=0;int right=x;while(left<=right){int mid=left+((right-left)>>1);if((long)mid*mid>x){//如果x过大，会造成mid*mid溢出right=mid-1;}else if(mid*mid<x){left=mid+1;}else return mid;}return right;} }

链表

1 24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路：从前往后，两两翻转，头指针每次跳两步，当头指针指向的节点为空或者指向的节点的下一个节点为空，则不用翻转

class Solution {public ListNode swapPairs(ListNode head) {if(head==null||head.next==null)return head; ListNode node=head.next.next; ListNode temp= head.next;temp.next=head;head.next=swapPairs(node);return temp; } }

迭代

class Solution {public ListNode swapPairs(ListNode head) {if(head==null||head.next==null)return head; ListNode newHead=head.next;//暂存新的头结点,新的头结点肯定是第二个节点 while(head!=null&&head.next!=null){ListNode node=head.next.next;ListNode node2=head.next;ListNode temp= head.next; temp.next=head; if(node==null||node.next==null)head.next=node;else head.next=node.next; head=node; } return newHead; } }

2 143. 重排链表

3 23. 合并K个升序链表

class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists.length==0) return null;ListNode p=null;for(int i=0;i<lists.length;i++){p=mergeTwo(p,lists[i]);}return p;}public ListNode mergeTwo(ListNode temp1,ListNode temp2){if(temp1==null) return temp2;if(temp2==null) return temp1;ListNode head=temp1.val<=temp2.val?temp1:temp2;ListNode temp=head;while(temp1!=null&&temp2!=null){if(temp1.val<=temp2.val){temp.next=temp1;temp1=temp1.next;}else{temp.next=temp2;temp2=temp2.next;}temp=temp.next;}temp.next=(temp1==null)?temp2:temp1;return head;} } class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists.length==0) return null;return merge(lists, 0, lists.length - 1);}public ListNode merge(ListNode[] lists, int l, int r) {if (l == r) {return lists[l];}int mid = (l + r) >> 1;return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));}public ListNode mergeTwoLists(ListNode a, ListNode b) {if (a == null || b == null) {return a != null ? a : b}ListNode head = new ListNode(0);ListNode tail = head, aPtr = a, bPtr = b;while (aPtr != null && bPtr != null) {if (aPtr.val < bPtr.val) {tail.next = aPtr;aPtr = aPtr.next;} else {tail.next = bPtr;bPtr = bPtr.next;}tail = tail.next;}tail.next = (aPtr != null ? aPtr : bPtr);return head.next;} }

4 92. 反转链表 II

class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {int cur=1;if(left==1) return subReverse(head,left-1,right);ListNode temp=head;while(temp!=null){if(cur==left-1) {temp.next=subReverse(temp.next,cur,right);break;}else{cur++; temp=temp.next;} }return head;}public ListNode subReverse(ListNode node,int start,int end){if(start==end) return node; ListNode pre=null;ListNode temp=node;while(start!=end){start++;ListNode next=temp.next;temp.next=pre;pre=temp;temp=next;}node.next=temp;//反转的第一个节点指向反转的最后一个节点的下一个节点return pre;} }

思路2 创建守卫节点和p，不断改变p.next和g.next

class Solution {public ListNode reverseBetween(ListNode head, int m, int n) {// 定义一个dummyHead, 方便处理ListNode dummyHead = new ListNode(0);dummyHead.next = head;// 初始化指针ListNode g = dummyHead;ListNode p = dummyHead.next;// 将指针移到相应的位置for(int step = 0; step < m - 1; step++) {g = g.next; p = p.next;}// 头插法插入节点for (int i = 0; i < n - m; i++) {ListNode removed = p.next;p.next = p.next.next;removed.next = g.next;g.next = removed;}return dummyHead.next;} }作者：mu-yi-cheng-zhou-2 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/java-shuang-zhi-zhen-tou-cha-fa-by-mu-yi-cheng-zho/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

深度优先搜索

1 200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

解题思路：一次深搜把一块岛屿的1全部置为0，每深搜一次，岛屿数量加1.

class Solution {public int numIslands(char[][] grid) {//解题思路，在一次深搜的过程中把所有的能触及到的1都置为0，再从另一个为1的地方开始覆盖if (grid == null || grid.length == 0) {return 0;}int count=0;for(int i=0;i<grid.length;i++){for(int j=0;j<grid[0].length;j++){if(grid[i][j]=='1'){count++;dfs(grid,i, j);}}}return count; }public void dfs(char grid[][],int i,int j){if(i<0||i>grid.length-1||j<0||j>grid[0].length-1||grid[i][j]=='0')return ; grid[i][j]='0';dfs(grid,i+1, j);dfs(grid,i-1, j);dfs(grid,i, j+1);dfs(grid,i, j-1);} }

2 47. 全排列 II

3 463. 岛屿的周长

解题思路一

有两点主要注意的地方
1我把遍历过的点设置为2之后，不用再把它还原为1，这样会造成重复计算，因为岛屿的1都是相邻的，我们一次深搜就可以遍历完

2 不用memo数组做记忆化存储，因为不涉及重复计算

class Solution {int m;int n;//Integer memo[][];public int islandPerimeter(int[][] grid) {m=grid.length;n=grid[0].length;memo=new Integer[m][n];for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){return dfs(grid,i,j);}}}return 0;}public int dfs(int grid[][],int i,int j){if(i<0||i>m-1||j<0||j>n-1||grid[i][j]==0)return 1;if(grid[i][j]==2){return 0;//不允许反向回溯}// if(memo[i][j]!=null)// return memo[i][j];grid[i][j]=2;int result= dfs(grid,i+1,j)+dfs(grid,i-1,j)+dfs(grid,i,j+1)+dfs(grid,i,j-1);// grid[i][j]=1;// return memo[i][j]=result;return result;} }

思路2：广搜应该是个不错的选择，遍历到某个节点就判断这个节点是否与水域相邻，计算边长

思路3 迭代，暴力遍历

class Solution {static int[] dx = {0, 1, 0, -1};static int[] dy = {1, 0, -1, 0};public int islandPerimeter(int[][] grid) {int n = grid.length, m = grid[0].length;int ans = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (grid[i][j] == 1) {int cnt = 0;for (int k = 0; k < 4; ++k) {int tx = i + dx[k];int ty = j + dy[k];if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] == 0) {cnt += 1;}}ans += cnt;}}}return ans;} }

思路4：找规律

只用算右边和下边两个方向的重叠边数，因为我们是从左向右，从上往下遍历的

class Solution {public int islandPerimeter(int[][] grid) {int row=grid.length,col=grid[0].length;int cnt=0,border=0;for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(grid[i][j]==1){cnt++;if(j<col-1&&grid[i][j+1]==1)border++;if(i<row-1&&grid[i+1][j]==1)border++;}}}return 4*cnt-2*border;} }

4 827. 最大人工岛

解题思路：从每一个0开始搜索，当前0能搜索到的所有的1的最大值加上1（它本身被填海造陆）就是我们的结果了

class Solution {int m;int n;boolean visited[][];public int largestIsland(int[][] grid) {m=grid.length;n=grid[0].length;visited=new boolean[m][n];int max=0;boolean flag=false;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==0){flag=true;//表示有0grid[i][j]=1;//不改成1没法dfs，一进去就直接退回来了max=Math.max(max,dfs(grid,i,j)); recoverVisited() ;//恢复未访问状态 grid[i][j]=0;//恢复为0}}}return flag==false?m*n:max;//原来grid中可能没有0}public int dfs(int [][]grid,int i,int j){if(i<0||i>m-1||j<0||j>n-1||grid[i][j]==0)return 0;if(visited[i][j])//访问过return 0;visited[i][j]=true;int result= 1+dfs(grid,i+1,j)+dfs(grid,i-1,j)+dfs(grid,i,j+1)+dfs(grid,i,j-1); return result;}public void recoverVisited(){for(int i=0;i<m;i++){for(int j=0;j<n;j++){visited[i][j]=false;}}}}

超时，逻辑没问题，再加一个记忆化搜索,但是我的每一个dfs表示的是从上一个的某个方向出发经过它的时候，它能接触的岛屿面积的最大数，它实际可以接触到的岛屿数很可能比这个值大，所以直接memo[i][j]=result会出错

我没想到怎么剪枝，但是看到一个跟我思路一样的老哥的提交通过的代码，修改如下，应该是原来每一次dfs完毕恢复访问状态为false比较耗时吧。

class Solution {int m;int n;public int largestIsland(int[][] grid) {m=grid.length;n=grid[0].length; int max=0;int timer=3;//记录标志位，用来判断当前坐标元素的boolean flag=false;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==0){flag=true;//表示有0grid[i][j]=1;max=Math.max(max,dfs(grid,i,j,timer++)); //每一次dfs传入的timer标志位不同，相当于每一次dfs都会改变grid中的元素，被当前0能够搜索到的原来的1会被改成timer//recoverVisited() ;//恢复未访问状态,应该是这耗时了 grid[i][j]=0;}}}return flag==false?m*n:max;}public int dfs(int [][]grid,int i,int j,int timer){if(i<0||i>m-1||j<0||j>n-1||grid[i][j]==0||grid[i][j]==timer)return 0; grid[i][j]=timer;int result= 1+dfs(grid,i+1,j,timer)+dfs(grid,i-1,j,timer)+dfs(grid,i,j+1,timer)+dfs(grid,i,j-1,timer); return result;} }

5 17. 电话号码的字母组合

解题思路：每次从digits的每一位数字对应的字母表中求出一个字母进行拼接

class Solution {Map<Character,String>map=new HashMap();List<String>list=new ArrayList();public List<String> letterCombinations(String digits) {map.put('2',"abc");map.put('3',"def");map.put('4',"ghi");map.put('5',"jkl");map.put('6',"mno");map.put('7',"pqrs");map.put('8',"tuv");map.put('9',"wxyz");if(digits.length()==0)return list;dfs( digits,"",0);return list;}public void dfs(String digits,String str,int cur){if(str.length()==digits.length()){list.add(str);return;}// for(int i=cur;i<digits.length();i++){String temp=map.get(digits.charAt(cur));for(int j=0;j<temp.length();j++){ dfs(digits,str+temp.charAt(j),cur+1);}// }} }

StringBuilder完胜

class Solution {Map<Character,String>map=new HashMap();List<String>list=new ArrayList();public List<String> letterCombinations(String digits) {map.put('2',"abc");map.put('3',"def");map.put('4',"ghi");map.put('5',"jkl");map.put('6',"mno");map.put('7',"pqrs");map.put('8',"tuv");map.put('9',"wxyz");if(digits.length()==0)return list;StringBuilder str=new StringBuilder();dfs( digits,str,0);return list;}public void dfs(String digits,StringBuilder str,int cur){if(str.length()==digits.length()){list.add(str.toString());return;}// for(int i=cur;i<digits.length();i++){String temp=map.get(digits.charAt(cur));for(int j=0;j<temp.length();j++){ str.append(temp.charAt(j));dfs(digits,str,cur+1);str.delete(str.length()-1,str.length());}// }} }

位运算

1 461. 汉明距离

异或出来的数就是两个数的不同位的1组成的数

class Solution {public int hammingDistance(int x, int y) {int z=x^y;int count=0;while(z>0){ if((z&1)==1)count++;z=z>>>1; //这是逻辑右移高位补0，>>是算术右移，高位补1 }return count;} } class Solution { public:int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;while (s) {s &= s - 1;ret++;}return ret;} };

2 190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

思路：从后往前依次取出n的二进制位，然后result左移加上取出来的n的二进制位

public class Solution {// you need treat n as an unsigned valuepublic int reverseBits(int n) {int res=0;for(int i=0;i<32;i++){res= (res<<1)+(n&1);//n的二进位从后往前取，加到res上就是从前往后加，实现颠倒n=n>>1;//n每次右移一位，好让出每一位}return res;} }

3 67. 二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = “11”, b = “1”
输出: “100”

示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

解题思路，将两个字符串补到相同长度，然后从末尾开始相加，考虑进位，最后反转字符串

class Solution {public String addBinary(String a, String b) {int len1=a.length();int len2=b.length();if(len1>len2){int mod=len1-len2;while(mod>0){b="0"+b;mod--;}}else if(len1<len2){int mod=len2-len1;while(mod>0){a="0"+a;mod--;} }int carry=0;char[]a1=a.toCharArray();char[]b1=b.toCharArray();String result="";for(int i=a1.length-1;i>=0;i--){if(a1[i]=='1'&&b1[i]=='1'){result+=carry;carry=1;}else if(a1[i]=='0'&&b1[i]=='0'){result+=carry;carry=0;}else{int c=(carry==0)?1:0;result+=c; // carry=carry; //carry是0就会变成0，carry是1就还是1 }}if(carry==1)result+="1";return new StringBuilder(result).reverse().toString();} }

String改成StringBuilder 2ms，减少String拼接时创建新字符串的花费

class Solution {public String addBinary(String a, String b) {int len1=a.length();int len2=b.length();if(len1>len2){int mod=len1-len2;while(mod>0){b="0"+b;mod--;}}else if(len1<len2){int mod=len2-len1;while(mod>0){a="0"+a;mod--;} }int carry=0;char[]a1=a.toCharArray();char[]b1=b.toCharArray();StringBuilder result=new StringBuilder();for(int i=a1.length-1;i>=0;i--){if(a1[i]=='1'&&b1[i]=='1'){result.append(carry);carry=1;}else if(a1[i]=='0'&&b1[i]=='0'){result.append(carry);carry=0;}else{int c=(carry==0)?1:0;result.append(c); // carry=carry; //carry是0就会变成0，carry是1就还是1 }}if(carry==1)result.append(1);return result.reverse().toString();} }

这个解法真的太优雅了。

class Solution {public String addBinary(String nums1, String nums2) {StringBuilder ans = new StringBuilder();int pos1 = nums1.length() - 1;int pos2 = nums2.length() - 1;int carry = 0; while(pos1 >= 0 || pos2 >= 0 || carry != 0){ int x = (pos1 >= 0 ? nums1.charAt(pos1) - '0' : 0);int y = (pos2 >= 0 ? nums2.charAt(pos2) - '0' : 0);int result = x + y + carry;ans.append(result % 2);carry = result / 2; pos1--;pos2--;} return ans.reverse().toString();} }

4 371. 两整数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-two-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1
因为整数都是32位的，我们可以在一个32的for循环中搞定，通过右移i位得到该位上的数，然后两数相加考虑进位，再把得到的结果累加到结果中

class Solution {public int getSum(int a, int b) {int ans = 0;// 存储进位int carry = 0;for (int i = 0; i < 32; i++) {// 从低位到高位依次计算int x = (a >> i) & 1;int y = (b >> i) & 1;if (x == 1 && y == 1) {// 不管carry是啥，肯定有进位ans |= carry << i;carry = 1;} else if (x == 1 || y == 1) {// carry为1则有进位，carry为0则无进位，与现有的carry一致ans |= (carry ^ 1) << i;} else {// 不管carry是啥，肯定没有进位ans |= carry << i;carry = 0;}}return ans;} }作者：tong-zhu 链接：https://leetcode-cn.com/problems/sum-of-two-integers/solution/tong-ge-lai-shua-ti-la-yi-ti-liang-jie-m-3uer/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路2
就是把两数相加拆分成进位部分和非进位部分相加，但是也许不能一次搞定，需要多次迭代或者递归

class Solution {public int getSum(int a, int b) {// 011011 011100 011010 010010 000010 100010// 000111 000110 001000 010000 100000 000000int carry;while (b != 0) {carry = (a & b) << 1;a = a ^ b;b = carry;}return a;} }作者：tong-zhu 链接：https://leetcode-cn.com/problems/sum-of-two-integers/solution/tong-ge-lai-shua-ti-la-yi-ti-liang-jie-m-3uer/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 class Solution {public int getSum(int a, int b) {return (b==0)?a:getSum(a^b,(a&b)<<1);} }

树

1 111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

思路：递归，有左子树和右子树的最小深度决定，需要考虑左右子树为空为不为空的情况

class Solution {public int minDepth(TreeNode root) { if(root==null)return 0;if(root.left==null&&root.right==null)return 1;if(root.left==null)return 1+minDepth(root.right);if(root.right==null)return 1+minDepth(root.left);return 1+Math.min(minDepth(root.left),minDepth(root.right)); } } class Solution {public int minDepth(TreeNode root) {if(root == null) return 0;//这道题递归条件里分为三种情况//1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可if(root.left == null && root.right == null) return 1;//2.如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度 int m1 = minDepth(root.left);int m2 = minDepth(root.right);//这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;if(root.left == null || root.right == null) return m1 + m2 + 1;//3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可return Math.min(m1,m2) + 1; } }作者：reals 链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/li-jie-zhe-dao-ti-de-jie-shu-tiao-jian-by-user7208/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 class Solution {public int minDepth(TreeNode root) {if(root == null) return 0;int m1 = minDepth(root.left);int m2 = minDepth(root.right);//1.如果左孩子和右孩子有为空的情况，直接返回m1+m2+1//2.如果都不为空，返回较小深度+1return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1,m2) + 1;} }

剪枝，瞬间效率提升

class Solution {private int min=Integer.MAX_VALUE;public int minDepth(TreeNode root) {if(root==null)return 0;helper(root,1);return min;}public void helper(TreeNode root,int level){if(root==null||(root.left==null&&root.right==null)){min=Math.min(min,level);}if(level<min){if(root.left!=null)helper(root.left,level+1);if(root.right!=null)helper(root.right,level+1);}} }

访问到每个节点时如果当前深度已经大于等于最小值就直接返回了

class Solution {public int minDepth(TreeNode root) {if (root == null) return 0;helper(root, 1);return min;}int min = Integer.MAX_VALUE;public void helper(TreeNode root, int deep) {if (root == null) return;if (deep >= min) return;if (root.left == null && root.right == null) min = Math.min(min, deep);helper(root.left, deep + 1);helper(root.right, deep + 1);} }

思路二，层序遍历

2 100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p==null&&q==null)return true;if(p==null||q==null)return false;if(p.val!=q.val)return false;return isSameTree( p.left,q.left)&&isSameTree( p.right,q.right);} }

简化.

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) { if(p==null||q==null)return p==q;if(p.val!=q.val)return false;return isSameTree( p.left,q.left)&&isSameTree( p.right,q.right);} }

思路2：层序遍历

快速幂

1 50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。

暴力超时解法

class Solution {public double myPow(double x, int n) {if(n==0)return 1;int m=n;if(n<0) {n=-n;}double sum=1;for(int i=1;i<=n;i++){sum*=x;}return m>0?sum:1.0/sum;} }

方法一：快速幂 + 递归

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {if (N == 0) {return 1.0;}double y = quickMul(x, N / 2);return N % 2 == 0 ? y * y : y * y * x;} } class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {double ans = 1.0;// 贡献的初始值为 xdouble x_contribute = x;// 在对 N 进行二进制拆分的同时计算答案while (N > 0) {if (N % 2 == 1) {// 如果 N 二进制表示的最低位为 1，那么需要计入贡献ans *= x_contribute;}// 将贡献不断地平方x_contribute *= x_contribute;// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可N /= 2;}return ans;} }

为什么一定是2次幂呢，3次幂行不行？我试了一下，是可以的

class Solution {public double myPow(double x, int n) {if(n==0) return 1;return n>0?helper(x, n):1.0/helper(x, -n); }public double helper(double x, int n){if(n==0) return 1;if(n%3==0){double y= helper(x,n/3);return y*y*y;}else if(n%3==1){double y= helper(x,n/3);return y*y*y*x;} else{double y= helper(x,n/3);return y*y*y*x*x;}} }

排序

1 75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

示例 3：

输入：nums = [0]
输出：[0]

示例 4：

输入：nums = [1]
输出：[1]

解题思路1 ：插入排序

class Solution {public void sortColors(int[] nums) {for(int i=1;i<nums.length;i++){int curIndex=i-1;int temp=nums[i];while(curIndex>=0&&temp<nums[curIndex]){nums[curIndex+1]=nums[curIndex];curIndex--;}nums[curIndex+1]=temp;}} }

2 215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

解题思路1：暴力排序

public class Solution {public int findKthLargest(int[] nums, int k) {int len = nums.length;Arrays.sort(nums);return nums[len - k];} }

解题思路2：堆排序

建立一个大小为k的小顶堆，堆顶就是第k大的元素
参考：Java 排序 + 小顶堆 实现

class Solution {public int findKthLargest(int[] nums, int k) {//前K个元素原地建小顶堆buildHeap(nums, k);//遍历剩下元素，比堆顶小，跳过；比堆顶大，交换后重新堆化for (int i = k; i < nums.length; i++) {if (nums[i] < nums[0]) continue;swap(nums, i, 0);heapify(nums, k, 0);}//K个元素的小顶堆的堆顶即是第K大元素return nums[0];}/*** 建堆函数* 从倒数第一个非叶子节点开始堆化，倒数第一个非叶子节点下标为 K/2-1*/public void buildHeap(int[] a, int k) {for (int i = k/2 - 1; i >= 0; i--) {heapify(a, k, i);}}/*** 堆化函数* 父节点下标i，左右子节点的下标分别为 2*i+1 和 2*i+2*/public void heapify(int[] a, int k, int i) {//临时变量 minPos 用于存储最小值的下标，先假设父节点最小int minPos = i;while (true) {//和左子节点比较if (i*2+1 < k && a[i*2+1] < a[i]) minPos = i*2+1;//和右子节点比较if (i*2+2 < k && a[i*2+2] < a[minPos]) minPos = i*2+2;//如果minPos没有发生变化，说明父节点已经是最小了，直接跳出if (minPos == i) break;//否则交换swap(a, i, minPos);//父节点下标进行更新，继续堆化i = minPos;}}public void swap(int[] a, int n, int m) {int tmp = a[n];a[n] = a[m];a[m] = tmp;} }

解题思路3：优先队列

public class Solution {public int findKthLargest(int[] nums, int k) {int len = nums.length;// 使用一个含有 k 个元素的最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);for (int i = 0; i < k; i++) {minHeap.add(nums[i]);}for (int i = k; i < len; i++) {// 看一眼，不拿出，因为有可能没有必要替换Integer topEle = minHeap.peek();// 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去if (nums[i] > topEle) {minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();} }

字符串

1 394. 字符串解码

class Solution {public String decodeString(String s) {Stack<StringBuilder> stringStack = new Stack();Stack<Integer> countStack = new Stack();StringBuilder currentString = new StringBuilder();int count = 0;//遇到数字，就计数需要重复的次数//遇到'[',把当前count压入数字栈，当前字符串压入字符串栈//遇到字符，就拼接字符串//遇到']',弹出一个数字和字符进行拼接for (char c: s.toCharArray()){if (c == '['){stringStack.push(currentString);countStack.push(count);currentString = new StringBuilder();count = 0;}else if ( c == ']'){count = countStack.pop();StringBuilder temp = stringStack.pop();while (count > 0){temp.append(currentString);count--;}currentString = temp;}else if (Character.isDigit(c)){count = count * 10 + c - '0';//避免出现多位整数，12这种一个一个地检测 }else {currentString.append(c);}}return currentString.toString();} }

总结

以上是生活随笔为你收集整理的leetcode刷的一些杂题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。