个人技术博客：www.zhenganwen.top

经典算法

Manacher算法

原始问题

Manacher算法是由题目“求字符串中最长回文子串的长度”而来。比如abcdcb的最长回文子串为bcdcb，其长度为5。

我们可以遍历字符串中的每个字符，当遍历到某个字符时就比较一下其左边相邻的字符和其右边相邻的字符是否相同，如果相同则继续比较其右边的右边和其左边的左边是否相同，如果相同则继续比较……，我们暂且称这个过程为向外“扩”。当“扩”不动时，经过的所有字符组成的子串就是以当前遍历字符为中心的最长回文子串。

我们每次遍历都能得到一个最长回文子串的长度，使用一个全局变量保存最大的那个，遍历完后就能得到此题的解。但分析这种方法的时间复杂度：当来到第一个字符时，只能扩其本身即1个；来到第二个字符时，最多扩两个；……；来到字符串中间那个字符时，最多扩(n-1)/2+1个；因此时间复杂度为1+2+……+(n-1)/2+1即O(N^2)。但Manacher算法却能做到O(N)。

Manacher算法中定义了如下几个概念：

  • 回文半径：串中某个字符最多能向外扩的字符个数称为该字符的回文半径。比如abcdcb中字符d，能扩一个c，还能再扩一个b，再扩就到字符串右边界了，再算上字符本身，字符d的回文半径是3。
  • 回文半径数组pArr：长度和字符串长度一样，保存串中每个字符的回文半径。比如charArr="abcdcb"，其中charArr[0]='a'一个都扩不了，但算上其本身有pArr[0]=1；而charArr[3]='d'最多扩2个，算上其本身有pArr[3]=3。
  • 最右回文右边界R：遍历过程中，“扩”这一操作扩到的最右的字符的下标。比如charArr=“abcdcb”，当遍历到a时，只能扩a本身，向外扩不动，所以R=0；当遍历到b时，也只能扩b本身，所以更新R=1；但当遍历到d时，能向外扩两个字符到charArr[5]=b，所以R更新为5。
  • 最右回文右边界对应的回文中心C：C与R是对应的、同时更新的。比如abcdcb遍历到d时，R=5，C就是charArr[3]='d'的下标3。

处理回文子串长度为偶数的问题：上面拿abcdcb来举例，其中bcdcb属于一个回文子串，但如果回文子串长度为偶数呢？像cabbac，按照上面定义的“扩”的逻辑岂不是每个字符的回文半径都是0，但事实上cabbac的最长回文子串的长度是6。因为我们上面“扩”的逻辑默认是将回文子串当做奇数长度的串来看的，因此我们在使用Manacher算法之前还需要将字符串处理一下，这里有一个小技巧，那就是将字符串的首尾和每个字符之间加上一个特殊符号，这样就能将输入的串统一转为奇数长度的串了。比如abba处理过后为#a#b#b#a，这样的话就有charArr[4]='#'的回文半径为4，也即原串的最大回文子串长度为4。相应代码如下：

public static char[] manacherString(String str){
  char[] source = str.toCharArray();
  char chs[] = new char[str.length() * 2 + 1];
  for (int i = 0; i < chs.length; i++) {
    chs[i] = i % 2 == 0 ? '#' : source[i / 2];
  }
  return chs;
}
复制代码

接下来分析，BFPRT算法是如何利用遍历过程中计算的pArr、R、C来为后续字符的回文半径的求解加速的。

首先，情况1是，遍历到的字符下标cur在R的右边（起初另R=-1），这种情况下该字符的最大回文半径pArr[cur]的求解无法加速，只能一步步向外扩来求解。

情况2是，遍历到的字符下标cur在R的左边，这时pArr[cur]的求解过程可以利用之前遍历的字符回文半径信息来加速。分别做cur、R关于C的对称点cur'和L：

  • 如果从cur'向外扩的最大范围的左边界没有超过L，那么pArr[cur]=pArr[cur']。

    证明如下：

    由于之前遍历过cur'位置上的字符，所以该位置上能扩的步数我们是有记录的（pArr[cur']），也就是说cur'+pArr[cur']处的字符y'是不等于cur'-pArr[cur']处的字符x'的。根据R和C的定义，整个L到R范围的字符是关于C对称的，也就是说cur能扩出的最大回文子串和cur'能扩出的最大回文子串相同，因此可以直接得出pArr[cur]=pArr[cur']。

  • 如果从cur'向外扩的最大范围的左边界超过了L，那么pArr[cur]=R-cur+1。

    证明如下：

    R右边一个字符x，x关于cur对称的字符y，x,y关于C对称的字符x',y'。根据C,R的定义有x!=x'；由于x',y'在以cur'为中心的回文子串内且关于cur'对称，所以有x'=y'，可推出x!=y'；又y,y'关于C对称，且在L,R内，所以有y=y'。综上所述，有x!=y，因此cur的回文半径为R-cur+1。

  • 以cur'为中心向外扩的最大范围的左边界正好是L，那么pArr[cur] >= （R-cur+1）

    这种情况下，cur'能扩的范围是cur'-L，因此对应有cur能扩的范围是R-cur。但cur能否扩的更大则取决于x和y是否相等。而我们所能得到的前提条件只有x!=x'、y=y'、x'!=y'，无法推导出x,y的关系，只知道cur的回文半径最小为R-cur+1（算上其本身），需要继续尝试向外扩以求解pArr[cur]。

综上所述，pArr[cur]的计算有四种情况：暴力扩、等于pArr[cur']、等于R-cur+1、从R-cur+1继续向外扩。使用此算法求解原始问题的过程就是遍历串中的每个字符，每个字符都尝试向外扩到最大并更新R（只增不减），每次R增加的量就是此次能扩的字符个数，而R到达串尾时问题的解就能确定了，因此时间复杂度就是每次扩操作检查的次数总和，也就是R的变化范围（-1~2N，因为处理串时向串中添加了N+1个#字符），即O(1+2N)=O(N)。

整体代码如下：

public static int maxPalindromeLength(String str) {
  char charArr[] = manacherString(str);
  int pArr[] = new int[charArr.length];
  int R = -1, C = -1;
  int max = Integer.MIN_VALUE;
  for (int i = 0; i < charArr.length; i++) {
    pArr[i] = i > R ? 1 : Math.min(pArr[C * 2 - i], R - i);
    while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
      if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
        pArr[i]++;
      } else {
        break;
      }
    }
    if (R < i + pArr[i]) {
      R = i + pArr[i]-1;
      C = i;
    }
    max = Math.max(max, pArr[i]);
  }
  return max-1;
}

public static void main(String[] args) {
  System.out.println(maxPalindromeLength("zxabcdcbayq"));
}
复制代码

