Every one is their God,if you give up on yourself,who else will save you?Every one is busy,some are busy livig,some are busy dying,and you, who are busy chasing fame and fortune,who are busy with daily necessities,try to stop to think a second:if your brain has been institutionalized?Where is your God?
每个人都是自己的上帝，如果你自己都放弃自己了，还有谁会救你？每个人都在忙，有的忙着生，有的忙着死。忙着追逐名利的你、忙着柴米油盐的你，不妨停下来想一秒：你的大脑是不是已经被体制化了？你的上帝在哪里？

– – 《肖申克的救赎》

Day01-用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

    /**
     * 思路:
     * 栈：先进后出，队列：先进后出
     * 1. 栈A正常插入，完事之后出栈插入到B栈中，这时候A的栈底元素在B中便是栈顶元素
     * 2. 队列出栈的时候直接从B栈pop，入栈的时候向A栈push
     * 3. 当B为空时需要从A把数据同步过来
     * 4. 当B为空，同时A也为空时，说明队列里面没有数据，直接返回-1
    */
class CQueue {
    Stack<Integer> headOperateStack;
    Stack<Integer> tailOperateStack;
    public CQueue() {
        headOperateStack = new Stack<Integer>();
        tailOperateStack = new Stack<Integer>();
    }
    public void appendTail(int value) {
        headOperateStack.push(value);
    }
    public int deleteHead() {
        if(!tailOperateStack.isEmpty()){
            return tailOperateStack.pop();
        }
        //考虑头为空和尾栈为空
        //1.队尾栈为空，队头栈也为空
        if(headOperateStack.isEmpty()){
            return -1;
        }
        //2.队尾栈为空，并且队头栈不为空
        while(!headOperateStack.isEmpty()){
            tailOperateStack.push(headOperateStack.pop());
        }
        return tailOperateStack.pop();
    }
}

Day01-包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

class MinStack {
    Stack<Integer> A,B;
    public MinStack() {
        A = new Stack<>();//存放实际数据
        B = new Stack<>();//辅助存放min
    }
    /**
     *  push函数： 重点为保持栈B的元素是 非严格降序 的。
     *  1. 将 x 压入栈 A（即 A.push(x) ）；
     *  2. 若 栈B为空 或 x小于等于栈B的栈顶元素，则将x压入栈 B （即 B.push(x) ）
     *  始终保证B的栈顶元素是此时栈A的元素最小值
     */
    public void push(int val) {
        A.push(val);
        if(B.isEmpty() || B.peek()>=val){
            B.push(val);
        }
    }
    /**
     *   pop函数： 重点为保持栈 A,B 的元素一致性 。
     *   1. 执行栈 A 出栈（即 A.pop() ），将出栈元素记为 y 
     *   2. 若 y 等于栈 B 的栈顶元素，则执行栈 B 出栈（即 B.pop() ）
     */
    public void pop() {
        if(B.peek().equals(A.pop())){
            B.pop();
        }
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}

Day02-从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

/**
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：
 * 链表正序遍历倒叙插入数组即可(从数组的最后一个开始插入)
 * 1.计算链表节点数量，初始化数组
 * 2.遍历链表，倒序插入数组
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null){
            return new int[0];
        }
        ListNode temp = head;
        int size = 0;
        while(temp != null){
            size++;
            temp = temp.next;
        }
        int [] res = new int[size];
        while(head!=null){
            res[--size] = head.val;
            head = head.next;
        }
        return res;
    }
}

Day02-反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

/**
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：原地反转链表
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode tmp = cur.next;//临时保存下一个节点
            cur.next = pre;//修改当前节点的前驱为原来的后继
            pre = cur;//继续下一个节点的操作
            cur = tmp;
        }
        return pre;
    }
}

Day02-复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

/*
 * class Node {
 *    int val;
 *    Node next;
 *    Node random;
 *    public Node(int val) {
 *        this.val = val;
 *        this.next = null;
 *        this.random = null;
 *    }
 * }
 */

哈希表法

/**
 * 思路：
 * 利用哈希表的查询特点，考虑构建原链表节点和新链表对应节点的键值对映射关系
 * 再遍历构建新链表各节点的 next 和 random 引用指向即可。
 *
 * 结果:
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
 * 内存消耗：38.3 MB, 在所有 Java 提交中击败了39.18% 的用户
 */
class Solution {
    public Node copyRandomList(Node head) {
        if(head==null)return head;
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur!=null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        Node build = head;
        while(build!=null){
            map.get(build).next = map.get(build.next);
            map.get(build).random = map.get(build.random);
            build = build.next;
        }
        return map.get(head);
    }
}

拼接 + 拆分

/**
 * 思路：
 * 在原链表的每一个节点后插入一个节点，然后构造新节点的random指向，最后再把新旧链表分离出来
 * 
 * 结果:
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
 * 内存消耗：37.3 MB, 在所有 Java 提交中击败了99.82% 的用户
 */
class Solution {
    public Node copyRandomList(Node head) {
        if(head==null)return head;
        Node cur = head;
        //构建节点，插入
        while(cur!=null){
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        //构建random指向
        cur = head;
        while(cur!=null){
            //需要非常注意，random可能为null
            if(cur.random!=null){
                cur.next.random =  cur.random.next;
            }
            cur = cur.next.next;
        }
        //拆链表
        cur = head.next;//始终指向新链表的节点
        Node newHead = head.next;
        Node pre = head;//始终指向原链表的节点
        while(cur.next!=null){//此处是指新链表节点的下一个节点(原链表节点)不为空，也就是还没遍历完
            pre.next = cur.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;//最后把原链表最后一个节点和新链表断开
        return newHead;
    }
}

Day03-替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

class Solution {
    public String replaceSpace(String s) {
        if(s==null)return s;
        StringBuilder res = new StringBuilder();
        for(int i = 0; i<s.length(); i++){
            if(' '==s.charAt(i)){
                res.append("%20");
            }else{
                res.append(s.charAt(i));
            }
        }
        return res.toString();
    }
}

Day03-II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n,s.length())+s.substring(0,n);
    }
    //速度太慢
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder();
        for(int i = n; i < n + s.length(); i++)
            res.append(s.charAt(i % s.length()));
        return res.toString();
    }
}

