手撕算法

快速排序

private static void quickSort(int[] nums){
    sort(nums,0,nums.length-1);
}

private static void sort(int[] nums, int l,int r){
    if(l>=r){return;}
    int m = partition(nums, l, r);
    sort(nums,l,m-1);
    sort(nums,m+1,r);
}
private static int partition(int[] nums,int left,int right){
    swap(nums,(int)(Math.random()*(right-left+1))+left,left); //important
    int l=left+1,r=right;
    while(true){
        while(l<=right && nums[l]<=nums[left]){
            l++;
        }
        while(r>left && nums[r]>=nums[left]){
            r--;
        }
        if(l>=r){break;}
        swap(nums,l,r);
    }
    swap(nums,left,r);
    return r;
}
private static void swap(int[] nums,int i,int j){
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}

LRU

@SuppressWarnings("FieldMayBeFinal")
public class LRUCache<K,V>{
	private Node<K,V> head=new Node<>();
	private Node<K,V> tail=new Node<>();
	private Map<K,Node<K,V>> map=new HashMap<>();
	private int remain; //剩余容量

	public LRUCache(int capacity){
		remain=capacity;
		head.next=tail;
		tail.pre=head;
	}

	public V get(K key){
		Node<K,V> node = map.get(key);
		if(node==null){return null;}
		//在链表中删除
		node.pre.next=node.next;
		node.next.pre=node.pre;
		//插入头部
		node.next=head.next;
		node.pre=head;
		head.next.pre=node;
		head.next=node;
		return node.value;
	}

	//返回key对应的value
	public V remove(K key){
		Node<K,V> node = map.remove(key);
		if(node==null){return null;}
		//在链表中删除
		node.pre.next=node.next;
		node.next.pre=node.pre;
		remain++;
		return node.value;
	}

	//返回旧value
	public V put(K key, V value){
		if(get(key)!=null){ //顺便更新key的位置
			Node<K,V> node = map.get(key);
			V oldVal=node.value;
			node.value=value;
			return oldVal;
		}else if(remain==0){ //容量已满，删除尾部节点
			remove(tail.pre.key); //就是因为这一步，才需要在Node中存key
		}
		//在链表头部插入节点
		Node<K,V> node = new Node<>(key, value, head, head.next);
		head.next.pre=node;
		head.next=node;
		map.put(key,node);
		remain--;
		return null;
	}

	private static class Node<K,V>{
		private K key;
		private V value;
		private Node<K,V> pre,next;

		private Node(){}

		private Node(K key, V value, Node<K,V> pre, Node<K,V> next){
			this.key=key;
			this.value=value;
			this.pre=pre;
			this.next=next;
		}
	}
}

堆

public class Heap{
	private final int[] heap;
	private int size=0;

	public Heap(int capacity){
		size=capacity;
		heap=new int[size+1];
	}

	/**
	 * O(n)建堆
	 */
	public Heap(int[] nums){
		size=nums.length;
		heap=new int[size+1];
		System.arraycopy(nums,0,heap,1,size);
		for(int i=size>>1;i>0;i--){
			sink(i);
		}
	}

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

	public int deleteMin(){
		int minVal=heap[1];
		swap(1, size--);
		sink(1);
		return minVal;
	}

	public void add(int val){
		heap[++size]=val;
		int k=size;
		while(k>1){//上浮
			if(heap[k>>1]>heap[k]){
				swap(k>>1,k);
				k>>=1;
			}else{return;}
		}
	}

	private void sink(int k){
		while(2*k<=size){//下沉
			//1.找出子节点最小值
			int child=2*k;
			//存在右节点
			if(2*k+1<=size && heap[2*k+1]<heap[2*k]) {
				child=2*k+1;
			}
			//2.如果k结点大于子节点的最小值，则交换两者(下沉一层)
			if(heap[k]>heap[child]){
				swap(k,child);
				//3.结点k移动到结点min处
				k=child;
			}else{return;}
		}
	}
}