网站 › 『编程语言讨论求助区』 › leetCode热题52-57 解题代码，调试代码和思路

黑白客 发表于 2024-2-6 14:15

leetCode热题52-57 解题代码，调试代码和思路

# 前言

本文属于特定的六道题目题解和调试代码。

1 ✔ [剑指 Offer 22]链表中倒数第k个节点 Easy 2022-09-01 91
2 ✔ 最小覆盖子串 Hard 2023-03-27 82
3 ✔ 比较版本号 Medium 2023-03-20 80
4 ✔ 从前序与中序遍历序列构造二叉树 Medium 2022-10-10 80
5 ✔ 最长有效括号 Hard 2023-04-05 79
6 ✔ 翻转字符串里的单词 Medium 2023-02-09 79

正所谓磨刀不误砍柴功，下面这几篇文章算是我用idea刷题的经验帖，对涉及的题型，数据结构的快速构建分析和解决很有帮助，这里放个链接仅供参考。

[如何调试递归程序，有何技巧？](https://blog.csdn.net/qq_44850489/article/details/129528264)

[按照树形结构直观地打印出一棵二叉树、快速创建leetcode中树的结构(Java)](https://blog.csdn.net/qq_44850489/article/details/129557959)


---




# 1 ✔        [剑指 Offer 22]链表中倒数第k个节点        Easy        2022-09-01        91

>//输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
//
// 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
//
//
//
// 示例：
//
//
//给定一个链表: 1->2->3->4->5, 和 k = 2.
//
//返回链表 4->5.
//
// Related Topics 链表 双指针 👍 447 👎 0


---



>自测代码

```java
public class P剑指Offer22_LianBiaoZhongDaoShuDiKgeJieDianLcof{
       public static void main(String[] args) {
              //测试代码
              Solution solution = new P剑指Offer22_LianBiaoZhongDaoShuDiKgeJieDianLcof().new Solution();
       }
       
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* public class ListNode {
*   int val;
*   ListNode next;
*   ListNode(int x) { val = x; }
* }
*/
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
                ListNode dummyHead = new ListNode(0, head);
                ListNode l = dummyHead.next;
                ListNode r = dummyHead;

                while (k >= 0){
                        k--;
                        r = r.next;
                }

                while (r != null){
                        r = r.next;
                        l = l.next;
                }

                return l;

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

}


```

> 提交代码

```java
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
                ListNode dummyHead = new ListNode(0, head);
                ListNode l = dummyHead.next;
                ListNode r = dummyHead;

                while (k >= 0){
                        k--;
                        r = r.next;
                }

                while (r != null){
                        r = r.next;
                        l = l.next;
                }

                return l;

        }
}
```

# 2 ✔        最小覆盖子串        Hard        2023-03-27        82

>//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
//
//
//
// 注意：
//
//
// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。
//
//
//
//
// 示例 1：
//
//
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
//解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
//
//
// 示例 2：
//
//
//输入：s = "a", t = "a"
//输出："a"
//解释：整个字符串 s 是最小覆盖子串。
//
//
// 示例 3:
//
//
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。
//
//
//
// 提示：
//
//
// m == s.length
// n == t.length
// 1 <= m, n <= 10⁵
// s 和 t 由英文字母组成
//
//
//
//进阶：你能设计一个在
//o(m+n) 时间内解决此问题的算法吗？
//
// Related Topics 哈希表 字符串 滑动窗口 &#128077; 2428 &#128078; 0


---

      /*疑惑点，通过控制两个指针分别缩小s的范围，但是一些特殊情况下，区分不出来，是删除左边好还是删除右边好*/
      /*解决方案：如果两边都可以删除，采用递归将两种情况都遍历出来，但是超时了*/

解决方案2： 在遍历s的时候，每次满足了所有t元素就遍历左指针，并记录最短的结果。


> 自测代码

```java
public class P76_MinimumWindowSubstring {
    public static void main(String[] args) {
      //测试代码
      Solution solution = new P76_MinimumWindowSubstring().new Solution();
      System.out.println(solution.minWindow("ADOBECODEBANC", "ABC"));
      /*疑惑点，通过控制两个指针分别缩小s的范围，但是一些特殊情况下，区分不出来，是删除左边好还是删除右边好*/
      /*解决方案：如果两边都可以删除，采用递归将两种情况都遍历出来，但是超时了*/
    }

    //力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
    class Solution {




      public String minWindow(String s, String t) {
            int tLen = t.length();
            HashMap<Character, Integer> data = new HashMap<>();
            for (char c : t.toCharArray()) {
                data.put(c, data.getOrDefault(c, 0) + 1);
            }

            LinkedList<Integer> res = new LinkedList<>();

            String resStr = "";
            int resLen = Integer.MAX_VALUE;

            for (int i = 0; i < s.length(); i++) {

                char c = s.charAt(i);
                if (data.containsKey(c)) {
                  tLen--;
                  res.addLast(i);
                  data.put(c, data.getOrDefault(c, 0) - 1);
                  if (data.get(c) < 0) {
                        tLen++;
                  }

                  if (tLen == 0) {
                        while (data.get(s.charAt(res.getFirst())) <= 0) {

                            if (data.get(s.charAt(res.getFirst())) == 0) {
                              if (resLen > res.getLast() - res.getFirst()+1) {
                                    resStr =s.substring(res.getFirst(), res.getLast() + 1);
                                    resLen = res.getLast() - res.getFirst()+1;
                              }
                              break;
                            }


                            if (data.get(s.charAt(res.getFirst())) < 0) {
                              Integer first = res.pollFirst();
                              data.put(s.charAt(first), data.getOrDefault(s.charAt(first), 0) + 1);
                              if (resLen > res.getLast() - res.getFirst()+1) {
                                    resStr =s.substring(res.getFirst(), res.getLast() + 1);
                                    resLen = res.getLast() - res.getFirst()+1;
                              }

                            }
                        }
                  }
                }


            }


            return resStr;



      }


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

}


```

>提交代码

```java
    class Solution {




      public String minWindow(String s, String t) {
            int tLen = t.length();
            HashMap<Character, Integer> data = new HashMap<>();
            for (char c : t.toCharArray()) {
                data.put(c, data.getOrDefault(c, 0) + 1);
            }

            LinkedList<Integer> res = new LinkedList<>();

            String resStr = "";
            int resLen = Integer.MAX_VALUE;

            for (int i = 0; i < s.length(); i++) {

                char c = s.charAt(i);
                if (data.containsKey(c)) {
                  tLen--;
                  res.addLast(i);
                  data.put(c, data.getOrDefault(c, 0) - 1);
                  if (data.get(c) < 0) {
                        tLen++;
                  }

                  if (tLen == 0) {
                        while (data.get(s.charAt(res.getFirst())) <= 0) {

                            if (data.get(s.charAt(res.getFirst())) == 0) {
                              if (resLen > res.getLast() - res.getFirst()+1) {
                                    resStr =s.substring(res.getFirst(), res.getLast() + 1);
                                    resLen = res.getLast() - res.getFirst()+1;
                              }
                              break;
                            }


                            if (data.get(s.charAt(res.getFirst())) < 0) {
                              Integer first = res.pollFirst();
                              data.put(s.charAt(first), data.getOrDefault(s.charAt(first), 0) + 1);
                              if (resLen > res.getLast() - res.getFirst()+1) {
                                    resStr =s.substring(res.getFirst(), res.getLast() + 1);
                                    resLen = res.getLast() - res.getFirst()+1;
                              }

                            }
                        }
                  }
                }


            }


            return resStr;



      }


    }
```


# 3 ✔        比较版本号        Medium        2023-03-20        80
>//给你两个版本号 version1 和 version2 ，请你比较它们。
//
// 版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编
//号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。
//
// 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。
//如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别
//为 0 和 1 ，0 < 1 。
//
// 返回规则如下：
//
//
// 如果 version1 > version2 返回 1，
// 如果 version1 < version2 返回 -1，
// 除此之外返回 0。
//
//
//
//
// 示例 1：
//
//
//输入：version1 = "1.01", version2 = "1.001"
//输出：0
//解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"
//
//
// 示例 2：
//
//
//输入：version1 = "1.0", version2 = "1.0.0"
//输出：0
//解释：version1 没有指定下标为 2 的修订号，即视为 "0"
//
//
// 示例 3：
//
//
//输入：version1 = "0.1", version2 = "1.1"
//输出：-1
//解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 <
//version2
//
//
//
//
// 提示：
//
//
// 1 <= version1.length, version2.length <= 500
// version1 和 version2 仅包含数字和 '.'
// version1 和 version2 都是 有效版本号
// version1 和 version2 的所有修订号都可以存储在 32 位整数 中
//
//
// Related Topics 双指针 字符串 &#128077; 360 &#128078; 0



---


>自测代码

```java
public class P165_CompareVersionNumbers{
       public static void main(String[] args) {
              //测试代码
              Solution solution = new P165_CompareVersionNumbers().new Solution();
                  solution.compareVersion("0.1","1.1");
       }
       
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int compareVersion(String version1, String version2) {

                String[] versionStr1 = version1.split("\\.");
                String[] versionStr2 = version2.split("\\.");

                int len1 = versionStr1.length;
                int len2 = versionStr2.length;

                int i1 = 0;
                int i2 = 0 ;

                while (i1 < len1 && i2 < len2){
                        int num1 = Integer.parseInt(versionStr1);
                        int num2 = Integer.parseInt(versionStr2);

                        if (num1 == num2) {
                                continue;
                        }

                        if (num1 > num2) {
                                return1;
                        }else {
                                return -1;
                        }
                }

                while (i1<len1){
                        int num1 = Integer.parseInt(versionStr1);
                        if (num1 > 0) {
                                return 1;
                        }
                }

                while (i2<len2){
                        int num2 = Integer.parseInt(versionStr2);
                        if (num2 > 0) {
                                return -1;
                        }
                }


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

}


```

> 提交代码

```java
class Solution {
    public int compareVersion(String version1, String version2) {

                String[] versionStr1 = version1.split("\\.");
                String[] versionStr2 = version2.split("\\.");

                int len1 = versionStr1.length;
                int len2 = versionStr2.length;

                int i1 = 0;
                int i2 = 0 ;

                while (i1 < len1 && i2 < len2){
                        int num1 = Integer.parseInt(versionStr1);
                        int num2 = Integer.parseInt(versionStr2);

                        if (num1 == num2) {
                                continue;
                        }

                        if (num1 > num2) {
                                return1;
                        }else {
                                return -1;
                        }
                }

                while (i1<len1){
                        int num1 = Integer.parseInt(versionStr1);
                        if (num1 > 0) {
                                return 1;
                        }
                }

                while (i2<len2){
                        int num2 = Integer.parseInt(versionStr2);
                        if (num2 > 0) {
                                return -1;
                        }
                }


                return 0;
        }
}
```

# 4 ✔        从前序与中序遍历序列构造二叉树        Medium        2022-10-10        80

>//给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并
//返回其根节点。
//
//
//
// 示例 1:
//
//
//输入: preorder = , inorder =
//输出:
//
//
// 示例 2:
//
//
//输入: preorder = [-1], inorder = [-1]
//输出: [-1]
//
//
//
//
// 提示:
//
//
// 1 <= preorder.length <= 3000
// inorder.length == preorder.length
// -3000 <= preorder, inorder <= 3000
// preorder 和 inorder 均 无重复 元素
// inorder 均出现在 preorder
// preorder 保证 为二叉树的前序遍历序列
// inorder 保证 为二叉树的中序遍历序列
//
//
// Related Topics 树 数组 哈希表 分治 二叉树 &#128077; 1922 &#128078; 0


---
          /*疑惑点： 用前序遍历确定顶点之后，遍历中序，得到所有在顶点左边的节点，但是左边的节点该怎么区分呢*/
          解决方法：利用递归不停的缩小每个节点的左节点数目和右节点数目，最终确定下来左节点的节点的左节点 从而确定下来整个树



>自测代码

```java
public class P105_ConstructBinaryTreeFromPreorderAndInorderTraversal{
       public static void main(String[] args) {
              //测试代码
              Solution solution = new P105_ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();
                  /*疑惑点： 用前序遍历确定顶点之后，遍历中序，得到所有在顶点左边的节点，但是左边的节点该怎么区分呢*/
       }
       
//力扣代码
//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 {

       Map<Integer, Integer> indexMap =new HashMap<Integer, Integer>();

        public TreeNode buildTree(int[] preorder, int[] inorder) {
                int len = preorder.length;
                for (int i = 0; i < len; i++) {
                        indexMap.put(inorder,i);
                }

                returnmyBuilTree(preorder,inorder,0,len-1,0,len-1);

        }

        private TreeNode myBuilTree(int[] preorder, int[] inorder, int i, int i1, int i2, int i3) {

                if (i > i1) {
                        return null;
                }

                int dummyTemp = preorder;
                TreeNode dummy = new TreeNode(dummyTemp);

                Integer midTemp = indexMap.get(dummyTemp);

                Integer leftSize = midTemp-i2;

                dummy.left = myBuilTree(preorder,inorder,i+1,i+leftSize,i2,midTemp-1);

                dummy.right = myBuilTree(preorder,inorder,i+leftSize+1,i1,midTemp+1,i3);

return dummy;
        }


}

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

}


```

> 提交代码

```java
class Solution {

       Map<Integer, Integer> indexMap =new HashMap<Integer, Integer>();

        public TreeNode buildTree(int[] preorder, int[] inorder) {
                int len = preorder.length;
                for (int i = 0; i < len; i++) {
                        indexMap.put(inorder,i);
                }

                returnmyBuilTree(preorder,inorder,0,len-1,0,len-1);

        }

        private TreeNode myBuilTree(int[] preorder, int[] inorder, int i, int i1, int i2, int i3) {

                if (i > i1) {
                        return null;
                }

                int dummyTemp = preorder;
                TreeNode dummy = new TreeNode(dummyTemp);

                Integer midTemp = indexMap.get(dummyTemp);

                Integer leftSize = midTemp-i2;

                dummy.left = myBuilTree(preorder,inorder,i+1,i+leftSize,i2,midTemp-1);

                dummy.right = myBuilTree(preorder,inorder,i+leftSize+1,i1,midTemp+1,i3);

return dummy;
        }


}
```


# 5 ✔        最长有效括号        Hard        2023-04-05        79

>//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
//
//
//
//
//
// 示例 1：
//
//
//
//
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
//
//
// 示例 2：
//
//
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
//
//
// 示例 3：
//
//
//输入：s = ""
//输出：0
//
//
//
//
// 提示：
//
//
// 0 <= s.length <= 3 * 10⁴
// s 为 '(' 或 ')'
//
//
// Related Topics 栈 字符串 动态规划 &#128077; 2226 &#128078; 0



---
               /*疑惑点：通过两个for循环，当左右指针，通过二维数组记录已经确定的值，但是当遇到多个值一组的时候就难以实现记录了"()(())"*/
               /*通过LinkList两边添加修改两个不相同的for从前到后，从后到前，但是超时了*/
解决方案：通过栈，只插入“（” 括号，遇到“）”括号就删除栈中的“（”括号，并插入已经删除的数量。每次都计算一下删除的数量


>自测代码

```java
public class P32_LongestValidParentheses{
       public static void main(String[] args) {
              //测试代码
              Solution solution = new P32_LongestValidParentheses().new Solution();
               System.out.println(solution.longestValidParentheses(")()())"));
               /*疑惑点：通过两个for循环，当左右指针，通过二维数组记录已经确定的值，但是当遇到多个值一组的时候就难以实现记录了"()(())"*/
               /*通过LinkList两边添加修改两个不相同的for从前到后，从后到前，但是超时了*/

       }
       
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestValidParentheses(String s) {
                char[] sChar = s.toCharArray();
                HashMap<Integer, Character> map = new HashMap<>();
                for (int i = 0; i < sChar.length; i++) {
                        map.put(i,sChar);
                }
                int res = 0;

                int l = 0 ;
                int r = 0 ;
                Stack<String> data = new Stack<>();

                for (int i = 0; i < s.length(); i++) {
                        char c = s.charAt(i);

                        int resTemp = 0;
                        while (!data.empty() && data.peek() != "(" ) {
                                String pop = data.pop();
                                resTemp += Integer.parseInt(pop);
                        }
                        res = Math.max(resTemp,res);
                        if (c == '(') {
                                data.push(String.valueOf(resTemp) );
                                data.push("(");
                        }else if (!data.empty() && data.peek() == "("){
                                                String pop = data.pop();
                                                resTemp += 2;
                                res = Math.max(resTemp,res);
                                data.push(String.valueOf(resTemp) );
                                        }
                }

                int resTemp = 0;
                while (!data.empty() && data.peek() != "(" ) {
                        String pop = data.pop();
                        resTemp += Integer.parseInt(pop);
                }
                res = Math.max(resTemp,res);
                return res;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}

```

> 提交代码

```java
class Solution {
    public int longestValidParentheses(String s) {
                char[] sChar = s.toCharArray();
                HashMap<Integer, Character> map = new HashMap<>();
                for (int i = 0; i < sChar.length; i++) {
                        map.put(i,sChar);
                }
                int res = 0;

                int l = 0 ;
                int r = 0 ;
                Stack<String> data = new Stack<>();

                for (int i = 0; i < s.length(); i++) {
                        char c = s.charAt(i);

                        int resTemp = 0;
                        while (!data.empty() && data.peek() != "(" ) {
                                String pop = data.pop();
                                resTemp += Integer.parseInt(pop);
                        }
                        res = Math.max(resTemp,res);
                        if (c == '(') {
                                data.push(String.valueOf(resTemp) );
                                data.push("(");
                        }else if (!data.empty() && data.peek() == "("){
                                                String pop = data.pop();
                                                resTemp += 2;
                                res = Math.max(resTemp,res);
                                data.push(String.valueOf(resTemp) );
                                        }
                }

                int resTemp = 0;
                while (!data.empty() && data.peek() != "(" ) {
                        String pop = data.pop();
                        resTemp += Integer.parseInt(pop);
                }
                res = Math.max(resTemp,res);
                return res;
        }
}
```


# 6 ✔        翻转字符串里的单词        Medium        2023-02-09        79

>//给你一个字符串 s ，请你反转字符串中 单词 的顺序。
//
// 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
//
// 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
//
// 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
//
//
//
// 示例 1：
//
//
//输入：s = "the sky is blue"
//输出："blue is sky the"
//
//
// 示例 2：
//
//
//输入：s = "hello world"
//输出："world hello"
//解释：反转后的字符串中不能存在前导空格和尾随空格。
//
//
// 示例 3：
//
//
//输入：s = "a good   example"
//输出："example good a"
//解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 10⁴
// s 包含英文大小写字母、数字和空格 ' '
// s 中 至少存在一个 单词
//
//
//
//
//
//
//
// 进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
//
// Related Topics 双指针 字符串 &#128077; 823 &#128078; 0


---


>自测代码

```java
public class P151_ReverseWordsInAString{
       public static void main(String[] args) {
              //测试代码
              Solution solution = new P151_ReverseWordsInAString().new Solution();
               System.out.println(solution.reverseWords("the sky is blue"));
       }
       
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String reverseWords(String s) {
                s = s.trim();

                List<String> words = Arrays.asList(s.split("\\s+"));
                Collections.reverse(words);

                return String.join(" ", words);


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

}


```

> 提交代码

```java
class Solution {
    public String reverseWords(String s) {
                s = s.trim();

                List<String> words = Arrays.asList(s.split("\\s+"));
                Collections.reverse(words);

                return String.join(" ", words);


        }
}
```

查看完整版本: leetCode热题52-57 解题代码，调试代码和思路