• 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。每个人喝完之后咖啡杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
  四个参数：arr, n, a, b
  假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。

• 给定两个整数数组A和B
  A是长度为m、元素从小到大排好序了
  B是长度为n、元素从小到大排好序了
  希望从A和B数组中，找出最大的k个数字

package class04;

import java.util.Arrays;

public class Code02_FindKthMinNumber {

    public static int findKthNum(int[] arr1, int[] arr2, int kth) {
        if (arr1 == null || arr2 == null) {
            return -1;
        }
        if (kth < 1 || kth > arr1.length + arr2.length) {
            return -1;
        }
        int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
        int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
        int l = longs.length;
        int s = shorts.length;
        if (kth <= s) {
            return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1);
        }
        if (kth > l) {
            if (shorts[kth - l - 1] >= longs[l - 1]) {
                return shorts[kth - l - 1];
            }
            if (longs[kth - s - 1] >= shorts[s - 1]) {
                return longs[kth - s - 1];
            }
            return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1);
        }
        // 短数组长度 < k <= 长数组长度
        if (longs[kth - s - 1] >= shorts[s - 1]) {
            return longs[kth - s - 1];
        }
        return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
    }

    // A[s1...e1]
    // B[s2...e2]
    // 这两段一定等长且都有序
    // 求这两段整体的上中位数，上中位数值返回
    public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) {
        int mid1 = 0;
        int mid2 = 0;
        while (s1 < e1) {
            mid1 = (s1 + e1) / 2;
            mid2 = (s2 + e2) / 2;
            if (A[mid1] == B[mid2]) {
                return A[mid1];
            }
            if (((e1 - s1 + 1) & 1) == 1) { // 奇数长度
                if (A[mid1] > B[mid2]) {
                    if (B[mid2] >= A[mid1 - 1]) {
                        return B[mid2];
                    }
                    e1 = mid1 - 1;
                    s2 = mid2 + 1;
                } else { // A[mid1] < B[mid2]
                    if (A[mid1] >= B[mid2 - 1]) {
                        return A[mid1];
                    }
                    e2 = mid2 - 1;
                    s1 = mid1 + 1;
                }
            } else { // 偶数长度
                if (A[mid1] > B[mid2]) {
                    e1 = mid1;
                    s2 = mid2 + 1;
                } else {
                    e2 = mid2;
                    s1 = mid1 + 1;
                }
            }
        }
        return Math.min(A[s1], B[s2]);
    }

    // For test, this method is inefficient but absolutely right
    public static int[] getSortedAllArray(int[] arr1, int[] arr2) {
        if (arr1 == null || arr2 == null) {
            throw new RuntimeException("Your arr is invalid!");
        }
        int[] arrAll = new int[arr1.length + arr2.length];
        int index = 0;
        for (int i = 0; i != arr1.length; i++) {
            arrAll[index++] = arr1[i];
        }
        for (int i = 0; i != arr2.length; i++) {
            arrAll[index++] = arr2[i];
        }
        Arrays.sort(arrAll);
        return arrAll;
    }

    public static int[] generateSortedArray(int len, int maxValue) {
        int[] res = new int[len];
        for (int i = 0; i != len; i++) {
            res[i] = (int) (Math.random() * (maxValue + 1));
        }
        Arrays.sort(res);
        return res;
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int len1 = 10;
        int len2 = 23;
        int maxValue1 = 20;
        int maxValue2 = 100;
        int[] arr1 = generateSortedArray(len1, maxValue1);
        int[] arr2 = generateSortedArray(len2, maxValue2);
        printArray(arr1);
        printArray(arr2);
        int[] sortedAll = getSortedAllArray(arr1, arr2);
        printArray(sortedAll);
        int kth = 17;
        System.out.println(findKthNum(arr1, arr2, kth));
        System.out.println(sortedAll[kth - 1]);


    }

}

