第一节课

前置知识

与运算

两个二进制位都为1时，结果才为1

  1. int a = 5; //0000 0101
  2. int b = 6; //0000 0110
  3. int c = a & b;
  4. System.out.println(c); //0000 0100 = 4

或运算

两个二进制位有一个为1，结果就为1

  1. int a = 5; //0000 0101
  2. int b = 6; //0000 0110
  3. int c = a | b;
  4. System.out.println(c); //0000 0111 = 7

异或运算

两个二进制位不相同，结果为1

  1. int a = 5; //0000 0101
  2. int b = 6; //0000 0110
  3. int c = a ^ b;
  4. System.out.println(c); //0000 0011 = 3

取反运算

0为1，1为0

  1. int a = 5; //0000 0101
  2. int b = ~a; //1111 1010
  3. //正数取反后，变为了负数，负数的10进制表示形式为  取反+1
  4. // 1111 1010
  5. // 0000 0101
  6. // 0000 0110
  7. System.out.println(b); //0000 0110 = -6

左移

  1. m << n //把m向左移动n位
  2. 0000 1110 << 2 = 0011 1000

有符号右移

有符号右移

  1. m >> n //把m向右移动n位，并在最左边补上n个符号位
  2. 0000 1110 >> 2 = 0000 0010

无符号右移

  1. m >> n //把m向右移动n位，并在最左边补上n个0
  2. 0000 1110 >> 2 = 0000 0010

打印整数的二进制

  1. public class PrintBinaryTest {
  2.     public static void print(int temp) {
  3.         for (int i = 31; i > 0; i--) {
  4.             //把1左移i位
  5.             System.out.print((temp & (1 << i)) == 0 ? "0" : "1");
  6.         }
  7.     }
  9.     public static void main(String[] args) {
  10.         int a = 2;
  11.         print(a);
  12.     }
  13. }

选择排序

  1. package class01;
  3. public class Code04_SelectionSortTest {
  5.     public static void print(int[] arr) {
  6.         for (int i : arr) {
  7.             System.out.print(i);
  8.         }
  9.         System.out.println();
  10.     }
  12.     public static void swap(int[] arr, int i, int j) {
  13.         int tmp = arr[i];
  14.         arr[i] = arr[j];
  15.         arr[j] = tmp;
  16.     }
  18.     public static void selectSort(int[] arr) {
  19.         if (arr == null || arr.length < 2) {
  20.             return;
  21.         }
  23.         int n = arr.length;
  24.         for (int i = 0; i < n-1; i++) {
  25.             int minIndex = i;
  26.             for (int j = i + 1; j < n; j++) {
  27.                 if(arr[j] < arr[minIndex]) {
  28.                     minIndex = j;
  29.                 }
  30.             }
  31.             swap(arr, i, minIndex);
  32.         }
  33.     }
  35.     public static void main(String[] args) {
  36.         int[] arr = {3, 2, 1, 4, 8, 5};
  37.         print(arr);
  38.         selectSort(arr);
  39.         print(arr);
  40.     }
  42. }

冒泡排序

  1. package class01;
  3. public class Code05_BubbleSortTest {
  5.     public static void print(int[] arr) {
  6.         for (int i : arr) {
  7.             System.out.print(i);
  8.         }
  9.         System.out.println();
  10.     }
  12.     public static void swap(int[] arr, int i, int j) {
  13.         int tmp = arr[i];
  14.         arr[i] = arr[j];
  15.         arr[j] = tmp;
  16.     }
  18.     public static void sort(int[] arr) {
  19.         if (arr == null || arr.length < 2) {
  20.             return;
  21.         }
  23.         int n = arr.length;
  24.         for (int end = n - 1; end > 0; end--) {
  25.             for (int i = 0; i < end; i++) {
  26.                 if (arr[i] > arr[i + 1]) {
  27.                     swap(arr, i, i + 1);
  28.                 }
  29.             }
  30.         }
  31.     }
  33.     public static void main(String[] args) {
  34.         int[] arr = {1, 5, 3, 9, 6, 2};
  35.         print(arr);
  36.         sort(arr);
  37.         print(arr);
  38.     }
  39. }

插入排序

  1. package class01;
  3. public class Code06_InsertionSortTest {
  5.     public static void sort(int[] arr) {
  6.         int n = arr.length;
  7.         for (int i = 1; i < n; i++) {
  8.             for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
  9.                 swap(arr, j, j + 1);
  10.             }
  11.         }
  12.     }
  14.     public static void swap(int[] arr, int i, int j) {
  15.         int tmp = arr[i];
  16.         arr[i] = arr[j];
  17.         arr[j] = tmp;
  18.     }
  20.     public static void print(int[] arr) {
  21.         for (int i : arr) {
  22.             System.out.print(i);
  23.         }
  24.         System.out.println();
  25.     }
  27.     public static void main(String[] args) {
  28.         int[] arr = {5, 3, 9, 2, 1, 8};
  29.         print(arr);
  30.         sort(arr);
  31.         print(arr);
  32.     }
  33. }