Day04-数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

/**
 * 法1思路：
 * 题目中说“长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内”，说明可以把各个元素放到改元素所表示的数组下标位置上去
 * 如果该元素表示的数组下标上的的值和当前元素相同，那么这个元素就是重复的元素
 * 当前元素的值 => nums[i]
 * 该元素表示的数组下标上的的值 => nums[nums[i]]
 
 * 执行用时: 0 ms
 * 内存消耗: 46.1 MB
 */
class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int i = 0;i<nums.length;i++){
            if(nums[i]==i){
                continue;
            }
            if(nums[nums[i]]==nums[i]){
                return nums[i];
            }
            int tmp = nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = tmp;
            --i;
        }
        return -1;
    }
}

/**
 * 法2思路：
 * 数组中每个元素都当做数组下标，把他放到该去的地方，如果已经有了说明重复了

 * 执行用时：1 ms, 在所有 Java 提交中击败了80.75% 的用户
 * 内存消耗：46.1 MB, 在所有 Java 提交中击败了70.29% 的用户
 */
class Solution {
    public int findRepeatNumber(int[] nums) {
        int[] tmp = new int[nums.length];
        for(int i:tmp){
            tmp[i] = -1;
        }
        for(int i : nums){
            if( tmp[i] == i ){
                return i;
            }
            //元素归位
            tmp[i] = i;
        }
        return -1;
    }
}

Day04-0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

/**
 * 仔细揣摩题意之后很简单的题目
 */
class Solution {
    public int missingNumber(int[] nums) {
        //根据题目“在范围0～n-1内的n个数字中有且只有一个数字不在该数组中”,我们可推断数组必须是从0开始
        //正常情况下，各个元素都应该在其下标对应的位置上，如果哪个下标对应的元素和下标不一致，则说明该元素缺失
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=i){
                return i;
            }
        }
        //如果到这里了还是相等的，说明缺了最后一个元素
        //比如{0，1，2，3，4}长度(n-1)=5，也就是说元素的范围是0-5
        return nums.length;
    }
}