• 约瑟夫环问题
  public class Code04_JosephusProblem {

  public static class Node {
  public int value;
  public Node next;

    public Node(int data) {
        this.value = data;
    }
  

  }

  public static Node josephusKill1(Node head, int m) {
  if (head == null || head.next == head || m < 1) {
  return head;
  }
  Node last = head;
  while (last.next != head) {
  last = last.next;
  }
  int count = 0;
  while (head != last) {
  if (++count == m) {
  last.next = head.next;
  count = 0;
  } else {
  last = last.next;
  }
  head = last.next;
  }
  return head;
  }

  public static Node josephusKill2(Node head, int m) {
  if (head == null || head.next == head || m < 1) {
  return head;
  }
  Node cur = head.next;
  int size = 1; // tmp -> list size
  while (cur != head) {
  size++;
  cur = cur.next;
  }
  int live = getLive(size, m); // tmp -> service node position
  while (--live != 0) {
  head = head.next;
  }
  head.next = head;
  return head;
  }

  // 现在一共有i个节点，数到m就杀死节点，最终会活下来的节点，请返回它在有i个节点时候的编号
  // 旧
  // getLive(N, m)
  public static int getLive(int i, int m) {
  if (i == 1) {
  return 1;
  }
  // getLive(i - 1, m) 长度为i-1时候，活下来的编号
  // (新编号+m-1)%i+1
  return (getLive(i - 1, m) + m - 1) % i + 1;
  }

  public static void printCircularList(Node head) {
  if (head == null) {
  return;
  }
  System.out.print("Circular List: " + head.value + " ");
  Node cur = head.next;
  while (cur != head) {
  System.out.print(cur.value + " ");
  cur = cur.next;
  }
  System.out.println("-> " + head.value);
  }

  public static void main(String[] args) {
  Node head1 = new Node(1);
  head1.next = new Node(2);
  head1.next.next = new Node(3);
  head1.next.next.next = new Node(4);
  head1.next.next.next.next = new Node(5);
  head1.next.next.next.next.next = head1;
  printCircularList(head1);
  head1 = josephusKill1(head1, 3);
  printCircularList(head1);

    Node head2 = new Node(1);
    head2.next = new Node(2);
    head2.next.next = new Node(3);
    head2.next.next.next = new Node(4);
    head2.next.next.next.next = new Node(5);
    head2.next.next.next.next.next = head2;
    printCircularList(head2);
    head2 = josephusKill2(head2, 3);
    printCircularList(head2);
  

  }

}

• 给定一个 N×3 的矩阵 matrix，对于每一个长度为 3 的小数组 arr，都表示一个大楼的三个数 据。arr[0]表示大楼的左边界，arr[1]表示大楼的右边界，arr[2]表示大楼的高度(一定大于 0)。 每座大楼的地基都在 X 轴上，大楼之间可能会有重叠，请返回整体的轮廓线数组。
  【举例】 matrix ={{2,5,6}, {1,7,4}, {4,6,7}, {3,6,5}, {10,13,2}, {9,11,3}, {12,14,4},{10,12,5} }
  返回: {{1,2,4},{2,4,6}, {4,6,7}, {6,7,4}, {9,10,3}, {10,12,5}, {12,14,4}}

/**
 * 给定一个 N×3 的矩阵 matrix，对于每一个长度为 3 的小数组 arr，都表示一个大楼的三个数 据。arr[0]表示大楼的左边界，
 * arr[1]表示大楼的右边界，arr[2]表示大楼的高度(一定大于 0)。 每座大楼的地基都在 X 轴上，大楼之间可能会有重叠，
 * 请返回整体的轮廓线数组。
 * 【举例】 matrix ={{2,5,6}, {1,7,4}, {4,6,7}, {3,6,5}, {10,13,2}, {9,11,3}, {12,14,4},{10,12,5} }
 * 返回: {{1,2,4},{2,4,6}, {4,6,7}, {6,7,4}, {9,10,3}, {10,12,5}, {12,14,4}}
 */
public class ContourLine {

    // 操作类表示每一个操作
    // 比如{2,5,6} 表示在2位置有一个增加高度6的操作
    // 6位置有一个减少高度6的操作
    static class Op{
        // 增加或减少的高度
        int height;
        // 增加还是减少
        boolean isAdd;
        // 操作所在位置
        int x;
        public Op(int height,boolean isAdd,int x){
            this.height = height;
            this.isAdd = isAdd;
            this.x = x;
        }
    }

    static class OpComparator implements Comparator<Op>{

