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/