class Solution {
    public int equalPairs(int[][] grid) {
        int ylen = grid.length;
        int xlen = grid[0].length;
        String[] rows = new String[ylen];
        String[] cols = new String[xlen];
        Map<String, List<Integer>> map = new HashMap<>(); 
        for (int y = 0; y < ylen;y++) {
            StringBuilder sb = new StringBuilder();
            for (int x = 0; x < xlen;x++) {
                sb.append(grid[y][x]).append(",");
            }
            String s = sb.toString();
            if (!map.containsKey(s)) {
                map.put(s, new ArrayList<>());
            }
            map.get(s).add(y);
        }
        
        int count = 0;
        for (int x = 0; x < xlen;x++) {
            StringBuilder sb = new StringBuilder();
            for (int y = 0; y < ylen;y++) {
                sb.append(grid[y][x]).append(",");
            }
            String s = sb.toString();
            if (map.containsKey(s)) {
                count += map.get(s).size();
            }
        }
        return count;
    }
}

    class FoodRatings {

         class Food {
            String name;
            String cuisines;
            int rate;

            public Food(String name, String cuisines, int rate) {
                this.name = name;
                this.cuisines = cuisines;
                this.rate = rate;
            }
        }
        
        Map<String, Queue<Food>> queues;
        Map<String, Food> nowFoodMap = new HashMap<>();
        public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
            int len = foods.length;
            queues = new HashMap<>();
            for (int i = 0;i<len;i++) {
                Food food = new Food(foods[i], cuisines[i], ratings[i]);
                nowFoodMap.put(foods[i], food);

                if (!queues.containsKey(cuisines[i])) {
                    queues.put(cuisines[i], new PriorityQueue<>((a,b)->(
                            a.rate != b.rate ? (b.rate - a.rate): (a.name.compareTo(b.name)))));
                }
                queues.get(cuisines[i]).offer(food);
            }
        }

        public void changeRating(String food, int newRating) {
            String cu = nowFoodMap.get(food).cuisines;
            Food food1 = new Food(food, cu, newRating);
            nowFoodMap.put(food, food1);
            queues.get(cu).offer(food1);
        }

        public String highestRated(String cuisine) {
            Queue<Food> queue = queues.get(cuisine);
            while (!queue.isEmpty()) {
                Food food = queue.peek();
                if (food != nowFoodMap.get(food.name)) {
                    queue.poll();
                } else {
                    return food.name;
                }
            }
            return null;
        }
    }


/**
 * Your FoodRatings object will be instantiated and called as such:
 * FoodRatings obj = new FoodRatings(foods, cuisines, ratings);
 * obj.changeRating(food,newRating);
 * String param_2 = obj.highestRated(cuisine);
 */

class Solution {
    public long countExcellentPairs(int[] nums, int k) {
        Set<Integer> set = Arrays.stream(nums).mapToObj(Integer::valueOf).collect(Collectors.toSet());

        int[] ontCounts = new int[set.size()];
        int[] newNums = new int[set.size()];
        int t = 0;
        for (int s : set) {
            newNums[t++] = s;
        }
        nums = newNums;

        for (int i = 0; i < nums.length;i++) {
            ontCounts[i] = Integer.bitCount(nums[i]);
        }
        Arrays.sort(ontCounts);

        long result = 0;
        for (int i = 0; i < nums.length;i++) {
            int oneCount = ontCounts[i];
            int needOneCount = k - oneCount;

            int left = 0, right = nums.length;
            while (left < right) {
                int mid =  left + (right - left)/2;
                if (ontCounts[mid] < needOneCount) {
                    left = mid+1;
                } else if (ontCounts[mid] >= needOneCount){
                    right = mid;
                } else {
                    break;
                }
            }
            int select = right;
            result += Math.max(0, ontCounts.length - select);
        }
        return result;
    }
}

long result = 0;
int left = 0, right = ontCounts.length - 1;
for (;left<ontCounts.length;left++) {
    while (right >=0 && ontCounts[left] + ontCounts[right] >= k) {
        right--;
    }
    result += (ontCounts.length - 1 - right);
}

private volatile int state;
protected final int getState() {
    return state;
}
protected final void setState(int newState) {
    state = newState;
}

// cas方法
compareAndSetState(int oldState, int newState);

