/**
 * 冒泡排序，从小到大
 * nums = [1,8,6,7,9,2];
 * @param nums
 */
public static int[] bubbleSort(int[] nums){
    for(int i = nums.length - 1; i > 0; i--){
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]){
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
    return nums;
}

/**
 * 选择排序，从小到大
 * @param nums
 * @return
 */
public static int[] selectionSort(int[] nums){
    for (int i = 0; i < nums.length; i++) {
        int min = Integer.MAX_VALUE, index = 0;
        for (int j = i; j < nums.length; j++){
            if (nums[j] < min){
                min = nums[j];
                index = j;
            }
        }
        int temp = nums[index];
        nums[index] = nums[i];
        nums[i] = temp;
    }
    return nums;
}

/**
 * 快排，递归
 * @param nums
 * @param low
 * @param high
 */
private static void quickSort(int[] nums, int low, int high) {
    if (low < high){
        int position = partition(nums, low, high);
        quickSort(nums, low, position - 1);
        quickSort(nums, position + 1, high);
    }
}

/**
 * 分区，返回每次分区的基值
 * @param nums
 * @param low
 * @param high
 * @return
 */
private static int partition(int[] nums, int low, int high) {
    int pivot = nums[high];
    int index = low;
    for (int i = low; i < high; i++) {
        if (nums[i] <= pivot){
            swap(nums, i, index);
            index++;
        }
    }
    swap(nums, index, high);
    return index;
}

public static void swap(int[] num, int i, int j){
    int temp = num[i];
    num[i] = num[j];
    num[j] = temp;
}

private static void quickSort(int[] nums, int low, int high){
    if (low < high){
        int position = partition(nums, low, high);
        int leftPosition = position - 1;
        int rightPosition = position + 1;
        //去重
        while (leftPosition > low && nums[leftPosition] == nums[position]){
            leftPosition--;
        }
        //去重
        while (rightPosition < high && nums[rightPosition] == nums[position]){
            rightPosition++;
        }
        quickSort(nums, low, leftPosition);
        quickSort(nums, rightPosition, high);
    }
}

private static int partition(int[] nums, int low, int high) {
    //随机
    int randomIndex = low + (int)Math.random() *(high - low + 1);
    swap(nums, high, randomIndex);
    int pivot = nums[high];
    int index = low;
    for (int i = low; i < high; i++){
        if (nums[i] <= pivot){
            swap(nums, i, index);
            index++;
        }
    }
    swap(nums, index, high);
    return index;
}

private static void swap(int[] nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

// 全局变量，用来记录当前堆的长度
public static int heapLen;

/**
* 堆排序
* @param nums
* @return
*/
public static int[] heapSort(int[] nums) {
    heapLen = nums.length;
    buildMaxHeap(nums);
    for (int i = nums.length - 1; i > 0; i--) {
        swap(nums, 0, i);
        heapLen--;
        heapify(nums, 0);
    }
    return nums;
}

/**
* 建立大顶堆
* @param nums
*/
private static void buildMaxHeap(int[] nums) {
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
        heapify(nums, i);
    }
}

/**
* 调整大顶堆
* @param nums
* @param i
*/
private static void heapify(int[] nums, int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < heapLen && nums[left] > nums[largest]){
        largest = left;
    }
    if (right < heapLen && nums[right] > nums[largest]){
        largest = right;
    }
    if (largest != i){
        swap(nums, i, largest);
        heapify(nums, largest);
    }
}