上述代码将四种情况的分支处理浓缩到了7~14行。其中第7行是确定加速信息：如果当前遍历字符在R右边，先算上其本身有pArr[i]=1，后面检查如果能扩再直接pArr[i]++即可；否则，当前字符的pArr[i]要么是pArr[i']（i关于C对称的下标i'的推导公式为2*C-i），要么是R-i+1，要么是>=R-i+1，可以先将pArr[i]的值置为这三种情况中最小的那一个，后面再检查如果能扩再直接pArr[i]++即可。

最后得到的max是处理之后的串（length=2N+1）的最长回文子串的半径，max-1刚好为原串中最长回文子串的长度。

进阶问题

给你一个字符串，要求添加尽可能少的字符使其成为一个回文字符串。

思路：当R第一次到达串尾时，做R关于C的对称点L，将L之前的字符串逆序就是结果。

BFPRT算法

题目：给你一个整型数组，返回其中第K小的数。

这道题可以利用荷兰国旗改进的partition和随机快排的思想：随机选出一个数，将数组以该数作比较划分为<,=,>三个部分，则=部分的数是数组中第几小的数不难得知，接着对<（如果第K小的数在<部分）或>（如果第K小的数在>部分）部分的数递归该过程，直到=部分的数正好是整个数组中第K小的数。这种做法不难求得时间复杂度的数学期望为O(NlogN)（以2为底）。但这毕竟是数学期望，在实际工程中的表现可能会有偏差，而BFPRT算法能够做到时间复杂度就是O(NlogN)。

BFPRT算法首先将数组按5个元素一组划分成N/5个小部分（最后不足5个元素自成一个部分），再这些小部分的内部进行排序，然后将每个小部分的中位数取出来再排序得到中位数：

BFPRT求解此题的步骤和开头所说的步骤大体类似，但是“随机选出一个的作为比较的那个数”这一步替换为上图所示最终选出来的那个数。

O(NlogN)的证明，为什么每一轮partition中的随机选数改为BFPRT定义的选数逻辑之后，此题的时间复杂度就彻底变为O(NlogN)了呢？下面分析一下这个算法的步骤：

BFPRT算法，接收一个数组和一个K值，返回数组中的一个数

  1. 数组被划分为了N/5个小部分，每个部分的5个数排序需要O(1)，所有部分排完需要O(N/5)=O(N)
  2. 取出每个小部分的中位数，一共有N/5个，递归调用BFPRT算法得到这些数中第(N/5)/2小的数（即这些数的中位数），记为pivot
  3. 以pivot作为比较，将整个数组划分为<pivot , =pivot , >pivot三个区域
  4. 判断第K小的数在哪个区域，如果在=区域则直接返回pivot，如果在<或>区域，则将这个区域的数递归调用BFPRT算法
  5. base case：在某次递归调用BFPRT算法时发现这个区域只有一个数，那么这个数就是我们要找的数。

代码示例：

public static int getMinKthNum(int[] arr, int K) {
  if (arr == null || K > arr.length) {
    return Integer.MIN_VALUE;
  }
  int[] copyArr = Arrays.copyOf(arr, arr.length);
  return bfprt(copyArr, 0, arr.length - 1, K - 1);
}

public static int bfprt(int[] arr, int begin, int end, int i) {
  if (begin == end) {
    return arr[begin];
  }
  int pivot = medianOfMedians(arr, begin, end);
  int[] pivotRange = partition(arr, begin, end, pivot);
  if (i >= pivotRange[0] && i <= pivotRange[1]) {
    return arr[i];
  } else if (i < pivotRange[0]) {
    return bfprt(arr, begin, pivotRange[0] - 1, i);
  } else {
    return bfprt(arr, pivotRange[1] + 1, end, i);
  }
}

public static int medianOfMedians(int[] arr, int begin, int end) {
  int num = end - begin + 1;
  int offset = num % 5 == 0 ? 0 : 1;
  int[] medians = new int[num / 5 + offset];
  for (int i = 0; i < medians.length; i++) {
    int beginI = begin + i * 5;
    int endI = beginI + 4;
    medians[i] = getMedian(arr, beginI, Math.min(endI, end));
  }
  return bfprt(medians, 0, medians.length - 1, medians.length / 2);
}

public static int getMedian(int[] arr, int begin, int end) {
  insertionSort(arr, begin, end);
  int sum = end + begin;
  int mid = (sum / 2) + (sum % 2);
  return arr[mid];
}

public static void insertionSort(int[] arr, int begin, int end) {
  if (begin >= end) {
    return;
  }
  for (int i = begin + 1; i <= end; i++) {
    for (int j = i; j > begin; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1);
      } else {
        break;
      }
    }
  }
}

public static int[] partition(int[] arr, int begin, int end, int pivot) {
  int L = begin - 1;
  int R = end + 1;
  int cur = begin;
  while (cur != R) {
    if (arr[cur] > pivot) {
      swap(arr, cur, --R);
    } else if (arr[cur] < pivot) {
      swap(arr, cur++, ++L);
    } else {
      cur++;
    }
  }
  return new int[]{L + 1, R - 1};
}

public static void swap(int[] arr, int i, int j) {
  int tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

public static void main(String[] args) {
  int[] arr = {6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9};
  System.out.println(getMinKthNum(arr,13));
}
复制代码

时间复杂度为O(NlogN)（底数为2）的证明，分析bfprt的执行步骤（假设bfprt的时间复杂度为T(N)）：

  1. 首先数组5个5个一小组并内部排序，对5个数排序为O(1)，所有小组排好序为O(N/5)=O(N)
  2. 由步骤1的每个小组抽出中位数组成一个中位数小组，共有N/5个数，递归调用bfprt求出这N/5个数中第(N/5)/2小的数（即中位数）为T(N/5)，记为pivot
  3. 对步骤2求出的pivot作为比较将数组分为小于、等于、大于三个区域，由于pivot是中位数小组中的中位数，所以中位数小组中有N/5/2=N/10个数比pivot小，这N/10个数分别又是步骤1中某小组的中位数，可推导出至少有3N/10个数比pivot小，也即最多有7N/10个数比pivot大。也就是说，大于区域（或小于）最大包含7N/10个数、最少包含3N/10个数，那么如果第i大的数不在等于区域时，无论是递归bfprt处理小于区域还是大于区域，最坏情况下子过程的规模最大为7N/10，即T(7N/10)

综上所述，bfprt的T(N)存在推导公式：T(N/5)+T(7N/10)+O(N)。根据 基础篇 中所介绍的Master公式可以求得bfprt的时间复杂度就是O(NlogN)（以2为底）。

morris遍历二叉树

关于二叉树先序、中序、后序遍历的递归和非递归版本在【直通BAT算法（基础篇）】中有讲到，但这6种遍历算法的时间复杂度都需要O(H)（其中H为树高）的额外空间复杂度，因为二叉树遍历过程中只能向下查找孩子节点而无法回溯父结点，因此这些算法借助栈来保存要回溯的父节点（递归的实质是系统帮我们压栈），并且栈要保证至少能容纳下H个元素（比如遍历到叶子结点时回溯父节点，要保证其所有父节点在栈中）。而morris遍历则能做到时间复杂度仍为O(N)的情况下额外空间复杂度只需O(1)。

遍历规则

首先在介绍morris遍历之前，我们先把先序、中序、后序定义的规则抛之脑后，比如先序遍历在拿到一棵树之后先遍历头结点然后是左子树最后是右子树，并且在遍历过程中对于子树的遍历仍是这样。

忘掉这些遍历规则之后，我们来看一下morris遍历定义的标准：

  1. 定义一个遍历指针cur，该指针首先指向头结点
  2. 判断cur的左子树是否存在
    • 如果cur的左孩子为空，说明cur的左子树不存在，那么cur右移来到cur.right
    • 如果cur的左孩子不为空，说明cur的左子树存在，找出该左子树的最右结点，记为mostRight
      • 如果，mostRight的右孩子为空，那就让其指向cur（mostRight.right=cur），并左移cur（cur=cur.left）
      • 如果mostRight的右孩子不空，那么让cur右移（cur=cur.right），并将mostRight的右孩子置空
  3. 经过步骤2之后，如果cur不为空，那么继续对cur进行步骤2，否则遍历结束。

下图所示举例演示morris遍历的整个过程：

先序、中序序列

遍历完成后对cur进过的节点序列稍作处理就很容易得到该二叉树的先序、中序序列：

示例代码：

public static class Node {
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data;
    }
}

public static void preOrderByMorris(Node root) {
    if (root == null) {
        return;
    }
    Node cur = root;
    while (cur != null) {
        if (cur.left == null) {
            System.out.print(cur.data+" ");
            cur = cur.right;
        } else {
            Node mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                System.out.print(cur.data+" ");
                mostRight.right = cur;
                cur = cur.left;
            } else {
                cur = cur.right;
                mostRight.right = null;
            }
        }
    }
    System.out.println();
}

public static void mediumOrderByMorris(Node root) {
    if (root == null) {
        return;
    }
    Node cur = root;
    while (cur != null) {
        if (cur.left == null) {
            System.out.print(cur.data+" ");
            cur = cur.right;
        } else {
            Node mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            } else {
                System.out.print(cur.data+" ");
                cur = cur.right;
                mostRight.right = null;
            }
        }
    }
    System.out.println();
}

public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    preOrderByMorris(root);
    mediumOrderByMorris(root);

}
复制代码

