class Solution {
public int[] sortArray(int[] nums) {
sort(nums, 0, nums.length-1);
return nums;
}
public void sort(int[] nums, int lo, int hi){
if(lo > hi){
return ;
}
int j = partition(nums, lo, hi);
sort(nums, lo, j-1);
sort(nums, j+1, hi);
}
public int partition(int[] nums, int lo, int hi){
int pivot = nums[lo];
int i = lo+1, j = hi;
while(i <= j){
while(i < hi && nums[i] < pivot){
i++;
}
while(j > lo && nums[j] > pivot){
j--;
}
if(i >= j){
break;
}
swap(nums, i, j);
}
swap(nums, lo, j);
return j;
}
public void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
class Solution {
int[] temp;
public int[] sortArray(int[] nums) {
temp = new int[nums.length];
sort(nums, 0, nums.length-1);
return nums;
}
public void sort(int[] nums, int low, int high){
if(low >= high){
return;
}
int mid = low + (high-low)/2;
sort(nums, low, mid);
sort(nums, mid+1, high);
merge(nums, low, mid, high);
}
public void merge(int[] nums, int low, int mid, int high){
for(int i = low; i <= high ;i++){
temp[i] = nums[i];
}
int i = low, j = mid+1;
for(int k = low;k <= high;k++){
if(i == mid + 1){
nums[k] = temp[j++];
}else if(j == high+1){
nums[k] = temp[i++];
}else if(temp[i] > temp[j]){
nums[k] = temp[j++];
}else {
nums[k] = temp[i++];
}
}
}
}
懒汉式：
双重校验，线程安全且在多线程情况下能保持高性能。
public class Singleton {
private volatile static Singleton singleton;
private Singleton (){}
public static Singleton getSingleton() {
if (singleton == null) {
synchronized (Singleton.class) {
if (singleton == null) {
singleton = new Singleton();
}
}
}
return singleton;
}
}
饿汉式：
线程安全，在程序启动时直接运行加载，但是可能造成资源浪费。
public class Singleton {
private static Singleton instance = new Singleton();
private Singleton (){}
public static Singleton getInstance() {
return instance;
}
}
public class LRUCache {
class LinkedNode {
int key;
int value;
LinkedNode prev;
LinkedNode next;
}
private void addNode(LinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(LinkedNode node){
LinkedNode prev = node.prev;
LinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void moveToHead(LinkedNode node){
removeNode(node);
addNode(node);
}
private LinkedNode popTail() {
LinkedNode res = tail.prev;
removeNode(res);
return res;
}
private Hashtable<Integer, LinkedNode> cache = new Hashtable<Integer,LinkedNode>();
private int size;
private int capacity;
private LinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new LinkedNode();
tail = new LinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
LinkedNode node = cache.get(key);
if (node == null) return -1;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
LinkedNode node = cache.get(key);
if(node == null) {
LinkedNode newNode = new LinkedNode();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addNode(newNode);
++size;
if(size > capacity) {
LinkedNode tail = popTail();
cache.remove(tail.key);
--size;
}
} else {
node.value = value;
moveToHead(node);
}
}
}
class ProducerConsumer {
private int maxSize;
private LinkedList<Object> storage;
public ProducerConsumer(int size) {
this.maxSize = size;
storage = new LinkedList<>();
}
public synchronized void put() throws InterruptedException {
while (storage.size() == maxSize) {
storage.wait();
}
storage.add(new Object());
storage.notifyAll();
}
public synchronized void take() throws InterruptedException {
while (storage.size() == 0) {
storage.wait();
}
System.out.println(storage.remove());
storage.notifyAll();
}
}
public class BlockingQueue<E> {
/**
* 阻塞队列最大容量
*/
private int size;
/**
* 队列底层实现
*/
LinkedList<E> list = new LinkedList<>();
ReentrantLock lock = new ReentrantLock();
/**
* 队列满的等待条件
*/
Condition full = lock.newCondition();
/**
* 队列空的等待条件
*/
Condition empty = lock.newCondition();
public BlockingQueue(int size) {
this.size = size;
}
public void enqueue(E e) throws InterruptedException {
lock.lock();
try {
// 队列满了，就在full条件上进行等待
while (list.size() == size){
full.await();
}
list.add(e);
System.out.println("入队："+e);
// 入队之后，就通知在empty条件下等待的线程
empty.signal();
} finally {
lock.unlock();
}
}
public E dequeue() throws InterruptedException {
E e;
lock.lock();
try {
// 队列为空，就在空条件上等待
while (list.size() == 0){
empty.await();
}
e = list.removeFirst();
System.out.println("出队："+e);
// 出队之后，就通知在full条件下等待的线程
full.signal();
return e;
} finally {
lock.unlock();
}
}
}
三个不同的线程 A、B、C 将会共用一个 Foo 实例。
线程 A 将会调用 first() 方法
线程 B 将会调用 second() 方法
线程 C 将会调用 third() 方法
class Foo {
private int i = 1;
private int n = 3;
public Foo() {
}
public void first(Runnable printFirst) throws InterruptedException {
while(i <= n){
synchronized(this){
if(i <= n && i % 3 == 1){
printFirst.run();
i++;
}
}
}
}
public void second(Runnable printSecond) throws InterruptedException {
while(i <= n){
synchronized(this){
if(i <= n && i % 3 == 2){
printSecond.run();
i++;
}
}
}
}
public void third(Runnable printThird) throws InterruptedException {
while(i <= n){
synchronized(this){
if(i <= n && i % 3 == 0){
printThird.run();
i++;
}
}
}
}
}
class Foo {
private int i = 1;
private int n = 3;
private Lock lock = new ReentrantLock();
public Foo() {
}
public void first(Runnable printFirst) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i <= n && i % 3 == 1){
printFirst.run();
i++;
}
}finally{
lock.unlock();
}
}
}
public void second(Runnable printSecond) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i <= n && i % 3 == 2){
printSecond.run();
i++;
}
}finally{
lock.unlock();
}
}
}
public void third(Runnable printThird) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i <= n && i % 3 == 0){
printThird.run();
i++;
}
}finally{
lock.unlock();
}
}
}
}
编写一个可以从 1 到 n 输出代表这个数字的字符串的程序，但是：
如果这个数字可以被 3 整除，输出 “fizz”。
如果这个数字可以被 5 整除，输出 “buzz”。
如果这个数字可以同时被 3 和 5 整除，输出 “fizzbuzz”。
class FizzBuzz {
private int n;
private int i = 1;
private Lock lock = new ReentrantLock();
public FizzBuzz(int n) {
this.n = n;
}
// printFizz.run() outputs "fizz".
public void fizz(Runnable printFizz) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i <= n && i % 3 == 0 && i % 5 != 0){
printFizz.run();
i++;
}
}finally{
lock.unlock();
}
}
}
// printBuzz.run() outputs "buzz".
public void buzz(Runnable printBuzz) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i <= n && i % 3 != 0 && i % 5 == 0){
printBuzz.run();
i++;
}
}finally{
lock.unlock();
}
}
}
// printFizzBuzz.run() outputs "fizzbuzz".
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i <= n && i % 3 == 0 && i % 5 == 0){
printFizzBuzz.run();
i++;
}
}finally{
lock.unlock();
}
}
}
// printNumber.accept(x) outputs "x", where x is an integer.
public void number(IntConsumer printNumber) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i <= n && i % 3 != 0 && i % 5 != 0){
printNumber.accept(i);
i++;
}
}finally{
lock.unlock();
}
}
}
}
class FizzBuzz {
private int n;
private int i = 1;
private Lock lock = new ReentrantLock();
private Condition condition = lock.newCondition();
public FizzBuzz(int n) {
this.n = n;
}
// printFizz.run() outputs "fizz".
public void fizz(Runnable printFizz) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i % 3 == 0 && i % 5 != 0){
printFizz.run();
i++;
condition.signalAll();
}else{
condition.await();
}
}finally{
lock.unlock();
}
}
}
// printBuzz.run() outputs "buzz".
public void buzz(Runnable printBuzz) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i % 3 != 0 && i % 5 == 0){
printBuzz.run();
i++;
condition.signalAll();
}else{
condition.await();
}
}finally{
lock.unlock();
}
}
}
// printFizzBuzz.run() outputs "fizzbuzz".
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i % 3 == 0 && i % 5 == 0){
printFizzBuzz.run();
i++;
condition.signalAll();
}else{
condition.await();
}
}finally{
lock.unlock();
}
}
}
// printNumber.accept(x) outputs "x", where x is an integer.
public void number(IntConsumer printNumber) throws InterruptedException {
while(i <= n){
lock.lock();
try{
if(i % 3 != 0 && i % 5 != 0){
printNumber.accept(i);
i++;
condition.signalAll();
}else{
condition.await();
}
}finally{
lock.unlock();
}
}
}
}
觉得本博客有用的客官，可以给个点赞+收藏哦！ 嘿嘿
喜欢本系列博客的可以关注下，以后除了会继续更新面试手撕代码文章外，还会出其他系列的文章！