        @Override
        public int compare(Op o1, Op o2) {
            if(o1.x != o2.x){
                return o1.x - o2.x;
            }
            if(o1.isAdd != o2.isAdd){
                return o1.isAdd ? -1 : 1;
            }
            return 0;
        }
    }

    // 流程：
    // 1.先把所有数组转化为Op数组
    // 3.生成一个k:高度 v:出现次数的有序表，排序规则，先按height排序，如果同一个height有增有减，吧加排在前面
    // 4.根据3中有序表生成，k 位置，v:最高点的有序表
    // 5.根据4中的有序表，生成轮廓线
    public static List<List<Integer>> contourLine(int[][] matrix){
        if(matrix == null || matrix[0].length == 0){
            return null;
        }

        Op[] ops = new Op[matrix.length << 1];
        for (int i = 0; i < matrix.length;i++) {
            ops[i*2] = new Op(matrix[i][2],true,matrix[i][0]);
            ops[i*2+1] = new Op(matrix[i][2],false,matrix[i][1]);
        }

        // 排序,按照高度从小到大排序，高度相同加在前，减在后
        Arrays.sort(ops,new OpComparator());

        // k 高度，v 出现次数
        TreeMap<Integer,Integer> heightNum = new TreeMap<>();
        // k x上的横坐标，v 此时的最大高度
        TreeMap<Integer,Integer> pointMaxHeight = new TreeMap<>();
        for (int i = 0; i < ops.length; i++) {
            if(ops[i].isAdd){
                // 如果是增加高度操作
                if(!heightNum.containsKey(ops[i].height)){
                    // 如果这个高度不存在
                    heightNum.put(ops[i].height,1);
                }else{
                    // 如果这个高度存在
                    heightNum.put(ops[i].height,heightNum.get(ops[i].height)+1);
                }
            }else{
                // 如果是减小操作
                if(heightNum.get(ops[i].height) == 1){
                    // 如果高度已经等于1了,吧这个记录移出
                    heightNum.remove(ops[i].height);
                }else{
                    // 高度频率减少1
                    heightNum.put(ops[i].height,heightNum.get(ops[i].height)-1);
                }
            }
            // 由于数组是从小到大排序的，所以同一个高度的加减是挨在一起的，且先操作加在操作减
            if(heightNum.isEmpty()){
                // 如果此时这个点不在其中，说明其高度为0
                // 只有可能是降低点，导致这个x上点的高度此时被移出了，为0
                pointMaxHeight.put(ops[i].x,0);

            }else{
                // 经过上面的加或者减，该点还有高度，一定是从小到大排序的,此时x点的高度一定是最大的
                // 但是每一轮都有可能更新x点最大值。
                pointMaxHeight.put(ops[i].x,heightNum.lastKey());
            }
        }

        List<List<Integer>> res = new ArrayList<>();
        // pointMaxHeight 记录着每个点的最大大高度
        // 之前的高度
        int preH = 0;
        // 之前的起点
        int start = 0;
        for (Map.Entry<Integer, Integer> item : pointMaxHeight.entrySet()){
            // 当前所在点
            int curX = item.getKey();
            int curH = item.getValue();
            if(preH != curH){
                // 如果之前的高度不等于现在的高度说明轮廓有变化收集
                if(preH != 0){
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(start);
                    list.add(curX);
                    list.add(preH);
                    res.add(list);
                }
                start = curX;
                preH = curH;
            }

        }
        return res;
    }

    public static void main(String[] args) {
        int[][] matrix ={{2,5,6}, {1,7,4}, {4,6,7}, {3,6,5}, {10,13,2}, {9,11,3}, {12,14,4},{10,12,5} };

        System.out.println(contourLine(matrix));
    }
}

• Nim博弈问题
  给定一个非负数组，每一个值代表该位置上有几个铜板。a和b玩游戏，a先手，b后手， 轮到某个人的时候，只能在一个位置上拿任意数量的铜板，但是不能不拿。谁最先把铜 板拿完谁赢。假设a和b都极度聪明，请返回获胜者的名字

