1.有效的括号（20题）
这题利用栈解决
这题最初我打算用hashmap试一下，发现不好实现，残不忍睹。
不过也有收获，就是hashmap是会造成空指针异常的。
还有就是在对数组操作的时候，很容易造成数组越界，一定要注意判断。
算了还是老老实实用栈实现了。
//(这段就不要看了，逻辑操作什么都出了问题)
public boolean isValid(String s) {
if(s.isEmpty()) return true;
Map<Character, Character> map = new HashMap<>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
map.put(')', ')');
map.put('}', ']');
map.put(']', '}');
char[] chars = new char[s.length()];
for (int i = 0; i < chars.length; i++) {
chars[i] = '0';
}
//System.out.println(chars.length);
chars[0] = s.charAt(0);
for (int i = 1; i < s.length(); i++) {
if(s.charAt(i) == map.get(chars[i - 1])) {
chars[i] = '0';
chars[i - 1] = '0';
if(i + 1 < s.length()){
chars[i + 1] = s.charAt(i + 1);
i++;
}
}else{
chars[i] = s.charAt(i);
}
}
for (int i = 0; i < s.length(); i++) {
while(chars[i] != '0') return false;
}
return true;
}
//这里利用了栈+HashMap
public boolean isValid(String s) {
Map<Character, Character> map = new HashMap<>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if(map.containsValue(s.charAt(i))){
if(stack.empty()) return false;
char c = stack.pop();
if(map.get(c) == s.charAt(i)){
}else{
return false;
}
}else{
stack.push(s.charAt(i));
}
}
if(stack.empty())
return true;
else return false;
}
//官方
class Solution {
// Hash table that takes care of the mappings.
private HashMap<Character, Character> mappings;
// Initialize hash map with mappings. This simply makes the code easier to read.
public Solution() {
this.mappings = new HashMap<Character, Character>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
public boolean isValid(String s) {
// Initialize a stack to be used in the algorithm.
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// If the current character is a closing bracket.
if (this.mappings.containsKey(c)) {
// Get the top element of the stack. If the stack is empty, set a dummy value of '#'
char topElement = stack.empty() ? '#' : stack.pop();
// If the mapping for this bracket doesn't match the stack's top element, return false.
if (topElement != this.mappings.get(c)) {
return false;
}
} else {
// If it was an opening bracket, push to the stack.
stack.push(c);
}
}
// If the stack still contains elements, then it is an invalid expression.
return stack.isEmpty();
}
}
//作者：LeetCode
2.合并两个有序链表
首先对链表的操作很陌生
其次不太理解
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
}
}
通过学习官方给出的解析做出解答，不过还是有考虑不充分的情况
就是当某一个单链表为空的时候，还需要拼接，这时候一个if判断是不充分的，需要if else配合使用
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
if(l1 == null) return l2;
if(l2 == null) return l1;
while(l1 != null && l2 != null){
if(l1.val > l2.val){
prev.next = l2;
l2 = l2.next;
}else{
prev.next = l1;
l1 = l1.next;
}
prev = prev.next;
}
if(l1 == null){
prev.next = l2;
return prehead.next;
}
else{
prev.next = l1;
return prehead.next;
}
}
}
下面是递归解法，递归解法看起来很简洁，不过不好想啊
//递归解法
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
作者：LeetCode
