栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

左程云算法课笔记(持续更新中...)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

左程云算法课笔记(持续更新中...)

B站课程连接

排序 交换数组中的两个数
//常规方法
public static void swap1(int[]arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
}
//用位运算,执行速度更快,少申请一个变量
public static void swap2(int[] arr,int i,int j){
        if(arr[i] == arr[j]){//如果arr[i]和arr[j]指向同一块内存会出错,所以干脆不交换
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[j] ^ arr[i];
        arr[i] = arr[i] ^ arr[j];
}
生成随机数组
public static int[] generateRandomArray(int maxSize,int maxValue){
        int[] arr = new int[(int)((maxSize + 1) * Math.random())];//随机长度
        for (int i = 0;i < arr.length;i++) {
            //一个随机数减去另一个随机数,生成一个[-maxValue,maxValue]的随机数
            arr[i] = (int)((maxValue+1)*Math.random()) 
                - (int)((maxValue+1)*Math.random());
        }
        return arr;
}
冒泡排序
public static void bubbleSort(int[] arr){
    if(arr == null || arr.length <2){
        return;
    }
    for(int i = 1; i < arr.length; i++){
        for(int j = 0; j < arr.length - i; j++){
            if (arr[j + 1] < arr[j]) {
                swap(arr,j + 1,j);
            }
        }
    }
}
选择排序
public static void selectSort(int[] arr){
    if(arr == null || arr.length <2){
        return;
    }
    for(int i = 0; i < arr.length - 1; i++){
        int minIndex = i;
        for(int j = i + 1; j < arr.length; j++){
            if(arr[minIndex] > arr[j]){
                minIndex = j;
            }
        }
        swap(arr,minIndex,i);
    }
}
插入排序
public static void insertSort(int[] arr){
    if(arr == null || arr.length <2){
        return;
    }
    for(int i = 1;i < arr.length;i++){
        for(int j = i; j > 0 && arr[j] < arr[j-1];j--){
            swap(arr,j,j - 1);
        }
    }
}
归并排序

merge:前半部分有序,后半部分有序,让整体变有序

public static void merge(int[] arr,int L,int M,int R){
    int[] help = new int[R - L + 1];
    int p1 = L;
    int p2 = M + 1;
    int i = 0;
    while(p1 <= M && p2 <= R){
        help[i++] = arr[p1] <= arr[p2]? arr[p1++]:arr[p2++];
    }
    while(p1 <= M){
        help[i++] = arr[p1++];
    }
    while(p2 <= R){
        help[i++] = arr[p2++];
    }
    for(i = 0;i < help.length;i++){
        arr[L + i] = help[i];
    }
}

递归实现

public void mergesort(int[] arr,int L,int R){
    if(L == R){
        return;
    }
    int mid = L + ((R - L) >> 1);
    mergesort(arr,L,mid);
    mergesort(arr,mid +1,R);
    merge(arr,L,mid,R);
}

非递归

public static void mergesort02(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    int mergeSize = 1;
    int N = arr.length;
    while(mergeSize < N){
        int L = 0;
        while(L < N){
            int M = L + mergeSize;
            if(M >= N){
                break;
            }
            int R =Math.min(L + mergeSize,N - 1);
            merge(arr,L,M,R);
            L = R + 1;
        }
        if(mergeSize > (N >> 1)){
            break;
        }
        mergeSize <<= 1;
    }
}
快速排序 Partition

给一个数,把数组中小于等于这个数的数放左边,其他放右边

public static int partition(int[] arr,int L,int R){
    if(L > R){
        return -1;
    }
    if(L == R){
        return L;
    }
    int less = L - 1;
    int more = R;
    int index = L;
    while(L < R){
        if(arr[index] == arr[R]){
            index++;
        }else if(arr[index] < arr[R]){
            swap(arr,index++,++less);
        }else{
            swap(arr,index,--more);
        }
    }
    swap(arr,more,R);
    return more;
}
public static void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
荷兰国旗问题

给一个数,把数组中小于这个数的数放左边,等于放中间,大于放右边

public static int partition(int[] arr,int L,int R){
    if(L > R){
        return -1;
    }
    if(L == R){
        return L;
    }
    int less = L - 1;
    int more = R;
    int index = L;
    while(L < R){
        if(arr[index] == arr[R]){
            index++;
        }else if(arr[index] < arr[R]){
            swap(arr,index++,++less);
        }else{
            swap(arr,index,--more);
        }
    }
    swap(arr,more,R);
    return more;
}
public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
快排1.0

用partition

public static void quicksort01(int[] arr,int L,int R){
    if(L >= R){
        return;
    }
    int M = partition(arr,L,R);
    quicksort01(arr,L,M);
    quicksort01(arr,M + 1,R);
}
快排2.0

用荷兰国旗

public static void quicksort02(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int[] equalArea = netherlandsFlag(arr, L, R);
    quicksort02(arr, L, equalArea[0] - 1);
    quicksort02(arr, equalArea[1] + 1, R);
}
快排3.0(随机快排)

在2.0的基础上加随机,达到s时间复杂度O(N*logN)

public static void quicksort03(int[] arr,int L,int R){
    if (L <= R){
        return;
    }
    swap(arr,L + (int) (Math.random() * (R - L + 1)),R);
    int[] equalArea = NetherlandsFlag.netherlandsFlag(arr,L,R);
    quicksort03(arr,L,equalArea[0] - 1);
    quicksort03(arr,equalArea[1] + 1,R);
}
public static void swap(int[]arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

结论:每种情况出现是等概率时,所有情况的时间复杂度的期望是O(N*logN)

堆排序

跳转

几乎有序的数组

桶排序

不基于比较的排序

应用范围很有限,如果数据有变动,算法很可能要大规模重写

计数排序
public static void countSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        int max = Integer.MIN_VALUE;
    	//找出最大值
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max,arr[i]);
        }
    	//准备一个max + 1 个桶
        int[] bucket = new int[max + 1];
    	//计数
        for(int i = 0; i < arr.length; i++){
            bucket[arr[i]]++;
        }
        int i = 0;
    	//倒出
        for(int j = 0; j < bucket.length; j++){
            while(bucket[j]-- > 0){
                arr[i++] = j;
            }
        }
    }
