文章目錄

• 20. 題目描述 & 解題
• 21. 題目描述 & 解題
• • • 1. 一開始的寫法
    • 2. 參考大佬的寫法

兩道簡單類型連著，就直接一起寫了。

20. 題目描述 & 解題

• 括號題是真挺煩人的。。。
• 經典題目了，在學數據結構到棧的時候也會寫到類似的題目
• 其實主要就是：后入的左括號，要先遇到對應的右括號（就很符合棧）
  
• 左括號直接入棧
• 右括號和pop的左括號匹配：不同則false
• 結束后棧不是空的情況：說明括號數量不匹配，false

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();// 時間復雜度 O(n)for (char ch : s.toCharArray()) {// 左括號直接入if (ch == '(' || ch == '[' || ch == '{') {// 空間復雜度O(n)stack.push(ch);}else {// 先出現右括號的情況if(stack.empty())return false;char left = stack.pop();switch (left){// 三種右括號未能正確對應左括號的情況case '(':{if(ch!=')'){return false;}break;}case '[':{if(ch!=']'){return false;}break;}case '{':{if(ch!='}'){return false;}break;}default:break;}}}if(stack.empty()){return true; }// 括號數量對不齊的情況return false;} }

• 時間復雜度 O(n)：就是遍歷一遍括號集合
• 空間復雜度 O(n)：括號集合納入棧中

21. 題目描述 & 解題

• 記得考慮鏈表空的情況
  

1. 一開始的寫法

/*** 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 l1, ListNode l2) {// 有鏈表為空的情況if(l1==null)return l2;if(l2==null)return l1;ListNode l3 = new ListNode();ListNode l1n = l1, l2n = l2, l3n = l3;// 遍歷兩條鏈表，時間復雜度O(m+n)// 空間復雜度O(m+n);while(l1n!=null || l2n!=null){if(l2n.val > l1n.val){l3n.val = l1n.val;l1n = l1n.next;}else{l3n.val = l2n.val;l2n = l2n.next;}// 跑完某個鏈表的情況，直接連上另外一條。if(l2n==null){l3n.next = l1n;break;}if(l1n==null){l3n.next = l2n;break;}ListNode newNode = new ListNode();l3n.next = newNode;l3n = l3n.next;}return l3;} }

• 遍歷兩條鏈表，時間復雜度O(m+n)
• 空間復雜度O(m+n)

2. 參考大佬的寫法

就很巧妙，又快又好

• 應該是分治？遞歸得很巧妙。

/*** 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 l1, ListNode l2) {// 有鏈表為空的情況if(l1==null)return l2;if(l2==null)return l1;// 一層遞歸加一個結點// 復雜度為O(m+n)，歸根結底還是要遍歷每個結點// 空間復雜度O(1)，根本不用額外空間= =else if(l1.val < l2.val){l1.next = mergeTwoLists(l1.next,l2);return l1;}else{l2.next = mergeTwoLists(l2.next,l1);return l2;}} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】20.有效的括号（Java、栈） 21. 合并两个有序链表（Java）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。