前言
本文属于特定的六道题目题解和调试代码。
1 ✔ [剑指 Offer 22]链表中倒数第k个节点 Easy 2022-09-01 91
2 ✔ [76]最小覆盖子串 Hard 2023-03-27 82
3 ✔ [165]比较版本号 Medium 2023-03-20 80
4 ✔ [105]从前序与中序遍历序列构造二叉树 Medium 2022-10-10 80
5 ✔ [32]最长有效括号 Hard 2023-04-05 79
6 ✔ [151]翻转字符串里的单词 Medium 2023-02-09 79
正所谓磨刀不误砍柴功，下面这几篇文章算是我用idea刷题的经验帖，对涉及的题型，数据结构的快速构建分析和解决很有帮助，这里放个链接仅供参考。
如何调试递归程序，有何技巧？
按照树形结构直观地打印出一棵二叉树、快速创建leetcode中树的结构(Java)
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
自测代码
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)
}
提交代码
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 ✔ [76]最小覆盖子串 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 哈希表 字符串 滑动窗口 👍 2428 👎 0
/*疑惑点，通过控制两个指针分别缩小s的范围，但是一些特殊情况下，区分不出来，是删除左边好还是删除右边好*/
/*解决方案：如果两边都可以删除，采用递归将两种情况都遍历出来，但是超时了*/
解决方案2： 在遍历s的时候，每次满足了所有t元素就遍历左指针，并记录最短的结果。
自测代码
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)
}
提交代码
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 ✔ [165]比较版本号 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 双指针 字符串 👍 360 👎 0
自测代码
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[i1++]);
int num2 = Integer.parseInt(versionStr2[i2++]);
if (num1 == num2) {
continue;
}
if (num1 > num2) {
return 1;
}else {
return -1;
}
}
while (i1<len1){
int num1 = Integer.parseInt(versionStr1[i1++]);
if (num1 > 0) {
return 1;
}
}
while (i2<len2){
int num2 = Integer.parseInt(versionStr2[i2++]);
if (num2 > 0) {
return -1;
}
}
return 0;
}
}
//leetcode submit region end(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[i1++]);
int num2 = Integer.parseInt(versionStr2[i2++]);
if (num1 == num2) {
continue;
}
if (num1 > num2) {
return 1;
}else {
return -1;
}
}
while (i1<len1){
int num1 = Integer.parseInt(versionStr1[i1++]);
if (num1 > 0) {
return 1;
}
}
while (i2<len2){
int num2 = Integer.parseInt(versionStr2[i2++]);
if (num2 > 0) {
return -1;
}
}
return 0;
}
}
4 ✔ [105]从前序与中序遍历序列构造二叉树 Medium 2022-10-10 80
//给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并
//返回其根节点。
//
//
//
// 示例 1:
//
//
//输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//输出: [3,9,20,null,null,15,7]
//
//
// 示例 2:
//
//
//输入: preorder = [-1], inorder = [-1]
//输出: [-1]
//
//
//
//
// 提示:
//
//
// 1 <= preorder.length <= 3000
// inorder.length == preorder.length
// -3000 <= preorder[i], inorder[i] <= 3000
// preorder 和 inorder 均 无重复 元素
// inorder 均出现在 preorder
// preorder 保证 为二叉树的前序遍历序列
// inorder 保证 为二叉树的中序遍历序列
//
//
// Related Topics 树 数组 哈希表 分治 二叉树 👍 1922 👎 0
/*疑惑点： 用前序遍历确定顶点之后，遍历中序，得到所有在顶点左边的节点，但是左边的节点该怎么区分呢*/
解决方法：利用递归不停的缩小每个节点的左节点数目和右节点数目，最终确定下来左节点的节点的左节点 从而确定下来整个树
自测代码
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],i);
}
return myBuilTree(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[i];
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)
}
提交代码
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],i);
}
return myBuilTree(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[i];
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 ✔ [32]最长有效括号 Hard 2023-04-05 79
//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
//
//
//
//
//
// 示例 1：
//
//
//
//
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
//
//
// 示例 2：
//
//
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
//
//
// 示例 3：
//
//
//输入：s = ""
//输出：0
//
//
//
//
// 提示：
//
//
// 0 <= s.length <= 3 * 10⁴
// s[i] 为 '(' 或 ')'
//
//
// Related Topics 栈 字符串 动态规划 👍 2226 👎 0
/*疑惑点：通过两个for循环，当左右指针，通过二维数组记录已经确定的值，但是当遇到多个值一组的时候就难以实现记录了"()(())"*/
/*通过LinkList两边添加修改 两个不相同的for从前到后，从后到前，但是超时了*/
解决方案：通过栈，只插入“（” 括号，遇到“）”括号就删除栈中的“（”括号，并插入已经删除的数量。每次都计算一下删除的数量
自测代码
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[i]);
}
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)
}
提交代码
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[i]);
}
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 ✔ [151]翻转字符串里的单词 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 双指针 字符串 👍 823 👎 0
自测代码
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)
}
提交代码
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);
}
}
发表于 2024-2-6 14:15