基数排序
public class RadixSort {
    //只能处理非负值
    public static void radixSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        radixSort(arr,0,arr.length - 1,maxBits(arr));
    }

    
    public static int maxBits(int[]arr){
        int max = Integer.MIN_VALUE;
        for(int i = 0;i < arr.length; i++){
            max = Math.max(max,arr[i]);
        }
        int res = 0;
        while(max != 0){
            res++;
            max /= 10;
        }
        return res;
    }

    public static void radixSort(int[] arr, int L, int R, int digit){
        final int radix = 10;//十进制
        int i = 0, j = 0;
        int[] help = new int[R - L +1];//等长数组
        for(int d = 1; d <= digit; d++) {//从个位开始,每一位入桶
            int[] count = new int[radix];
            //count
            for(i = L;i <= R; i++){
                j = getDigit(arr[i], d);
                count[j]++;
            }
            //count'
            for(i = 1; i < radix; i++){
                count[i] += count[i - 1];
            }
            //help
            for(i = R; i >= L; i--){
                j = getDigit(arr[i], d);
                help[count[j] - 1] = arr[i];
                count[j]--;
            }
            //倒回去
            for(i = L,j =0; i <= R; i++,j++){
                arr[i] = help[j];
            }
        }
    }

    
    public static int getDigit(int num, int digit){
        int bits = 0;
        int cloneOfNum = num;
        while(cloneOfNum != 0){
            bits++;
            cloneOfNum /= 10;
        }
        if(digit > bits || digit <= 0){
            return 0;
        }
        return (num / (int)Math.pow(10,digit - 1)) % 10;
    }
}

总结
基于比较时间复杂度空间复杂度稳定性
选择排序O(N^2)O(1)无
冒泡排序O(N^2)O(1)有
插入排序O(N^2)O(1)有
归并排序O(N*logN)O(N)有
随即快排O(N*logN)O(logN)无
堆排序O(N*logN)O(1)无
不基于比较
计数排序O(N)O(M)有
基数排序O(N)O(N)有
  • 比时间,选快排

  • 比空间,选堆排

  • 比稳定性,选归并

