剑指Offer刷题笔记

@TOC

思路:
题目其实已经提示了，本题的主要思路。队列的特点是先进先出，但是栈的特点是先进后出。所以栈的入栈顺序和队列的入栈顺序是一致的，但是栈的出栈顺序与队列不同。
所以我们引入一个新的栈，当有元素需要入队的时候，我们将元素添加到栈in中，比如1 ， 2， 3三个元素，出栈的时候，我们把栈in依次出栈到栈out中。此时栈b的出栈顺序为1 2 3 这时候弹出栈out 的栈顶， 就是队列1 2 3的队首。
代码：

class CQueue {
    Deque StackA;
    Deque StackB;

    public CQueue() {
        StackA = new ArrayDeque();
        StackB = new ArrayDeque();
    }
    
    public void appendTail(int value) {
        StackA.push(value);
    }
    
    public int deleteHead() {
        if (StackB.isEmpty()){
            if (StackA.isEmpty())
                return -1;
            a2b();

        }
        return StackB.pop();
    }

    public void a2b(){
        while (!StackA.isEmpty()){
            StackB.push(StackA.pop());
        }
    }
}

思路：还是利用了两个栈，我们同时维护一个元素栈和一个对应到该元素入栈后的最小值栈。比如0 -3 1入栈 对应的最小值栈为 MAX_VAULE 0 - 3 -3。 值得一提的是我们维护的最小值栈的栈低为最大值。
代码：

class MinStack {
    Deque StackA;
    Deque StackB;
    
    public MinStack() {
        StackA = new LinkedList();
        StackB = new LinkedList();
        StackB.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        StackA.push(x);
        StackB.push(Math.min(StackB.peek(), x));
    }
    
    public void pop() {
        StackA.pop();
        StackB.pop();
    }
    
    public int top() {
        return StackA.peek();
    }
    
    public int min() {
        return StackB.peek();
    }
}

剑指 Offer 06. 从尾到头打印链表
思路：
给我们了一个链表要求返回一个倒序的数组，思路有很多，首先可以利用栈的特点，将每一个链表的元素入栈，再依次出栈存入数组中即可。不适用栈也可以，我们可以直接遍历一遍链表得到其长度，再构造一个数组，和一个下标表达式，假设长度为3 那么数组0下标要对应链表的2下标，所以我们可以得出一个式子：n - i - 1 ，n为链表长度， i为链表下标。
代码：

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack stack = new Stack();
        ListNode temp = head;
        while (temp != null){
            stack.push(temp.val);
            temp = temp.next;
        }
        int n = stack.size();
        int[] ans = new int[n];
        for (int i = 0; i < n; i ++ ){
            ans[i] = stack.pop();
        }
        return ans;
    }
}

剑指 Offer 24. 反转链表
思路：
1.迭代的写法
在遍历链表时，将当前节点的next指针改为指向前一个节点,再更新prev为当前节点（相当于往后走一步）。由于链表只有next没有prev所以，我们存一下前一个节点的指针，在更改引用前再存一下后一个节点，用于遍历吗，最后返回新的头引用。
代码：
1.迭代写法的代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

2.递归写法的代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }

        ListNode curr = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return curr;
    }
}

剑指 Offer 35. 复杂链表的复制
1.回溯、哈希表、递归
思路：
因为这个链表是复杂链表，节点中存在一个random指的指向是随机的，所以我们不能简单的遍历后然后存一个新的链表。
我们利用哈希表将每一次遇到的节点存入，再递归获得该节点的next和random即可。在递归的过程中可能最开始我们需要的random还未创建，但是在递归回溯的过程中我们一定可以找到需要的random指针。
代码：

class Solution {
    Map cachedNode = new HashMap();
    public Node copyRandomList(Node head) {
        if (head == null){
            return null;
        }

        if (!cachedNode.containsKey(head)) {
            Node newNode = new Node(head.val);
            cachedNode.put(head, newNode);
            newNode.random = copyRandomList(head.random);
            newNode.next = copyRandomList(head.next);
        }
        return cachedNode.get(head);
    }
}

剑指 Offer 05. 替换空格
思路：
替换空格，非常简单的一道字符串的题，我们直接遍历一遍字符串，遇到空格时在StringBuffer中加入%20否则直接加入原字符。
当然我们也可以不使用StringBuffer，使用简单的数组也可以实现同样的效果。
代码：
1.StringBuffer

class Solution {
    public String replaceSpace(String s) {
        StringBuffer sb = new StringBuffer();
        int n = s.length();
        for (int i = 0; i < n; i ++ ) {
            if (s.charAt(i) == ' ') {
                sb.append("%20");
                continue;
            }
            else sb.append(s.charAt(i));
        }

        return sb.toString();
    }
}

2.Array数组

class Solution {
    public String replaceSpace(String s) {
        int n = s.length();
        char[] arr = new char[n * 3]; 
        int size = 0;
        for (int i = 0; i < n; i ++ ) {
            if (s.charAt(i) == ' ') {
                arr[size ++ ] = '%';
                arr[size ++ ] = '2';
                arr[size ++ ] = '0';
            } else {
                arr[size ++] = s.charAt(i);
            }
        }

        String ans = new String(arr, 0, size);
        return ans;
    }

剑指 Offer 58 - II. 左旋转字符串
思路：
本题同样很简单，思路有很多，我就简单的说一下。
首先我们可以用一个StringBuffer，先把不用旋转的字符串添加进去，再将需要旋转的部分，添加到sb的末尾即可。
但是这样直接遍历，我们需要两个for，代码不够简洁，我们可以利用余数的性质将其优化为一个for循环解决问题。
代码：
1.

class Solution {
    public String reverseLeftWords(String s, int n) {
        int l = s.length();
        StringBuffer sb = new StringBuffer();
        for (int i = n; i < l; i ++ ) {
            sb.append(s.charAt(i));
        } 

        for (int i = 0; i < n; i ++ ) {
            sb.append(s.charAt(i));
        }

        return sb.toString();
    }
}

class Solution {
    public String reverseLeftWords(String s, int n) {
        int l = s.length();
        String res = "";
        for(int i = n; i < n + l; i++)
            res += s.charAt(i % l);
        return res;
    }
}