这里值得注意的是：morris遍历会来到一个左孩子不为空的结点两次，而其它结点只会经过一次。因此使用morris遍历打印先序序列时，如果来到的结点无左孩子，那么直接打印即可（这种结点只会经过一次），否则如果来到的结点的左子树的最右结点的右孩子为空才打印（这是第一次来到该结点的时机），这样也就忽略了cur经过的结点序列中第二次出现的结点；而使用morris遍历打印中序序列时，如果来到的结点无左孩子，那么直接打印（这种结点只会经过一次，左中右，没了左，直接打印中），否则如果来到的结点的左子树的最右结点不为空时才打印（这是第二次来到该结点的时机），这样也就忽略了cur经过的结点序列中第一次出现的重复结点。

后序序列

使用morris遍历得到二叉树的后序序列就没那么容易了，因为对于树种的非叶结点，morris遍历最多会经过它两次，而我们后序遍历实在第三次来到该结点时打印该结点的。因此要想得到后序序列，仅仅改变在morris遍历时打印结点的时机是无法做到的。

但其实，在morris遍历过程中，如果在每次遇到第二次经过的结点时，将该结点的左子树的右边界上的结点从下到上打印，最后再将整个树的右边界从下到上打印，最终就是这个数的后序序列：

其中无非就是在morris遍历中在第二次经过的结点的时机执行一下打印操作。而从下到上打印一棵树的右边界，可以将该右边界上的结点看做以right指针为后继指针的链表，将其反转reverse然后打印，最后恢复成原始结构即可。示例代码如下（其中容易犯错的地方是18行和19行的代码不能调换）：

public static void posOrderByMorris(Node root) {
    if (root == null) {
        return;
    }
    Node cur = root;
    while (cur != null) {
        if (cur.left == null) {
            cur = cur.right;
        } else {
            Node mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            } else {
                mostRight.right = null;
                printRightEdge(cur.left);
                cur = cur.right;
            }
        }
    }
    printRightEdge(root);
}

private static void printRightEdge(Node root) {
    if (root == null) {
        return;
    }
    //reverse the right edge
    Node cur = root;
    Node pre = null;
    while (cur != null) {
        Node next = cur.right;
        cur.right = pre;
        pre = cur;
        cur = next;
    }
    //print 
    cur = pre;
    while (cur != null) {
        System.out.print(cur.data + " ");
        cur = cur.right;
    }
    //recover
    cur = pre;
    pre = null;
    while (cur != null) {
        Node next = cur.right;
        cur.right = pre;
        pre = cur;
        cur = next;
    }
}

public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    posOrderByMorris(root);
}
复制代码

时间复杂度分析

因为morris遍历中，只有左孩子非空的结点才会经过两次而其它结点只会经过一次，也就是说遍历的次数小于2N，因此使用morris遍历得到先序、中序序列的时间复杂度自然也是O(1)；但产生后序序列的时间复杂度还要算上printRightEdge的时间复杂度，但是你会发现整个遍历的过程中，所有的printRightEdge加起来也只是遍历并打印了N个结点：

因此时间复杂度仍然为O(N)。

morris遍历结点的顺序不是先序、中序、后序，而是按照自己的一套标准来决定接下来要遍历哪个结点。

morris遍历的独特之处就是充分利用了叶子结点的无效引用（引用指向的是空，但该引用变量仍然占内存），从而实现了O(1)的时间复杂度。

求和为aim的最长子数组长度

举例：数组[7,3,2,1,1,7,-6,-1,7]中，和为7的最长子数组长度为4。（子数组：数组中任意个连续的数组成的数组）

大前提：如果我们求出以数组中每个数结尾的所有子数组中和为aim的子数组，那么答案一定就在其中。

规律：对于数组[i,……,k,k+1,……,j]，如果要求aim为800，而我们知道从i累加到j的累加和为2000，那么从i开始向后累加，如果累加到k时累加和才达到1200，那么k+1~j就是整个数组中累加和为800的最长子数组。

步骤：以[7,3,2,1,1,7,-6,-3,7]、aim=7为例，

  • 首先将(0,-1)放入HashMap中，代表0这个累加和在还没有遍历时就出现了。->(0,-1)
  • 接着每遍历一个数就将该位置形成的累加和存入HashMap，比如arr[0]=7，0位置上形成的累加和为前一个位置形成的累加和0加上本位置上的7，因此将(7,0)放入HashMap中表示0位置上第一次形成累加和为7，然后将该位置上的累加和减去aim，即7-7=0，找第一次形成累加和为0的位置，即-1，因此以下标为0结尾的子数组中和为aim的最长子数组为0~0，即7一个元素，记最大长度maxLength=1。->(7,0)
  • 接着来到arr[1]=3，1位置上形成的累加和为7+3=10，HashMap中没有key为10的记录，因此放入(10,1)表示1位置上最早形成累加和为10，然后将该位置上的累加和减去aim即10-7=3，到HashMap中找有没有key为3的记录（有没有哪个位置最早形成累加和为3），发现没有，因此以下标为1结尾的子数组中没有累加和为aim的。->(10,1)
  • 接着来到arr[2]=2，2位置上形成的累加和为10+2=12，HashMap中没有key为12的记录，因此放入(12,2)，sum-aim=12-7=5，到HashMap中找有没有key为5的记录，发现没有，因此以下标为2结尾的子数组中没有累加和为aim的。->(12,2)
  • 来到arr[3]=1，放入(13,3)，sum-aim=5，以下标为3结尾的子数组没有累加和为aim的。->(13,3)
  • 来到arr[4]=1，放入(14,4)，sum-aim=7，发现HashMap中有key=7的记录 (7,0)，即在0位置上累加和就能达到7了，因此1~4是以下标为4结尾的子数组中累积和为7的最长子数组，更新maxLength=4。->(14,4)
  • 来到arr[5]=7，放入(21,5)，sum-aim=14，HashMap中有(14,4)，因此5~5是本轮的最长子数组，但maxLength=4>1，因此不更新。->(21,5)
  • 来到arr[6]=-6，放入15,6，没有符合的子数组。->(15,6)
  • 来到arr[7]=-1，累加和为15+(-1)=14，但 HashMap中有key=14的记录，因此不放入(14,7)（HashMap中保存的是某累加和第一次出现的位置，而14这个了累加和最早在4下标上就出现了）。sum-aim=7，HashMap中有(7,0)，因此本轮最长子数组为1~7，因此更新maxLength=7。
  • 来到arr[8]=7，累加和为21，存在key为21的记录，因此不放入（21，7）。sum-aim=14，本轮最长子数组为5~8，长度为4，不更新maxLength。

示例代码：

public static int maxLength(int[] arr,int aim) {
    //key->accumulate sum value->index
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    hashMap.put(0, -1);
    int curSum = 0;
    int maxLength = 0;
    for (int i = 0; i < arr.length; i++) {
        curSum += arr[i];
        if (!hashMap.containsKey(curSum)) {
            hashMap.put(curSum, i);
        }
        int gap = curSum - aim;
        if (hashMap.containsKey(gap)) {
            int index = hashMap.get(gap);
            maxLength = Math.max(maxLength, i - index);
        }
    }
    return maxLength;
}

public static void main(String[] args) {
    int arr[] = {7, 3, 2, 1, 1, 7, -6, -1, 7};
    int aim = 7;
    System.out.println(maxLength(arr, aim));//7
}
复制代码

拓展

求奇数个数和偶数个数相同的最长子数组长度

将奇数置为1，偶数置为-1，就转化成了求和为0的最长子数组长度

求数值为1的个数和数值为2的个数相同的最长子数组（数组只含0、1、2三种元素）

将2置为-1，就转化成了求和为0的最长子数组长度

进阶

求任意划分数组的方案中，划分后，异或和为0的子数组最多有多少个

举例：给你一个数组[1,2,3,0,2,3,1,0]，你应该划分为[1,2,3],[0],[2,3,1],[0]，答案是4。

大前提：如果我们求出了以数组中每个数为结尾的所有子数组中，任意划分后，异或和为0的子数组最多有多少个，那么答案一定就在其中。