二分法 有序数组中查找某个数是否存在
    
public static boolean dichotomySearch(int[] arr,int target){
    if(arr == null || arr.length ==0){
        return false;
    }
    int L = 0;
    int R = arr.length-1;
    int mid = 0;
    while(L < R){
        mid = L + ((R - L) >> 1);
        if(arr[mid] == target){
            return true;
        }
        else if(arr[mid] > target){
            R = mid - 1;
        }
        else {
            L = mid + 1;
        }

    }
    return arr[L] == target;
}
有序数组中,找>=某个数最左侧的位置
public static int firstLeft(int[]arr,int target){
    int L = 0;
    int R = arr.length -1;
    int mid = 0;
    int res = -1;
    while(L <= R){
        mid = L + ((R - L) >> 1);
        if(arr[mid] >= target){
            res = mid;
            R = mid -1;
        }
        else{
            L = mid + 1;
        }
    }
    return res;
}
局部最小值

无序数组中,任何相邻的两个数都不相等,找局部最小值,局部最小值定义为既小于左边数,也小于右边数。

public static int localMin(int[] arr){
    if(arr == null || arr.length == 0){
        return -1;
    }
    int L = 0;
    int R = arr.length - 1;
    //先看开头和末尾是不是局部最小
    if(arr.length == 1 || arr[0] < arr[1]){
        return 0;
    }
    if(arr[R] < arr[R - 1]){
        return R - 1;
    }
    //如果开头和末尾没有局部最小,则中间必定存在局部最小
    //按这种思路二分,总会找到
    while(L < R){
        int mid = L + ((R - L) >> 1);
        if(arr[mid] > arr[mid + 1]){
            L = mid + 1;
        }else if(arr[mid] > arr[mid -1]){
            R = mid - 1;
        }else{
            return mid;
        }
     }
    return -1;
    //这里return什么都可以,因为不可能执行到这一步,上面那个while必找到局部最小
    //任何相邻不相等的数组必存在局部最小
}
认识异或运算
  1. 0 ^ N == N N ^ N == 0
  2. 异或运算满足交换律和结合律
  3. 用无进位相加来理解异或运算
