网站 › 『编程语言讨论求助区』 › leetCode热题10-15 解题代码，思路

黑白客 发表于 2023-3-24 10:56

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

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

---



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

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





>自测代码

```java
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;
                                returnres.next;
                        }

                        if(list2 == null){
                                listNode.next = list1;
                                returnres.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)

}

```

> 提交代码

```java
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;
                                returnres.next;
                        }

                        if(list2 == null){
                                listNode.next = list1;
                                returnres.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        二叉树的层序遍历        Medium        2022-09-21        202
//给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
//
//
//
// 示例 1：
//
//
//输入：root =
//输出：[,,]
//
//
// 示例 2：
//
//
//输入：root =
//输出：[]
//
//
// 示例 3：
//
//
//输入：root = []
//输出：[]
//
//
//
//
// 提示：
//
//
// 树中节点数目在范围 内
// -1000 <= Node.val <= 1000
//
//
// Related Topics 树 广度优先搜索 二叉树 &#128077; 1604 &#128078; 0




> 自测代码

```java
public class P102_BinaryTreeLevelOrderTraversal{
       public static void main(String[] args) {
              //测试代码
              Solution solution = new P102_BinaryTreeLevelOrderTraversal().new Solution();
                  String data = "";
               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;
        }


}

```

>提交代码

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



>自测代码

```java

public class P33_SearchInRotatedSortedArray{
       public static void main(String[] args) {
              //测试代码
              Solution solution = new P33_SearchInRotatedSortedArray().new Solution();

                  String data = "";
               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){
                        returnres;
                }

                if ( num == 1 ) {
                        if (nums == target) {
                                return 0;
                        }else {
                                return res;
                        }
                }

                int r = 0;
                int l = num-1;
                while (r <= l){
                        int mid = (l-r)/2 +r;

                        if ( nums == target ) {
                                return mid;
                        }
                       
                        if (nums <= nums ) {

                                if (nums <= target && target < nums ) {
                                        l = mid -1 ;
                                }else {
                                        r = mid +1;
                                }

                        }else{

                                if (target <= nums && target > nums ) {
                                        r = mid +1 ;
                                }else{
                                        l = mid -1;
                                }

                        }

                }

                return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}

```

> 提交代码

```java
class Solution {
    public int search(int[] nums, int target) {
                int num = nums.length;

                int res = -1;
               
                if (nums.length == 0){
                        returnres;
                }

                if ( num == 1 ) {
                        if (nums == target) {
                                return 0;
                        }else {
                                return res;
                        }
                }

                int r = 0;
                int l = num-1;
                while (r <= l){
                        int mid = (l-r)/2 +r;

                        if ( nums == target ) {
                                return mid;
                        }
                       
                        if (nums <= nums ) {

                                if (nums <= target && target < nums ) {
                                        l = mid -1 ;
                                }else {
                                        r = mid +1;
                                }

                        }else{

                                if (target <= nums && target > nums ) {
                                        r = mid +1 ;
                                }else{
                                        l = mid -1;
                                }

                        }

                }

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

# 4 ✔        有效的括号        Easy        2023-01-12        194

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



>自测代码

```java
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);
                                if (s1 == null) {
                                        String pop = data.pop();
                                        if (pop == null || !pop.equals(split)) {
                                                return false;
                                        }
                                }else{
                                        data.add(s1);
                                }
                        }
                }catch (Exception e){
                        return false;
                }

                if (!data.empty()) {
                        returnfalse;
                }
                return true;
    }


}
//leetcode submit region end(Prohibit modification and deletion)

}


```

> 提交代码

```java
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);
                                if (s1 == null) {
                                        String pop = data.pop();
                                        if (pop == null || !pop.equals(split)) {
                                                return false;
                                        }
                                }else{
                                        data.add(s1);
                                }
                        }
                }catch (Exception e){
                        return false;
                }

                if (!data.empty()) {
                        returnfalse;
                }
                return true;
    }


}
```

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

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

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

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

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

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

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

>自测代码

```java
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;
            data = true;
            int[] res = new int;
            res = 0;
            res = 0;
            for (int i = 1; i < length; i++) {
                for (int j = 0; j < i; j++) {
                  /*长度小于三的情况*/
                  if (i - j < 3) {
                        if (chars == chars) {
                            data = true;
                        }else {
                            data = false;
                        }
                  } else if (chars == chars &&data   ) {
                        data = true;
                  }else{
                        data = false;
                  }

                  if (data) {
                        if (res - res <= i -j) {
                            res = j;
                            res = i;
                        }
                  }
                }
            }


//            0 1 2 3 4
            return s.substring(res,res+1);
      }
    }
//leetcode submit region end(Prohibit modification and deletion)

}


```

> 提交代码

```java
    class Solution {
      public String longestPalindrome(String s) {
            char[] chars = s.toCharArray();
            int length = chars.length;

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

                  if (data) {
                        if (res - res <= i -j) {
                            res = j;
                            res = i;
                        }
                  }
                }
            }


//            0 1 2 3 4
            return s.substring(res,res+1);
      }
    }
```

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



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

>自测代码

```java
public class P121_BestTimeToBuyAndSellStock{
       public static void main(String[] args) {
              //测试代码
              Solution solution = new P121_BestTimeToBuyAndSellStock().new Solution();
                String data = "";
               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 <min ? prices : min;
                        res = prices - min > res ? prices - min : res;
                }

                return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}


```

> 提交代码

```java
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 <min ? prices : min;
                        res = prices - min > res ? prices - min : res;
                }

                return res;
    }
}
```

lsy832 发表于 2023-3-24 16:10

学习新思路

侃遍天下无二人 发表于 2023-3-24 16:42

排版太糟糕了。。。

黑白客 发表于 2023-3-27 18:38

侃遍天下无二人 发表于 2023-3-24 16:42
排版太糟糕了。。。

这还糟糕吗，大佬，有没有好的例子，发个连接出来，我学习一下:loveliness:

Him8848 发表于 2023-3-28 12:26

黑白客 发表于 2023-3-27 18:38
这还糟糕吗，大佬，有没有好的例子，发个连接出来，我学习一下

楼主，我的建议是去用一下markdown吧，我的lua那两个贴子就是markdown写的，你可以看一下，你这里题目的排版确实有点糟糕，代码排版没啥问题

侃遍天下无二人 发表于 2023-4-3 11:05

黑白客 发表于 2023-3-27 18:38
这还糟糕吗，大佬，有没有好的例子，发个连接出来，我学习一下

题目描述用引用样式包裹，不要在前面打一堆 双斜杠

查看完整版本: leetCode热题10-15 解题代码，思路