小试牛刀

  • 异或：^
    • 无进位相加
    • 满足结合律、交换律
    • O^N=N;N^N=0
    • ab交换
      1. //不借助第三方变量；
      2. //！必须保证ab不是同一内存
      3. a = a^b;
      4. b = a^b;
      5. a = a^b;

  1. 找数组出现奇数次的数

    1. int[] a = {xx,x,x,x,x,x,x};
    2. int eor = 0;
    3. for(ina q:a){
    4.  eor ^= q; 
    5. }
    6. //eor即为奇数次的数值

    归并排序的扩展

  2. 数组中小和问题 

    1. int xioaSum = 0;
    2. int[] a = {1,3,4,2,5};
    3. //数a[i]左边比它小的数的和，爆破O(n^2)
    4. //优：数a[i]右边比他大的数的次数c;c*a[i] 依次求和。O(nlogn)

  3. 逆序对问题

    1. int[] = {3,2,4,5,0};
    2. //逆序对：a[i]右边比它小的数组成的

    快排前夕

    1. //a(快排1.0).将数组小于等于最后一个数的元素放在左边，大于的元素放在右边。

  4. 荷兰国旗问题

    1. int[] a = {5,2,3,7,8,1,4};
    2. //b(快排2.0).将数组小于某数（取最后一个数）的元素放在左边，等于某数的元素放在中间，大于的元素放在右边。
    3. //要求时间O(n)，空间O(1)
    1. //c(快排3.0).将数组小于某数（随机获取）的元素放在左边，等于某数的元素放在中间，大于的元素放在右边。
    2. //综合时间O(nlogn),荷兰国旗不要求排序，1.0 2.0 可能取得有序数组的边直导致时间为O(n^2)

    堆结构和堆排序

  • 优先级队列就是堆，堆是完全二叉树
  • PriorityQueue默认是小根堆
  • 节点：
    • 父节点：（i-1）/2
    • 子节点：2i+1、2i-1
  • heapInsert()插入，从下往上与父节点比较
  • heapofy()调整，从上往下与子节点大的节点比较

有序表

  • RBT树、AVL树、SBT树（size-balance-tree）、跳表都是有序表结构。
    • 基础类型可比较，非基础类型必须提供比较器（Comparator）。

      链表

  1. 回文判断 ```java //T：给定单链表头节点head，判断是否回文 //Ex:1->2->1 true; 1-2-2-1 true

//A：放入栈，取出与原表遍历比较。 //A：优空间，后一半入栈，与原前半比较

//快慢指针FS;F：一次走两步；S：一次走一步。分析奇偶情况。 ```