private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

    /**
     * 归并排序
     * @param nums
     * @return
     */
    private static void mergeSort(int[] nums, int low, int high) {
        if (low < high){
            int mid = (low + high) / 2;
            //归并左边
            mergeSort(nums, low, mid);
            //归并右边
            mergeSort(nums, mid + 1, high);
            //合并两边的数组
            merge(nums, low, mid, high);
        }
    }

    /**
     * 合并两个数组
     * @param nums
     * @param low
     * @param mid
     * @param high
     */
    private static void merge(int[] nums, int low, int mid, int high) {
        int[] arr = new int[high - low + 1];
        int index = 0;
        int left = low, right = mid + 1;
        //看谁小，谁就先放前面
        while(left <= mid && right <= high){
            if (nums[left] < nums[right]){
                arr[index++] = nums[left++];
            }else{
                arr[index++] = nums[right++];
            }
        }
        //如果左边还没合并完
        while(left <= mid){
            arr[index++] = nums[left++];
        }
        //如果右边还没合并完
        while (right <= high){
            arr[index++] = nums[right++];
        }
        //将合并好的结果放回原来的数组
        for (int i = 0; i < arr.length; i++) {
            nums[i + low] = arr[i];
        }
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 1){
            return s.length();
        }
        int ans = 0, index = 0;
        HashSet<Character> set = new HashSet<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(set.contains(c)){
                ans = Math.max(ans, set.size());
                while(s.charAt(index) != c){
                    set.remove(s.charAt(index));
                    index++;
                }
                set.remove(s.charAt(index));
                index++;
            }
            set.add(c);
        }
        return Math.max(ans, set.size());
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0, index = 0;
        int[] dict = new int[128];
        for(int i = 0; i < 128; i++){
            dict[i] = -1;
        }
        for(int i = 0; i < s.length(); i++){
            index = Math.max(index, dict[s.charAt(i)] + 1);
            ans = Math.max(ans, i - index + 1);
            dict[s.charAt(i)] = i;
        }
        return ans;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode p = head, q = null;
        while(p != null){
            ListNode temp = p.next;
            p.next = q;
            q = p;
            p = temp;
        }
        return q;
    }
}

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

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = new ListNode(0);
        ListNode p = head, q = null;
        while(p != null){
            q = p.next;
            p.next = newHead.next;
            newHead.next = p;
            p = q;
        }
        return newHead.next;
    }
}

class LRUCache {

    private int cap;
    private Map<Integer, Integer> map = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    
    public int get(int key) {
        if(map.keySet().contains(key)){
            int value = map.get(key);
            //保证每次查询，都在最后
            map.remove(key, value);
            map.put(key, value);
            return value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if(map.keySet().contains(key)){
            map.remove(key, map.get(key));
        }else if(map.size() == cap){
            // 使用Iterator遍历并删除第一个元素
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            if (iterator.hasNext()) {
                iterator.next();
                iterator.remove();
            }
        }
        map.put(key, value);
    }
}

class LRUCache {

    // 手写双向链表
    class DLinkedNode{
        public int key;
        public int value;
        public DLinkedNode pre;
        public DLinkedNode next;

        public DLinkedNode(){}
        public DLinkedNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    //删除节点
    public void removeNode(DLinkedNode node){
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }

    //将节点添加到最前面
    public void addToHead(DLinkedNode node){
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }

    //将指定节点移动到最前面
    public void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);
    }

    //删除最后面节点，并返回该节点
    public DLinkedNode removeLastNode(){
        DLinkedNode resNode = tail.pre;
        removeNode(resNode);
        return resNode;
    }

