Java每日一练(20230401) 合并K个升序链表、最长有效括号、分割回文串

简介: Java每日一练(20230401) 合并K个升序链表、最长有效括号、分割回文串

1. 合并K个升序链表

给你一个链表数组,每个链表都已经按升序排列

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]

输出:[1,1,2,3,4,4,5,6]

解释:链表数组如下:[1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到 1->1->2->3->4->4->5->6

示例 2:

输入:lists = []

输出:[]

示例 3:

输入:lists = [[]]

输出:[]


提示:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i]升序 排列
  • lists[i].length 的总和不超过 10^4

以下程序实现了这一功能,请你填补空白处内容:

```Java
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 mergeKLists(ListNode[] lists) {
        if (lists.length == 0)
            return null;
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int low, int high) {
        if (high - low == 0)
            return lists[low];
        else if (high - low == 1)
            return mergeTwoLists(lists[low], lists[high]);
        else {
            int mid = (low + high) / 2;
            _____________________________;
            return mergeTwoLists(tmp1, tmp2);
        }
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode p = head;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                p.next = l2;
                l2 = l2.next;
                p = p.next;
            } else {
                p.next = l1;
                l1 = l1.next;
                p = p.next;
            }
        }
        if (l1 != null)
            p.next = l1;
        if (l2 != null)
            p.next = l2;
        return head.next;
    }
}
```

出处:

https://edu.csdn.net/practice/24394311

代码:

public class mergeKLists {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public static class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0)
                return null;
            return merge(lists, 0, lists.length - 1);
        }
        public ListNode merge(ListNode[] lists, int low, int high) {
            if (low == high)
                return lists[low];
            int mid = low + (high - low) / 2;
            ListNode l1 = merge(lists, low, mid);
            ListNode l2 = merge(lists, mid + 1, high);
            return mergeTwoLists(l1, l2);
        }
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(-1);
            ListNode cur = dummy;
            while (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    cur.next = l1;
                    l1 = l1.next;
                } else {
                    cur.next = l2;
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            cur.next = l1 != null ? l1 : l2;
            return dummy.next;
        }
    }
    public static ListNode[] arraysToLists(int[][] nums) {
        ListNode[] lists = new ListNode[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int[] arr = nums[i];
            ListNode head = new ListNode(0);
            ListNode cur = head;
            for (int num : arr) {
                cur.next = new ListNode(num);
                cur = cur.next;
            }
            lists[i] = head.next;
        }
        return lists;
    }
    public static void traverseList(ListNode head) {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        System.out.print("[");
        for (cur = head; cur != null; cur = cur.next) {
            if (--count>0)
                System.out.print(cur.val + ",");
            else
                System.out.print(cur.val);
        }
        System.out.println("]");
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] lists = {{1,4,5},{1,3,4},{2,6}};
        ListNode[] nodelists = arraysToLists(lists);
        traverseList(s.mergeKLists(nodelists));
    }
}

输出:

[1,1,2,3,4,4,5,6]


2. 最长有效括号

给你一个只包含 '('')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

示例 1:

输入:s = "(()"

输出:2

解释:最长有效括号子串是 "()"

示例 2:

输入:s = ")()())"

输出:4

解释:最长有效括号子串是 "()()"

示例 3:

输入:s = ""

输出:0


提示:

  • 0 <= s.length <= 3 * 10^4
  • s[i]'('')'

以下程序实现了这一功能,请你填补空白处内容:

```Java
import java.util.*;
class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(')
                left++;
            else
                right++;
            if (left == right)
                max = Math.max(max, left * 2);
            if (right > left)
                left = right = 0;
        }
        left = 0;
        right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            __________________;
            if (left == right)
                max = Math.max(max, left * 2);
            if (right < left)
                left = right = 0;
        }
        return max;
    }
}
```

出处:

https://edu.csdn.net/practice/24394312

代码:

import java.util.*;
public class longestValidParentheses {
    public static class Solution {
        public int longestValidParentheses(String s) {
            int left = 0, right = 0, max = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(')
                    left++;
                else
                    right++;
                if (left == right)
                    max = Math.max(max, left * 2);
                if (right > left)
                    left = right = 0;
            }
            left = 0;
            right = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                if (s.charAt(i) == '(')
                    left++;
                else
                    right++;
                if (left == right)
                    max = Math.max(max, left * 2);
                if (right < left)
                    left = right = 0;
            }
            return max;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestValidParentheses("(()"));
        System.out.println(s.longestValidParentheses(")()()"));
        System.out.println(s.longestValidParentheses(""));
    }
}