/**
 * Nim博弈问题
 * 给定一个非负数组，每一个值代表该位置上有几个铜板。a和b玩游戏，a先手，b后手，
 * 轮到某个人的时候，只能在一个位置上拿任意数量的铜板，但是不能不拿。谁最先把铜
 * 板拿完谁赢。假设a和b都极度聪明，请返回获胜者的名字
 */
public class Nim {

    // 流程：
    // 对arr数组中所有元素求异或和，
    // 结果不等于0，先手获胜，等于0后手获胜
    // 原因：
    // 假如假如先手，每次拿完后都可以让 数组中所有元素的异或和都为0，
    // 0000，当后手拿的时候一定会破坏这个平衡导致，异或和不为0，先后永远
    // 不会输，先手总是面对，数字不为空的境地（异或和不为0），后手永远面对异或和为0的境地
    // 到最后一定是后手最先面对没有数可拿的境地
    //
    public static String nim(int[] arr){
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        return eor != 0 ? "先手" :"后手";
    }


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

• 给定一个数组arr，长度为N且每个值都是正数，代表N个人的体重。再给定一个正数 limit，代表一艘船的载重。

• 以下是坐船规则，
• 1)每艘船最多只能做两人;
• 2)乘客 的体重和不能超过limit
• 返回如果同时让这N个人过河最少需要几条船。

/**
 * 给定一个数组arr，长度为N且每个值都是正数，代表N个人的体重。再给定一个正数 limit，代表一艘船的载重。
 * 以下是坐船规则，
 * 1)每艘船最多只能做两人;
 * 2)乘客 的体重和不能超过limit
 * 返回如果同时让这N个人过河最少需要几条船。
 */

public class NeedShipNum {
    // 数组必须有序
    public static int needShipNum(int[] arr,int limit){
        if(arr == null || arr.length == 0 || limit <= 0){
            // -1没有方案
            return -1;
        }

        // 每个人的体重都大于limit的一半
        boolean flag = true;
        // 如果有人的体重超过了limit，没有方案
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > limit){
                return -1;
            }
            if(arr[i] < limit / 2){
                flag = false;
            }
        }
        // 都大于limit的一半，则只有每个人单独乘坐一条船
        if(flag){
            return arr.length;
        }

        // 双指针，流程：
        // 1.先找到小于等于limit一半的数的位置left，另一个指针为right = left + 1(此时)
        // 2.从left开始和right位置的数配对
        //  1）如果left位置的数和right位置的数加起来大于limit,那么则right位置不变，left位置向左移动一步
        //     这种类型的记为x，
        //  2) 如果left位置的数小于等于right的数，那么继续移动right看看一共有多少个数能和left配对，
        //     我们找到了一批匹配成功的数，右边right移动了多少位，左边left用等长的位数和他配对
        //  3)如果右边先匹配完，那么左边剩下的可以两个为一组用一个船，如果左边先匹配完，只能单独一人一只船
        // 所有船只加起来

        Arrays.sort(arr);
        // 小于等于limit/2的最右的位置
        int right = 0;
        int left = 0;
        for(int i = arr.length-1;i >= 0;i--){
            if(arr[i] <= limit/2){
                left = i;
                break;
            }
        }
        right = left+1;
        // 左边画x的个数
        int x = 0;
        // 左边剩余的个数leftRemain
        int leftRemain = 0;
        // 左边配对的个数leftPair
        int leftPair = 0;
        // 右边剩余的个数
        int rightRemain = 0;
        // 从中间向两边匹配
        while (left >=0 && right < arr.length) {
            if(arr[left]+arr[right] > limit){
                // left位置画x，x的个数增加
                x++;
                left--;
            }else if(arr[left]+arr[right] <= limit){
                // 向右能扩多远
                int temp = 0;
                while (right < arr.length && arr[left]+arr[right] <= limit){
                    temp ++;
                    right++;
                }
                // 结算此次left能搞定几个
                leftPair += temp;
                left = left - temp;
            }
        }
        // 右边剩余个数
        rightRemain = arr.length - right;
        // 左边剩余个数
        leftRemain = left - 0;
        int res = 0;
        res = ((leftRemain+1) / 2) + leftPair + (x+1)/2 + rightRemain;
        return res;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5 };
        int weight = 6;
        System.out.println(needShipNum(arr, weight));
    }
}