规律：异或运算符合交换律和结合律。0^N=N，N^N=0。

可能性分析：对于一个数组[i，……，j，m，……，n,k]，假设进行符合题意的最优划分后形成多个子数组后，k作为整个数组的末尾元素必定也是最后一个子数组的末尾元素。最后一个子数组只会有两种情况：异或和不为0、异或和为0。

  • 如果是前者，那么最后一个子数组即使去掉k这个元素，其异或和也不会为0，否则最优划分会将最后一个子数组划分为两个子数组，其中k单独为一个子数组。比如最后一个子数组是indexOf(m)~indexOf(k)，其异或和不为0，那么dp[indexOf(k)]=dp[indexOf(k)-1]，表示数组0~indexOf(k)的解和其子数组0~(indexOf(k)-1)的解是一样的。->case 1
  • 如果是后者，那么最后一个子数组中不可能存在以k为结尾的更小的异或和为0的子数组。比如最后一个子数组是indexOf(m)~indexOf(k)，其异或和为0，那么dp[indexOf(k)]=dp[indexOf(m)-1]+1，表示数组0~indexOf(k)的解=子数组0~(indexOf(m)-1)的解+1。->case 2

示例代码：

public static int maxSubArrs(int[] arr) {
    if (arr == null) {
        return 0;
    }
    HashMap<Integer, Integer> map = new HashMap();
    map.put(0, -1);
    int curXorSum = 0;
    int res = 0;
    int[] dp = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        curXorSum ^= arr[i];
        //case 1，之前没有出现过这个异或和，那么该位置上的dp等于前一个位置的dp
        if (!map.containsKey(curXorSum)) {
            dp[i] = i > 0 ? dp[i - 1] : 0;
        } else {
            //case 2，之前出现过这个异或和，那么之前这个异或和出现的位置到当前位置形成的子数组异或和为0
            int index = map.get(curXorSum);
            dp[i] = index > 0 ? dp[index] + 1 : 1;
        }
        //把最近出现的异或和都记录下来，因为要划分出最多的异或和为0的子数组
        map.put(curXorSum, i);
    }
    //最后一个位置的dp就是整个问题的解
    return dp[dp.length -1];
}

public static void main(String[] args) {
    int arr[] = {1, 2, 3, 0, 2, 3, 1, 0,4,1,3,2};
    System.out.println(maxSubArrs(arr));
}
复制代码

高度套路的二叉树信息收集问题

求一棵二叉树的最大搜索二叉子树的结点个数

最大搜索二叉子树指该二叉树的子树中，是搜索二叉树且结点个数最多的。

这类题一般都有一个大前提：假设对于以树中的任意结点为头结点的子树，我们都能求得其最大搜索二叉子树的结点个数，那么答案一定就在其中。

而对于以任意结点为头结点的子树，其最大搜索二叉子树的求解分为三种情况（列出可能性）：

  • 整棵树的最大搜索二叉子树存在于左子树中。这要求其左子树中存在最大搜索二叉子树，而其右子树不存在。
  • 整棵树的最大搜索二叉子树存在于右子树中。这要求其右子树中存在最大搜索二叉子树，而其左子树不存在。
  • 最整棵二叉树的最大搜索二叉子树就是其本身。这需要其左子树就是一棵搜索二叉子树且左子树的最大值结点比头结点小、其右子树就是一棵搜索二叉子树且右子树的最小值结点比头结点大。

要想区分这三种情况，我们需要收集的信息：

  • 子树中是否存在最大搜索二叉树
  • 子树的头结点
  • 子树的最大值结点
  • 子树的最小值结点

因此我们就可以开始我们的高度套路了：

  1. 将要从子树收集的信息封装成一个ReturnData，代表处理完这一棵子树要向上级返回的信息。
  2. 假设我利用子过程收集到了子树的信息，接下来根据子树的信息和分析问题时列出的情况加工出当前这棵树要为上级提供的所有信息，并返回给上级（整合信息）。
  3. 确定base case，子过程到子树为空时，停。

根据上面高度套路的分析，可以写出解决这类问题高度相似的代码：

public static class Node{
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data;
    }
}

public static class ReturnData {
    int size;
    Node head;
    int max;
    int min;
    public ReturnData(int size, Node head, int max, int min) {
        this.size = size;
        this.head = head;
        this.max = max;
        this.min = min;
    }
}