第二节课

前缀和数组

可以计算出一个数组L到R之间的和

  1. package class02;
  3. public class Code01_PreSumTest {
  5.     public static void preSum(int[] arr, int[] result) {
  6.         int n = arr.length;
  7.         result[0] = arr[0];
  8.         for (int i = 1; i < n; i++) {
  9.             result[i] = arr[i] + result[i - 1];
  10.         }
  11.     }
  13.     public static void print(int[] arr) {
  14.         for (int i : arr) {
  15.             System.out.print(i + " ");
  16.         }
  17.         System.out.println();
  18.     }
  20.     public static int cal(int[] result, int L, int R) {
  21.         return L == 0 ? result[R]: result[R] - result[L-1];
  22.     }
  24.     public static void main(String[] args) {
  25.         int[] arr = {1, 4, 7, 4};
  26.         int[] result = new int[arr.length];
  27.         preSum(arr,result);
  28.         print(result);
  29.         System.out.println(cal(result,0,2));
  31.     }
  32. }

有一个1-5等概率返回的函数，求1-7等概率？

package class02;

public class Code02_RandToRandTest {

    //求1-5等概率返回
    public static int f1() {
        //Math.random() = [0,1)
        return (int) ((Math.random() * 5) + 1);
    }

    //做一个0-1的等概率发生器
    // 当返回1，2的时候 = 0
    // 当返回4，5的时候 = 1
    // 当返回3的时候 重做
    public static int f2() {
        int ans = 0;
        do {
            ans = f1();
        } while (f1() == 3);
        return ans == 0 ? 0 : 1;
    }

    //0-6等概率返回
    public static int f3() {
        int ans = 0;
        do {
            ans = (f2() << 2) + (f2() << 1) + (f2() << 0);
        } while (f2() == 7);
        return ans;
    }

    //求1-7等概率返回
    //三个二进制位可以表示7种组合
    public static int g1() {
        return f3() + 1;
    }

}

第三节课

有序数组中找到num

public static int find(int[] arr, int n) {
    if (null == arr || arr.length < 1) {
        return -1;
    }
    int N = arr.length;
    int left = 0;
    int right = N - 1;

    while (left <= right) {
        int mid = (right + left) / 2;
        if (arr[mid] == n) {
            return mid;
        }
        if (arr[mid] > n) {
            right = mid - 1;
        }
        if (arr[mid] < n) {
            left = mid + 1;
        }
    }
    return -1;
}

有序数组中找到大于等于num最左的位置

public static int mostLeftNoLessNumIndex(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int L = 0;
    int R = arr.length - 1;
    int ans = -1;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (arr[mid] >= num) {
            ans = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return ans;
}

无序且相邻不相等的数组中找一个局部最小

// arr 整体无序
// arr 相邻的数不相等！
public static int oneMinIndex(int[] arr) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int N = arr.length;
    if (N == 1) {
        return 0;
    }
    if (arr[0] < arr[1]) {
        return 0;
    }
    if (arr[N - 1] < arr[N - 2]) {
        return N - 1;
    }
    int L = 0;
    int R = N - 1;
    // L...R 肯定有局部最小
    while (L < R - 1) {
        int mid = (L + R) / 2;
        if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
            return mid;
        } else {
            if (arr[mid] > arr[mid - 1]) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
    }
    return arr[L] < arr[R] ? L : R;
}

第四节课

反转单链表

public static void print(Node node) {
        while (node != null) {
            System.out.println(node.num);
            node = node.next;
        }
    }

    public static Node reverseSingleList(Node head) {
        Node next = null;
        Node pre = null;

        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        node.next = new Node(2);
        node.next.next = new Node(3);
        print(node);
        Node reverseNode = reverseSingleList(node);
        System.out.println("-----");
        print(reverseNode);
    }

反转双向链表

image.png
image.png
image.png
image.png
image.png
image.png

public static DoubleNode reverseDoubleList(DoubleNode head) {
    DoubleNode pre = null;
    DoubleNode next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        head.last = next;
        pre = head;
        head = next;
    }
    return pre;
}

单链表实现队列

public void offer(V value) {
    Node<V> cur = new Node<V>(value);
    if (tail == null) {
        head = cur;
        tail = cur;
    } else {
        tail.next = cur;
        tail = cur;
    }
    size++;
}

public V poll() {
    V ans = null;
    if (head != null) {
        ans = head.value;
        head = head.next;
        size--;
    }
    if (head == null) {
        tail = null;
    }
    return ans;
}

单链表实现栈

public void push(V value) {
    Node<V> cur = new Node<>(value);
    if (head == null) {
        head = cur;
    } else {
        cur.next = head;
        head = cur;
    }
    size++;
}

