leetCode热题10-15 解题代码，思路

前言

计划做一系列算法题的文章，因为自己这块确实比较薄弱，但又很重要！写这篇文章前，我已经刷了一本剑指offer，leetcode top150道，牛客某题库106道 这个样子吧，感觉题量算是入门了吧？个人感觉还是入门级别，因为最开始的题完全是硬刷，全是混个脸熟。到现在才开始对里面的门门道道研究，总结。
所以打算从这篇文章开始，静下心来过一遍。留下自己的足迹也算是给自己打气吧！

---

1 ✔ [21]合并两个有序链表 Easy 2023-02-22 222

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//
//
//
// 示例 1：
//
//
//输入：l1 = [1,2,4], l2 = [1,3,4]
//输出：[1,1,2,3,4,4]
//
//
// 示例 2：
//
//
//输入：l1 = [], l2 = []
//输出：[]
//
//
// 示例 3：
//
//
//输入：l1 = [], l2 = [0]
//输出：[0]
//
//
//
//
// 提示：
//
//
// 两个链表的节点数目范围是 [0, 50]
// -100 <= Node.val <= 100
// l1 和 l2 均按 非递减顺序 排列
//
//
// Related Topics 递归 链表 👍 2826 👎 0

自测代码

public class P21_MergeTwoSortedLists{public static void main(String[] args) {int[] ints = {1, 2, 4};ListNode listNode = new ListNode(ints);int[] ints2 =  {1,3,4};ListNode listNode2 = new ListNode(ints2);//测试代码Solution solution = new P21_MergeTwoSortedLists().new Solution();ListNode listNode1 = solution.mergeTwoLists(listNode, listNode2);System.out.println(listNode1.toString());}//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode listNode = new ListNode(0);ListNode res = listNode;while (list1 != null || list2 != null ){if (list1 == null){listNode.next = list2;return  res.next;}if(list2 == null){listNode.next = list1;return  res.next;}if (list1.val > list2.val) {listNode.next = list2;list2 = list2.next;}else {listNode.next = list1;list1 = list1.next;}listNode = listNode.next;}return res.next;}
}
//leetcode submit region end(Prohibit modification and deletion)}

提交代码

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode listNode = new ListNode(0);ListNode res = listNode;while (list1 != null || list2 != null ){if (list1 == null){listNode.next = list2;return  res.next;}if(list2 == null){listNode.next = list1;return  res.next;}if (list1.val > list2.val) {listNode.next = list2;list2 = list2.next;}else {listNode.next = list1;list1 = list1.next;}listNode = listNode.next;}return res.next;}
}

2 [102]二叉树的层序遍历 Medium 2022-09-21 202

//给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
//
//
//
// 示例 1：
//
//
//输入：root = [3,9,20,null,null,15,7]
//输出：[[3],[9,20],[15,7]]
//
//
// 示例 2：
//
//
//输入：root = [1]
//输出：[[1]]
//
//
// 示例 3：
//
//
//输入：root = []
//输出：[]
//
//
//
//
// 提示：
//
//
// 树中节点数目在范围 [0, 2000] 内
// -1000 <= Node.val <= 1000
//
//
// Related Topics 树 广度优先搜索 二叉树 👍 1604 👎 0

自测代码