输出:

2

4

0


3. 分割回文串

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1:

输入:s = "aab"

输出:[["a","a","b"],["aa","b"]]


示例 2:

输入:s = "a"

输出:[["a"]]


提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

出处:

https://edu.csdn.net/practice/24394313

代码:

import java.util.*;
public class partition {
    public static class Solution {
        public List<List<String>> partition(String s) {
            boolean[][] dp = new boolean[s.length()][s.length()];
            for (int len = 1; len <= s.length(); len++) {
                for (int i = 0; i <= s.length() - len; i++) {
                    if (len == 1)
                        dp[i][i] = true;
                    else if (s.charAt(i) == s.charAt(i + len - 1) && (len == 2 || dp[i + 1][i + len - 2])) {
                        dp[i][i + len - 1] = true;
                    }
                }
            }
            return solution(s, 0, dp);
        }
        public List<List<String>> solution(String s, int start, boolean[][] dp) {
            ArrayList<List<String>> list = new ArrayList<>();
            if (start == s.length()) {
                List<String> li = new ArrayList<>();
                list.add(li);
                return list;
            }
            for (int i = start; i < s.length(); i++) {
                if (dp[start][i]) {
                    String first = s.substring(start, i + 1);
                    for (List<String> li : solution(s, i + 1, dp)) {
                        li.add(0, first);
                        list.add(li);
                    }
                }
            }
            return list;
        }
    }
    public static void showStringLists(List<List<String>> lists){
        int size_lists = lists.size();
        System.out.print("[");
        for (List<String> innerList : lists) {
            int size_inner = innerList.size();
            System.out.print("[\"");
            for (String str : innerList) {
                System.out.print(str);
                if (--size_inner>0)
                    System.out.print("\",\"");
            }
            System.out.print("\"]");
            if (--size_lists>0)
                System.out.print(", ");
        }
        System.out.println("]");       
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        showStringLists(s.partition("aab"));
    }
}

输出:

[["a","a","b"], ["aa","b"]]


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/


目录
相关文章
|
26天前
|
算法
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
30 0
|
2月前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
29天前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
22 3
|
3月前
|
算法
LeetCode第23题合并 K 个升序链表
这篇文章介绍了LeetCode第23题"合并K个升序链表"的解题方法,使用分而治之的思想,通过递归合并链表的方式解决了这个难题。
LeetCode第23题合并 K 个升序链表
|
3月前
|
存储 Java
|
3月前
|
Java
Java系列之:字符串的截取及分割 split() 和 substring()
这篇文章通过示例代码讲解了Java中字符串的截取和分割操作,包括使用`split()`方法根据正则表达式进行字符串分割以及使用`substring()`方法进行字符串截取的不同使用方式及其输出结果。
Java系列之:字符串的截取及分割 split() 和 substring()
|
3月前
|
存储 Java API
|
3月前
|
存储 Java 开发者
揭秘!HashMap底层结构大起底:从数组到链表,再到红黑树,Java性能优化的秘密武器!
【8月更文挑战第24天】HashMap是Java集合框架中的核心组件,以其高效的键值对存储和快速访问能力广受开发者欢迎。在JDK 1.8及以后版本中,HashMap采用了数组+链表+红黑树的混合结构,实现了高性能的同时解决了哈希冲突问题。数组作为基石确保了快速定位;链表则用于处理哈希冲突;而当链表长度达到一定阈值时,通过转换为红黑树进一步提升性能。此外,HashMap还具备动态扩容机制,当负载因子超过预设值时自动扩大容量并重新哈希,确保整体性能。通过对HashMap底层结构的深入了解,我们可以更好地利用其优势解决实际开发中的问题。
96 0
|
3月前
|
存储 算法 Python
【面试题】合井K个升序链表
【面试题】合井K个升序链表
35 0
|
3月前
|
存储 Java
【Java集合类面试十】、HashMap中的循环链表是如何产生的?
在多线程环境下,HashMap在扩容时如果发生条件竞争,元素的插入顺序可能形成循环链表,导致死循环。