剑指 Offer - 学习

1 - 剑指 Offer 09. 用两个栈实现队列

 1 class CQueue {
 2     Stack a, b;
 3     // a : insert
 4     // b : delete
 5     public CQueue() {
 6         a = new Stack<>();
 7         b = new Stack<>();
 8     }
 9     public void appendTail(int value) {
10         a.push(value);
11     }
12     public int deleteHead() {
13         if (b.empty())
14         {
15             while (!a.empty())
16                 b.push(a.pop());
17         }
18         return (b.empty()) ? -1 : b.pop();
19     }
20 }

2 - 剑指 Offer 30. 包含min函数的栈

 1 class MinStack {
 2     /** initialize your data structure here. */
 3     Stack a, b;
 4     public MinStack() {
 5         a = new Stack<>();
 6         b = new Stack<>();
 7     }
 8     public void push(int x) {
 9         a.push(x);
10         if (b.empty() || x <= b.peek())
11             b.push(x);
12     }
13     public void pop() {
14         if (a.pop().equals(b.peek()))
15             b.pop();
16     }
17     public int top() {
18         return a.peek();
19     }
20     public int min() {
21         return b.peek();
22     }
23 }

3 - 剑指 Offer 06. 从尾到头打印链表

 1 class Solution {
 2     public int[] reversePrint(ListNode head) {
 3         Stack a = new Stack<>();
 4         int n = 0;
 5         for (; head != null; head = head.next)
 6         {
 7             a.push(head.val);
 8             n ++;
 9         }
10         int[] b = new int[n];
11         int m = 0;
12         for (; !a.empty(); )
13         {
14             b[m ++] = a.pop();
15         }
16         return b;
17     }
18 }

4 - 剑指 Offer 24. 反转链表

 1 class Solution {
 2     public ListNode reverseList(ListNode head) {
 3         ListNode prev, cur, next;
 4         for (prev = null, cur = head; cur != null; prev = cur, cur = next)
 5         {
 6             next = cur.next;
 7             cur.next = prev;
 8         }
 9         return prev;
10     }
11 }

5 - 剑指 Offer 35. 复杂链表的复制

 1 class Solution {
 2     public Node copyRandomList(Node head) {
 3         HashMap a = new HashMap<>();
 4         Node cur, b;
 5         for (cur = head; cur != null; cur = cur.next)
 6         {
 7             b = new Node(cur.val);
 8             a.put(cur, b);
 9         }
10         for (cur = head; cur != null; cur = cur.next)
11         {
12             Node c = a.get(cur);
13             c.next = a.get(cur.next);
14             c.random = a.get(cur.random);
15         }
16         return a.get(head);
17     }
18 }