public V pop() {
    V ans = null;
    if (head != null) {
        ans = head.value;
        head = head.next;
        size--;
    }
    return ans;
}

K个节点的组内逆序调整

给定一个单链表的头节点head，和一个正数K 实现K个节点的小组内部逆序，如果最后一组不够k个就不调整 举例： 调整前：1->2->3->4->5->6->7->8, k=3 调整后：3->2->1->6->5->4->7->8

图解第一组转换

image.png
image.png
image.png
image.png
image.png
image.png
image.png

public static class ListNode {
    public int val;
    public ListNode next;
}

public static ListNode getKGroupEnd(ListNode start, int k) {
    while (--k != 0 && start != null) {
        start = start.next;
    }
    return start;
}

public static void reverse(ListNode start, ListNode end) {
    end = end.next;
    ListNode pre = null;
    ListNode cur = start;
    ListNode next = null;
    while (cur != end) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    start.next = end;
}

public static ListNode reverseKGroup(ListNode head, int k) {
    ListNode start = head;
    ListNode end = getKGroupEnd(start, k);
    if(null == end) {
        return head;
    }
    // 第一组凑齐了！
    head = end;
    reverse(start, end);
    // 上一组的结尾节点
    ListNode lastEnd = start;
    while (lastEnd.next != null) {
        start = lastEnd.next;
        end = getKGroupEnd(start, k);
        if (end == null) {
            return head;
        }
        reverse(start, end);
        lastEnd.next = end;
        lastEnd = start;
    }
    return head;
}

两个链表相加

给定两个链表的头节点head1和head2，认为从左到右是某个数字从低位到高位，返回相加之后的链表 举例：4->3->6 2->5->3 返回：6->8->9 解释：634 + 352 = 986 反着看数字

public static class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
    int len1 = listLength(head1);
    int len2 = listLength(head2);
    ListNode l = len1 >= len2 ? head1 : head2;
    ListNode s = l == head1 ? head2 : head1;
    ListNode curL = l;
    ListNode curS = s;
    ListNode last = curL;
    int carry = 0;
    int curNum = 0;
    while (curS != null) {
        curNum = curL.val + curS.val + carry;
        curL.val = (curNum % 10);
        carry = curNum / 10;
        last = curL;
        curL = curL.next;
        curS = curS.next;
    }
    while (curL != null) {
        curNum = curL.val + carry;
        curL.val = (curNum % 10);
        carry = curNum / 10;
        last = curL;
        curL = curL.next;
    }
    if (carry != 0) {
        last.next = new ListNode(1);
    }
    return l;
}

// 求链表长度
public static int listLength(ListNode head) {
    int len = 0;
    while (head != null) {
        len++;
        head = head.next;
    }
    return len;
}

第五节课

位运算

public static class BitMap {
    private long[] bit;

    BitMap(int i) {
        //(i+64) >> 6 相当于 (i+64) / 64
        bit = new long[(i+64) >> 6];
    }

    public void add(int num) {
        //num >> 6 等价于 num / 64
        //num % 64 等价于 num & 63
        bit[num >> 6] |= (1L << (num & 63));
    }

    public void delete(int num) {
        bit[num >> 6] &= ~(1L << (num & 63));
    }

    public boolean contains(int num) {
        return (bit[num >> 6] & (1L << (num & 63))) != 0;
    }
}

加法运算

public static int add(int a, int b) {
    int sum = a;
    while (b != 0) {
        sum = a ^ b;
        b = (a & b) << 1;
        a = sum;
    }
    return sum;
}

减法

public static int negNum(int n) {
    return add(~n, 1);
}

public static int minus(int a, int b) {
    return add(a, negNum(b));
}

乘法

public static int multi(int a, int b) {
    int res = 0;
    while (b != 0) {
        if ((b & 1) != 0) {
            res = add(res, a);
        }
        a <<= 1;
        b >>>= 1;
    }
    return res;
}

除法

public static boolean isNeg(int n) {
    return n < 0;
}

public static int div(int a, int b) {
    int x = isNeg(a) ? negNum(a) : a;
    int y = isNeg(b) ? negNum(b) : b;
    int res = 0;
    for (int i = 30; i >= 0; i = minus(i, 1)) {
        if ((x >> i) >= y) {
            res |= (1 << i);
            x = minus(x, y << i);
        }
    }
    return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}

public static int divide(int a, int b) {
    if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
        return 1;
    } else if (b == Integer.MIN_VALUE) {
        return 0;
    } else if (a == Integer.MIN_VALUE) {
        if (b == negNum(1)) {
            return Integer.MAX_VALUE;
        } else {
            int c = div(add(a, 1), b);
            return add(c, div(minus(a, multi(c, b)), b));
        }
    } else {
        return div(a, b);
    }
}