    public HashMap<Integer, DLinkedNode> map = new HashMap<>();
    public int mapCap;
    public int size;	//记录链表中节点个数
    public DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.mapCap = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        DLinkedNode node = map.get(key);
        //如果节点存在，那么就将节点移到最前面，并返回value
        if(node != null){
            moveToHead(node);
            return node.value;
        }else{
            return -1;
        }
    }
    
    public void put(int key, int value) {
        DLinkedNode node = map.get(key);
        //如果节点不存在
        if(node == null){
            //新建一个节点，添加到最前面，并使得size++
            node = new DLinkedNode(key, value);
            map.put(key, node);
            addToHead(node);
            size++;
            //如果链表中节点个数大于定义的最大容量，就移除链表中最后一个元素
            if(size > mapCap){
                DLinkedNode lastNode = removeLastNode();
                //并在map中也删除这个节点
                map.remove(lastNode.key);
                size--;
            }
        }else{
            //如果节点存在，那么把节点移动到最前面，然后更新节点的value
            moveToHead(node);
            node.value = value;
        }
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }

    public void quickSort(int[] nums, int low, int high){
        if(low < high){
            int position = partition(nums, low, high);
            quickSort(nums, low, position - 1);
            quickSort(nums, position + 1, high);
        }
    }

    public int partition(int[] nums, int low, int high){
        int randomIndex = low + (int)Math.random()*(high - low + 1);
        swap(nums, randomIndex, high);
        int povit = nums[high];
        int index = low;
        for(int i = low; i < high; i++){
            if(nums[i] <= povit){
                swap(nums, i, index);
                index++;
            }
        }
        swap(nums, high, index);
        return index;
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //维护一个只有k个元素的小根堆
        int[] arr = new int[k];
        for (int i = 0; i < k; i++) {
            arr[i] = nums[i];
        }
        buildHeap(arr, k - 1);
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > arr[0]) {
                arr[0] = nums[i];
                heapify(arr, k - 1, 0);
            }
        }
        return arr[0];
    }
    private void buildHeap(int[] nums, int n) {
        for (int i = n / 2; i >= 0; i--) {
            heapify(nums, n, i);
        }
    }
    private void heapify(int[] nums, int n, int i) {
        while (true) {
            int minPos = i;
            int left = 2 * i + 1;
            int right = left + 1;
            if (left <= n && nums[minPos] > nums[left]){
                minPos = left;
            }
            if (right <= n && nums[minPos] > nums[right]){
                minPos = right;
            } 
            if (minPos == i){
                break;
            }
            swap(nums, i, minPos);
            i = minPos;
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //创建一个优先队列
        PriorityQueue<Integer> minTree = new PriorityQueue<>();
        for(int i = 0; i < nums.length; i++){
            //将每一个元素都加入到优先队列中
            minTree.add(nums[i]);
            //维护优先队列中元素为k个，大于k的就弹出
            if(minTree.size() > k){
                minTree.poll();
            }
        }
        //最后弹出的那个一定是第k大的元素
        return minTree.peek();
    }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int listLength = 0;
        ListNode newHead = new ListNode(0), p = newHead, q = head, temp;
        newHead.next = head;
        //统计链表长度
        while(head != null){
            listLength++;
            head = head.next;
        }
        head = newHead.next;
        //要翻转listLength/k组
        for(int i = 0; i < listLength / k; i++){
            //每组内要翻转k - 1次
            for(int j = 0; j < k - 1; j++){
                temp = q.next;
                q.next = temp.next;
                temp.next = p.next;
                p.next = temp;
            }
            p = q;
            q = p.next;
        }
        return newHead.next;
    }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        Deque<ListNode> stack = new ArrayDeque<>();
        ListNode newHead = new ListNode(0);
        ListNode p = newHead;
        while(true){
            //用count记录stack中节点个数
            int count = 0;
            ListNode q = head;
            //使得k个一组节点陆续入栈
            while(q != null && count < k){
                stack.add(q);
                q = q.next;
                count++;
            }
            //当节点个数不足k个时，说明stack中的节点就不需要翻转了，直接连接上就可以跳出循环
            if(count != k){
                p.next = head;
                break;
            }
            //将节点出栈，也即翻转k个节点
            while(!stack.isEmpty()){
                p.next = stack.pollLast();
                p = p.next;
            }
            p.next = q;
            head = q;
        }
        return newHead.next;
    }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            //剩余数量小于k的话，则不需要反转。
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(head, tail);
        //下一轮的开始的地方就是tail
        head.next = reverseKGroup(tail, k);
        return newHead;
    }

    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode next = null;
        while (head != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ansList = new ArrayList<>();
        Arrays.sort(nums);
        //判断排序后的开始和结尾元素是否符合要求，不符合的话直接退出即可
        if(nums[0] > 0 || nums[nums.length - 1] < 0){
            return ansList;
        }
        for(int i = 0; i < nums.length - 2; i++){
            //如果第一个都不符合要求，那后面肯定都不行
            if(nums[i] > 0){
                return ansList;
            }
            //去重，如果前面一个元素和当前元素相同，直接跳过，不然肯定添加的是相通的
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int left = i + 1, right = nums.length - 1;
            while(left < right){
                int target = nums[i] + nums[left] + nums[right];
                if(target < 0){
                    left++;
                }else if(target > 0){
                    right--;
                }else{
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    ansList.add(temp);
                    //去重，同样是找相邻是否有相同的元素，有的话就跳过
                    while(left < right && nums[left] == nums[left + 1]){
                        left++;
                    }
                    //去重
                    while(left < right && nums[right] == nums[right - 1]){
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return ansList;
    }
}

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quickSort(int[] nums, int low, int high){
        if(low < high){
            int position = partition(nums, low, high);
            int leftPosition = position - 1;
            int rightPosition = position + 1;
            //去掉重复的元素
            while(leftPosition > low && nums[position] == nums[leftPosition]){
                leftPosition--;
            }
            while(rightPosition < high && nums[position] == nums[rightPosition]){
                rightPosition++;
            }
            quickSort(nums, low, leftPosition);
            quickSort(nums, rightPosition, high);
        }
    }

    public int partition(int[] nums, int low, int high){
        //随机选取基准元素
        int randomIndex = low + (int)Math.random() * (high - low + 1);
        swap(nums, randomIndex, high);
        int pivot = nums[high];
        int index = low;
        for(int i = low; i < high; i++){
            if(nums[i] <= pivot){
                swap(nums, index, i);
                index++;
            }
        }
        swap(nums, high, index);
        return index;
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int max = 0;
        int ans = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++){
            max = Math.max(nums[i] + max, nums[i]);
            ans = Math.max(max, ans);
        }
        return ans;
    }
}

class Solution{
    public int maxSubAray(int[] nums){
        //类似寻找最大最小值的题目,初始值一定要定义成理论上的最小最大值
        int result = Integer.MIN_VALUE;
        int numsSize = nums.length;
        int sum = 0;
        for (int i = 0; i < numsSize; i++){
            sum += nums[i];
            result = Math.max(result, sum);
            //如果sum < 0,重新开始找子序串
            if (sum < 0){
                sum = 0;
            }
        }

        return result;
    }
}

class Solution {
    public int maxSubAray(int[] nums) {
        if (nums == null || nums.length <= 0)// 输入校验
            return 0;
        int len = nums.length;// 获取输入长度
        return getInfo(nums, 0, len - 1).mSum;
    }

    class wtevTree { //线段树
        int lSum;// 以左区间为端点的最大子段和
        int rSum;// 以右区间为端点的最大子段和
        int iSum;// 区间所有数的和
        int mSum;// 该区间的最大子段和
        wtevTree(int l, int r, int i, int m) { // 构造函数
            lSum = l;
            rSum = r;
            iSum = i;
            mSum = m;
        }
    }

    // 通过既有的属性,计算上一层的属性,一步步往上返回,获得线段树
    wtevTree pushUp(wtevTree leftT, wtevTree rightT) {
        // 新子段的lSum等于左区间的lSum或者左区间的 区间和 加上右区间的lSum
        int l = Math.max(leftT.lSum, leftT.iSum + rightT.lSum);
        // 新子段的rSum等于右区间的rSum或者右区间的 区间和 加上左区间的rSum
        int r = Math.max(leftT.rSum + rightT.iSum, rightT.rSum);
        // 新子段的区间和等于左右区间的区间和之和
        int i = leftT.iSum + rightT.iSum;
        // 新子段的最大子段和,其子段有可能穿过左右区间,或左区间,或右区间
        int m = Math.max(leftT.rSum + rightT.lSum, Math.max(leftT.mSum, rightT.mSum));
        return new wtevTree(l, r, i, m);
    }

    // 递归建立和获得输入区间所有子段的结构
    wtevTree getInfo(int[] nums, int left, int right) {
        if (left == right) // 若区间长度为1,其四个子段均为其值
            return new wtevTree(nums[left], nums[left], nums[left], nums[left]);
        int mid = (left + right) >> 1;// 获得中间点mid,右移一位相当于除以2,运算更快
        wtevTree leftT = getInfo(nums, left, mid);
        wtevTree rightT = getInfo(nums, mid + 1, right);//mid+1,左右区间没有交集。
        return pushUp(leftT, rightT);//递归结束后,做最后一次合并
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                p.next = list1;
                list1 = list1.next;
            }else{
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        if(list1 == null){
            p.next = list2;
        }else{
            p.next = list1;
        }
        return head.next;
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //终止条件
        if(list1 == null){
            return list2;
        }
        //终止条件
        if(list2 == null){
            return list1;
        }
        if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans = new int[2];
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                if(nums[i] + nums[j] == target){
                    ans[0] = i;
                    ans[1] = j;
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            if(!map.containsKey(nums[i])){
                map.put(temp, i);
            }else{
                ans[0] = i;
                ans[1] = map.get(nums[i]);
                break;
            }
        }
        return ans;
    }
}

class Singleton{
    // 私有构造函数
    private Singleton() {}

    private static Singleton LazyMan;

    // 加锁保证LazyMan只实例化一次，时间换空间
    public static synchronized Singleton getInstance(){
        if (LazyMan == null) {
            LazyMan = new Singleton();
        }
        return LazyMan;
    }
}

class Singleton {
    // 私有构造函数
    private Singleton() {}
    // volatile关键字禁止指令重排，如果不加，可能会出现return为null的情况
    private volatile static Singleton LazyMan;

    public static Singleton getInstance(){
        // 已有实例则直接返回，不走锁
        if (LazyMan == null) {
            // 仅在没生成实例时加锁控制，使并发访问串行化
            synchronized (Singleton.class) {
                // 多个线程会按序执行到此处，需要再次检查是否已实例化
                if (LazyMan == null) {
                    LazyMan = new Singleton();
                }
            }
        }
        return LazyMan;
    }
}

class Singleton{
    // 私有构造函数
    private Singleton() {}
    // 类加载时就实例化对象
    private static Singleton Hungry = new Singleton();
    
    public static Singleton getInstance(){
        return Hungry;
    }
}

class Singleton{
    // 私有构造函数
    private Singleton() {}

    // 静态内部类
    private static class SingletonHolder {
        private static Singleton Hungry = new Singleton();
    }
    public static Singleton getInstance(){
        return SingletonHolder.Hungry;
    }
}

public class Main {
    private int num;
    private static Object Lock = new Object();

    private void printABC(String name, int targetNum){
        synchronized (Lock){
            while (num % 3 != targetNum){
                try {
                    Lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            num++;
            System.out.print(name);
            Lock.notifyAll();
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        new Thread(() -> {
            main.printABC("A", 0);
        }, "ThreadA").start();
        new Thread(() -> {
            main.printABC("B", 1);
        }, "ThreadB").start();
        new Thread(() -> {
            main.printABC("C", 2);
        }, "ThreadC").start();
    }
}

public class Main {
    private int num;
    private static Object Lock = new Object();

    private void printABC(String threadName, int targetNum){
        for (int i = 0; i < 10; i++) {
            synchronized (Lock){
                while (num % 3 != targetNum){
                    try {
                        Lock.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                num++;
                System.out.print(threadName);
                Lock.notifyAll();
            }
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        new Thread(() -> {
            main.printABC("A", 0);
        }, "ThreadA").start();
        new Thread(() -> {
            main.printABC("B", 1);
        }, "ThreadB").start();
        new Thread(() -> {
            main.printABC("C", 2);
        }, "ThreadC").start();
    }
}

public class Main {
    private int num = 1;
    private static Object Lock = new Object();

    private void printOddEven(){
        synchronized (Lock){
            while (num <= 20){
                //线程Odd先拿到锁
                System.out.print(Thread.currentThread().getName() + ":");
                System.out.println(num++);
                try {
                    Lock.notifyAll();   //唤醒Even线程
                    Lock.wait();        //阻塞Odd线程
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            Lock.notifyAll();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Main main = new Main();
        new Thread(() -> {
            main.printOddEven();
        }, "Odd").start();
        //确保Odd线程比Even线程先拿到锁
        Thread.sleep(10);
        new Thread(() -> {
            main.printOddEven();
        }, "Even").start();
    }
}

public class Main {
    private int num;
    private static Object Lock = new Object();
    private int maxNum = 20;
    private int N = 4;

    private void printMaxNum(int targetNum){
        while (true){
            synchronized (Lock){
                while (num % N != targetNum){
                    if (num >= maxNum){
                        break;
                    }
                    try {
                        Lock.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                if (num >= maxNum){
                    break;
                }
                num++;
                System.out.println(Thread.currentThread().getName() + ":" + num);
                Lock.notifyAll();
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Main main = new Main();
        new Thread(() -> {
            main.printMaxNum(0);
        }, "T1").start();
        new Thread(() -> {
            main.printMaxNum(1);
        }, "T2").start();
        new Thread(() -> {
            main.printMaxNum(2);
        }, "T3").start();
        new Thread(() -> {
            main.printMaxNum(3);
        }, "T4").start();
    }
}

public class Main {
    static class printABC implements Runnable{
        private Thread beforeThread;
        public printABC(Thread beforeThread){
            this.beforeThread = beforeThread;
        }

        @Override
        public void run() {
            //判断前面是否有线程
            if (beforeThread != null){
                try {
                    beforeThread.join();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            System.out.println(Thread.currentThread().getName());
        }
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10; i++) {
            Thread T1 = new Thread(new printABC(null), "A");
            Thread T2 = new Thread(new printABC(T1), "B");
            Thread T3 = new Thread(new printABC(T2), "C");
            T1.start();
            T2.start();
            T3.start();
            Thread.sleep(10);       //保证三个为一组
        }
    }
}

public class Main {
    private static int num;
    private Lock lock = new ReentrantLock();

    private void printABC(int targetNum){
        for (int i = 0; i < 10; ) {
            lock.lock();
            if (num % 3 == targetNum){
                System.out.print(Thread.currentThread().getName());
                num++;
                i++;
            }
            lock.unlock();
        }
    }

    public static void main(String[] args){
        Main main = new Main();
        new Thread(() -> {
            main.printABC(0);
        }, "A").start();
        new Thread(() -> {
            main.printABC(1);
        }, "B").start();
        new Thread(() -> {
            main.printABC(2);
        }, "C").start();
    }
}

class ListNode{
    int value;
    ListNode next;
    public ListNode(){};
    public ListNode(int value){
        this.value = value;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        ListNode head = buildList(nums);
        //打印链表
        while (head != null){
            System.out.print(head.value);
            head = head.next;
        }
    }
    //根据数组建立链表
    public static ListNode buildList(int[] arr){
        ListNode head = new ListNode(-1);
        ListNode p = head;
        for (int i = 0; i < arr.length; i++) {
            ListNode q = new ListNode(arr[i]);
            p.next = q;
            p = p.next;
        }
        return head.next;
    }
}

class TreeNode{
    int value;
    TreeNode left;
    TreeNode right;

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        TreeNode root = buildTree(nums);
    }

    //输入数组建立二叉树
    public static TreeNode buildTree(int[] arr){
        if (arr == null || arr.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(arr[0]);
        //借助队列来实现
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        //从数组中两个两个一读，代表该节点的左右节点
        for (int i = 1; i < arr.length; i += 2) {
            //从队列中出队，拼接该节点的左右子节点
            TreeNode node = queue.poll();
            //连上该节点的左子节点
            if (arr[i] != -1){
                node.left = new TreeNode(arr[i]);
                //将新加的节点入队
                queue.offer(node.left);
            }
            //连上该节点的右子节点，这里一定要先保证i + 1不会越界
            if (i + 1 < arr.length && arr[i + 1] != -1){
                node.right = new TreeNode(arr[i + 1]);
                queue.offer(node.right);
            }
        }
        return root;
    }
}

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // 创建一个数组来保存每个节点的引用
        TreeNode[] nodes = new TreeNode[n + 1];
        for (int i = 1; i <= n; i++) {
            nodes[i] = new TreeNode(i);
        }
        for (int i = 0; i < n - 1; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            // 根据输入的边关系连接节点
            if (nodes[u].left == null) {
                nodes[u].left = nodes[v];
            } else {
                nodes[u].right = nodes[v];
            }
        }
        // 假设根节点是节点1
        TreeNode root = nodes[1];
    }
}