常见面试算法题整理（持续更新中）

public class LRUCache<K,V> extends LinkedHashMap<K,V> {

    int maxSize = 50;

    Lock lock = new ReentrantLock();

    public LRUCache(int initialCapacity, float loadFactor, boolean accessOrder, int maxSize) {
        super(initialCapacity, loadFactor, accessOrder);
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return this.size() > maxSize;
    }

    public V get(Object key) {
        try {
            lock.lock();
            return super.get(key);
        } finally {
            lock.unlock();
        }
    }

    public V put(K key, V value) {
        try {
            lock.lock();
            return super.put(key, value);
        } finally {
            lock.unlock();
        }
    }
}

public class ThreadTest {

    final static AtomicInteger flag = new AtomicInteger(1);
    static Object lock = new Object();
    static int i = 1;

    public static void main(String[] args) {
        Thread thread1 = new Thread(() -> {
            while(i <= 100) {
                synchronized (lock) {
                    lock.notify();
                    if(i % 2 != 0) {
                        System.out.println("thread1:" + i++);
                    } else {
                        try {
                            lock.wait();
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                }
            }
        });

        Thread thread2 = new Thread(() -> {
            while(i <= 100) {
                synchronized (lock) {
                    lock.notify();
                    if(i % 2 == 0) {
                        System.out.println("thread2:" + i++);
                    } else {
                        try {
                            lock.wait();
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                }
            }
        });
        thread1.start();
        thread2.start();
    }
}

/**
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}
**/


public class BinaryLayerSout {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        if(root == null) return new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        stack.addLast(root);
        while (!stack.isEmpty()) {
            int size = stack.size();
            ArrayList<Integer> temp = new ArrayList<>(size);
            while(size-- > 0) {
                TreeNode tempNode = stack.pollFirst();
                temp.add(tempNode.val);
                if(tempNode.left != null) {
                    stack.addLast(tempNode.left);
                }
                if(tempNode.right != null) {
                    stack.addLast(tempNode.right);
                }
            }
            res.add(temp);
        }
        return res;
    }
}

/**
@Data
public class ListNode {
    int val;
    ListNode next;
}
**/

public class MergeSortedLinkedList {

    public ListNode mergeSortedLinkedList(ListNode head1, ListNode head2) {
        if(null == head1) return head2;
        if(null == head2) return head1;
        ListNode mergeNode = new ListNode();
        ListNode p = mergeNode;
        while(head1 != null && head2 != null) {
            if(head1.val <= head2.val) {
                p.next = head1;
                p = p.next;
                head1 = head1.next;
            } else {
                p.next = head2;
                p = p.next;
                head2 = head2.next;
            }
        }
        if(head1 != null) {
            p.next = head1;
        }
        if(head2 != null) {
            p.next = head2;
        }
        return mergeNode.next;
    }
}

public class QuickSort {

    public static void main(String[] args) {
        int[] array = {7,6,5,4,3,2,1,6};
        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
        System.out.println(1 >> 1);
    }

    public static void sort(int[] array, int beginIndex, int endIndex) {
        if(beginIndex >= endIndex) {
            return;
        }
        int partition = partition(array, beginIndex, endIndex);
        sort(array, beginIndex, partition - 1);
        sort(array, partition + 1, endIndex);
    }

    public static int partition(int[] array, int beginIndex, int endIndex) {
        int pivot = array[endIndex];
        int index = beginIndex;
        for(int i = beginIndex; i < endIndex; i++) {
            if(array[i] < pivot) {
                int temp = array[i];
                array[i] = array[index];
                array[index] = temp;
                index++;
            }
        }
        int temp = array[endIndex];
        array[endIndex] = array[index];
        array[index] = temp;
        return index;
    }
}

public class CycleInLinkedList {

    /**
     * 验证链表是否有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if(null == head) return false;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }


    /**
     * 寻找链表中的环入口
     * @param head
     * @return
     */
    public ListNode findEntryNodeOfCycle(ListNode head) {
        if(null == head) return null;

        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                slow = head;
                while(slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                break;
            }
        }

        if(fast == null || fast.next == null) return null;
        return slow;
    }
}