分类 JAVA 下的文章

https://leetcode-cn.com/problems/building-h2o/comments/
解题关键:
用两个信号量 一个信号量吞1个 一个信号量吞2个那么我们只需要让h的信号量一开始给他有两位 o的信号量有0位即可, 然后h线程每次开始则吞一个h的信号量 释放o一个信号量 则o线程则要吞两个o信号量 释放两个h信号量。

import java.util.concurrent.*;
class H2O {
    private Semaphore a,b;
    public H2O() {
        a = new Semaphore(2);
        b = new Semaphore(0);
    }

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        a.acquire();
        releaseHydrogen.run();
        b.release();
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        b.acquire(2);
        releaseOxygen.run();
        a.release(2);
    }
}

https://leetcode-cn.com/problems/print-zero-even-odd/submissions/
关键: 采用Semaphore 每个线程都用for循环 来维护i值打印 然后ZeroEvenOdd决定啥时候调用奇偶线程。

import java.util.concurrent.*;
class ZeroEvenOdd {
    private int n;
    private Semaphore s,s1,s2;
    public ZeroEvenOdd(int n) {
        this.n = n;
         s = new Semaphore(1);
        s1 = new Semaphore(0);
        s2 = new Semaphore(0);
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        for(int i = 1; i<=n; i++){
            s.acquire();
            printNumber.accept(0);
             if((i&1) == 0)
                s1.release();
            else
                s2.release();
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        for(int i = 2; i<=n; i += 2){
            s1.acquire();
            printNumber.accept(i);
            s.release();
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        for(int i = 1; i<=n; i += 2){
            s2.acquire();
            printNumber.accept(i);
            s.release();
        }
    }
}

参考昨天的:https://leetcode-cn.com/problems/print-foobar-alternately/submissions/

class FooBar {
    private int n;
    private Object object = new Object();
    private boolean f = false;
    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            synchronized(object) {
                if(f){//如果第二个进程没执行完则等待
                    object.wait();
                }
                printFoo.run();
                f = true;
                object.notify();
            }
            // printFoo.run() outputs "foo". Do not change or remove this line.
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            synchronized(object) {
                if(!f){//如果之前进程没执行完则等待
                    object.wait();
                }
                printBar.run();
                f = false;
                object.notify();
            }
        }
    }
}

https://leetcode-cn.com/problems/print-in-order/submissions/
构造执行屏障实现
解题关键:
我们可以用一个lock来做一个锁对象 三个函数都对他进行synchronized 然后函数2、3在synchronized里面则用while(!firstFinished){lock.wait()}, while(!secondFinished){lock.wait()}来循环判断是否执行完毕 如果未执行完毕则继续调用wait 当调用wait时当前线程会阻塞 等待其他线程调用lock.notify或者lock.notifyAll()来唤醒 这也是为什么需要while 因为如果用lock.notifyAll的话他会全部唤醒 需要再走一遍判断。

class Foo {
    private boolean firstFinished;
    private boolean secondFinished;
    private Object lock = new Object();
    public Foo() {
        
    }

    public void first(Runnable printFirst) throws InterruptedException {
        synchronized (lock) {
            printFirst.run();
            firstFinished = true;
            lock.notifyAll();
        }
        // printFirst.run() outputs "first". Do not change or remove this line.
    }

    public void second(Runnable printSecond) throws InterruptedException {
        
        // printSecond.run() outputs "second". Do not change or remove this line.
        synchronized(lock) {
            while (!firstFinished) {
                lock.wait();
            }
            printSecond.run();
            secondFinished = true;
            lock.notifyAll();
        }
        
    }

    public void third(Runnable printThird) throws InterruptedException {
        synchronized(lock) {
            while(!secondFinished){
                lock.wait();
            }
            printThird.run();
        }
    }
}

我们每次都把最大的值翻到最后则就把问题简化 直到无即可。
先从从尾部遍历到头部取最大的值 然后翻转前i项则 最大的值到了头部 然后我们翻转A.length则最大值到了最右边依次类推即可得到最终结果。

class Solution {
    private int[] reverse(int[] A, int k){
        int[] res = new int[A.length];
        int index = 0;
        for(int i = k; i>=0; i--){
            res[index++] = A[i];
        }
        for(int i = k+1; i<A.length; i++){
            res[index++] = A[i];
        }
        return res;
    }
    public List<Integer> pancakeSort(int[] A) {
        List<Integer> res = new ArrayList();
        for(int i = A.length - 1; i>=0; i--){
            //找最大的然后煎饼两次
            int max = 0;
            for(int j = 0; j <= i; j++){
                if(A[j] >= A[max]){
                    max = j;
                }
            }
            res.add(max + 1);
            res.add(i + 1);
            A = reverse(A, max);
            A = reverse(A, i);
        }
        return res;
    }
}