leetcode算法

反转链表

反转一个单链表。

1 2	输入: 1->2->3->4->5 输出: 5->4->3->2->1

解法1：迭代，重复某一过程，每一次处理结果作为下一次处理的初始值，这些初始值类似于状态、每

次处理都会改变状态、直至到达最终状态

从前往后遍历链表，将当前节点的next指向上一个节点，因此需要一个变量存储上一个节点prev，当前

节点处理完需要寻找下一个节点，因此需要一个变量保存当前节点curr，处理完后要将当前节点赋值给

prev，并将next指针赋值给curr，因此需要一个变量提前保存下一个节点的指针next

1、将下一个节点指针保存到next变量 next = curr.next

2、将下一个节点的指针指向prev，curr.next = prev

3、准备处理下一个节点，将curr赋值给prev

4、将下一个节点赋值为curr，处理一个节点

解法2：递归：以相似的方法重复，类似于树结构，先从根节点找到叶子节点，从叶子节点开始遍历

大的问题(整个链表反转)拆成性质相同的小问题(两个元素反转)curr.next.next = curr

将所有的小问题解决，大问题即解决

只需每个元素都执行curr.next.next = curr，curr.next = null两个步骤即可

为了保证链不断，必须从最后一个元素开始

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

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

    // 迭代
    public static ListNode iterate(ListNode head){
        ListNode prev = null;  // 临时头节点
        ListNode next = null;  // 下一个节点
        ListNode curr = head;  // 当前节点
        while (curr != null) {
            next = curr.next;  // 临时保存当前节点的下一个节点
            curr.next = prev;   // 临时头结点指向当前节点的下一个节点
            prev = curr;       // 当前节点赋值给临时头节点
            curr = next;      // 下一个节点赋值为当前节点
        }
        return prev;
    }

    // 递归 recursion
    public static ListNode recursion(ListNode head){
        // head 为当前节点
        // newNode 为头节点
        if (head == null || head.next == null ) {
            return head;
        }
        ListNode newNode = recursion( head.next);
        head.next.next = head;  // head.next 当前节点的下一个节点， 设置当前节点为下一个节点的下一个节点
        head.next = null; // 当前节点的下一个节点设为空
        return newNode;
    }

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        ListNode prev = iterate(node1);
        System.out.println(prev);
    }
}

统计N以内的素数

素数：只能被1和自身整除的数，0、1除外

解法一：暴力算法

直接从2开始遍历，判断是否能被2到自身之间的数整除