private Node enq(final Node node) {
    //多次尝试，直到成功为止
    for (;;) {
        Node t = tail;
        //tail不存在，设置为首节点
        if (t == null) {
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            //设置为尾节点
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        // 发现中断过，则触发中断异常
        selfInterrupt();
}

protected final boolean tryAcquire(int acquires){
 final Thread current = Thread.currentThread();
            int c = getState();
            // state==0代表当前没有锁，可以进行获取
            if (c == 0) {
            	// 非公平才有的判断，会判断是否还有前驱节点，直接自己为头节点了或者同步队列空了才会继续后面的锁的获取操作
                if (!hasQueuedPredecessors() 
                     //CAS设置state为acquires，成功后标记exclusiveOwnerThread为当前线程
                    && compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            // 当前占有线程等于自己，代表重入
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                // 出现负数，说明溢出了
                if (nextc < 0) // 
                    throw new Error("Maximum lock count exceeded");
                // 因为是重入操作，可以直接进行state的增加，所以不需要CAS
                setState(nextc);
                return true;
            }
            return false;
}

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    // Try the fast path of enq; backup to full enq on failure
    Node pred = tail;
    if (pred != null) {
        node.prev = pred;
        // 通过CAS竞争队尾
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    // 竞争队尾失败，于是进行CAS频繁循环竞争队尾
    enq(node);
    return node;
}

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

final boolean acquireQueued(final Node node, int arg) {
    // 标识是否获取资源失败                
    boolean failed = true;
    try {
        // 标识当前线程是否被中断过
        boolean interrupted = false;
        // 自旋操作
        for (;;) {
            // 获取当前节点的前继节点
            final Node p = node.predecessor();
            // 如果前继节点为头结点，说明排队马上排到自己了，可以尝试获取资源，若获取资源成功，则执行下述操作
            if (p == head && tryAcquire(arg)) {
                // 将当前节点设置为头结点
                setHead(node);
                // 说明前继节点已经释放掉资源了，将其next置空，好让虚拟机提前回收掉前继节点
                p.next = null; // help GC
                // 获取资源成功，修改标记位
                failed = false;
                // 返回中断标记
                return interrupted;
            }
            // 若前继节点不是头结点，或者获取资源失败，
            // 则需要判断是否需要阻塞该节点持有的线程
            // 若可以阻塞，则继续执行parkAndCheckInterrupt()函数，
            // 将该线程阻塞直至被唤醒
            // 唤醒后会检查是否已经被中断，若返回true，则将interrupted标志置于true
            if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        // 最终获取资源失败，则当前节点放弃获取资源
        if (failed)
            cancelAcquire(node);

    }
 }

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    // 获取前继节点的等待状态
    int ws = pred.waitStatus;
    // 如果等待状态为Node.SIGNAL(-1)，则直接返回true即可以阻塞
    // 因为这说明前继节点完成资源的释放或者中断后，会主动唤醒后继节点的（这也即是signal信号的含义），因此方法外面不用再反复CAS了，直接阻塞吧
    if (ws == Node.SIGNAL) return true;

    // 如果前继节点的等待值大于0即CANCELLED（1）,说明前继节点的线程发生过cancel动作
    // 那就继续往前遍历，直到当前节点的前继节点的状态不为cancel
    if (ws > 0) {
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        // 前继节点的等待状态不为SIGNAL(-1)，也不为Cancel(1)
        // 那么只能是PROPAGATE(-3)或者CONDITION(-2)或者INITIAL（0）
        // 直接设置成SIGNAL，下一次还没CAS成功，就直接睡觉了
        // 因此在前面所有节点没辩护的情况下， 最多一次之后就会返回true让外面阻塞
       compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

private final boolean parkAndCheckInterrupt() {
             LockSupport.park(this);
    		 // 确认是否是中断导致的park结束，并清除中断标记
             return Thread.interrupted();
}

public static void park(Object blocker) {
    Thread t = Thread.currentThread();
    setBlocker(t, blocker);
    UNSAFE.park(false, 0L);
    setBlocker(t, null);
}

reentrantLock.lock();
try {
    System.out.println("t1");
    TimeUnit.SECONDS.sleep(30);
} catch (InterruptedException e) {
    e.printStackTrace();
} finally {
    reentrantLock.unlock();
}

public final boolean release(int arg) {
    // 是否释放成功，tryRelease是子类要实现的方法
    if (tryRelease(arg)) {
        Node h = head;
        // 判断头节点是否正在阻塞中，是的话唤醒
        if (h != null && h.waitStatus != 0)
            // 唤醒头节点
            unparkSuccessor(h);
        return true;
    }
    return false;
}

protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
        free = true;
     	// 设置当前占用线程为null
        setExclusiveOwnerThread(null);
    }
    // 不需要CAS，因为只有持有锁的人才能做释放，不担心竞争
    setState(c);
    return free;
}

static final class FairSync extends Sync {
    private static final long serialVersionUID = -3000897897090466540L;

    final void lock() {
        acquire(1);
    }

Sync(int permits) {
    setState(permits);
}

protected int tryAcquireShared(int acquires) {
    for (;;) {
        // 队头判断，公平锁核心
        if (hasQueuedPredecessors())
            return -1;
        int available = getState();
        int remaining = available - acquires;
        // 信号量不足，直接返回负数
        if (remaining < 0 ||
            // 能抢成功，返回修改后的值，抢失败则for循环继续
            compareAndSetState(available, remaining))
            return remaining;
    }
}

if (current == getExclusiveOwnerThread()) {
    int nextc = c + acquires;
    // 出现负数，说明溢出了
    if (nextc < 0) // 
        throw new Error("Maximum lock count exceeded");
    // 因为是重入操作，可以直接进行state的增加，所以不需要CAS
    setState(nextc);
    return true;
}

protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
        // 只有资源数为0才会解锁
        // 才算释放成功，否则这锁还是占住了
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

Lock lock = new ReentrantLock();
Condition condition = lock.newCondition();
public void conditionWait() throws InterruptedException {
    lock.lock();
    try {
        	// if(xxxx)判断不满足条件，等待，释放锁
            condition.await();
    } finally {
            lock.unlock();
    }
}
public void conditionSignal() throws InterruptedException {
    lock.lock();
    try {
        	// 做完事情了，通知condition上等待的开始抢占
            condition.signal();
    } finally {
            lock.unlock();
    }
}

public final void await() throws InterruptedException {
    if (Thread.interrupted())
        throw new InterruptedException();
    // 添加本线程到等待队列尾部
    Node node = addConditionWaiter();
    // 释放锁，唤醒同步队列中的后继节点
    int savedState = fullyRelease(node);
    int interruptMode = 0;
    // 如果已经在同步队列中了，说明被成功sign唤醒
    while (!isOnSyncQueue(node)) {
        // 阻塞挂起
        LockSupport.park(this);
        // 确认是否需要中断时就退出
        if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
            break;
    }
    // 在同步队列中，那就按同步队列的规则在队列中用CAS竞争同步状态
    if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
        interruptMode = REINTERRUPT;
    // 清理已经不是CONDITION状态的等待队列节点
    if (node.nextWaiter != null) 
        unlinkCancelledWaiters();
    if (interruptMode != 0)
        reportInterruptAfterWait(interruptMode);
}

do {
    Node next = first.nextWaiter;
    first.nextWaiter = null;
    transferForSignal(first);
    first = next;
} while (first != null);

public class Cache {
    static Map<String, Object> map = new HashMap<String, Object>();
    static ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
    static Lock r = rwl.readLock();
    static Lock w = rwl.writeLock();
    // 获取一个key对应的value
    public static final Object get(String key) {
            // 
        	r.lock();
            try {
                    return map.get(key);
            } finally {
                    r.unlock();
            }
    }
    // 设置key对应的value，并返回旧的value
    public static final Object put(String key, Object value) {
            w.lock();
            try {
                    return map.put(key, value);
            } finally {
                    w.unlock();
            }
    }
    // 清空所有的内容
    public static final void clear() {
            w.lock();
            try {
                    map.clear();
            } finally {
                    w.unlock();
            }
    }
}

protected final boolean tryAcquire(int acquires) {
    Thread current = Thread.currentThread();
    int c = getState();
    int w = exclusiveCount(c);
    if (c != 0) {
            // 存在读锁或者当前获取线程不是已经获取写锁的线程
            if (w == 0 || current != getExclusiveOwnerThread())
                    return false;
            if (w + exclusiveCount(acquires) > MAX_COUNT)
                    throw new Error("Maximum lock count exceeded");
            setState(c + acquires);
            return true;
    }
    if (writerShouldBlock() || !compareAndSetState(c, c + acquires)) {
            return false;
    }
    setExclusiveOwnerThread(current);
    return true;
}

protected final int tryAcquireShared(int unused) {
    // 一直处理，读锁竞争都是CAS，不存在阻塞！
    for (;;) {
            int c = getState();
            int nextc = c + (1 << 16);
            if (nextc < c)
                    throw new Error("Maximum lock count exceeded");
            // 有写锁且不是重入，返回-1获取失败
            if (exclusiveCount(c) != 0 && owner != Thread.currentThread())
                    return -1;
            // cas修改值
            if (compareAndSetState(c, nextc)) 
                    return 1;
    }
}

// 返回当前邮戳，这个方法不会阻塞写方法！
long stamp = lock.tryOptimisticRead();
// 校验此时是否邮戳不匹配
if(!lock.validate(stamp)){
    // 如果不匹配，说明发生了写操作！读动作最好等写动作结束后再触发！
	// 锁升级 为悲观读readLock
    stamp = stampedLock.readLock();//锁升级为悲观读
    // 处理...
    
    // 解锁
    stampedLock.unlockRead(stamp);
}