这是我参与11月更文挑战的第19天,活动详情查看:2021最后一次更文挑战
今日题目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%的用户
小结
这两道题都相对比较简单,只要合理的利用数据结构的特点,花点时间做出来还是不难的。
近期评论