瓜子面经汇总

    /**
     * 根据key的哈希值和key获取对应的节点
     * getNode可分为以下几个步骤：
     * 1.如果哈希表为空，或key对应的桶为空，返回null
     * 2.如果桶中的第一个节点就和指定参数hash和key匹配上了，返回这个节点。
     * 3.如果桶中的第一个节点没有匹配上，而且有后续节点
     * 3.1如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点
     * 3.2如果当前的桶不采用红黑树，即桶中节点结构为链式结构，遍历链表，直到key匹配
     * 4.找到节点返回null，否则返回null。
     */

    /**
     * putVal方法可以分为下面的几个步骤:
     * 1.如果哈希表为空，调用resize()创建一个哈希表。
     * 2.如果指定参数hash在表中没有对应的桶，即为没有碰撞，直接将键值对插入到哈希表中即可。
     * 3.如果有碰撞，遍历桶，找到key映射的节点
     * 3.1桶中的第一个节点就匹配了，将桶中的第一个节点记录起来。
     * 3.2如果桶中的第一个节点没有匹配，且桶中结构为红黑树，则调用红黑树对应的方法插入键值对。
     * 3.3如果不是红黑树，那么就肯定是链表。遍历链表，如果找到了key映射的节点，就记录这个节点，退出循环。如果没有找到，在链表尾部插入节点。插入后，如果链的长度大于TREEIFY_THRESHOLD这个临界值，则使用treeifyBin方法把链表转为红黑树。
     * 4.如果找到了key映射的节点，且节点不为null
     * 4.1记录节点的vlaue。
     * 4.2如果参数onlyIfAbsent为false，或者oldValue为null，替换value，否则不替换。
     * 4.3返回记录下来的节点的value。
     * 5.如果没有找到key映射的节点（2、3步中讲了，这种情况会插入到hashMap中），插入节点后size会加1，这时要检查size是否大于临界值threshold，如果大于会使用resize方法进行扩容。
     */
    
    /**
     * 对table进行初始化或者扩容。
     * 如果table为null，则对table进行初始化
     * 如果对table扩容，因为每次扩容都是翻倍，与原来计算（n-1）&hash的结果相比，节点要么就在原来的位置，要么就被分配到“原位置+旧容量”这个位置
     * resize的步骤总结为:
     * 1.计算扩容后的容量，临界值。
     * 2.将hashMap的临界值修改为扩容后的临界值
     * 3.根据扩容后的容量新建数组，然后将hashMap的table的引用指向新数组。
     * 4.将旧数组的元素复制到table中。
     */

Object obj = new Object();

Object obj = new Object();
SoftReference<Object> sf = new SoftReference<Object>(obj);

Object obj = new Object();
WeakReference<Object> wf = new WeakReference<Object>(obj);

Object obj = new Object();
PhantomReference<Object> pf = new PhantomReference<Object>(obj);