交换数组中的两个数
public static void swap2(int[] arr,int i,int j){
        if(arr[i] == arr[j]){//如果arr[i]和arr[j]指向同一块内存会出错,所以干脆不交换
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[j] ^ arr[i];
        arr[i] = arr[i] ^ arr[j];
}
数组中只有一种数出现了奇数次,打印这种数
public static void onlyOne(int[] arr){
    if(arr == null){
        return;
    }
    if(arr.length < 2){
        System.out.println(arr[0]);
        return;
    }
    int ans = arr[0];
    for(int i = 1;i < arr.length;i++){
        ans ^= arr[i];
    }
    System.out.println(ans);
}
提取最右侧的1

举例:把二进制数0111100变成0000100

取反加1再相与

N&((~N)+1)

public static int farRightOne(int num){
    return num & ((~num)+1);
}
数组中有两种数出现了奇数次,打印这两种数
public static void twoOddTimes(int[] arr){
    int eor = arr[0];
    for(int i = 1;i < arr.length;i++){
        eor ^= arr[i];
    }
    //假设答案是a和b,全部相与,得到a^b的值
    //eor = a ^ b
    //eor != 0
    //eor必然有一个位置是1
    //a和b中必然有一个数某一位是1,但另一个数这一位不是1
    int farRightOne = eor & ((~eor)+1);//提取最右侧的1
    int eor1 = 0;
    //将数组分为某一位是1和0的两组
    for(int i = 0;i < arr.length;i++){
        if((arr[i] & farRightOne) != 0){//相与不为0说明这一位上是1
            eor1 ^= arr[i];
        }
    }
    System.out.println(eor1 + " " + (eor1 ^ eor));
}
数出一个数的二进制形式中有几个1
public static int howManyOnes(int num){
    int count = 0;
    while(num != 0){
        int farRightOne = num & ((~num)+1);
        num ^= farRightOne;//每次消去最右侧的1
        count ++;
    }
    return count;
}
链表 单向链表
public class Node {
    public int value;
    public Node next;

    public Node(int data){
        value = data;
    }
	//翻转
    public static Node reverseLinkedList(Node head){
        Node next = null;
        Node last = null;
        while(head != null){
            next = head.next;

            head.next = last;

            last = head;

            head = next;
        }
        return last;
    }
	//删除指定元素
    public static Node removeValue(Node head,int num){
        while(head != null){
            if(head.value != num){
                break;
            }
            head = head.next;
        }
        Node last = head;
        Node cur = head;
        while(cur != null){
            if(cur.value == num){
                last.next = cur.next;
            }else{
                last = cur;
            }
            cur = cur.next;
        }
        return head;
    }
}
双向链表
public class DoubleNode {
    public T value;
    public DoubleNode next;
    public DoubleNode last;
    public DoubleNode(T data){
        value = data;
    }
	//翻转
    public DoubleNode reverseDoubleList(DoubleNode head){
        DoubleNode last = null;
        DoubleNode next = null;
        while(head != null){
            head.next = next;

            head.next = last;
            head.last = next;

            last = head;

            head = next;
        }
        return last;
    }
	//删除指定元素
    public DoubleNode removeValue(DoubleNode head, T num){
        while(head != null){
            if(head.value != num){
                break;
            }
            head = head.next;
        }
        DoubleNode last = head;
        DoubleNode cur = head;
        DoubleNode next = head.next;
        while(cur != null){
            if(cur.value == num){
                last.next = next;
                next.last = last;
            } else{
                last = cur;
            }
            next = cur.next;
            cur = cur.next;
        }
        return head;
    }

}
双向链表实现队列和栈
public class MyNode {
    public DoubleNode H;
    public DoubleNode T;

    public void pushFromHead(T data){
        DoubleNode newNode = new DoubleNode<>(data);
        if(H == null){
            T = newNode;
        }else {
            H.last = newNode;
            newNode.next = H;
        }
        H = newNode;
    }

    public void pushFromTail(T data){
        DoubleNode newNode = new DoubleNode<>(data);
        if(T == null){
            H = newNode;
        }else{
            T.next = newNode;
            newNode.last = T;
        }
        T = newNode;
    }

    public T popFromHead(){
        if(H == null){
            return null;
        }
        DoubleNode popNode = H;
        if(H == T){
            H = null;
            T = null;
        }else {
            H = H.next;
            H.last = null;
            popNode.next = null;
        }
        return popNode.value;
    }
    public T popFromTail(){
        if(T == null){
            return null;
        }
        DoubleNode popNode = T;
        if(H == T){
            H = null;
            T = null;
        }else {
            T = T.last;
            T.next = null;
            popNode.last = null;
        }
        return popNode.value;
    }
}
实现队列
public class ListQueue {
    MyNode node;
    public ListQueue(){
        node = new MyNode();
    }

    public void push(T value){
        node.pushFromTail(value);
    }

    public void pop(){
        node.popFromHead();
    }
}
实现栈
public class ListStack {
    MyNode node;
    public ListStack(){
        node = new MyNode();
    }

    public void push(T value){
        node.pushFromTail(value);
    }

    public void pop(){
        node.popFromTail();
    }
}
返回中点
import java.util.ArrayList;

public class GetMid {
    //笔试用Arraylist
    //时间复杂度:O(N)
    //空间复杂度:O(N)
    public static Node getMid01(Node head){
        if(head == null){
            return null;
        }
        ArrayList help = new ArrayList<>();
        while(head.next != null){
            help.add(head);
            head = head.next;
        }
        return help.get((help.size() - 1) / 2);//返回中点或上中点
    }
    //面试用双指针
    //时间复杂度O(N)而且比上面的Arraylist节省一半的时间
    //空间复杂度O(1)
    //双指针
    //中点和上中点
    public static Node getMid02(Node head){
        if(head == null){
            return null;
        }
        Node f = head;
        Node s = head;
        while(f.next != null && f.next.next != null){
            f = f.next.next;
            s = s.next;
        }
        return s;
    }

    //中点和下中点
    public static Node getMid03(Node head){
        if(head == null || head.next == null){
            return head;
        }
        Node f = head;
        Node s = head.next;
        while(f.next != null && f.next.next != null){
            f = f.next.next;
            s = s.next;
        }
        return s;
    }
}

是否为回文结构
public class IsPalindrome {
    public static boolean isPalindrome(Node head){
        if(head == null || head.next == null){
            return true;
        }
        Node help = GetMid.getMid02(head);
        Node l = help.next;
        Node r = null;
        //让后半部分的指针反向指
        while(l != null){
            r = l.next;
            l.next = help;
            help = l;
            l = r;
        }
        r = help;
        l = head;
        boolean res = true;
        //对比前半部分和后半部分
        while(r != null && l != null){
            if(r.value != l.value){
                res = false;
                break;//不直接return false是因为要把链表还原回去
            }
            r = r.next;
            l = l.next;
        }
        r = help.next;
        help.next = null;
	    //还原
        while(r != null){
            l = r.next;
            r.next = help;
            help = r;
            r = l;
        }
        return res;
    }
}

Partition
public static Node listPartition(Node head, int value){
    Node lh = null;
    Node lt = null;
    Node eh = null;
    Node et = null;
    Node mh = null;
    Node mt = null;
    Node next = null;
    while(head != null){
        next = head.next;
        head.next = null;
        if(head.value < value){
            if(lh == null){
                lh = head;
            }else{
                lt.next = head;
            }
            lt = head;
        }else if(head.value == value){
            if(eh == null){
                eh = head;
            }else{
                et.next = head;
            }
            et = head;
        }else{
            if(mh == null){
                mh = head;
            }else{
                mt.next = head;
            }
            mt = head;
        }
        head = next;
    }
    if(lt != null){
        lt.next = eh;
        et = et == null ? lt : et;
    }
    if(et != null){
        et.next = mh;
    }
    return lh != null ? lh : eh != null ? eh : mh;
}
rand克隆
import java.util.HashMap;

public class Node {
    int value;
    Node next;
    Node rand;
    public Node(int v){
        value = v;
    }
}

public class Clone {
    //用hashmap
    public static Node clone01(Node head){
        HashMap hashMap = new HashMap<>();
        Node cur = head;
        while(cur != null){
            hashMap.put(cur,new Node(cur.value));
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            hashMap.get(cur).next = hashMap.get(cur.next);
            hashMap.get(cur).rand = hashMap.get(cur.rand);
            cur = cur.next;
        }
        return hashMap.get(head);
    }
	//不用hashmap
    public static Node clone02(Node head){
        if(head == null){
            return null;
        }
        Node cur = head;
        while(cur != null){
            Node cloneNode = new Node(cur.value);
            cloneNode.next = cur.next;
            cur.next = cloneNode;
            cur = cloneNode.next;
        }
        cur = head;
        while(cur != null){
            cur.next.rand = cur.rand == null ? null : cur.rand.next;
            cur = cur.next.next;
        }
        Node res = head.next;
        cur = head;
        Node help;
        while(cur != null){
            help = cur.next;
            cur.next = cur.next.next == null ? null : cur.next.next;
            help.next = cur.next == null ? null : cur.next.next;
            cur = cur.next;
        }
        return res;
    }
}

入环节点
public static Node intersection(Node head){
    //节点数小于3返回null
    if(head == null || head.next == null || head.next.next == null){
        return null;
    }
    Node s = head.next;
    Node f = head.next.next;
    while(!s.equals(f)){
        //为null说明无环
        if(f.next == null || f.next.next == null){
            return null;
        }
        s = s.next;
        f = f.next.next;
    }
    //相遇后f回到head的位置
    f = head;
    //再次相遇时便是入环节点的位置
    while(!s.equals(f)){
        f = f.next;
        s = s.next;
    }
    return s;
}

证明:
快指针与慢指针均从X出发,在Z相遇。此时,慢指针行使距离为a+b,快指针为a+b+n(b+c)。

所以2*(a+b)=a+b+n*(b+c),推出

a=(n-1)b+nc=(n-1)(b+c)+c;

得到,将此时两指针分别放在起始位置和相遇位置,并以相同速度前进,当一个指针走完距离a时,另一个指针恰好走出 绕环n-1圈加上c的距离。

环形链表第一个入环节点

相交节点 数组 固定大小的数组实现队列和栈 实现队列
public class ArrayQueue {
    private Object[] arr;
    private int size;
    private int H;
    private int T;
    private final int limit =7;

    public ArrayQueue(){
        arr = new Object[7];
        size = 0;
        H = 0;
        T = 0;
    }

    public void push(Object value){
        if(size == limit){
            System.out.println("Queue is full");
            return;
        }
        if(++T >= limit){
            T = 0;
        }
        arr[T] = value;
        size++;
    }

    public Object pop(){
        if(size == 0){
            System.out.println("Queue is empty");
            return null;
        }
        Object popValue = arr[H];
        if(H != T){
            if(++H >=limit){
                H = 0;
            }
        }
        size--;
        return popValue;
    }
}
实现栈
public class ArrayStack {
    Object[] arr;
    int size;
    public ArrayStack(){
        arr = new Object[7];
        size = 0;
    }

    public void push(Object value){
        if(size == 7){
            System.out.println("Stack is full");
            return;
        }
        arr[size++] = value;
    }

    public Object pop(){
        if(size == 0){
            System.out.println("Stack is empty");
            return null;
        }
        return arr[--size];
    }
}
栈 可以返回最小元素的栈

实现一个特殊的栈,再基本功能的基础上,再实现返回栈中最小元素的功能

  1. pop、push、getMin操作的时间复杂度都是O(1)
  2. 设计的栈类型可以用现成的栈结构
public class MinStack {
    private Stack dataStack;
    private Stack minStack;
    int min;
    public MinStack(){
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }
    public void push(int value){
        minStack.push(minStack.peek() > value? value:minStack.peek());
        dataStack.push(value);
    }
    public int getMin(){
        return minStack.peek();
    }
    public Object pop(){
        minStack.pop();
        return dataStack.pop();
    }
}
固定大小的数组实现栈

跳转

用栈实现队列
public class StackToQueue {
    private Stack pushStack;
    private Stack popStack;
    public StackToQueue(){
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }
    public void push(T value){
        pushStack.push(value);
    }
    public T pop(){
        if(popStack.isEmpty() && pushStack.isEmpty()){
            System.out.println("Queue is empty");
            return null;
        }else if(popStack.isEmpty()){
            while(!pushStack.isEmpty()){
                popStack.push(pushStack.pop());
            }
        }
        return popStack.pop();
    }
}
用队列实现栈

跳转

双向链表实现栈

跳转到双向链表

队列 固定大小数组实现队列

跳转

用队列实现栈
public class QueueToStack {
    LinkedList l1;
    LinkedList l2;
    public QueueToStack(){
        l1 = new LinkedList<>();
        l2 = new LinkedList<>();
    }
    public void push(T value){
        if(l2.isEmpty()){
            l1.push(value);
        }else {
            l2.push(value);
        }
    }
    public T pop(){
        if(l1.isEmpty() && l2.isEmpty()){
            System.out.println("Stack is empty");
            return null;
        }
        if(l2.isEmpty()){
            for(int i = 0;i < l1.size()-1;i++){
                l2.push(l1.pop());
            }
            return l1.pop();
        }else {
            for(int i = 0;i < l2.size()-1;i++){
                l1.push(l2.pop());
            }
            return l2.pop();
        }
    }
}
用栈实现队列

跳转

双向链表实现队列

跳转到双向链表

递归 Master公式

形如

T(N) = a * T(N/b) + O(N^d)(其中a、b、d都是常数)

的递归函数,可以直接通过Master公式来确定时间复杂度

如果log(b,a) < d,复杂度为O(N^d)

如果log(b,a) > d,复杂度为O(N^log(b,a))

如果log(b,a) = d,复杂度为O(N^d * logN)

用递归实现数组上下标L到R的最大值
public static int getMax(int[] arr,int L,int R){
    if(L == R){
        return arr[L];
    }
    int mid = L + ((R - L) >> 1);
    int leftMax = getMax(arr,L,mid);
    int rightMax = getMax(arr,mid + 1,R);
    return Math.max(leftMax,rightMax);
}
归并排序

跳转

数组小和

在一个数组中,一个数左边比它小的数的总和,叫数的小和,数组中所有数的小和,叫数组小和

public int smallSum(int[] arr,int L,int R){
    if(L == R){
        return 0;
    }
    int M = L + ((R - L) >> 1);
    return smallSum(arr,L,M)
            +
            smallSum(arr,M + 1,R)
            +
            merge(arr,L,M,R);
}
public static int merge(int[] arr,int L,int M,int R){
    int[] help = new int[R - L + 1];
    int i = 0;
    int res = 0;
    int p1 = L;
    int p2 = M + 1;
    while(p1 <= M && p2 <= R){
        res = arr[p1] < arr[p2]? (R - p2 + 1) * arr[p1]:0;
        help[i++] = arr[p1] <= arr[p2]?arr[p1++]:arr[p2++];
    }
    while(p1 <= M){
        help[i++] = arr[p1++];
    }
    while(p2 <= R){
        help[i++] = arr[p2];
    }
    for(i = 0;i < help.length;i++){
        arr[L + i] = help[i];
    }
    return res;
}
树 堆 大根堆

任何子树最大值都是头结点的值

public class BigHeap {
    //heapSize既表示新来的数该放哪,又表示堆大小
    int heapSize;
    int[] heap;
    private final int limit;
    public BigHeap(int limit){
        heapSize = 0;
        heap = new int[limit];
        this.limit = limit;
    }
    public boolean isEmpty(){
        return heapSize == 0;
    }
    public boolean isFull(){
        return heapSize == limit;
    }

    
    public void push(int value){
        if(isFull()){
            throw new RuntimeException("heap is full");
        }
        heap[heapSize] = value;
        heapInsert(heap,heapSize++);
    }

    
    private void heapInsert(int[] arr,int index){
        while(arr[index] > arr[(index - 1) / 2]){
            swap(arr,index,(index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

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

    
    public int pop(){
        int ans = heap[0];
        //第一个数和最后一个数交换,
        swap(heap,0,--heapSize);
        heapify(heap,0,heapSize);
        return ans;
    }

    
    private void heapify(int[] arr,int index,int heapSize){
        //左孩子下标
        int left = index * 2 + 1;
        //不越界时
        while(left < heapSize){
            //获取较大孩子的下标
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //获取子树中最大值的下标
            largest = arr[largest] > arr[index] ? largest : index;
            //如果最大值就是自己,break
            if(largest == index){
                break;
            }
            //自己和最大值交换
            swap(arr,index,largest);
            //下沉
            index = largest;
            //左孩子下标
            left = index * 2 + 1;
        }
    }

}

堆排序

在时间复杂度O(N*logN)的情况下,额外空间复杂度可达到O(1)

public class HeapSort {
    
    public void heapSort1(int[] arr){
        //从后往前heapify
        for(int i = arr.length - 1; i > 0; i--){ //O(N)
            heapify(arr, i, arr.length);//O(logN)
        }
    }
    
    public void heapSort2(int[] arr){
        for(int i = 0;i < arr.length; i++){ //O(N)
            heapInsert(arr,i);//O(logN)
        }
    }

    
    public void bigHeapSort(int[] bigHeap){
        int heapSize = bigHeap.length;
        while(heapSize > 0){ //O(N)
            swap(bigHeap,0,--heapSize);//O(1)
            heapify(bigHeap,0,heapSize);//O(logN)
        }
    }
    
    public void sort(int[] arr){
        heapSort1(arr);//O(N)
        bigHeapSort(arr);//O(N*logN)
    }
    
    private void heapify(int[] arr,int index,int heapSize) {
        //左孩子下标
        int left = index * 2 + 1;
        //不越界时
        while (left < heapSize) {
            //获取较大孩子的下标
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //获取子树中最大值的下标
            largest = arr[largest] > arr[index] ? largest : index;
            //如果最大值就是自己,break
            if (largest == index) {
                break;
            }
            //自己和最大值交换
            swap(arr, index, largest);
            //下沉
            index = largest;
            //左孩子下标
            left = index * 2 + 1;
        }
    }
    
    private void heapInsert(int[] arr,int index){
        while(arr[index] > arr[(index - 1) / 2]){
            swap(arr,index,(index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

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

系统实现的堆PriorityQueue 几乎有序的数组 此处尽量有文字(否则可能会跳转到页面顶部)

题目:已知一个几乎有序的数组。几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离一定不会超过k,并且k相对于数组长度来说是比较小的

请选择一个合适的排序策略,对这个数组进行排序

import java.util.PriorityQueue;
//在k小于数组长度时,时间复杂度O(N * logk)
//在k大于数组长度时,时间复杂度O(N * logN)
//所以在k小于数组长度时是非常好的排序策略
public class PriorityQueue_ {
    public static void AlmostOrderly(int[] arr,int k){
        PriorityQueue pq = new PriorityQueue<>();//小根堆
        int index = 0;
        //所有数依次入堆
        for(int i = 0;i < arr.length;i++){//O(N)
            pq.add(arr[i]);//O(1)
            //前k + 1个数入堆后开始弹出
            if(pq.size() > k + 1 ){//O(logk)
                arr[index++] = pq.poll();
            }
        }
        //弹出剩下的k个数  每次弹出O(logk)
        //或者在数组长度不大于k的情况下,全部弹出 每次弹出O(logN)
        while(!pq.isEmpty()){
            arr[index++] = pq.poll();
        }
    }
}
比较器

用比较器把PriorityQueue改成大根堆

public static class MyComp implements Comparator{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}
    
public static void main(String[] args) {
    PriorityQueue priorityQueue1 = new PriorityQueue<>(new MyComp());
    //或者
    PriorityQueue priorityQueue2 = new PriorityQueue<>(new Comparator() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
}
前缀树
import java.util.HashMap;
public class TrieTree {
    public static class Node{
        public int pass;//该节点被通过了多少次
        public int end;//有多少字符串以此节点作为结尾
        public HashMap next;//key -> 通往某个字符的路  ,  valve -> 此路指向的节点
        public Node(){
            pass = 0;
            end = 0;
            next = new HashMap<>();
        }
    }
    public static class Trie{
        private Node root;
        public Trie(){
            root = new Node();
        }

        public void insert(String s){
            if(s == null){
                return;
            }
            Node node = root;
            node.pass++;
            for(int i = 0; i < s.length(); i++){
                if(!node.next.containsKey(s.charAt(i))){
                    node.next.put(s.charAt(i),new Node());
                }
                node = node.next.get(s.charAt(i));
                node.pass++;
            }
            node.end++;
        }


        
        public int search(String s){
            if(s == null){
                return 0;
            }
            Node node = root;
            for(int i = 0; i < s.length(); i++){
                if(!node.next.containsKey(s.charAt(i))){
                    return 0;
                }
                node = node.next.get(s.charAt(i));
            }
            return node.end;
        }

        
        public void delete(String s){
            if(search(s) == 0){
                return;
            }
            Node node = root;
            node.pass--;
            for(int i = 0; i < s.length(); i++){
                if(--node.next.get(s.charAt(i)).pass == 0){
                    node.next.remove(s.charAt(i));
                    return;
                }
                node = node.next.get(s.charAt(i));
            }
            node.end--;
        }

        
        public int prefixNumber(String pre){
            if(pre == null){
                return 0;
            }
            Node node = root;
            for(int i = 0; i < pre.length(); i++){
                if(!node.next.containsKey(pre.charAt(i))){
                    return 0;
                }
                node = node.next.get(pre.charAt(i));
            }
            return node.pass;
        }
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/978670.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号