hot100（7）

61.31. 下一个排列 - 力扣（LeetCode）

数组问题，下一个更大的排列

题解：31. 下一个排列题解 - 力扣（LeetCode）

（1）从后向前找到一个相邻的升序对（i,j)，此时(j,end)为降序

（2）从(j,end)从后向前找到一个大于i对应的数，其下标k，这个数就是要替换的“较小的大数”

（3）交换i和k对应的数

（4）此时(j,end)为降序，将(j,end)置为升序

public void nextPermutation(int[] nums) {int i,j,k;for(i = nums.length - 2 ; i >= 0 ; i--){if(nums[i] < nums[i+1]){break;}}j = i + 1;if(i == -1){Arrays.sort(nums);return ;}for(k = nums.length - 1 ; k >= j ; k--){if(nums[k] > nums[i]){break;}}int tmp = nums[i];nums[i] = nums[k];nums[k] = tmp;Arrays.sort(nums,j,nums.length);}

62.538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

一看到累加树，相信很多小伙伴都会疑惑：如何累加？遇到一个节点，然后再遍历其他节点累加？怎么一想这么麻烦呢。

然后再发现这是一棵二叉搜索树，二叉搜索树啊，这是有序的啊。

那么有序的元素如何求累加呢？

其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。

为什么变成数组就是感觉简单了呢？

因为数组大家都知道怎么遍历啊，从后向前，挨个累加就完事了，这换成了二叉搜索树，看起来就别扭了一些是不是。

那么知道如何遍历这个二叉树，也就迎刃而解了，从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。

像前面的数组的累加遍历，需要用到前一个处理过的元素的值和当前元素累加，本题页需要一个pre指针记录当前遍历节点cur的前一个节点，这样才方便做累加。

int prev = 0;public TreeNode convertBST(TreeNode root) {reverseInOrder(root);return root;}public void reverseInOrder(TreeNode root){if(root == null){return ;}reverseInOrder(root.right);root.val += prev;prev = root.val;reverseInOrder(root.left);}

63.23. 合并 K 个升序链表 - 力扣（LeetCode）

方法一：顺序合并
思路

我们可以想到一种最朴素的方法：用一个变量 ans 来维护以及合并的链表，第 i 次循环把第 i 个链表和 ans 合并，答案保存到 ans 中。

public ListNode mergeKLists(ListNode[] lists) {ListNode ans = null;for (ListNode list : lists) {ans = mergeTwoLists(ans,list);}return ans;}public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode head = new ListNode(0);ListNode p = head;ListNode pa = list1 , pb = list2;while(pa != null && pb != null){if(pa.val < pb.val){p.next = pa;pa = pa.next;}else{p.next = pb;pb = pb.next;}p = p.next;}p.next = (pa != null)? pa : pb;return head.next;}

public ListNode mergeKLists(ListNode[] lists) {return merge(lists,0,lists.length - 1);}public ListNode merge(ListNode[] lists,int l, int r){if(l == r){return lists[l];}if(l > r){return null;}int mid = l + (r - l)/2;return mergeTwoLists(merge(lists,l,mid),merge(lists,mid + 1, r));}public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode head = new ListNode(0);ListNode p = head;ListNode pa = list1 , pb = list2;while(pa != null && pb != null){if(pa.val < pb.val){p.next = pa;pa = pa.next;}else{p.next = pb;pb = pb.next;}p = p.next;}p.next = (pa != null)? pa : pb;return head.next;}

class Status implements Comparable<Status>{int val;ListNode ptr;Status(int val , ListNode ptr){this.val = val;this.ptr = ptr;}@Overridepublic int compareTo(Status o) {return this.val - o.val;}}public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<Status> queue = new PriorityQueue<>();for (ListNode list : lists) {if(list != null){queue.offer(new Status(list.val,list));}}ListNode head = new ListNode(0);ListNode tail = head;while(!queue.isEmpty()){Status f = queue.poll();tail.next = f.ptr;tail = tail.next;if(f.ptr.next != null){queue.offer(new Status(f.ptr.next.val,f.ptr.next));}}return head.next;}

64.560. 和为 K 的子数组 - 力扣（LeetCode）

I枚举

枚举所有子数组并计算其和，枚举时先枚举结尾，再枚举开头，让开头倒序遍历，可以让后面的计算用到前面计算的结果。