public class BinarySearch {
    public static int binarySearch(int[] array, int key) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (end - start) / 2 + start;
            if (key < array[mid]) {
                end = mid - 1;
            } else if (key > array[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static int binarySearch_2(int[] array, int start, int end, int key) {
        int mid = (end - start) / 2 + start;
        if (array[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        } else if (key > array[mid]) {
            return binarySearch_2(array, mid + 1, end, key);
        } else if (key < array[mid]) {
            return binarySearch_2(array, start, mid - 1, key);
        }
        return -1;
    }
}

    public ListNode ReverseList(ListNode head) {
        //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null
        ListNode pre = null;//pre为当前节点的前一节点
        ListNode next = null;//next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre.head.next1.next2变成pre<-head next1.next2
        //即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1.2.3.4.5
        //1<-2<-3 4.5
        //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
        while (head != null) {
            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了
            head.next = pre;
            //head指向pre后，就继续依次反转下一个节点
            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }

    public ListNode ReverseList(ListNode head) {
        //如果链表为空或者链表中只有一个元素 
        if (head == null || head.next == null) return head;
        //先递归找到到链表的末端结点，从后依次反转整个链表
        ListNode reverseHead = ReverseList(head.next);
        //再将当前节点设置为后面节点的后续节点 
        head.next.next = head;
        head.next = null;
        return reverseHead;
    }

    public static void preOrder(TreeNode biTree)
    {
        System.out.println(biTree.value);
        TreeNode leftTree = biTree.left;
        if(leftTree != null)
        {
            preOrder(leftTree);
        }
        TreeNode rightTree = biTree.right;
        if(rightTree != null)
        {
            preOrder(rightTree);
        }
    }
    
    public static void preOrder_2(TreeNode biTree)
    {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(biTree != null || !stack.isEmpty())
        {
            while(biTree != null)
            {
                System.out.println(biTree.value);
                stack.push(biTree);
                biTree = biTree.left;
            }
            if(!stack.isEmpty())
            {
                biTree = stack.pop();
                biTree = biTree.right;
            }
        }
    }

import java.util.Stack;

/**
 * 思路：
 * 栈A用来作入队列，栈B用来出队列
 * 当栈B为空时，栈A全部出栈到栈B,栈B再出栈（即出队列）
 */
public class Solution18 {

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);//stack1负责入队
    }

    public int pop() {
        if (stack1.empty() && stack2.empty()) {
            throw new RuntimeException("队列为空");
        }
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();//stcak2负责出队
    }
}

    /**
     * 直接利用hashmap记录出现次数
     *
     * @param nums
     * @return
     */
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        int count;
        for (int val :
                nums) {
            if (!map.containsKey(val)) {
                map.put(val, 1);
            } else {
                count = map.get(val);
                map.put(val, ++count);
            }
            if (map.get(val) == 2) {
                res.add(val);
            }
        }
        return res;
    }
    
    /**
     * 因为数组输入的特点 1<=a[i]<=n,则可以把原数组当hash表用 ，因为原数组是正数，标为负数表示出现过，如果遇到负数就表示第二次出现，就可以找出所有出现过两次的元素
     *
     * @param nums
     * @return
     */    
    public List<Integer> findDuplicates_2(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] < 0) {
                res.add(Math.abs(index + 1));
            }
            nums[index] = -nums[index];
        }
        return res;
    }

    public static void quickSort(int[] array, int _left, int _right) {
        int left = _left;//
        int right = _right;
        int pivot;//基准线
        if (left < right) {
            pivot = array[left];
            while (left != right) {
                //从右往左找到比基准线小的数
                while (left < right && pivot <= array[right]) {
                    right--;
                }
                //将右边比基准线小的数换到左边
                array[left] = array[right];
                //从左往右找到比基准线大的数
                while (left < right && pivot >= array[left]) {
                    left++;
                }
                //将左边比基准线大的数换到右边
                array[right] = array[left];
            }
            //此时left和right指向同一位置
            array[left] = pivot;
            quickSort(array, _left, left - 1);
            quickSort(array, left + 1, _right);
        }
    }

    public int reverseInt(int x) {
        int ans = 0;
        while (x != 0) {
            ans = ans * 10 + (x % 10);
            x /= 10;
        }
        if (ans < Integer.MIN_VALUE || ans > Integer.MAX_VALUE) {
            ans = 0;
        }
        return ans;
    }

import java.util.Scanner;

public class Main {
    /**
     * 进行分解质因数
     *
     * @param number
     */
    public static void factor(int number) {
        for (int i = 2; i < number; i++) {
            if (number % i == 0) {
                System.out.print(i + " ");
                //判断number/i是不是素数，如果是素数就直接输出
                if (isPrime(number / i)) {
                    System.out.print(number / i + " ");
                } else {
                    factor(number / i);
                }
                return;
            }
        }
    }

