免费中英文网站源码,品牌建设 ,网站网站弹出窗口去掉,秦皇岛黄金海岸旅游景点文章目录20. 题目描述 解题21. 题目描述 解题1. 一开始的写法2. 参考大佬的写法两道简单类型连着#xff0c;就直接一起写了。 20. 题目描述 解题
括号题是真挺烦人的。。。经典题目了#xff0c;在学数据结构到栈的时候也会写到类似的题目其实主要就是 解题21. 题目描述 解题1. 一开始的写法2. 参考大佬的写法两道简单类型连着就直接一起写了。 20. 题目描述 解题
括号题是真挺烦人的。。。经典题目了在学数据结构到栈的时候也会写到类似的题目其实主要就是后入的左括号要先遇到对应的右括号就很符合栈 左括号直接入栈右括号和pop的左括号匹配不同则false结束后栈不是空的情况说明括号数量不匹配false
class Solution {public boolean isValid(String s) {StackCharacter 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(l1null)return l2;if(l2null)return l1;ListNode l3 new ListNode();ListNode l1n l1, l2n l2, l3n l3;// 遍历两条链表时间复杂度O(mn)// 空间复杂度O(mn);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(l2nnull){l3n.next l1n;break;}if(l1nnull){l3n.next l2n;break;}ListNode newNode new ListNode();l3n.next newNode;l3n l3n.next;}return l3;}
}遍历两条链表时间复杂度O(mn)空间复杂度O(mn)
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(l1null)return l2;if(l2null)return l1;// 一层递归加一个结点// 复杂度为O(mn)归根结底还是要遍历每个结点// 空间复杂度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;}}
}
