猫眼面经汇总

    /**
     * 扩容，以确保它可以至少持有由参数指定的元素的数目
     *
     * @param minCapacity 所需的最小容量
     */
    private void grow(int minCapacity) {
        // 获取到ArrayList中elementData数组的内存空间长度
        int oldCapacity = elementData.length;
        // 扩容至原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 再判断一下新数组的容量够不够，够了就直接使用这个长度创建新数组，
        // 不够就将数组长度设置为需要的长度
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //若预设值大于默认的最大值检查是否溢出
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间
        // 并将elementData的数据复制到新的内存空间
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }
    public int intValue() {
        return value;
    }

    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;
    }

package Recursion;

/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 */
public class Solution04 {
    public static void main(String[] args) {
        Solution04 solution04 = new Solution04();
        System.out.println(solution04.JumpFloor_2(3));

    }

    /**
     * 直接用递归
     * * 对于第n个台阶来说，只能从n-1或者n-2的台阶跳上来，所以
     * F(n) = F(n-1) + F(n-2)
     * f(1)=1
     * f(2)=2
     *
     * @param target 台阶数
     * @return 跳法
     */
    public int JumpFloor(int target) {
        if (target <= 1) {
            return 1;
        }
        if (target <= 2) {
            return 2;
        } else {
            return JumpFloor(target - 1) + JumpFloor(target - 2);
        }
    }

    /**
     * 用迭代的方法，用两个变量记录f(n-1) f(n-2)
     *
     * @param target 台阶数
     * @return 跳法
     */
    public int JumpFloor_2(int target) {
        int one = 1, two = 2, fN = 0;
        if (target <= 0) {
            return 0;
        } else if (target == 1) {
            return 1;
        } else if (target == 2) {
            return 2;
        } else {
            for (int i = 3; i <= target; i++) {
                fN = one + two;
                one = two;
                two = fN;
            }
            return fN;
        }
    }
}

package Array;

/**
 * 连续子数组的最大和
 * 在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？
 * 例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。(子向量的长度至少是1)
 */

public class Solution01 {
    public static void main(String[] args) {
        int[] arr = {6,-3,-2,7,-15,1,2,2};
        System.out.println(FindGreatestSumOfSubArray(arr));
    }
    public static int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0)
            return 0;
        int sum = array[0];//保存每组的和
        int maxSum = array[0];//连续子数组最大和
        //动态规划
        for(int i = 1;i<array.length;i++){
            sum = Math.max(sum+array[i],array[i]);
            maxSum = Math.max(sum,maxSum);
        }
        return maxSum;
    }
}

    /**
     * 快速排序
     *
     * @param array
     * @param _left
     * @param _right
     */
    private 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);
        }
    }

package Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
 * 思路：
 * 按层次输出二叉树
 * 访问根节点，并将根节点入队。
 * 当队列不空的时候，重复以下操作。
 * 1、弹出一个元素。作为当前的根节点。
 * 2、如果根节点有左孩子，访问左孩子，并将左孩子入队。
 * 3、如果根节点有右孩子，访问右孩子，并将右孩子入队。
 */
public class Solution8 {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        Solution8 solution8 = new Solution8();
        TreeNode treeNode = solution8.createBinaryTreeByArray(array, 0);
        for (ArrayList list :
                solution8.Print(treeNode)) {
            System.out.println(list);
        }
    }


    /**
     * 层次遍历
     *
     * @param pRoot 根节点
     * @return arrayLists
     */
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        //存放结果
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (pRoot == null) {
            return arrayLists;
        }
        //使用队列，先进先出
        Queue<TreeNode> queue = new LinkedList<>();
        //存放每行的列表
        ArrayList<Integer> arrayList = new ArrayList<>();
        //记录本层打印了多少个
        int start = 0;
        //记录下层打几个
        int end = 1;
        queue.add(pRoot);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.remove();
            //添加到本行的arrayList
            arrayList.add(temp.val);
            start++;
            //每打印一个节点，就把此节点的下一层的左右节点加入队列，并记录下一层要打印的个数
            if (temp.left != null) {
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
            //判断本层打印是否完成
            if (start == end) {
                //此时的queue中存储的都是下一层的节点，则end即为queue大小
                end = queue.size();
                start = 0;
                //把arrayList添加到结果列表arrayLists中
                arrayLists.add(arrayList);
                //重置arrayList
                arrayList = new ArrayList<>();
            }
        }

        return arrayLists;
    }



    private TreeNode createBinaryTreeByArray(int[] array, int index) {
        TreeNode tn = null;
        if (index < array.length) {
            int value = array[index];
            tn = new TreeNode(value);
            tn.left = createBinaryTreeByArray(array, 2 * index + 1);
            tn.right = createBinaryTreeByArray(array, 2 * index + 2);
            return tn;
        }
        return tn;
    }


    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}

    public void levelOrder(TreeNode root) {
        //使用队列，先进先出
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            System.out.print(temp.val + "  ");
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
    }

package LinkedList;

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） 从相遇点开始走的那个指针也一定刚好到达环入口点。
     * 所以两者会相遇，且恰好相遇在环的入口点。
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     *
     * @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;
        }
    }
}

    /**
     * 冒泡排序
     *
     * @param array
     */
    private static void bubbleSort(int[] array) {
        if (array == null || array.length == 0 || array.length == 1)
            return;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {//注意数组边界
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
    
    private static void bubbleSort(int[] array) {
        if (array == null || array.length == 0 || array.length == 1)
            return;
        boolean flag = true;//发生了交换就为true, 没发生就为false，第一次判断时必须标志位true
        int k = array.length - 1;
        int pos = 0;//pos变量用来标记循环里最后一次交换的位置
        for (int i = 0; i < array.length - 1; i++) {
            flag = false;//每次开始排序前，都设置flag为未排序过
            for (int j = 0; j < k; j++) {//注意数组边界
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = true;//表示交换过数据;
                    pos = j;
                }
            }
            k = pos;
            //判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
            if (flag == false)
                return;
        }
    }

package Array;

/**
 * 88. Merge Sorted Array（合并两个有序数组）
 * 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
 */
public class Solution88 {
    public static void main(String[] args) {
        Solution88 solution88 = new Solution88();

        solution88.merge();
    }

    /**
     * 从两个数组中的末尾开始进行合并，先找两个数组中较大的移动到正确的位置，将那个移动的位置值向前移动一个位置，再进行同样的操作，直到所有的元素处理完。
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[index--] = nums1[i--];
            } else {
                nums1[index--] = nums2[j--];
            }
        }
        while (j >= 0) {
            nums1[index--] = nums2[j--];
        }
    }
}