public class P102_BinaryTreeLevelOrderTraversal{public static void main(String[] args) {//测试代码Solution solution = new P102_BinaryTreeLevelOrderTraversal().new Solution();String data = "[3,9,20,null,null,15,7]";TreeNode treeNode = mkTree(data);List<List<Integer>> lists = solution.levelOrder(treeNode);for (int i = 0; i < lists.size(); i++) {System.out.println();List<Integer> integers = lists.get(i);for (int i1 = 0; i1 < integers.size(); i1++) {System.out.print("  " + integers.get(i1));}}}//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue = new ArrayDeque<>();List<List<Integer>> res = new ArrayList<>();if(root != null){queue.add(root);}if (!queue.isEmpty()) {do {queue = check(queue, res);}while (!queue.isEmpty()) ;}return res;}public Queue<TreeNode> check(Queue<TreeNode> queue,List<List<Integer>> data){Queue<TreeNode> res = new ArrayDeque<>();ArrayList<Integer> integers = new ArrayList<>();while (!queue.isEmpty() ){TreeNode poll = queue.poll();if (poll == null) {break;}int val = poll.val;integers.add(val);TreeNode left = poll.left;if (left != null) {res.add(left);}TreeNode right = poll.right;if (right != null) {res.add(right);}}data.add(integers);return res;}}

提交代码

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue = new ArrayDeque<>();List<List<Integer>> res = new ArrayList<>();if(root != null){queue.add(root);}if (!queue.isEmpty()) {do {queue = check(queue, res);}while (!queue.isEmpty()) ;}return res;}public Queue<TreeNode> check(Queue<TreeNode> queue,List<List<Integer>> data){Queue<TreeNode> res = new ArrayDeque<>();ArrayList<Integer> integers = new ArrayList<>();while (!queue.isEmpty() ){TreeNode poll = queue.poll();if (poll == null) {break;}int val = poll.val;integers.add(val);TreeNode left = poll.left;if (left != null) {res.add(left);}TreeNode right = poll.right;if (right != null) {res.add(right);}}data.add(integers);return res;}}

主要是使用了队列的特性，然后通过新建一个方法更清晰的区分，每一层的数据

3 ✔ [33]搜索旋转排序数组 Medium 2023-03-08 197

//整数数组 nums 按升序排列，数组中的值 互不相同 。
//
// 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[
//k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2
//,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
//
// 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
//
// 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
//
//
//
// 示例 1：
//
//
//输入：nums = [4,5,6,7,0,1,2], target = 0
//输出：4
//
//
// 示例 2：
//
//
//输入：nums = [4,5,6,7,0,1,2], target = 3
//输出：-1
//
// 示例 3：
//
//
//输入：nums = [1], target = 0
//输出：-1
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 5000
// -10⁴ <= nums[i] <= 10⁴
// nums 中的每个值都 独一无二
// 题目数据保证 nums 在预先未知的某个下标上进行了旋转
// -10⁴ <= target <= 10⁴
//
//
// Related Topics 数组 二分查找 👍 2422 👎 0

自测代码