public static ReturnData process(Node root) {
    if (root == null) {
        return new ReturnData(0, null, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    ReturnData leftInfo = process(root.left);
    ReturnData rightInfo = process(root.right);
    
    //case 1
    int leftSize = leftInfo.size;
    //case 2
    int rightSize = rightInfo.size;
    int selfSize = 0;
    if (leftInfo.head == root.left && rightInfo.head == root.right
        && leftInfo.max < root.data && rightInfo.min > root.data) {
        //case 3
        selfSize = leftInfo.size + rightInfo.size + 1;
    }
    int maxSize = Math.max(Math.max(leftSize, rightSize), selfSize);
    Node maxHead = leftSize > rightSize ? leftInfo.head : 
    				selfSize > rightSize ? root : rightInfo.head;
    
    return new ReturnData(maxSize, maxHead, 
                          Math.max(Math.max(leftInfo.max, rightInfo.max), root.data), 
                          Math.min(Math.min(leftInfo.min, rightInfo.min), root.data));
}

public static void main(String[] args) {
    Node root = new Node(0);
    root.left = new Node(5);
    root.right = new Node(1);
    root.left.left = new Node(3);
    root.left.left.left = new Node(2);
    root.left.left.right = new Node(4);
    System.out.println(process(root).size);//4
}
复制代码

求一棵二叉树的最远距离

如果在二叉树中，小明从结点A出发，既可以往上走到达它的父结点，又可以往下走到达它的子结点，那么小明从结点A走到结点B最少要经过的结点个数（包括A和B）叫做A到B的距离，任意两结点所形成的距离中，最大的叫做树的最大距离。

高度套路化：

大前提：如果对于以该树的任意结点作为头结点的子树中，如果我们能够求得所有这些子树的最大距离，那么答案就在其中。

对于该树的任意子树，其最大距离的求解分为以下三种情况：

  • 该树的最大距离是左子树的最大距离。
  • 该树的最大距离是右子树的最大距离。
  • 该树的最大距离是从左子树的最深的那个结点经过该树的头结点走到右子树的最深的那个结点。

要从子树收集的信息：

  • 子树的最大距离
  • 子树的深度

示例代码：

public static class Node{
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data;
    }
}

public static class ReturnData{
    int maxDistance;
    int height;
    public ReturnData(int maxDistance, int height) {
        this.maxDistance = maxDistance;
        this.height = height;
    }
}

public static ReturnData process(Node root){
    if (root == null) {
        return new ReturnData(0, 0);
    }
    ReturnData leftInfo = process(root.left);
    ReturnData rightInfo = process(root.right);

    //case 1
    int leftMaxDistance = leftInfo.maxDistance;
    //case 2
    int rightMaxDistance = rightInfo.maxDistance;
    //case 3
    int includeHeadDistance = leftInfo.height + 1 + rightInfo.height;

    int max = Math.max(Math.max(leftMaxDistance, rightMaxDistance), includeHeadDistance);
    return new ReturnData(max, Math.max(leftInfo.height, rightInfo.height) + 1);
}

public static void main(String[] args) {
    Node root = new Node(0);
    root.left = new Node(5);
    root.right = new Node(1);
    root.right.right = new Node(6);
    root.left.left = new Node(3);
    root.left.left.left = new Node(2);
    root.left.left.right = new Node(4);
    System.out.println(process(root).maxDistance);
}
复制代码

高度套路化：列出可能性->从子过程收集的信息中整合出本过程要返回的信息->返回

舞会最大活跃度

一个公司的上下级关系是一棵多叉树，这个公司要举办晚会，你作为组织者已经摸清了大家的心理：一个员工的直 接上级如果到场，这个员工肯定不会来。每个员工都有一个活跃度的值（值越大，晚会上越活跃），你可以给某个员工发邀请函以决定谁来，怎么让舞会的气氛最活跃？返回最大的活跃值。

举例：

如果邀请A来，那么其直接下属BCD一定不会来，你可以邀请EFGHJKL中的任意几个来，如果都邀请，那么舞会最大活跃度为A(2)+E(9)+F(11)+G(2)+H(4)+J(7)+K(13)+L(5)；但如果选择不邀请A来，那么你可以邀请其直接下属BCD中任意几个来，比如邀请B而不邀请CD，那么B的直接下属E一定不回来，但CD的直接下属你可以选择性邀请。

大前提：如果你知道每个员工来舞会或不来舞会对舞会活跃值的影响，那么舞会最大活跃值就容易得知了。比如是否邀请A来取决于：B来或不来两种情况中选择对舞会活跃值增益最大的那个+C来或不来两种情况中选择对舞会活跃值增益最大的那个+D来或不来两种情况中选择对舞会活跃值增益最大的那个；同理，对于任意一名员工，是否邀请他来都是用此种决策。

列出可能性：来或不来。

子过程要收集的信息：返回子员工来对舞会活跃值的增益值和不来对舞会的增益值中的较大值。

示例代码：

public static class Node{
    int happy;
    List<Node> subs;
    public Node(int happy) {
        this.happy = happy;
        this.subs = new ArrayList<>();
    }
}

public static class ReturnData {
    int maxHappy;
    public ReturnData(int maxHappy) {
        this.maxHappy = maxHappy;
    }
}

public static ReturnData process(Node root) {
    if (root.subs.size() == 0) {
        return new ReturnData(root.happy);
    }
    //case 1:go
    int go_Happy = root.happy;
    //case 2:don't go
    int unGo_Happy = 0;
    for (Node sub : root.subs) {
        unGo_Happy += process(sub).maxHappy;
    }
    return new ReturnData(Math.max(go_Happy, unGo_Happy));
}

public static int maxPartyHappy(Node root) {
    if (root == null) {
        return 0;
    }
    return process(root).maxHappy;
}

public static void main(String[] args) {
    Node A = new Node(2);
    Node B = new Node(8);
    Node C = new Node(5);
    Node D = new Node(24);
    B.subs.add(new Node(9));
    C.subs.addAll(Arrays.asList(new Node(11),new Node(2),new Node(4),new Node(7)));
    D.subs.addAll(Arrays.asList(new Node(13), new Node(5)));
    A.subs.addAll(Arrays.asList(B, C, D));
    System.out.println(maxPartyHappy(A));//57
}
复制代码

求一个数学表达式的值

给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右括号，返回公式的计算结果。

举例：str="48*((70-65)-43)+8*1"，返回-1816。str="3+1*4"，返回7。 str="3+(1*4)"，返回7。

说明：

  1. 可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。
  2. 如果是负数，就需要用括号括起来，比如"4*(-3)"。但如果负数作为公式的开头或括号部分的开头，则可以没有括号，比如"-3*4"和"(-3*4)"都是合法的。
  3. 不用考虑计算过程中会发生溢出的情况

最优解分析：此题的难度在于如何处理表达式中的括号，可以借助一个栈。但如果仅仅靠一个栈，代码量会显得纷多繁杂。如果我们将式中包含左右括号的子表达式的计算单独抽出来作为一个过程（记为process），那么该过程可以被复用，如果我们将整个表达式中所有包含左右括号的子表达式当做一个数值，那么原始问题就转化为计算不含括号的表达式了。

以表达式3+2*5-(7+2)*3为例分析解题步骤：

示例代码：

public static int getValue(String exp){
    return process(exp.toCharArray(), 0)[0];
}

/** * @param exp expression * @param index the start index of expression * @return int[], include two elements:the result and the endIndex */
public static int[] process(char[] exp, int index) {

    LinkedList que = new LinkedList();
    //下一个要往队尾放的数
    int num = 0;
    //黑盒process返回的结果
    int sub[];

    while (index < exp.length && exp[index] != ')') {

        if (exp[index] >= '0' && exp[index] <= '9') {
            num = num * 10 + exp[index] - '0';
            index++;
        } else if (exp[index] != '(') {
            // +、-、*、/
            addNum(num, que);
            num = 0;
            que.addLast(String.valueOf(exp[index]));
            index++;
        } else {
            // '('
            sub = process(exp, index + 1);
            num = sub[0];
            index = sub[1] + 1;
        }
    }

    addNum(num, que);

    return new int[]{getSum(que), index};
}

private static int getSum(LinkedList<String> que) {
    int res = 0;
    boolean add = true;
    while (!que.isEmpty()) {
        int num = Integer.valueOf(que.pollFirst());
        res += add ? num : -num;
        if (!que.isEmpty()) {
            add = que.pollFirst().equals("+") ? true : false;
        }
    }
    return res;
}

private static void addNum(int num, LinkedList<String> que) {
    if (!que.isEmpty()) {
        String element = que.pollLast();
        if (element.equals("+") || element.equals("-")) {
            que.addLast(element);
        } else{
            // * or /
            Integer preNum = Integer.valueOf(que.pollLast());
            num = element.equals("*") ? (preNum * num) : (preNum / num);
        }
    }
    que.addLast(String.valueOf(num));
}

public static void main(String[] args) {
    String exp = "48*((70-65)-43)+8*1";
    System.out.println(getValue(exp));
    System.out.println(-48*38+8);
}
复制代码

求异或和最大的子数组

给你一个数组，让你找出所有子数组的异或和中，最大的是多少。

暴力解

遍历数组中的每个数，求出以该数结尾所有子数组的异或和。

public static class NumTrie{
    TrieNode root;

    public NumTrie() {
        root = new TrieNode();
    }

    class TrieNode{
        TrieNode[] nexts;
        public TrieNode(){
            nexts = new TrieNode[2];
        }
    }

    public void addNum(int num) {
        TrieNode cur = root;
        for (int i = 31; i >= 0; i--) {
            int path = (num >> i) & 1;
            if (cur.nexts[path] == null) {
                cur.nexts[path] = new TrieNode();
            }
            cur = cur.nexts[path];
        }
    }

    /** * find the max value of xor(0,k-1)^xor(0,i)-> the max value of xor(k,i) * @param num -> xor(0,i) * @return */
    public int maxXor(int num) {
        TrieNode cur = root;
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            int path = (num >> i) & 1;
            //如果是符号位，那么尽量和它相同（这样异或出来就是正数），如果是数值位那么尽量和它相反
            int bestPath = i == 31 ? path : (path ^ 1);
            //如果贪心路径不存在，就只能走另一条路
            bestPath = cur.nexts[bestPath] != null ? bestPath : (bestPath ^ 1);
            //记录该位上异或的结果
            res |= (bestPath ^ path) << i;

            cur = cur.nexts[bestPath];
        }
        return res;
    }
}

public static int maxXorSubArray(int arr[]) {
    int maxXorSum = Integer.MIN_VALUE;
    NumTrie numTrie = new NumTrie();
    //没有数时异或和为0，这个也要加到前缀数中，否则第一次到前缀树找bestPath会报空指针
    numTrie.addNum(0);
    int xorZeroToI = 0;
    for (int i = 0; i < arr.length; i++) {
        xorZeroToI ^= arr[i];
        maxXorSum = Math.max(maxXorSum, numTrie.maxXor(xorZeroToI));
        numTrie.addNum(xorZeroToI);
    }
    return maxXorSum;
}


public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 1, 2, -7};
    System.out.println(maxXorSubArray(arr));
}
复制代码

时间复杂度为O(N^3)

优化暴力解

观察暴力解，以 {1, 2, 3, 4, 1, 2, 0}为例，当我计算以4结尾的所有子数组的异或和时，我会先计算子数组{4}的，然后计算{3,4}的，然后计算{2,3,4}的，也就是说每次都是从头异或到尾，之前的计算的结果并没有为之后的计算过程加速。于是，我想着，当我计算{3,4}的时候，将3^4的结果临时保存一下，在下次的{2,3,4}的计算时复用一下，再保存一下2^3^4的结果，在下次的{1,2,3,4}的计算又可以复用一下。于是暴力解就被优化成了下面这个样子：