public int subarraySum(int[] nums, int k) {int cnt = 0;for(int i = 0 ; i < nums.length ; i++){int sum = 0 ;for(int j = i ; j >= 0; j--){sum = sum + nums[j];if(sum == k){cnt++;}}}return cnt;}

时间复杂度O(n^2)，空间复杂度O(1)

II 前缀和 + 哈希表

public int subarraySum(int[] nums, int k) {int pre = 0 ,cnt = 0;HashMap<Integer,Integer> map = new HashMap<>();map.put(0,1);for(int i = 0 ; i < nums.length ; i++){pre += nums[i];if(map.containsKey(pre - k)){cnt += map.get(pre - k);}map.put(pre,map.getOrDefault(pre,0) + 1);}return cnt;}

 65.21. 合并两个有序链表 - 力扣（LeetCode）

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode head = new ListNode(0);ListNode p = head;ListNode pa = list1 , pb = list2;while(pa != null && pb != null){if(pa.val < pb.val){p.next = pa;pa = pa.next;}else{p.next = pb;pb = pb.next;}p = p.next;}p.next = (pa != null)? pa : pb;return head.next;}

66.20. 有效的括号 - 力扣（LeetCode）

栈

public boolean isValid(String s) {Deque<Character> stack = new ArrayDeque<>();for(int i = 0 ; i < s.length() ; i++){if(isLeft(s.charAt(i))){stack.push(s.charAt(i));}else{if(stack.isEmpty()){return false;}else if(s.charAt(i) == ')'){if(stack.pop() != '('){return false;}}else if(s.charAt(i) == '}'){if(stack.pop() != '{'){return false;}}else if(s.charAt(i) == ']'){if(stack.pop() != '['){return false;}}}}return stack.isEmpty();}public boolean isLeft(char c){if(c == '(' || c == '{' || c =='['){return true;}return false;}

67.19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

快慢指针

dummyNode避免边界条件讨论

在纸上画出后观察边界条件

public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyNode = new ListNode(0);dummyNode.next = head;ListNode fast = dummyNode,slow = dummyNode;for(int i = 0 ; i < n ; i++){fast = fast.next;}while(fast.next != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummyNode.next;}

68.17. 电话号码的字母组合 - 力扣（LeetCode）

回溯问题

String[] mapping = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};List<String> res = new ArrayList<>();StringBuilder path = new StringBuilder();String digits;public List<String> letterCombinations(String digits) {this.digits = digits;if(digits.isEmpty()){return res;}dfs(0);return res;}public void dfs(int index){if(index == digits.length()){res.add(new String(path));return ;}int digit = digits.charAt(index) - '0';String s = mapping[digit];for (char c : s.toCharArray()) {path.append(c);dfs(index + 1);path.deleteCharAt(path.length() - 1);}}

69.15. 三数之和 - 力扣（LeetCode）

双指针

算法讲解：两数之和 三数之和【基础算法精讲 01】_哔哩哔哩_bilibili

降低时间复杂度的原因：利用数组有序的特性，用O(1)的时间得到了O(n)的信息（某个数和任何数相加都小于target或某个数和任何数相加都大于target）

public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for(int i = 0 ; i < nums.length - 2 ; i++){int j = i + 1;int k = nums.length - 1;if(nums[i] > 0){return res;}if(i > 0 && nums[i] == nums[i-1]){continue;}while(j < k){int s = nums[i] + nums[j] +nums[k];if(s > 0){k--;}else if(s < 0){j++;}else{res.add(List.of(nums[i],nums[j],nums[k]));while(j < k && nums[j] == nums[j+1]){j++;}while(j < k && nums[k] == nums[k-1]){k--;}j++;k--;}}}return res;}

70.11. 盛最多水的容器 - 力扣（LeetCode）

双指针

用分析，尝试用O(1)的操作获得O(n)的信息

对于当前盛水的较短者，中间任意一根垂线与其组成的容器，其容量都不会大于当前的容量（高不会超过当前容器的高，宽会比当前容器的宽更小），如果要找到一个容量更大的容器，肯定不会包括这条线。

题解：盛最多水的容器 接雨水_哔哩哔哩_bilibili

public int maxArea(int[] height) {int i = 0 , j = height.length - 1;int area = 0;int ans = 0;while(i < j){int h = Math.min(height[i],height[j]);area = h *(j-i);ans = Math.max(area,ans);if(height[i] < height[j]){i++;}else{j--;}}return ans;}

每次花费O(1)的时间就去掉了一条垂线，时间复杂度O(n)，空间复杂度O(1)