    /**
     * 判断是不是素数
     *
     * @param number
     * @return
     */
    public static boolean isPrime(int number) {
        for (int i = 2; i < number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

import java.util.HashSet;

public class Solution24 {

    /**
     * 假设x为环前面的路程，a为环入口到相遇点的路程， c为环的长度
     * 当快慢指针相遇的时候： 此时慢指针走的路程为Sslow = x + m * c + a
     * 快指针走的路程为Sfast = x + n * c + a
     * 2 Sslow = Sfast
     * 2 * ( x + m*c + a ) = (x + n *c + a)
     * 从而可以推导出： x = (n - 2 * m )*c - a = (n - 2 *m -1 )*c + c - a
     * 即环前面的路程 = 数个环的长度（为可能为0） + c - a
     * 什么是c - a？这是相遇点后，环后面部分的路程。
     * 所以，我们可以让一个指针从起点A开始走，让一个指针从相遇点B开始继续往后走， 2个指针速度一样，
     * 那么，当从原点的指针走到环入口点的时候（此时刚好走了x） 从相遇点开始走的那个指针也一定刚好到达环入口点。
     * 所以两者会相遇，且恰好相遇在环的入口点。
     *
     * @param pHead
     * @return
     */
    public ListNode EntryNodeOfLoop_2(ListNode pHead) {
        if (pHead == null || pHead.next == null || pHead.next.next == null)
            return null;
        ListNode fast = pHead.next.next;
        ListNode slow = pHead.next;
        //先判断有没有环
        while (fast != slow) {
            if (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            } else {
                //没有环
                return null;
            }
        }

        fast = pHead;//把fast指向头节点
        //有环
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    /**
     * 利用HashSet元素不能重复
     *
     * @param pHead
     * @return
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        HashSet<ListNode> hashSet = new HashSet<>();
        while (pHead != null) {
            if (!hashSet.add(pHead)) {
                return pHead;
            }
            pHead = pHead.next;
        }
        return null;
    }

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}

import java.util.HashMap;

public class Solution42 {
    /**
     * 利用 Boyer-Moore Majority Vote Algorithm（摩尔投票算法）来解决这个问题
     *
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution_2(int[] array) {
        int majority = array[0];
        for (int i = 1, count = 1; i < array.length; i++) {
            count = array[i] == majority ? count + 1 : count - 1;
            if (count == 0) {
                majority = array[i];
                count = 1;
            }
        }
        int count = 0;
        for (int val : array) if (val == majority) count++;
        return count > array.length / 2 ? majority : 0;
    }

    /**
     * 利用HashMap记录每个数字以及数字出现的次数
     *
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0)
            return 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int count;
        for (int val :
                array) {
            if (!map.containsKey(val)) {
                map.put(val, 1);
            } else {
                count = map.get(val);
                map.put(val, ++count);
            }
            if (map.get(val) > array.length / 2) {
                return val;
            }
        }
        return 0;
    }
}

import java.util.ArrayList;
import java.util.HashMap;

public class Solution34 {
    /**
     * 两头夹逼
     *
     * @param array
     * @param sum
     * @return
     */
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Integer> result = new ArrayList<>();
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            if (array[left] + array[right] == sum) {
                result.add(array[left]);
                result.add(array[right]);
                break;
            } else if (array[left] + array[right] > sum) {
                right--;
            } else {
                left++;
            }
        }
        return result;
    }

    /**
     * 用HashMap存放元素和下标，然后开始遍历数组找到和为sum的两个元素，从左到右找到的第一对和为sum的就是最小的一对。
     *
     * @param array
     * @param sum
     * @return
     */
    public ArrayList<Integer> FindNumbersWithSum_2(int[] array, int sum) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> result = new ArrayList<>();
        int len = array.length;
        for (int i = 0; i < len; i++) {
            map.put(array[i], i);
        }
        for (int i = 0; i < len; i++) {
            int sub = sum - array[i];
            if (map.containsKey(sub)) {
                result.add(array[i]);
                result.add(sub);
                break;
            }
        }
        return result;
    }
}

public class Singleton {
    private volatile static Singleton instance = null;

    private Singleton() {

    }

    /**
     * 当第一次调用getInstance()方法时，instance为空，同步操作，保证多线程实例唯一
     * 当第一次后调用getInstance()方法时，instance不为空，不进入同步代码块，减少了不必要的同步
     */
    public static Singleton getInstance() {
        if (instance == null) {
            synchronized (Singleton.class) {
                if (instance == null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}