public static int solution2(int[] arr) {
    int res = 0;
    int temp=0;
    for (int i = 0; i < arr.length; i++) {
        //以i结尾的最大异或和
        int maxXorSum = 0;
        for (int j = i; j >= 0; j--) {
            temp ^= arr[j];
            maxXorSum = Math.max(maxXorSum, temp);
        }
        //整体的最大异或和
        res = Math.max(res, maxXorSum);
    }
    return res;
}

public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 1, 2, 0};
    System.out.println(solution2(arr));//7
}
复制代码

这时时间复杂度降为了O(N^2)

最优解

然而使用前缀树结构能够做到时间复杂度O(N)。

解题思路：将以i结尾的所有子数组的最大异或和的求解限制在O(1)。

解题技巧：

  1. 对于子数组0~i（i是合法下标）和0~i之间的下标k(k大于等于0，小于等于i)，k~i的异或和xor(k,i)、0~i的异或和xor(0,i)、0~k-1之间的异或和xor(0,k-1)三者之间存在如下关系：xor(k,i)=xor(0,i) ^ xor(o,k-1)（A^B=C -> B=C^A），因此求xor(k,i)的最大值可以转化成求xor(0,i) ^ xor(o,k-1)的最大值（这个思路很重要，后续步骤就是根据这个来的）。

  2. 遍历数组，将以首元素开头，以当前遍历元素结尾的子数组的异或和的32位二进制数放入前缀树结构中（每一位作为一个字符，且字符非0即1）。遍历结束后，所有0~i的异或和就存放在前缀树中了。比如：遍历{1, 2, 3, 4, 1, 2, 0}形成的前缀树如下：

  3. 假设遍历数组建立前缀树的过程中，遍历到4这个数来了，将0 100放入其中，由于之前还遍历过1,2,3，所以xor(0,0)、xor(0,1)、xor(0,2)也是在前缀树中的。如果此时要求xor(k,3)的最大值（k在下标0和3之间且包括0和3），可以将其转化为求xor(0,3) ^ xor(0,k-1)，而我们已知xor(0,3)=0 100，所以xor(0,k-1)的求解就变成了关键。

    xor(0,k-1)的求解：此时游标cur从前缀树的根结点走向叶子结点，cur沿途经过的二进制位连在一起就是xor(0,k-1)，要求每次选择要经过哪个二进制位时，尽可能使之与xor(0,3)的异或结果更大：

    这个求解过程就是在贪心（如果是符号位，那么尽可能让异或结果为0，如果是数值位，那么尽可能让异或结果为1），前缀树里只放着xor(0,0)、xor(0,1)、xor(0,2)、xor(0,3)，而xor(0,k-1)只能从中取值，这个从根节点一步步试探走到叶子结点的过程就是在贪，哪一条路径对应的xor使得xor ^ xor(0,3)最大。

    示例代码：

    public static class NumTrie{
    TrieNode root;

    public NumTrie() {
        root = new TrieNode();
    }

    class TrieNode{
        TrieNode[] nexts;
        public TrieNode(){
            nexts = new TrieNode[2];
        }
    }

    public void addNum(int num) {
        TrieNode cur = root;
        for (int i = 31; i >= 0; i--) {
            int path = (num >> i) & 1;
            if (cur.nexts[path] == null) {
                cur.nexts[path] = new TrieNode();
            }
            cur = cur.nexts[path];
        }
    }

    /** * find the max value of xor(0,k-1)^xor(0,i)-> the max value of xor(k,i) * @param num -> xor(0,i) * @return */
    public int maxXor(int num) {
        TrieNode cur = root;
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            int path = (num >> i) & 1;
            //如果是符号位，那么尽量和它相同（这样异或出来就是正数），如果是数值位那么尽量和它相反
            int bestPath = i == 31 ? path : (path ^ 1);
            //如果贪心路径不存在，就只能走另一条路
            bestPath = cur.nexts[bestPath] != null ? bestPath : (bestPath ^ 1);
            //记录该位上异或的结果
            res |= (bestPath ^ path) << i;

            cur = cur.nexts[bestPath];
        }
        return res;
    }
}

public static int maxXorSubArray(int arr[]) {
    int maxXorSum = 0;
    NumTrie numTrie = new NumTrie();
    //一个数自己异或自己异或和为0，这个也要加到前缀数中，否则第一次到前缀树找bestPath会报空指针
    numTrie.addNum(0);
    int xorZeroToI = 0;
    for (int i = 0; i < arr.length; i++) {
        xorZeroToI ^= arr[i];
        maxXorSum = Math.max(maxXorSum, numTrie.maxXor(xorZeroToI));
        numTrie.addNum(xorZeroToI);
    }
    return maxXorSum;
}


public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 1, 2, -7};
    System.out.println(maxXorSubArray(arr));//7
}
复制代码

求和为aim的最长子数组（都大于0）

基础篇中有过相同的题，只不过这里的数组元素值为正数，而基础篇中的可正可负可0。

基础篇中的做法是用一个哈希表记录子数组和出现的最早的位置。而此题由于数据特殊性（都是正数）可以在额外空间复杂度O(1)，时间复杂度O(N)内完成。

使用一个窗口，用L表示窗口的左边界、R表示窗口的右边界，用sum表示窗口内元素之和（初始为0）。起初，L和R都停在-1位置上，接下来每次都要将L向右扩一步或将R向右扩一步，具体扩哪个视情况而定：

  • 如果sum<aim，那么R往右边扩
  • 如果sum=aim，那么记录窗口内元素个数，L往右边扩
  • 如果sum>aim，那么L往右边扩

直到R扩到arr.length越界，那么此时窗口内元素之和必定小于aim，整个过程可以结束。答案就是所有sum=aim情况下窗口内元素最多时的个数。

示例代码：

/** * 数组元素均为正数，求和为aim的最长子数组的长度 * @param arr * @return */
public static int aimMaxSubArray(int arr[],int aim) {
    int L=-1;
    int R= -1;
    int sum = 0;
    int len=0;
    while (R != arr.length) {
        if (sum < aim) {
            R++;
            if (R < arr.length) {
                sum += arr[R];
            } else {
                break;
            }
        } else if (sum == aim) {
            len = Math.max(len, R - L);
            sum -= arr[++L];
        } else {
            sum -= arr[++L];
        }
    }
    return len;
}

public static void main(String[] args) {
    int arr[] = {1, 2, 3, 5, 1, 1, 1, 1, 1, 1, 9};
    System.out.println(aimMaxSubArray(arr,6));
}
复制代码

思考：为什么这个流程得到的答案是正确的呢？也就是说，为什么窗口向右滑动的过程中，不会错过和为aim的最长子数组？我们可以来证明一下：

假设，椭圆区域就是和为aim的最长子数组，如果L来到了椭圆区域的左边界L2，那么R的位置有两种情况：在椭圆区域内比如R1，在椭圆区域外比如R2。如果是前者，由于窗口L2~R1是肯定小于aim的（元素都是正数），因此在R从R1右移到椭圆区域右边界过程中，L是始终在L2上的，显然不会错过正确答案；如果是后者，窗口L2~R2的sum明显超过了aim，因此这种情况是不可能存在的。而L在L2左边的位置上，比如L1时，R更不可能越过椭圆区域来到了R2，因为窗口是始终保持sum<=aim的。

求和小于等于aim的最长子数组（有正有负有0）

如果使用暴力枚举，枚举出以每个元素开头的子数组，那么答案一定就在其中（O(N^3)）。但这里介绍一种时间复杂度O(N)的解。

首先从尾到头遍历一遍数组，生成两个辅助数组min_sum和min_sum_index作为求解时的辅助信息。min_sum表示以某个元素开头的所有子数组中和最小为多少，min_sum_index则对应保存该最小和子数组的结束下标。