public class P33_SearchInRotatedSortedArray{public static void main(String[] args) {//测试代码Solution solution = new P33_SearchInRotatedSortedArray().new Solution();String data = "[4,5,6,7,0,1,2]";int[] ints = StrToIntArray(data);System.out.println(solution.search(ints, 0));}//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int search(int[] nums, int target) {int num = nums.length;int res = -1;if (nums.length == 0){return  res;}if ( num == 1 ) {if (nums[0] == target) {return 0;}else {return res;}}int r = 0;int l = num-1;while (r <= l){int mid = (l-r)/2 +r;if ( nums[mid] == target ) {return mid;}if (nums[r] <= nums[mid] ) {if (  nums[r] <= target && target < nums[mid] ) {l = mid -1 ;}else {r = mid +1;}}else{if (target <= nums[l] && target > nums[mid] ) {r = mid +1 ;}else{l = mid -1;}}}return res;}
}
//leetcode submit region end(Prohibit modification and deletion)}

提交代码

class Solution {public int search(int[] nums, int target) {int num = nums.length;int res = -1;if (nums.length == 0){return  res;}if ( num == 1 ) {if (nums[0] == target) {return 0;}else {return res;}}int r = 0;int l = num-1;while (r <= l){int mid = (l-r)/2 +r;if ( nums[mid] == target ) {return mid;}if (nums[r] <= nums[mid] ) {if (  nums[r] <= target && target < nums[mid] ) {l = mid -1 ;}else {r = mid +1;}}else{if (target <= nums[l] && target > nums[mid] ) {r = mid +1 ;}else{l = mid -1;}}}return res;}
}

中等难度，笔者之前也刷到过，但是还是想了很久。
第一： 看错了题目，以为要求旋转之前 target的下标
第二：善用二分查找方法， 遇到查找的时候想想二分方法，二分方法有一个特性就是可以直接舍弃一半数据，用另一半数据计算，所以当有一部分条件不是有序的时候，二分还是可以使用。
第三：边界值判断， 如果直接把mind赋值给左或者右，可能会导致死循环，因为 只有两个数的时候做除法mind值可能一直和左下标相同。
所以之后在自己声明了左右指针的时候，赋值时最好把中间值+1或者-1。
另外 循环条件也需要改成<=或者>= 因为 +1 / -1之后很可能导致 两个数相等，这个时候需要有等于的条件继续循环判断

4 ✔ [20]有效的括号 Easy 2023-01-12 194

//给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
//
// 有效字符串需满足：
//
//
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 每个右括号都有一个对应的相同类型的左括号。
//
//
//
//
// 示例 1：
//
//
//输入：s = “()”
//输出：true
//
//
// 示例 2：
//
//
//输入：s = “()[]{}”
//输出：true
//
//
// 示例 3：
//
//
//输入：s = “(]”
//输出：false
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 10⁴
// s 仅由括号 ‘()[]{}’ 组成
//
//
// Related Topics 栈 字符串 👍 3786 👎 0

自测代码

public class P20_ValidParentheses{public static void main(String[] args) {//测试代码Solution solution = new P20_ValidParentheses().new Solution();String s = "]";solution.isValid(s);}//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public boolean isValid(String s) {HashMap<String, String> hashMap = new HashMap<>();hashMap.put("(",")");hashMap.put("{","}");hashMap.put("[","]");String[] split = s.split("");int length = split.length;Stack<String> data = new Stack<>();try{for (int i = 0; i < length; i++) {String s1 = hashMap.get(split[i]);if (s1 == null) {String pop = data.pop();if (pop == null || !pop.equals(split[i])) {return false;}}else{data.add(s1);}}}catch (Exception e){return false;}if (!data.empty()) {return  false;}return true;}}
//leetcode submit region end(Prohibit modification and deletion)}

提交代码

class Solution {public boolean isValid(String s) {HashMap<String, String> hashMap = new HashMap<>();hashMap.put("(",")");hashMap.put("{","}");hashMap.put("[","]");String[] split = s.split("");int length = split.length;Stack<String> data = new Stack<>();try{for (int i = 0; i < length; i++) {String s1 = hashMap.get(split[i]);if (s1 == null) {String pop = data.pop();if (pop == null || !pop.equals(split[i])) {return false;}}else{data.add(s1);}}}catch (Exception e){return false;}if (!data.empty()) {return  false;}return true;}}

对我来说没有太大难度了，感觉对字符串操作的我貌似都擅长一些。
这道题目就是利用了一下栈的先进先出特性

5 ✔ [5]最长回文子串 Medium 2023-03-05 193

//给你一个字符串 s，找到 s 中最长的回文子串。
//
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
//
//
//
// 示例 1：
//
//
//输入：s = “babad”
//输出：“bab”
//解释：“aba” 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = “cbbd”
//输出：“bb”
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成
//
//
// Related Topics 字符串 动态规划 👍 6257 👎 0

动态规划 这个问题我其实已经写了好几遍了，但是这次再做还是做不出来，或者想到的方法非常复杂。感觉还是没有完全掌握动态规划。
因此，我特地去学习了动态规划相关的知识。
首先 动态规划是解决 有重复计算，可以拆分成子问题的一类问题的解决方案。
主要表现 求最短路径，最大回文子序列，多少种走法。
分析原问题 =》找出子问题 =》 找出子问题和原问题的关系 =》 解决子问题 并记录答案=》根据子问题 解决原问题。
正确子问题： 一般情况下都比较简单，特点 一般是 个数少，逻辑和原问题有关联
记录子问题答案 ： 通过记录子问题答案，帮助解决原问题，减少重复计算，一般通过数组，二维数组来做。

这道题目 求最长回文子序列，
首先回文子序列 如果满足，那么去调开头和结尾的字母，依然满足是回文子序列。
如果一直去除，那么就会变成单个字母或者两个相同的字母，
利用这个特性，就可以找到子问题。

因为子问题和原问题的连接点 是两边添加参数，所以一定要注意动态规划的循环顺序

然后就是边界值的判断，
只有一个的时候肯定是回文串，两个的时候只需要判断两个是否相等。

自测代码

public class P5_LongestPalindromicSubstring {public static void main(String[] args) {//测试代码Solution solution = new P5_LongestPalindromicSubstring().new Solution();String s = "bb";System.out.println(solution.longestPalindrome(s));}//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)class Solution {public String longestPalindrome(String s) {char[] chars = s.toCharArray();int length = chars.length;/*简单的动态规划都是记录一个值，这个最长回文子序列可以通过记录左右两个值*/Boolean[][] data  = new Boolean[length][length];data[0][0] = true;int[] res = new int[2];res[0] = 0;res[1] = 0;for (int i = 1; i < length; i++) {for (int j = 0; j < i; j++) {/*长度小于三的情况*/if (i - j < 3) {if (chars[i] == chars[j]) {data[j][i] = true;}else {data[j][i] = false;}} else if (chars[i] == chars[j] &&  data[j+1][i-1]   ) {data[j][i] = true;}else{data[j][i] = false;}if (data[j][i]) {if (res[1] - res[0] <= i -j) {res[0] = j;res[1] = i;}}}}//            0 1 2 3 4return s.substring(res[0],res[1]+1);}}
//leetcode submit region end(Prohibit modification and deletion)}

提交代码

