记录于2019年5月22日
文章目录
[20. 有效的括号](https://leetcode.com/problems/valid-parentheses/)① 题目描述② 使用堆栈（Stack）
[21. 合并两个有序链表](https://leetcode.com/problems/merge-two-sorted-lists/)① 题目描述② 借助新的链表头
[22. 括号生成](https://leetcode.com/problems/generate-parentheses/)① 题目描述② 回溯法③ 暴力法
[23. 合并K个排序链表](https://leetcode.com/problems/merge-k-sorted-lists/)① 题目描述② 自己的笨办法③ 一列一列的比较（效果好像比自己的笨办法差很多）④ 使用优先队列（掌握优先队列的定义）
20. 有效的括号
① 题目描述
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。示例 1:
输入: “()” 输出: true
示例 2:
输入: “()[]{}” 输出: true
示例 3:
输入: “(]” 输出: false
示例 4:
输入: “([)]” 输出: false
示例 5:
输入: “{[]}” 输出: true
② 使用堆栈（Stack）
括号配对问题，典型的方法——使用stack。当stack为empty时，将括号压入stack；当栈顶和当前待扫描括号配对时，弹出栈顶的括号；如果都不满足直接压入stack，比如({[。时间复杂度：O(n)，因为我们一次只遍历给定的字符串中的一个字符并在栈上进行 O(1) 的推入和弹出操作。空间复杂度：O(n)，当我们将所有的开括号都推到栈上时以及在最糟糕的情况下，我们最终要把所有括号推到栈上。例如 ((((((((((。代码如下：
public boolean isValid(String s
) {
int len
= s
.length();
if (len
== 0) {
return true;
}
if (len
% 2 != 0) {
return false;
}
Stack
<Character> stack
= new Stack<>();
for (int i
= 0; i
< len
; i
++) {
if (stack
.isEmpty()) {
stack
.push(s
.charAt(i
));
} else {
if (stack
.peek() == '(' && s
.charAt(i
) == ')') {
stack
.pop();
} else if (stack
.peek() == '[' && s
.charAt(i
) == ']') {
stack
.pop();
} else if (stack
.peek() == '{' && s
.charAt(i
) == '}') {
stack
.pop();
} else {
stack
.push(s
.charAt(i
));
}
}
}
if (stack
.isEmpty()) {
return true;
}
return false;
}
21. 合并两个有序链表
① 题目描述
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
② 借助新的链表头
通过比较l1和l2的val，决定是将l1加入新的链表，还是将l2加入新的链表，并且更新l1或l2的指针。注意特殊情况： ① l1或l2为null，直接返回另一条链表； ② 完成合并后，总有一条链表不在末尾，直接将其加入新的链表即可。
public ListNode
mergeTwoLists(ListNode l1
, ListNode l2
) {
if (l1
== null
) {
return l2
;
}
if (l2
== null
) {
return l1
;
}
ListNode result
= new ListNode(0);
ListNode cur
= result
;
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
;
}
if (l1
!= null
) {
cur
.next
= l1
;
} else {
cur
.next
= l2
;
}
return result
.next
;
}
22. 括号生成
① 题目描述
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。例如，给出 n = 3，生成结果为：
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
② 回溯法
public List
<String> generateParenthesis(int n
) {
List
<String> result
= new ArrayList<>();
if (n
== 0) {
return result
;
}
helper(result
, "", 0, 0, n
);
return result
;
}
public void helper(List
<String> result
, String s
, int open
, int close
, int n
) {
if (s
.length() == n
* 2) {
result
.add(s
);
return;
}
if (open
< n
) {
helper(result
, s
+ "(", open
+ 1, close
, n
);
}
if (open
> close
) {
helper(result
, s
+ ")", open
, close
+ 1, n
);
}
}
③ 暴力法
public List
<String> generateParenthesis(int n
) {
List
<String> result
= new ArrayList<>();
if (n
== 0) {
return result
;
}
helper(result
, "", n
);
return result
;
}
public void helper(List
<String> result
, String s
, int n
) {
if (s
.length() == n
* 2) {
if (isTrue(s
)) {
result
.add(s
);
}
return;
}
helper(result
, s
+ "(", n
);
helper(result
, s
+ ")", n
);
}
public boolean isTrue(String s
) {
int count
= 0;
for (int i
= 0; i
< s
.length(); i
++) {
if (s
.charAt(i
) == '(') {
count
++;
} else {
count
--;
}
if (count
< 0) {
return false;
}
}
return count
== 0;
}
23. 合并K个排序链表
① 题目描述
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例:
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
② 自己的笨办法
先获取所有排序链表的节点值，重新排序后将其存入新的链表中。巧用List和Collections.sort()，实现快速从新排序。代码如下：
public ListNode
mergeKLists(ListNode
[] lists
) {
ListNode result
= new ListNode(0);
ListNode cur
= reuslt
;
if (lists
.length
== 1) {
return lists
[0];
}
List
<Integer> arr
= new ArrayList<>();
for (int i
= 0; i
< lists
.length
; i
++) {
ListNode p
= lists
[i
];
while (p
!= null
) {
arr
.add(p
.val
);
p
= p
.next
;
}
}
Collections
.sort(arr
);
for (int i
= 0; i
< arr
.size(); i
++) {
ListNode node
= new ListNode(arr
.get(i
));
cur
.next
= node
;
cur
= cur
.next
;
}
cur
.next
= null
;
return result
.next
;
}
③ 一列一列的比较（效果好像比自己的笨办法差很多）
将所有的链表对齐，一列一列的查找当前列的最小值，直到所有链表均为null。示意图如下： 代码如下：
public ListNode
mergeKLists(ListNode
[] lists
) {
ListNode result
= new ListNode(0);
ListNode cur
= reuslt
;
if (lists
.length
== 1) {
return lists
[0];
}
while (true) {
int min
= Integer
.MAX_VALUE
;
int min_index
= 0;
boolean flag
= true;
for (int i
= 0; i
< lists
.length
; i
++) {
if (lists
[i
] != null
) {
if (lists
[i
].val
< min
) {
min
= lists
[i
].val
;
min_index
= i
;
}
flag
= false;
}
}
if (flag
) {
break;
}
cur
.next
= lists
[min_index
];
cur
= cur
.next
;
lists
[min_index
] = lists
[min_index
].next
;
}
cur
.next
= null
;
return result
.next
;
}
④ 使用优先队列（掌握优先队列的定义）
通过自定义比较器，实现针对ListNode的优先队列。整体思想与一列一列的比较一样的，只是将比较过程交给了优先队列自己完成。
Queue
<ListNode> q
= new PriorityQueue<ListNode>(cmp
);
注意链表的特殊性，看起来队列中存储的是一个节点，其实他存储的是整条链表。初始化优先队列时，一定不要忘记判断lists[i]是否为null！
Comparator
<ListNode> cmp
= new Comparator<ListNode>() {
@Override
public int compare(ListNode o1
, ListNode o2
) {
return o1
.val
- o2
.val
;
}
};
public ListNode
mergeKLists(ListNode
[] lists
) {
ListNode result
= new ListNode(0);
ListNode cur
= result
;
if (lists
.length
== 1) {
return lists
[0];
}
Queue
<ListNode> q
= new PriorityQueue<ListNode>(cmp
);
for (int i
= 0; i
< lists
.length
; i
++) {
if (lists
[i
] != null
) {
q
.add(lists
[i
]);
}
}
while (!q
.isEmpty()) {
cur
.next
= q
.poll();
cur
= cur
.next
;
if (cur
.next
!= null
) {
q
.add(cur
.next
);
}
}
cur
.next
= null
;
return result
.next
;
}