举例：对于[100,200,7,-6]。

  1. 首先遍历3位置上的-6，以-6开头的子数组只有[-6]，因此min_sum[3] = -6, min_sum_index[3] = 3（[-6]的尾元素-6在原数组中的下标是3）。
  2. 接着遍历到2位置上的7，以7开头的最小和子数组是[7,-6]，因此min_sum[2] = 7-6 = 1, min_sum_index[2]=3。（[7,-6]的尾元素-6在原数组中的下标是3）。
  3. 接着遍历到1位置上的200，有min_sum[1] = 200, min_sum_index[1] = 1。
  4. 接着遍历到0位置上的100，有min_sum[0] = 100, min_sum_index[0] = 0。

那么遍历完数组，生成两个辅助数组之后，就可以开始正式的求解流程了：

使用一个窗口，L表示窗口的左边界，R表示窗口的右边界，sum表示窗口内元素之和。

  • L从头到尾依次来到数组中的每个元素，每次L来到其中一个元素上时，都尝试向右扩R，R扩到不能扩时，窗口大小R-L即为以该元素开头的、和小于等于aim的最长子数组的长度。
  • L起初来到首元素，R起初也停在首元素，sum=0。
  • R向右扩一次的逻辑是：如果sum + min_sum[L] <= aim，那么R就扩到min_sum_index[L] + 1的位置，并更新sum。
  • R扩到不能扩时，记录R-L，L去往下一个元素，并更新sum。
  • 如果L来到一个元素后，sum > aim，说明以该元素开头的、和小于等于aim的最长子数组的长度，比当前的窗口大小R-L还要小，那么以该元素开头的子数组不在正确答案的考虑范围之内（因为上一个元素形成的最大窗口大于当前元素能形成的最大窗口，并且前者已经被记录过了），L直接去往一下个元素并更新sum。

示例代码：

public static int lessOrEqualAim(int arr[], int aim) {
    int min_sum[] = new int[arr.length];
    int min_sum_index[] = new int[arr.length];
    min_sum[arr.length-1] = arr[arr.length - 1];
    min_sum_index[arr.length-1] = arr.length - 1;
    for (int i = arr.length - 2; i >= 0; i--) {
        if (min_sum[i + 1] < 0) {
            min_sum[i] = arr[i] + min_sum[i + 1];
            min_sum_index[i] = min_sum_index[i + 1];
        } else {
            min_sum[i] = arr[i];
            min_sum_index[i] = i;
        }
    }

    int R = 0;
    int sum = 0;
    int maxLen = 0;
    for (int L = 0; L < arr.length; L++) {
        while (R < arr.length && sum + min_sum[R] <= aim) {
            sum += min_sum[R];
            R = min_sum_index[R] + 1;
        }
        maxLen = Math.max(maxLen, R - L);
        sum -= R == L ? 0 : arr[L];
        R = Math.max(R, L + 1);
    }
    return maxLen;
}

public static void main(String[] args) {
    int arr[] = {1, 2, 3, 2, -1, -1, 1, 1, -1, -1, 9};
    System.out.println(lessOrEqualAim(arr,3));//8
}
复制代码

19-27行是实现的难点，首先19行是L从头到尾来到数组中的每个元素，然后20-23的while是尝试让R扩直到R扩不动为止，24行当R扩不动时就可以记录以当前L位置上的元素开头的、和小于等于aim的最长子数组长度，最后在进入下一次for循环、L右移一步之前，sum的更新有两种情况：

  1. 29行的while执行了，R扩出去了，因此sum直接减去当前L上的元素即可。
  2. 29行的while压根就没执行，R一步都没扩出去且和L在同一位置上，也就是说此刻窗口内没有元素（只有当R>L时，窗口才包含从L开始到R之前的元素），sum=0，L和R应该同时来到下一个元素，sum仍为0，所以sum不必减去arr[L]（只有当L右移导致一个元素从窗口出去时才需要减arr[L]）。

最后26行也是为了保证如果L在右移的过程中，R一直都扩不出去，那么在L右移到R上R仍旧扩不出去时，接下来R应该和L同时右移一个位置。

此方法能够做到O(N)时间复杂度的关键点是：舍去无效情况。比如L在右移一步更新sum之后，如果发现sum > aim，显然以当前L开头的、和小于等于aim的最长子数组肯定小于当前的R-L，而在上一步就记录了R-(L-1)，以当前L开头的满足条件的子数组可以忽略掉（因为一定小于R-(L-1)），而不必让R回退到当前L重新来扩R。

这样L和R都只右移而不回退，所以时间复杂度就是遍历了一遍数组。

环形单链表的约瑟夫问题

据说著名犹太历史学家Josephus有过以下故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，报数到3的人就自杀，然后再由下一个人重新报1，报数到3的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表描述该结构并呈现整个自杀过程。

输入：一个环形单向链表的头节点head和报数的值m。

返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删掉。

进阶：如果链表节点数为N，想在时间复杂度为O(N)时完成原问题的要求，该怎么实现？

暴力方法：从头结点开始数，从1数到m，数到m时删除结点，再从下一个结点开始数……如此要删除（n-1）个结点，并且每次删除之前要数m个数，因此时间复杂度为O(NxM)

这里介绍一种O(N)的方法。

首先介绍一个函数：

如果从头结点开始，为每个结点依次编号1、2、3、……，比如环形链表有3个结点，每次报数到7时杀人：

结点编号 报数
1 1
2 2
3 3
1 4
2 5
3 6
1 杀人

那么在杀人之前，结点编号和报数有如下对应关系（x轴代表此刻报数报到哪儿了，y轴则对应是几号结点报的，n是结点数量）：

假设每次杀人后，都从下一结点重新编号、重新报数，比如环形链表有9个结点，报数到7就杀人，那么杀人之前结点的旧编号和杀人重新编号后结点的新编号有如下关系：

旧编号 新编号
1 3
2 4
3 5
4 6
5 7
6 8
7 被杀，从下一结点开始重新编号
8 1
9 2

如果链表结点数为n，报数到m杀人，那么结点的新旧编号对应关系如下（其中s为报数为m的结点编号）：

这个图也可以由基本函数y = (x - 1) % n + 1向左平移s个单位长度变换而来：

即y = (x - 1 + s) % n + 1。

现在我们有了如下两个公式：

  1. 结点编号 = (报数 - 1) % n + 1
  2. 旧编号 = (新编号 - 1 + s) % n +1，其中s为报数为m的结点编号

由1式可得s = (m - 1) % n + 1，带入2式可得

  1. 旧编号 = (新编号 - 1 + (m - 1) % n + 1) % n + 1 = (新编号 + m - 1) % n + 1，其中m和n由输入参数决定。

现在我们有了等式3，就可以在已知一个结点在另一个结点被杀之后的新编号的情况下，求出该结点的旧编号。也就是说，假设现在杀到了第n-1个结点，杀完之后只剩下最后一个结点了（天选结点），重新编号后天选结点肯定是1号，那么第n-1个被杀结点被杀之前天选结点的编号我们就可以通过等式3求出来，通过这个结果我们又能求得天选结点在第n-2个被杀结点被杀之前的编号，……，依次往回推就能还原一个结点都没死时天选结点的编号，这样我们就能从输入的链表中找到该结点，直接将其后继指针指向自己然后返回即可。

示例代码：

static class Node {
    char data;
    Node next;

    public Node(char data) {
        this.data = data;
    }
}

public static Node aliveNode(Node head, int m) {
    if (head == null) {
        return null;
    }
    int tmp = 1;
    Node cur = head.next;
    while (cur != head) {
        tmp++;
        cur = cur.next;
    }

    //第n-1次杀人前还有两个结点，杀完之后天选结点的新编号为1
    //通过递归调用getAlive推出所有结点存活时，天选结点的编号
    int nodeNumber = getAlive(1, m, 2, tmp);

    cur = head;
    tmp = 1;
    while (tmp != nodeNumber) {
        cur = cur.next;
        tmp++;
    }
    cur.next = cur;
    return cur;
}