// 判断是否素数
public static boolean isPrime(int n){
    for (int i = 2; i * i  <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// 暴力算法
public static int bf(int n){
    int count = 0;
    for (int i = 2; i < n; i++) {
        count += isPrime(i) ? 1 : 0;
    }
    return count;
}

解法2：埃氏筛

利用合数的概念(非素数)，素数*n必然是合数，因此可以从2开始遍历，将所有的合数做上标记

// 素数  非素数(合数)
    public static int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n]; // false 代表素数
        int count = 0;
        for (int i = 2; i < n; i++){
            if(!isPrime[i]) {
                count++;
                for(int j = i * i; j < n; j += i){
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }

将合数标记为true，j = i * i 从 2 * i 优化而来，系数2会随着遍历递增（j += i，相当于递增了系数2），

每一个合数都会有两个比本身要小的因子(0,1除外)，2 * i 必然会遍历到这两个因子

当2递增到大于根号n时，其实后面的已经无需再判断（或者只需判断后面一段），而2到根号n、实际

上在 i 递增的过程中已经计算过了，i 实际上就相当于根号n

例如：n = 25 会计算以下

2 * 4 = 8

3 * 4 = 12

但实际上8和12已经标记过，在n = 17时已经计算了 3 * 4，2 * 4

删除排序数组中的重复项

一个有序数组 nums ，原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

双指针算法：

数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要

nums[i]=nums[j]，我们就增加 j 以跳过重复项。

当遇到 nums[j] ！= nums[i]时，跳过重复项的运行已经结束，必须把nums[j]）的值复制到 nums[i +

1]。然后递增 i，接着将再次重复相同的过程，直到 j 到达数组的末尾为止。

public static int removeDuplicates(int[] nums){
       int i = 0;
       for (int j = 1; j < nums.length; j++){
           if(nums[j] != nums[i]) {
               i++;
               nums[i] = nums[j];
           }
       }
       return i + 1;
   }

寻找数组的中心索引

数组中某一个下标，左右两边的元素之后相等，该下标即为中心索引

思路：先统计出整个数组的总和，然后从第一个元素开始叠加

总和递减当前元素，叠加递增当前元素，知道两个值相等

public static int pivotIndex(int[] nums) { 
       int sum1 = Arrays.stream(nums).sum(); 
       int sum2 = 0; 
       for(int i = 0; i<nums.length; i++){
           sum2 += nums[i]; 
           if(sum1 == sum2){ 
               return i; 
           }
           sum1 = sum1 - nums[i];
       }
       return -1; 
   }

x的平方根

在不使用 sqrt(x) 函数的情况下，得到 x的平方根的整数部分

解法一：二分查找

x的平方根肯定在0到x之间，使用二分查找定位该数字，该数字的平方一定是最接近x的，m平方值如果

大于x、则往左边找，如果小于等于x则往右边找

找到0和X的最中间的数m，

如果m * m > x，则m取x/2到x的中间数字，直到m * m < x，m则为平方根的整数部分

如果m * m <= x，则取0到x/2的中间值，知道两边的界限重合，找到最大的整数，则为x平方根的整数部分

时间复杂度：O(logN)

三个数的最大乘积

一个整型数组 nums ，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。乘积不会越界

如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。

如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。

分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。

解法一：排序

public static int sort(int[] nums) {
      Arrays.sort(nums);
      int n = nums.length;
      return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
  }

解法二：线性扫描

public static int getMaxMin(int[] nums) {
        // 最小的和第二小的
        int min1 = 0, min2 = 0;
        // 最大的、第二大的和第三大的
        int max1 = 0, max2 = 0, max3 = 0;
        for (int x : nums) { 
            if (x < min1) { 
                min2 = min1; min1 = x; 
            } else if (x < min2) { 
                min2 = x; 
            }
            if (x > max1) { 
                max3 = max2; max2 = max1; max1 = x; 
            } else if (x > max2) {
                max3 = max2; max2 = x; 
            } else if (x > max3) { 
                max3 = x; 
            } 
        }
        return Math.max(min1 * min2 * max1, max1 * max2 * max3); 
    }

两数之和（无序）

给定一个升序排列的整数数组 numbers ，从数组中找出两个数满足相加之和等于目标数 target 。

假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素。

返回两数的下标值，以数组形式返回

暴力解法

public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

时间复杂度：O(N的平方)

空间复杂度：O(1)

哈希表：将数组的值作为key存入map，target - num作为key

public int[] twoSum(int[] nums, int target) {
      Map<Integer, Integer> map = new HashMap<Integer, Integer>();
      for (int i = 0; i < nums.length; ++i) {
          if (map.containsKey(target - nums[i])) {
              return new int[]{map.get(target - nums[i]), i};
          }
          map.put(nums[i], i);
      }
      return new int[0];
  }

时间复杂度：O(N)

空间复杂度：O(N)

两数之和（升序）

解法一：二分查找

先固定一个值(从下标0开始)，再用二分查找查另外一个值，找不到则固定值向右移动，继续二分查找

public int[] twoSearch(int[] numbers, int target) {
       for (int i = 0; i < numbers.length; ++i) {
           int low = i, high = numbers.length - 1;
           while (low <= high) {
               int mid = (high - low) / 2 + low;
               if (numbers[mid] == target - numbers[i]) {
                   return new int[]{i, mid};
               } else if (numbers[mid] > target - numbers[i]) {
                   high = mid - 1;
               } else {
                   low = mid + 1;
               }
           }
       }
   }

时间复杂度：O(N * logN)

空间复杂度：O(1)

解法二：双指针

左指针指向数组head，右指针指向数组tail，head+tail > target 则tail 左移，否则head右移

public int[] twoPoint(int[] numbers, int target) {
       int low = 0, high = numbers.length - 1;
       while (low < high) {
           int sum = numbers[low] + numbers[high];
           if (sum == target) {
               return new int[]{low + 1, high + 1};
           } else if (sum < target) {
               ++low;
           } else {
               --high;
           }
       }
       return new int[]{-1, -1};
   }

时间复杂度：O(N)

空间复杂度：O(1)

斐波那契数列

求取斐波那契数列第N位的值。

斐波那契数列：每一位的值等于他前两位数字之和。前两位固定 0，1,1,2,3,5,8。。。。

解法一：暴力递归

public static int calculate(int num) {
       if (num == 0) {
           return 0;
       }
       if (num == 1) {
           return 1;
       }
       return calculate(num - 1) + calculate(num - 2);
   }

解法二：去重递归

递归得出具体数值之后、存储到一个集合(下标与数列下标一致)，后面递归之前先到该集合查询一次，

如果查到则无需递归、直接取值。查不到再进行递归计算

public static int calculate2(int num) {
       int[] arr = new int[num + 1];
       return recurse(arr, num);
   }

   private static int recurse(int[] arr, int num) {
       if (num == 0) {
           return 0;
       }
       if (num == 1) {
           return 1;
       }
       if (arr[num] != 0) {
           return arr[num];
       }
       arr[num] = recurse(arr, num - 1) + recurse(arr, num - 2);
       return arr[num];
   }

解法三：双指针迭代

基于去重递归优化，集合没有必要保存每一个下标值，只需保存前两位即可，向后遍历，得出N的值

排列硬币

总共有 n 枚硬币，将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。

n 是一个非负整数，并且在32位有符号整型的范围内

解法一：迭代

从第一行开始排列，排完一列、计算剩余硬币数，排第二列，直至剩余硬币数小于或等于行数

public static int arrangeCoins(int n) {
     for (int i = 1; i <= n; i++) {
         n = n - i;
         if (n <= i) {
             return i;
         }
     }
     return 0;
 }

解法二：二分查找

假设能排 n 行，计算 n 行需要多少硬币数，如果大于 n，则排 n/2行，再计算硬币数和 n 的大小关系

public static int arrangeCoins2(int n) {
        int low = 0, high = n;
        while (low <= high) {
            long mid = (high - low) / 2 + low;
            long cost = ((mid + 1) * mid) / 2;
            if (cost == n ) {
                return (int) mid;
            } else if (cost > n) {
                high = (int) mid - 1;
            } else {
                low = (int) mid + 1;
            }
        }
        return high;
    }

解法三：牛顿迭代

使用牛顿迭代求平方根，(x + n/x)/2

假设能排 x 行则 1 + 2 + 3 + …+ x = n，即 x(x+1)/2 = n 推导出 x = 2n - x

public static double sqrts(double x, int n) {
       double res = (x + (2 * n - x) / x) / 2;
       if (res == x) {
           return x;
       } else {
           return sqrts(res, n);
       }
   }

环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达该节点，则链表中存在环

如果链表中存在环，则返回 true 。否则，返回 false 。

解法一：哈希表

public static boolean hasCycle(ListNode head) {
       Set<ListNode> seen = new HashSet<ListNode>();
       while (head != null) {
           if (!seen.add(head)) {
               return true;
           }
           head = head.next;
       }
       return false;
   }

解法二：双指针

public static boolean hasCycle2(ListNode head){
      if (head == null){
          return false;
      }
      ListNode slow = head;
      ListNode quick = head.next;
      while (slow != quick){
          if(quick == null || quick.next == null){
              return false;
          }
          slow = slow.next;
          quick = quick.next.next;
      }
      return true;
  }

合并两个有序数组

两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。假设 nums1 的空间大小等于 m + n，这样它就

有足够的空间保存来自 nums2 的元素。

解法一：合并后排序

public void merge(int[] nums1, int m, int[] nums2, int n) {
       System.arraycopy(nums2, 0, nums1, m, n);
       Arrays.sort(nums1);
   }

时间复杂度 : O((n+m)log(n+m))。

空间复杂度 : O(1)。

解法二：双指针从前往后

将两个数组按顺序进行比较，放入新的数组

public static int[] merge(int[] nums1, int m, int[] nums2, int n) {
      int [] nums1_copy = new int[m];
      System.arraycopy(nums1, 0, nums1_copy, 0, m);//拷贝数组1
      int p1 = 0; // 指向nums1_copy
      int p2 = 0; // 指向nums2
      int p = 0;  // 指向nums1

      while (p1 < m && p2 < n){
          nums1[p++] = nums1_copy[p1] < nums2[p2] ? nums1_copy[p1++] : nums2[p2++];
      }
      if (p1 < m){
          System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
      }
      if (p2 < n){
          System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
      }
      return nums1;
  }

时间复杂度 : O(n + m)。

空间复杂度 : O(m)。

解法三：双指针优化

从后往前

public void merge(int[] nums1, int m, int[] nums2, int n) {
       int p1 = m - 1;
       int p2 = n - 1;
       int p = m + n - 1;
       while ((p1 >= 0) && (p2 >= 0)) nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
       System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
   }

时间复杂度 : O(n + m)。

空间复杂度 : O(1)。

子数组最大平均数

给一个整数数组，找出平均数最大且长度为 k 的下标连续的子数组，并输出该最大平均数。

滑动窗口：

窗口移动时，窗口内的和等于sum加上新加进来的值，减去出去的值

public static double findMaxAverage(int[] nums, int k) {
      int sum = 0;
      int n = nums.length;
      // 先统计第一个窗口的和
      for (int i = 0; i < k; i++) {
          sum += nums[i];
      }
      int max = sum;
      for (int i = k; i < n; i++){
          sum = sum - nums[i - k] + nums[i];
          max = Math.max(sum, max);
      }
      return 1.0 * max / k;
  }

二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

解法一：深度优先

遍历整颗数，找到每一个叶子节点，从叶子节点往上开始计算，左右子节点都为空则记录深度为1

左右子节点只有一边，深度记录为子节点深度+1

左右两边都有子节点，则记录左右子节点的深度较小值+1

public static int minDepth(TreeNode root){
       if(root == null){
           return 0;
       }
       if(root.left == null && root.right == null){
           return 1;
       }

       int min = Integer.MAX_VALUE;
       if (root.left != null){
           min = Math.min(minDepth(root.left), min);
       }
       if (root.right != null){
           min = Math.min( minDepth(root.right), min);
       }
       return min + 1;
   }

public class TreeNode {

    public int val;
    public TreeNode left;
    public TreeNode right;
    public int deep;

    public TreeNode (int val, TreeNode left, TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

时间复杂度：O(N)

空间复杂度：O(logN) 取决于树的高度

解法二：广度优先

从上往下，找到一个节点时，标记这个节点的深度。查看该节点是否为叶子节点，如果是直接返回深度

如果不是叶子节点，将其子节点标记深度(在父节点深度的基础上加1)，再判断该节点是否为叶子节点

public static int minDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList();
        int deep;
        root.deep = 1;
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (node.left == null && node.right == null) {
                return node.deep;
            }
            if (node.left != null){
                node.left.deep = node.deep + 1;
                queue.offer(node.left);
            }

            if (node.right != null){
                node.right.deep = node.deep + 1;
                queue.offer(node.right);
            }
        }

        return 0;
    }

public class QueueNode {
    public TreeNode node;
    public int depth;

    public QueueNode(TreeNode node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

时间复杂度：O(N)

空间复杂度：O(N)

最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。序列的下标是连续的

贪心算法

从0开始寻找递增序列，并将长度记录，记录递增序列的最后一个下标，然后从该下标继续寻找，记录长度，取长度最大的即可

public static int findLength(int[] nums){
     int start = 0;  // 临时开始位置
     int max = 0;   // 最大长度
    for(int i = 1; i < nums.length; i++){
        if(nums[i] <= nums[i - 1]){
            start = i;
        }
        max = Math.max(max, i - start + 1);
    }
    return max;
}

柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。必须给每个顾客正确找零

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

1 2	输入：[5,5,5,10,20] 输出：true 输入：[10,10] 输出：false

贪心：

public static boolean change(int[] bills){
       int five = 0, ten = 0;
       for(int bill : bills){
           if (bill == 5){
               five++;
           }else if(bill == 10){
               if (five == 0){
                   return false;
               }
               five--;
               ten++;
           }else{
               if(five > 0 && ten > 0){
                   five--;
                   ten--;
               }else if(five > 2 ){
                   five -= 3;
               }else {
                   return false;
               }
           }
       }
      return true;
  }

三角形的最大周长

给定由一些正数（代表长度）组成的数组 A ，返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形，返回 0 。

贪心：

先小到大排序，假设最长边是最后下标，另外两条边是倒数第二和第三下标，则此时三角形周长最大

n < (n-1) + (n-2)，如果不成立，意味着该数组中不可能有另外两个值之和大于n，此时将n左移，重新计算

public int largestPerimeter(int[] A) {
      Arrays.sort(A);
      for (int i = A.length - 1; i >= 2; --i) {
          if (A[i - 2] + A[i - 1] > A[i]) {
              return A[i - 2] + A[i - 1] + A[i];
          }
      }
      return 0;
  }

二叉树遍历

从根节点往下查找，先找左子树、直至左子树为空(左子节点逐个入栈、直至左子节点为空)，再找右子树(出栈找右子节点)

前序遍历：根左右，第一次经过节点即打印，直到打印null，往回溯，打印右子树

中序遍历：左根右，第二次经过该节点时进行打印，即左边回溯时

后序遍历：左右根，第三次经过该节点时进行打印，即右边回溯时

层序遍历：按照层级，从上往下，从左到右。使用广度优先搜索算法。

递归遍历：

public static void preorder(TreeNode root) {
       if (root == null) {
           return;
       }
       System.out.println(root.val);//前序 第一次成为栈顶
       preorder(root.left);
      // System.out.println(root.val);//中序 第二次成为栈顶
       preorder(root.right);
       //System.out.println(root.val);//后序 第三次成为栈顶
   }

迭代遍历

// 前序遍历， 根 左右
  public static void preorder2(TreeNode root) {
      if (root != null) {
          Stack<TreeNode> stack = new Stack<>();
          stack.add(root);
          while (!stack.isEmpty()) {
              root = stack.pop();
              if (root != null){
                  System.out.println(root.val);
                  stack.push(root.right);
                  stack.push(root.left);
              }
          }
      }
  }

// 中序遍历   左根右
   public static void midorder(TreeNode root) {
       if (root != null) {
           Stack<TreeNode> stack = new Stack<>();
           while (!stack.isEmpty() || root.left != null) {
               if (root != null){
                   stack.push(root);
                   root = root.left;
               }else {
                   root = stack.pop();
                   System.out.println(root.val);
                   root = root.right;
               }
           }
       }
   }

// 后序遍历   左右根
   public static void postorder(TreeNode root) {
       if (root != null) {
           Stack<TreeNode> stack = new Stack<>();
           TreeNode prev = null;
           while (!stack.isEmpty() || root != null) {
               while (root != null){
                   stack.push(root);
                   root = root.left;
               }
               root = stack.pop();
               if(root.right == null || root.right == prev){
                   System.out.println(root.val);
                   prev = root;
                   root = null;
               }else {
                   stack.push(root);
                   root = root.right;
               }
           }
       }
   }

层序遍历：

public static void levelOrder(TreeNode root){
      Queue<TreeNode> queue = new LinkedList<>();
      queue.add(root);
      while (!queue.isEmpty()){
          TreeNode node = queue.poll();
          if (node != null){
              System.out.println(node.val);
              queue.add(node.left);
              queue.add(node.right);
          }
      }
  }

线索二叉树：

在N个节点的二叉树中，每个节点有2个指针，所以一共有2N个指针，除了根节点以外，每一个节点都有一个指针从它的父节点指向它，所以一共使用了N-1个指针，所以剩下2N-(N-1)也就是N+1个空指针；

如果能利用这些空指针域来存放指向该节点的直接前驱或是直接后继的指针，则可由此信息直接找到在该遍历次序下的前驱节点或后继节点，从而比递归遍历提高了遍历速度，节省了建立系统递归栈所使用的存储空间；

这些被重新利用起来的空指针就被称为线索（Thread），加上了线索的二叉树就是线索二叉树

实现思路：按某种次序遍历二叉树，在遍历过程中用线索取代空指针即可。以中序遍历为例，首先找到中序遍历的开始节点，然后利用线索依次查找后继节点即可。

由于它充分利用了空指针域的空间（等于节省了空间），又保证了创建时的一次遍历就可以终生受用前驱、后继的信息（这意味着节省了时间），所以在实际问题中，如果所使用的二叉树需要经常遍历或查找节点时需要某种遍历中的前驱和后继，那么采用线索二叉链表的存储结构就是不错的选择

morris遍历：构建中序线索二叉树的过程中，如果发现前驱节点的右指针指向自身，则将指针（线索）删除

public static void morrisPre(TreeNode cur){
      if(cur == null){
          return;
      }
      TreeNode mostRight = null;
      while(cur != null){
          // cur 表示当前节点， mostRight 表示cur的左孩子的最右节点
          mostRight = cur.left;
          if(mostRight != null){
              // cur有左孩子，找到cur左子树最右节点
              while(mostRight.right != null && mostRight.right != cur){
                  mostRight = mostRight.right;
              }
              // mostRight 的又孩子指向空， 让其指向cur，cur向左移动
              if(mostRight.right == null){ // // mostRight.right != cur  建立线索指针
                  mostRight.right = cur;
                  System.out.println(cur.val);
                  cur = cur.left;
                  continue;
              }else { // mostRight.right == cur  删除线索指针
                  // mostRight 的右孩子指向cur, 让其指向空， cur向右移动
                  mostRight.right = null;
              }
          }else {
              System.out.println(cur.val);
          }
          cur = cur.right;
      }
  }

省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

解法一：深度优先

public static void main(String[] args) {
       System.out.println(getProvince(new int[][]{{1,1,0}, {1,1,0},{0,0,1}}));
       System.out.println(getProvince(new int[][]{{1,0,0}, {0,1,0},{0,0,1}}));
   }

   private static int getProvince(int[][] cityConnected){
       int citys = cityConnected.length;
       boolean[] visited = new boolean[citys];
       int provinces = 0; // 计数器
       for(int i = 0; i < citys; i++){
           if(!visited[i]){
               // 深度优先
               dfs(i, citys,visited, cityConnected);
               provinces++;
           }
       }
       return provinces;
   }

   private static void dfs(int i, int citys, boolean[] visited, int[][] cityConnected) {
       for(int j = 0; j < citys; j++){
           if(cityConnected[i][j] == 1 && !visited[j] ){
               visited[j] = true;
               dfs(j,  citys,  visited, cityConnected);
           }
       }
   }

解法二：广度优先

获取一个城市，先标记与该城市直连的城市(最近的)，然后逐步向外扩散寻找

public static void main(String[] args) {
       System.out.println(bfs(new int[][]{{1, 1, 0, 0}, {1, 1, 0, 1}, {0, 0, 1, 0}, {0, 1, 0, 1}}));
       System.out.println(bfs(new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}));
   }

   public static int bfs(int[][] isConnected) {
       int provinces = isConnected.length;
       boolean[] visited = new boolean[provinces];
       int circles = 0;
       Queue<Integer> queue = new LinkedList<Integer>();
       for (int i = 0; i < provinces; i++) {
           if (!visited[i]) {
               queue.offer(i);
               while (!queue.isEmpty()) {
                   int j = queue.poll();
                   visited[j] = true;
                   for (int k = 0; k < provinces; k++) {
                       if (isConnected[j][k] == 1 && !visited[k]) {
                           queue.offer(k);
                       }
                   }
               }
               circles++;
           }
       }
       return circles;
   }

解法三：并查集

将每个城市看成一个节点，如果两个城市相连，则建立树关系，选出其中一个为head，

如果两个树中的节点也相连，则将其中一个head设置为另一个树的head

两个方法：一个寻找head节点，一个合并树

public static void main(String[] args) {
       System.out.println(mergeFind(new int[][]{{1, 1, 0, 0}, {1, 1, 0, 1}, {0, 0, 1, 0}, {0, 1, 0, 1}}));
       System.out.println(mergeFind(new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}));
   }

   static int mergeFind(int[][] isConnected) {
       int provinces = isConnected.length;
       int[] head = new int[provinces];
       int[] level = new int[provinces];
       for (int i = 0; i < provinces; i++) {
           head[i] = i;
           level[i] = 1;
       }
       for (int i = 0; i < provinces; i++) {
           for (int j = i + 1; j < provinces; j++) {
               if (isConnected[i][j] == 1) {
                   merge(i, j, head, level);
               }
           }
       }
       int count = 0;
       //找出所有的head
       for (int i = 0; i < provinces; i++) {
           if (head[i] == i) {
               count++;
           }
       }
       return count;
   }

   //查找head节点
   static int find(int x, int[] arr) {
       if (arr[x] == x)
           return x;
       else
           arr[x] = find(arr[x], arr);
       //路径压缩，每一个节点直接能找到head
       return arr[x];
   }

   static void merge(int x, int y, int[] arr, int[] level) {
       int i = find(x, arr);
       int j = find(y, arr);
       //深度比较短的树的head往深度大的树上挂，使合并后的深度尽量小
       if (i == j) {
           return;
       }
       if (level[i] <= level[j]) {
           arr[i] = j;
       } else {
           arr[j] = i;
       }
       //深度加1
       level[j]++;
   }

预测赢家

给定一个表示分数的非负整数数组。玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

两个值的时候必然是取较大的，三个值，取一个能使自己分数和最大的，后手必然留较小的给先手，因此先手选一个值加上该较小值最大化

static int maxScore(int[] nums, int l, int r) {
       //剩下一个值，只能取该值
       if (l == r) {
           return nums[l];
       }
       int selectLeft = 0, selectRight = nums.length - 1;
       //剩下大于两个值，先手选一边(使自己得分最高的一边)，后手则选使对手得分最低的一边
       if ((r - l) >= 2) {
           int num =  maxScore(nums, l + 1, r - 1);
           selectLeft = nums[l] + Math.min(maxScore(nums, l + 2, r),num);
           selectRight = nums[r] + Math.min(num, maxScore(nums, l, r - 2));
       }
       //剩下两个值，取较大的
       if ((r - l) == 1) {
           selectLeft = nums[l];
           selectRight = nums[r];
       }
       return Math.max(selectLeft, selectRight);
   }

// 差值
  static int maxScore1(int[] nums, int l, int r){
      //剩下一个值，只能取该值
      if (l == r) {
          return nums[l];
      }
      int selectLeft = nums[l] - maxScore1(nums, l + 1, r);  // l + 1 到 r 之间的差值
      int selectRight = nums[r] - maxScore1(nums, l , r - 1);
      return Math.max(selectLeft, selectRight);
  }

动态规划：使用二维数组存储差值

public boolean PredictTheWinner(int[] nums) {
       int length = nums.length;
       int[][] dp = new int[length][length];
       for (int i = 0; i < length; i++) {
           dp[i][i] = nums[i];
       }
       for (int i = length - 2; i >= 0; i--) {
           for (int j = i + 1; j < length; j++) {
               //j = i +1 因此可以优化为一维数组,下标位置相同才有值，据此推导其他的值
               // Math.max(nums[i] - dp[j][j], nums[j] - dp[j - 1][j - 1]);
               dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
           }
       }
       return dp[0][length - 1] >= 0;
   }

香槟塔

我们把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，第二层有2个，依次类推到第100层，每个玻璃杯(250ml)将盛有香槟。

从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）

例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟

现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（i 和 j都从0 开始）。

public static double champagneTower(int poured, int query_row, int query_glass) {
        double[][] A = new double[102][102];
        A[0][0] = (double) poured;
        for (int r = 0; r <= query_row; ++r) {
            for (int c = 0; c <= r; ++c) {
                double q = (A[r][c] - 1.0) / 2.0;
                if (q > 0) {
                    A[r + 1][c] += q;
                    A[r + 1][c + 1] += q;
                }
            }
        }
        return Math.min(1, A[query_row][query_glass]);
    }

井字游戏

用字符串数组作为井字游戏的游戏板 board，判断该游戏板有没有可能最终形成游戏板是一个 3 x 3 数组，由字符 “ “，”X” 和 “O” 组成。字符 “ “ 代表一个空位。

两个玩家轮流将字符放入空位，一个玩家执X棋，另一个玩家执O棋 “X” 和 “O” 只允许放置在空位中，不允许对已放有字符的位置进行填充。

当有 3 个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，board生成

分类讨论

public static void main(String[] args) {
       System.out.println(validBoard(new String[]{"XXX", " XO", "O O"}));
   }

   public static boolean validBoard(String[] board) {
       int xCount = 0, oCount = 0;
       for (String row : board)
           for (char c : row.toCharArray()) {
               if (c == 'X') xCount++;
               if (c == 'O') oCount++;
           }
       //X与O 一样多，或者X比O多一个(X赢则X多一个，O赢则一样多)
       if (oCount != xCount && oCount != xCount - 1) return false;
       if (win(board, "XXX") && oCount != xCount - 1) return false;
       if (win(board, "OOO") && oCount != xCount) return false;
       return true;
   }

   public static boolean win(String[] board, String flag) {
       for (int i = 0; i < 3; ++i) {
           //纵向3连
           if (flag.equals("" + board[i].charAt(0) + board[i].charAt(1) + board[i].charAt(2))) return true;
           //横向3连
           if (flag.equals(board[i])) return true;
       }
       // \向3连
       if (flag.equals("" + board[0].charAt(0) + board[1].charAt(1) + board[2].charAt(2))) return true;
       // /向3连
       if (flag.equals("" + board[0].charAt(2) + board[1].charAt(1) + board[2].charAt(0))) return true;
       return false;
   }

字符串匹配

字符串匹配是计算机科学领域中最古老、研究最普遍的问题之一，层出不穷的前辈们也总结了很是多经典的优秀算法，例如 BF 算法、RK 算法、BM 算法、KMP 算法，今天我介绍的主角是 BM 算法。java

字符串匹配能够简单归纳为前缀匹配，后缀匹配，子串匹配，下面的讲解我都以最多见的子串匹配为例。子串匹配的概念很简单，一句话解释就是：在一个字符串 A 中寻找另外一个字符串 B，这里的字符串 A 能够叫作主串，字符串 B 能够叫作 模式串。

BF 算法

在一个字符串中寻找另外一字符串，最容易想到的，也是最简单的办法是：取主串和模式串中的每一位依次比较，若是匹配则同时后移一位继续比较，直至匹配到模式串的最后一位；若是出现不匹配的字符，则模式串向后移动一位，继续比较。这种解决问题的思路简单暴力，也是这个算法被叫作BF（Brute Force）的缘由。数组

整个匹配的过程能够参考下图：

整个代码实现也很是简单，我这里写一个示例供参考

public static int bruteForce(String main, String ptn){
    if (main == null || ptn == null){
        return -1;
    }

    int m = main.length();
    int n = ptn.length();
    if (n > m){
        return bf(ptn, main);
    }

    for (int i = 0; i <= m - n; i++) {
        int j = i;
        int k = 0;
        while (k < n && main.charAt(j) == ptn.charAt(k)){
            ++j;
            ++k;
        }
        if (k == n){
            return i;
        }
    }
    return -1;
}

时间复杂度是 O(m * n) 。

空间复杂度是 O(1)

RK 算法

RK 算法是以其两位发明者 Rabin、Karp 的名字命名的，它实际上是 BF 算法的一个优化版本。设计

前面讲到的 BF 算法，每次在主串和模式串进行匹配时，都须要遍历模式串，而 RK 算法借助了哈希算法来下降时间复杂度。

当模式串和主串进行比较时，并不直接依次遍历每一个字符，而是计算主串的子字符串的哈希值，而后将哈希值和模式串的哈希值进行比较，若是哈希值相等，则能够断定匹配成功，整个匹配的过程能够参考下图：

能够看到，优化的地方在于将每次的遍历模式串比较，变成了哈希值之间的比较，这样的话匹配的速度就加快了。但须要注意的是，若是求解哈希值的函数须要遍历字符串的话，那么这个算法的时间复杂度并无获得提高，反而还有可能降低，由于每次遍历的话，这和 BF 算法暴力匹配的思路就没有区别了，因此哈希函数的设计就要避免这个问题。

容易想到的一种简单的哈希函数是，直接将每一个字符的 ASCII 码相加，获得一个哈希值。假设主串是 a b d e a，模式串为 d e a ，长度是 3，第一次匹配时，取的子字符串是 a b d，第二次取的子字符串是 b d e，能够看到这两个子字符串是有重合的部分的，只有首尾两个字符不同，因此代码实现能够利用这一点来避免遍历字符串。固然这种哈希函数比较简单，还有其余一些更加精妙的设计，感兴趣的话能够自行研究下。

还有一个问题即是，若是存在哈希冲突的话，即两个字符串的哈希值虽然同样，可是字符串可能并不同，这个问题的解决思路其实很简单，当哈希值相同时，再依次遍历两个字符串看是否相同，若是相同，则匹配成功。由于哈希冲突并不会常常出现，因此这一次的依次遍历匹配的开销仍是能够接受的，对算法总体效率的影响并不大。

下面是一个简单的代码示例供参考：

public static int rabinKarp(String main, String ptn){
    if (main == null || ptn == null){
        return -1;
    }

    int m = main.length();
    int n = ptn.length();
    if (n > m){
        return rk(ptn, main);
    }

    //计算模式串的hash值
    int ptnHash = 0;
    for (int i = 0; i < n; i++) {
        ptnHash += ptn.charAt(i);
    }

    int mainHash = 0;
    for (int i = 0; i <= m - n; i++) {
        //i == 0时须要遍历计算哈希值，后续不须要
        if (i == 0) {
            for (int j = 0; j < n; j++) {
                mainHash += main.charAt(j);
            }
        }else {
            mainHash = mainHash - main.charAt(i - 1) + main.charAt(i + n - 1);
        }

        //若是哈希值相同，为避免哈希冲突，再依次遍历比较
        if (mainHash == ptnHash){
            int k = i;
            int j = 0;
            while (j < n && main.charAt(k) == ptn.charAt(j)){
                ++k;
                ++j;
            }
            if (j == n){
                return i;
            }
        }
    }

    return -1;
}

模式串和主串之间的匹配是常数时间的，最多只须要遍历 m - n + 1 次，再加上可能存在哈希冲突的状况，所以 RK 算法的整体的时间复杂度大概为 O(m)。

在极端状况下，若是哈希函数设计得十分不合理，产生哈希冲突的几率很高的话，那么每次遍历都须要扫描一遍模式串，那么算法的时间复杂度就退化为 O(m * n) 了。

时间复杂度 O(m) 最坏 O(m * n)

BM 算法

了解了两种基本的字符串匹配算法以后，其实能够发现 BF 算法和 RK 算法都存在一个很明显的缺陷，那就是若是出现了不匹配的状况，那么每次模式串都是向后移动一位，而后再继续比较。那有没有更加高效的办法让模式串多移动几位呢，这就是 BM 算法试图解决的问题。

BM 算法也是由两位发明者 Boyer 和 Moore 的名字命名的，其核心思想是在主串和模式串进行比较时，若是出现了不匹配的状况，可以尽量多的获取一些信息，借此跳过那些确定不会匹配的状况，以此来提高字符串匹配的效率，大多数文本编辑器中的字符查找功能，通常都会使用 BM 算法来实现。

BM 算法主要由两部分组成，分别是坏字符规则和好后缀规则，下面依次介绍。

坏字符规则

前面说到的字符串匹配，匹配的顺序都是从前到后，按位依次匹配的，而利用坏字符规则的时候，主串和模式串的匹配顺序是从后往前，倒着匹配的，像下图这样：

匹配的时候，若是主串中的字符和模式串的字符不匹配，那么就将主串中这个字符叫作坏字符，例如上图中的字符 e，由于它和模式串中的 d 不匹配：

若是遇到了坏字符，能够看到坏字符 e 在模式串中是不存在的，那么能够断定，主串中字符 e 以前的部分确定不会匹配，所以能够直接将模式串移动至坏字符 e后面继续匹配，相较于暴力匹配每次移动一位，这样显然更加高效：

但须要注意的是，若是坏字符在模式串中是存在的，那么就不能直接移动模式串至坏字符的后面了，而是将模式串移动至和坏字符相同的字符处，而后继续比较，参考下图：

能够看到，坏字符可能在模式串中存在多个，那么移动模式串的时候，应该移动至更靠前的那个，仍是更靠后的那个呢？为了不错过正确匹配的状况，咱们应该移动更少的位数，所以必须移动至更靠后的那个坏字符处。就像上图中的那样，坏字符 f在模式串中存在两个，移动时须要将模式串移动至更靠后的那个坏字符处。

总结一下规律，当匹配的时候，若是遇到了坏字符，有两种状况：一是坏字符不在模式串中，那么直接移动模式串至坏字符后一位；若是坏字符在模式串中，那么移动模式串至与坏字符匹配的最靠后的那个字符处，而后继续比较。

如今很关键的一个问题来了，咱们怎么知道一个字符在模式串中是否存在呢？最常规的思路是遍历整个模式串，查找是否存在，可是这样的时间复杂度是 O(n)，对算法效率的影响很大，有没有更加高效的方法呢？此时很容易想到哈希表，哈希表的特性是经过哈希映射实现了高效的查找，用到如今这个场合是很是合适的。

先假设一种比较基础的状况，咱们的匹配的字符只包含常规的英文字符，总共 256 个，那么能够构建一个数组，模式串中字符的 ACSII 码为数组的下标，下标对应的值为模式串每一个字符的位置，参考下图：

这样，当匹配的时候，若是遇到了坏字符，就能够从数组中对应的下标查询，若是值大于等于 0，说明坏字符在模式串中，而且数组中的值是字符在模式串中的位置，能够利用这个值来判断模式串移动的位数，大体的代码实现以下：

private static final int[] badChar = new int[256];

    public static int bm(String main, String ptn){
        if (main == null || ptn == null){
            return -1;
        }

        int m = main.length();
        int n = ptn.length();
        badCharRule(ptn, badChar);

        int i = n - 1;
        while (i <= m - 1) {
            int j = n - 1;
            while (j >= 0 && main.charAt(i) == ptn.charAt(j)){
                --i;
                if (--j == -1){
                    return i + 1;
                }
            }

            //计算坏字符规则下移动的位数
            int moveWithBC = j - badChar[main.charAt(i)];
            i += moveWithBC;
        }

        return -1;
    }

    /**
     * 生成坏字符数组
     */
    private static void badCharRule(String str, int[] badChar){
        if (str == null){
           return;
        }

        Arrays.fill(badChar, -1);
        for (int i = 0; i < str.length(); i++) {
            badChar[str.charAt(i)] = i;
        }
    }

坏字符规则虽然利用起来比较高效，可是在某些状况下，它仍是有点问题的，例如主串是 a a a a a a a a ，模式串是 b a a a的这种状况，若是利用坏字符规则，那么计算出来的移动位数有多是负数，所以 BM 算法还须要使用好后缀规则来避免这种状况。

好后缀规则

好后缀规则要稍微复杂一点了，当匹配的时候，若是遇到了坏字符，而且若是前面已经有匹配的字符的话，那么就把这段字符叫作好后缀，参考下图：

和坏字符规则的处理思路相似，若是出现了好后缀，那么能够查看好后缀在模式串中是否存在。

第一种状况，若是不存在的话，则直接移动模式串至好后缀的后一位，而后继续匹配。例以下图中的好后缀 a f 在模式串中是不存在的，所以移动模式串至a f 后面：

可是这样移动会存在一个问题，例以下面的这个例子，主串是c a c d e f a d e f c a，模式串是e f a d e f，好后缀 d e f 虽然在模式串中是不存在的，若是直接移动模式串至好后缀的后面，那么就会错过正确匹配的状况，因此下图这样的移动方式就是错误的：

因此这种状况下应该怎么移动呢？能够看到，虽然好后缀 d e f 不在模式串中，可是好后缀的后缀子串 e f 和模式串的前缀子串 e f 是相同的，所以咱们须要移动模式串至和好后缀的后缀子串重合的地方。

这段话稍微有点很差理解，再来解释一下，一个字符串的后缀子串，就是除了第一个字符的其他子串，例如字符串 d e f，它的后缀子串就有两个，分别是 f、e f；而一个字符串的前缀子串，就是除了最后一个字符的其他子串，例如 a d e f，它的前缀子串就有 a、a d、a d e 这三个。

具体到上面的那个例子，好后缀是 d e f ，它的一个后缀子串 e f 和模式串的前缀子串 e f 是匹配的，所以须要移动至两部分重合的地方：

而后再看第二种状况，就很简单了，若是好后缀在模式串中是存在的，那么移动模式串至和好后缀匹配的地方：

总结一下规律，好后缀状况下，模式串的移动整体分为了三种状况，一是好后缀在模式串中，那么移动模式串至好后缀匹配的地方，二是好后缀不在模式串中，而且好后缀的后缀子串和模式串的前缀子串无重合部分，那么直接移动模式串至好后缀的后一位，三是好后缀不在模式串中，可是好后缀的后缀子串和模式串的前缀子串有重合部分，那么须要移动模式串至和好后缀的后缀子串重合的地方，参考下图：

再来看看这部分的代码实现，所以好后缀自己也是在模式串中的，因此整个好后缀的匹配均可以经过预处理模式串来解决。

这里引入一个 int 类型的数组 suffix，长度为模式串的长度，数组的下标为模式串后缀子串的长度，值为后缀子串在模式串中可匹配的子串的起始下标；而后再引入一个 boolean 类型的 prefix 数组，它表示的是模式串的后缀子串是否有可匹配的前缀子串，若是有，则值为 true。

计算 suffix 数组和 prefix 数组的代码以下：

/**
 * 生成好后缀数组
 */
private static void goodSuffixRule(String str, int[] suffix, boolean[] prefix){
    if (str == null){
        return;
    }

    Arrays.fill(suffix, -1);
    Arrays.fill(prefix, false);

    int n = str.length();
    for (int i = 0; i < n - 1; i++){
        int j = i;
        int k = 0;

        while (j >= 0 && str.charAt(j) == str.charAt(n - k - 1)){
            --j;
            ++k;
            suffix[k] = j + 1;
        }
        if (j == -1){
            prefix[k] = true;
        }
    }
}

这段代码稍微有点难以理解，看的时候能够举一个具体的例子，而后根据代码推出来结果，这样理解起来会比较容易些。

根据生成的这两个数组，就能够计算在好后缀状况下的模式串移动位数，须要注意的是，前面坏字符状况下也有一个模式串移动的位数，这二者该如何选择呢？其实很是简单，咱们固然但愿模式串可以尽可能多移动一点，所以只须要取这两个规则所计算出来的移动位数中的较大的那个值便可。

将坏字符规则和好后缀规则两种状况结合在一块儿，就是 BM 算法的完整实现，代码以下：

public class BoyerMoore {
    
    private static final int[] badChar = new int[256];

    public static int bm(String main, String ptn){
        if (main == null || ptn == null){
            return -1;
        }

        int m = main.length();
        int n = ptn.length();
        badCharRule(ptn, badChar);

        int[] suffix = new int[n];
        boolean[] prefix = new boolean[n];
        goodSuffixRule(ptn, suffix, prefix);

        int i = n - 1;
        while (i <= m - 1) {
            int j = n - 1;
            while (j >= 0 && main.charAt(i) == ptn.charAt(j)){
                --i;
                if (--j == -1){
                    return i + 1;
                }
            }

            //计算坏字符规则下移动的位数
            int moveWithBC = j - badChar[main.charAt(i)];

            //计算好后缀规则下移动的位数
            int moveWithGS = Integer.MIN_VALUE;
            if (j < n - 1){
                moveWithGS = moveWithGS(n, j, suffix, prefix);
            }
            i += Math.max(moveWithBC, moveWithGS);
        }

        return -1;
    }

    /**
     * 生成坏字符数组
     */
    private static void badCharRule(String str, int[] badChar){
        Arrays.fill(badChar, -1);
        for (int i = 0; i < str.length(); i++) {
            badChar[str.charAt(i)] = i;
        }
    }

    /**
     * 生成好后缀数组
     */
    private static void goodSuffixRule(String str, int[] suffix, boolean[] prefix){
        Arrays.fill(suffix, -1);
        Arrays.fill(prefix, false);

        int n = str.length();
        for (int i = 0; i < n - 1; i++){
            int j = i;
            int k = 0;

            while (j >= 0 && str.charAt(j) == str.charAt(n - k - 1)){
                --j;
                ++k;
                suffix[k] = j + 1;
            }
            if (j == -1){
                prefix[k] = true;
            }
        }
    }

    /**
     * 计算好后缀状况下的移动位数
     */
    private static int moveWithGS(int n, int j, int[] suffix, boolean[] prefix){
        int k = n - j - 1;
        if (suffix[k] != -1){
            return j - suffix[k] + 1;
        }

        for (int i = k - 1; i >= 0; i--) {
            if (prefix[i]){
                return n - i;
            }
        }

        return n;
    }
}

KMP

在KMP算法中有个数组，叫做前缀数组，也有的叫next数组，每一个子串有一个固定的next数组，它记录着字符串匹配过程中失配情况下可以向前多跳几个字符，当然它描述的也是子串的对称程度，程度越高，值越大，当然之前可能出现再匹配的机会就更大

源字符串：aaacdaaaxb，目标字符串：aaax

第一步还是和之前一样，从起始位置开始对字符一一进行比较。

但是第二步开始和之前不同，在KMP算法中，我们通常不用将字符串位置全部回溯，因为很明显，目标字符串的第2、3个字符和源字符串的2、3个字符已经比较过是相等的，既然比较过是相等的，后面如果采用暴力破解法中的方式全部回溯显然是没有必要的，如果全部回溯必然某个位置还是会不等。

所以我们可以跳过这两个已经比较过的字符，也就是 i 不用进行回溯，我们回溯的是指向目标字符串的指针 j 。故第二步为：

再次进行比较后直接就不相等，那么我们继续回溯指向目标字符串的指针 j，i 仍然不用回溯。故第三步：

还是不相等，目标字符串已经无法回溯了，就保持当前指向的位置，且i仍不需要回溯，最后再次进行比较，可以看到，就可以得到结果了。

可以看到在上面的算法中，我们只有四步就完成了我们的需求，而使用暴力破解法，由于每次指向源字符串的指针 i 和指向目标字符串的指针 j 都需要回溯，所以效率很低。使用KMP算法只回溯了 j ，大幅提高效率。

在上图第一步到第二步时我们说过，因为有些部分已经比较过了，所以不需要再进行比较，虽然人很容易发现这一点，但是怎么让计算机实现我们的想法，就是我们需要解决的问题。

前缀和后缀

既然 i 值不进行回溯，所以我们可以不考虑 i 的问题，考虑的是 j 的问题，j 是指向目标字符串的每一个字符的，所以这个问题也可以转换为对目标字符串的处理。

这个 j 值其实和源字符串没什么关系，关键是取决于目标字符串中字符的重复问题。如下图，目标字符串 target="abcdf" ，没有一个重复元素，所以当下一次比较时，由4转换为0，从字符串索引 0 处重新开始比较：

而像前面的字符串就如 target="aaax" 时，显然就不需要全部回溯，也就是说，我们需要在查找字符串之前，对目标字符串进行处理，就可以减少查找的难度，大幅提高查找效率。而KMP算法中，就是推到出如下图中的一个辅助数组：

通过上面的数组，我们可以得到这么一个函数公式，用于定义辅助数组next：

很多人看到这个公式可能就懵逼了，什么是公共后缀？？前面没说说过呀，别急，下面进行讲解，我们先了解一下字符串的前缀和后缀。我们还是以图的方式先简单了解一下前后缀的方式

可以发现，前缀和后缀的区别就是：

前缀就是除了不包含最后一个字符外，其他的所有从索引为0开始向后偏移的子字符串。
后缀就是除了不包含第一个字符串外，其他所有从索引为length() - 1 开始向前偏移的子字符串。

而公共后缀，就是前缀集合和后缀集合中相交部分的最大长度。

next 辅助数组推导

知道了上面的知识，我们应该就更能吗明白，如何通过上上图中的函数公式，求得next数组了，毕竟如果我们人都不会，如何写的出算法让计算机”理解”呢？

例1：设目标字符串 target="ababd"，则其next数组如下：

计算步骤：

当 k=0 时，next[0] = -1。

当 k = 1 时，其前面只有一个a，无前后缀，故 next[1] = 0。

当 k = 2 时，其前面的字符串为ab，前缀为a，后缀为b，无公共元素。故 next[2] = 0。

当 k = 3 时，其前面的字符串为aba，前缀为{ a,ab }，后缀为{ a, ba }，公共元素为 a，长度为1，故 next[3] = 1。

当 k = 4 时，其前面的字符串为abab，前缀为{ a,ab,aba }，后缀为{ b,ab,bab }，公共元素为 ab，长度为2，故 next[4] = 2。

例2：设目标字符串 target="abcdf"，则其next数组如下：

计算步骤：

当 k = 0 时，next[0] = -1。
当 k = 1 时，其前面的字符串为 a，无前后缀，故 next[1] = 0。
当 k = 2 时，其前面的字符串为 ab，前缀为 a，后缀为 b，无公共元素。故 next[2] = 0。
当 k = 3 时，其前面的字符串为 abc，前缀为{ a,ab }，后缀为{ c,bc }，无公共元素，故 next[3] = 0。
当 k = 4 时，其前面的字符串为 abcd，前缀为{ a,ab,abc }，后缀为{ d,cd,bcd }，无公共元素，故 next[3] = 0。

代码实现

public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDC";
        String str2 = "ABCDABD";
        int[] next = kmpNext(str2);
        System.out.println(str2+"的部分匹配表："+ Arrays.toString(next));
        int index = kmpSearch(str1, str2, next);
        System.out.println(index);
    }
    //编写一个获取字串部分匹配表的方法
    public static int[] kmpNext(String str){
        //创建一个和字符串等长度的数组，用来存放部分匹配表
        int[] next = new int[str.length()];
        next[0] = 0;//因为只有一个元素时，前缀为空，后缀也为空，所以长度为0
        //循环寻找前缀和后缀匹配的字符下标
        for (int i = 1,j = 0; i < str.length(); i++) {
            //当str.charAt(i) != str.charAt(j),并且j > 0时，j = next[j-1];,直到str.charAt(i) == str.charAt(j)
            while (j > 0 && str.charAt(i) != str.charAt(j)){
                j = next[j-1];
            }
            //假如只有两个元素，i=1，j=0，第一个元素和第二个元素匹配，则匹配表为[0,1],比如AA
            /*假如有三个元素ABA，
            从A开始考虑，A的前后缀都为空，所以next[0] = 0;
            考虑AB，前缀A，后缀B，没有共同字串，所以next[1] = 0;
            考虑ABA，前缀A，AB，后缀BA，A，有一个共同字串，并且长度为1，所以next[2] = 1;
            所以ABA的部分匹配表next={0,0,1}
             */
            if (str.charAt(i) == str.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    //写出kmp的搜索算法

    /**
     *
     * @param str1 源字符串
     * @param str2 子串
     * @param next 部分匹配表
     * @return 如果没有匹配返回-1，否则返回第一个匹配的位置
     */
    public static int kmpSearch(String str1,String str2,int[] next){
        //遍历str1
        for (int i = 0,j= 0; i < str1.length(); i++) {
            //如果不匹配，则采用部分匹配表，重置i的位置，避免暴力匹配
            while (j > 0 && str1.charAt(i) != str2.charAt(j)){
                j = next[j-1];
            }
            if (str1.charAt(i) == str2.charAt(j)){
                j++;//如果str1和 str2匹配，则str2的下拨啊加1
            }
            if(j == str2.length()){
                return i-j+1;
            }
        }
        return -1;
    }

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素

就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报

警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷

窃到的最高金额。

输入：[1,2,3,1] 输出：4

输入：[2,7,9,3,1] 输出：12

public static void main(String[] args) {
       int[] nums = new int[]{1,2,3,1};
       System.out.println(maxMoney(nums, nums.length - 1));
   }

   static int maxMoney(int[] nums, int index){
       if(nums == null || index < 0){
           return 0;
       }
       if(index == 0){
           return nums[0];
       }
     return Math.max( maxMoney(nums, index - 1), maxMoney(nums, index - 2) + nums[index]);
   }

首位相连（舍弃头或尾，再比较）

public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,1};
        System.out.println(Math.max(maxMoney(nums, 0, nums.length - 2), maxMoney(nums, 1, nums.length - 1)));
    }

    static int maxMoney(int[] nums, int start, int end){
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for(int i = start + 2; i <= end; i++){
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

参考链接