    class Solution {public String longestPalindrome(String s) {char[] chars = s.toCharArray();int length = chars.length;/*简单的动态规划都是记录一个值，这个最长回文子序列可以通过记录左右两个值*/Boolean[][] data  = new Boolean[length][length];data[0][0] = true;int[] res = new int[2];res[0] = 0;res[1] = 0;for (int i = 1; i < length; i++) {for (int j = 0; j < i; j++) {/*长度小于三的情况*/if (i - j < 3) {if (chars[i] == chars[j]) {data[j][i] = true;}else {data[j][i] = false;}} else if (chars[i] == chars[j] &&  data[j+1][i-1]   ) {data[j][i] = true;}else{data[j][i] = false;}if (data[j][i]) {if (res[1] - res[0] <= i -j) {res[0] = j;res[1] = i;}}}}//            0 1 2 3 4return s.substring(res[0],res[1]+1);}}

6 ✔ [121]买卖股票的最佳时机 Easy 2023-01-12 192

//给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
//
// 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
//
// 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
//
//
//
// 示例 1：
//
//
//输入：[7,1,5,3,6,4]
//输出：5
//解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
// 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
//
//
// 示例 2：
//
//
//输入：prices = [7,6,4,3,1]
//输出：0
//解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
//
//
//
//
// 提示：
//
//
// 1 <= prices.length <= 10⁵
// 0 <= prices[i] <= 10⁴
//
//
// Related Topics 数组 动态规划 👍 2672 👎 0

配合上一道也是动态规划问题，正好巩固一下
这道题目 相对来说简单，
还是通过找关系，
求最大收益，我就先求每天的最大收益，每天的最大收益和买入时的价格有关，就记录能够买入的最小价格，
循环的顺序从前往后，子问题就和主问题联系起来了

自测代码

public class P121_BestTimeToBuyAndSellStock{public static void main(String[] args) {//测试代码Solution solution = new P121_BestTimeToBuyAndSellStock().new Solution();String data = "[7,1,5,3,6,4]";System.out.println(solution.maxProfit(ArrayUtil.StrToIntArray(data)));}//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int maxProfit(int[] prices) {int len = prices.length;int min = Integer.MAX_VALUE;int res = 0;for (int i = 0; i < len; i++) {min = prices[i] <min ? prices[i] : min;res = prices[i] - min > res ? prices[i] - min : res;}return res;}
}
//leetcode submit region end(Prohibit modification and deletion)}

提交代码

class Solution {public int maxProfit(int[] prices) {int len = prices.length;int min = Integer.MAX_VALUE;int res = 0;for (int i = 0; i < len; i++) {min = prices[i] <min ? prices[i] : min;res = prices[i] - min > res ? prices[i] - min : res;}return res;}
}