/** * 旧编号 = (新编号 + m - 1) % n + 1 * * @param newNumber 新编号 * @param m * @param n 旧编号对应的存活的结点个数 * @param len 结点总个数 * @return */
public static int getAlive(int newNumber, int m, int n, int len) {
    if (n == len) {
        return (newNumber + m - 1) % n + 1;
    }
    //计算出新编号对应的旧编号，将该旧编号作为下一次计算的新编号
    return getAlive((newNumber + m - 1) % n + 1, m, n + 1, len);
}

public static void main(String[] args) {
    Node head = new Node('a');
    head.next = new Node('b');
    head.next.next = new Node('c');
    head.next.next.next = new Node('d');
    head.next.next.next.next = new Node('e');
    head.next.next.next.next.next = head;

    System.out.println(aliveNode(head, 3).data);//d
}
复制代码

经典结构

窗口最大值更新结构

最大值更新结构

当向此结构放数据时会检查一下结构中的已有数据，从时间戳最大的开始检查，如果检查过程中发现该数据小于即将放入的数据则将其弹出并检查下一个，直到即将放入的数据小于正在检查的数据或者结构中的数据都被弹出了为止，再将要放入的数据放入结构中并盖上时间戳。如此每次从该结构取数据时，都会返回结构中时间戳最小的数据，也是目前为止进入过此结构的所有数据中最大的那一个。

此结构可以使用一个双端队列来实现，一端只用来放数据（放数据之前的检查过程可能会弹出其他数据），另一端用来获取目前为止出现过的最大值。

示例如下：

package top.zhenganwen.structure;

import java.util.LinkedList;

public class MaxValueWindow {

  private LinkedList<Integer> queue;
  public MaxValueWindow() {
    this.queue = new LinkedList();
  }

  //更新窗口最大值
  public void add(int i){
    while (!queue.isEmpty() && queue.getLast() <= i) {
      queue.pollLast();
    }
    queue.add(i);
  }

  //获取窗口最大值
  public int getMax() {
    if (!queue.isEmpty()) {
      return queue.peek();
    }
    return Integer.MIN_VALUE;
  }

  //使窗口最大值过期
  public void expireMaxValue() {
    if (!queue.isEmpty()) {
      queue.poll();
    }
  }

  public static void main(String[] args) {
    MaxValueWindow window = new MaxValueWindow();
    window.add(6);
    window.add(4);
    window.add(9);
    window.add(8);
    System.out.println(window.getMax());//9
    window.expireMaxValue();
    System.out.println(window.getMax());//8
  }
}
复制代码

例题

窗口移动

给你一个长度为N的整型数组和大小为W的窗口，用一个长度为N-W+1的数组记录窗口从数组由左向右移动过程中窗口内最大值。

对于数组[1,2,3,4,5,6,7]和窗口大小为3，窗口由左向右移动时有：

  • [1,2,3],4,5,6,7，窗口起始下标为0时，框住的数是1,2,3，最大值是3
  • 1,[2,3,4],5,6,7，最大值是4
  • 1,2,[3,4,5],6,7，最大值是5
  • ……

因此所求数组是[3,4,5,6,7]。

思路：前面介绍的窗口最大值更新结构的特性是，先前放入的数如果还存在于结构中，那么该数一定比后放入的数都大。此题窗口移动的过程就是从窗口中减一个数和增一个数的过程。拿[1,2,3],4到1,[2,3,4]这一过程分析：首先[1,2,3],4状态下的窗口应该只有一个值3（因为先加了1，加2之前弹出了1，加3之前弹出了2）；转变为1,[2,3,4]的过程就是向窗口先减一个数1再加一个数4的过程，因为窗口中不含1所以直接加一个数4（弹出窗口中的3，加一个数4）。

代码示例：

public static void add(int arr[], int index, LinkedList<Integer> queue) {
  if (queue == null) {
    return;
  }
  while (!queue.isEmpty() && arr[queue.getLast()] < arr[index]) {
    queue.pollLast();
  }
  queue.add(index);
}

public static void expireIndex(int index, LinkedList<Integer> queue) {
  if (queue == null) {
    return;
  }
  if (!queue.isEmpty() && queue.peek() == index) {
    queue.pollFirst();
  }
}

public static int[] maxValues(int[] arr, int w) {
  int[] res = new int[arr.length - w + 1];
  LinkedList<Integer> queue = new LinkedList();
  for (int i = 0; i < w; i++) {
    add(arr, i, queue);
  }
  for (int i = 0; i < res.length; i++) {
    res[i] = queue.peek();
    if (i + w <= arr.length - 1) {
      expireIndex(i, queue);
      add(arr, i + w, queue);
    }
  }
  for (int i = 0; i < res.length; i++) {
    res[i] = arr[res[i]];
  }
  return res;
}

public static void main(String[] args) {
  int[] arr = {3, 2, 1, 5, 6, 2, 7, 8, 10, 6};
  System.out.println(Arrays.toString(maxValues(arr,3)));//[3, 5, 6, 6, 7, 8, 10, 10]
}
复制代码

这里需要的注意的是，针对这道题将窗口最大值更新结构的add和expire方法做了改进（结构中存的是值对应的下标）。例如[2,1,2],-1->2,[1,2,-1]，应当翻译为[2,1,2],-1状态下的窗口最大值为2下标上的数2，变为2,[1,2,-1]时应当翻译为下标为0的数从窗口过期了，而不应该是数据2从窗口过期了（这样会误删窗口中下标为2的最大值2）。

求达标的子数组个数

给你一个整型数组，判断其所有子数组中最大值和最小值的差值不超过num（如果满足则称该数组达标）的个数。（子数组指原数组中任意个连续下标上的元素组成的数组）

暴力解：遍历每个元素，再遍历以当前元素为首的所有子数组，再遍历子数组找到其中的最大值和最小值以判断其是否达标。很显然这种方法的时间复杂度为o(N^3)，但如果使用最大值更新结构，则能实现O(N)级别的解。

如果使用L和R两个指针指向数组的两个下标，且L在R的左边。当L~R这一子数组达标时，可以推导出以L开头的长度不超过R-L+1的所有子数组都达标；当L~R这一子数组不达标时，无论L向左扩多少个位置或者R向右扩多少个位置，L~R还是不达标。

O(N)的解对应的算法是：L和R都从0开始，R先向右移动，R每右移一个位置就使用最大值更新结构和最小值更新结构记录一下L~R之间的最大值和最小值的下标，当R移动到如果再右移一个位置L~R就不达标了时停止，这时以当前L开头的长度不超过R-L+1的子数组都达标；然后L右移一个位置，同时更新一下最大值、最小值更新结构（L-1下标过期了），再右移R至R如果右移一个位置L~R就不达标了停止（每右移R一次也更新最大、小值更新结构）……；直到L到达数组尾元素为止。将每次R停止时，R-L+1的数量累加起来就是O(N)的解，因为L和R都只向右移动，并且每次R停止时，以L开头的达标子串的数量直接通过R-L+1计算，所以时间复杂度就是将数组遍历了一遍即O(N)。

示例代码：

public static int getComplianceChildArr(int arr[], int num) {
  //最大值、最小值更新结构
  LinkedList<Integer> maxq = new LinkedList();
  LinkedList<Integer> minq = new LinkedList<>();
  int L = 0;
  int R = 0;
  maxq.add(0);
  minq.add(0);
  int res = 0;
  while (L < arr.length) {
    while (R < arr.length - 1) {
      while (!maxq.isEmpty() && arr[maxq.getLast()] <= arr[R + 1]) {
        maxq.pollLast();
      }
      maxq.add(R + 1);
      while (!minq.isEmpty() && arr[minq.getLast()] >= arr[R + 1]) {
        minq.pollLast();
      }
      minq.add(R + 1);
      if (arr[maxq.peekFirst()] - arr[minq.peekFirst()] > num) {
        break;
      }
      R++;
    }
    res += (R - L + 1);
    if (maxq.peekFirst() == L) {
      maxq.pollFirst();
    }
    if (minq.peekFirst() == L) {
      minq.pollFirst();
    }
    L++;
  }
  return res;
}

public static void main(String[] args) {
  int[] arr = {1, 2, 3, 5};
  System.out.println(getComplianceChildArr(arr, 3));//9
}
复制代码