今日题目1
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
两个链表的节点数目范围是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列
思路
这道题相对比较简单，链表相关的操作一般首先考虑递归
- 首先对l1和l2进行判空，否则直接返回非空的list
- 然后循环遍历两个链表，对于两个链表中较小的节点，加到新链表去，同时该链表后移一位
- 当有一条链表遍历结束后，若另一条链表还有剩余，将其加入新链表
- 最后比较两个链表的表头大小，返回小的那个表头指针
代码实现
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null) { return l2; } if(l2 == null) { return l1; } if(l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } }
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38 MB, 在所有 Java 提交中击败了8.37%的用户
其他解法
能用递归解决的问题肯定能用迭代的方式解决，递归方式占用空间比较大，代码结构清晰
迭代则相反，结构稍显复杂
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null){ return l2; } if (l2 == null){ return l1; } ListNode head = new ListNode(); ListNode cuur = head; while (l1 != null && l2 != null) { if (l1.val < l2.val) { cuur.next = l1; l1 = l1.next; } else { cuur.next = l2; l2 = l2.next; } cuur = cuur.next; } if (l1 == null) { cuur.next = l2; } if (l2 == null) { cuur.next = l1; } return head.next; }
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.6 MB, 在所有 Java 提交中击败了85.34%的用户
今日题目2
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}" 输出：true
示例 3：
输入：s = "(]" 输出：false
示例 4：
输入：s = "([)]" 输出：false
示例 5：
输入：s = "{[]}" 输出：true
提示：
1 <= s.length <= 104 s 仅由括号 '()[]{}' 组成
思路
这道题会使用计算机常用的一种数据结构： 栈
利用栈的压栈、出栈操作，来实现括号的配对
- 首选判断字符长度必须为偶数，奇数肯定不能配对的
- 从左向右依次遍历字符串的每一个字符
- 如果字符是左括号，则存入栈中，等待配对的右括号；
- 如果是右括号，先判断此时栈是否为空。如果是空的，则右括号无法消除，返回false；如果栈不是空的，再将此字符于栈顶元素进行比较，判断是否符合条件。
- 当遍历完所有字符元素，判断栈是否为空。如果是空，说明所有括号配对成功，反之不成功
public boolean isValid(String s) { int n = s.length(); if (n % 2 != 0) { return false; } Stack<Character> stack = new Stack<>(); char[] c = s.toCharArray(); for (int i=0;i<n;i++) { if (c[i] == '(') { stack.push(')'); } else if (c[i] == '[') { stack.push(']'); } else if (c[i] == '{'){ stack.push('}'); } else if (stack.isEmpty() || c[i] != stack.pop()) { return false; } } return stack.isEmpty(); }
执行用时：1 ms, 在所有 Java 提交中击败了98.88%的用户
内存消耗：36.7 MB, 在所有 Java 提交中击败了18.45%的用户
小结
这两道题都相对比较简单，只要合理的利用数据结构的特点，花点时间做出来还是不难的
