Leaky Cauldron

public class KMP {
    public static int[] getNextTable(String needle) {
        int len = needle.length();
        int[] next = new int[len];
        next[0] = -1;
        int lp = -1, rp = 0;    // 左右指针, 即文章中的 k 和 index

        while (rp < len - 1) {
            if (lp == -1 || needle.charAt(rp) == needle.charAt(lp))
                // lp = -1 时, 左右指针均向右移动
                // 当左右指针所指元素相等时, 均向右移动
                next[++rp] = ++lp;
            else
                // 左右指针所指元素不等, 左指针移向其所指字符的对应 next 指向的位置
                lp = next[lp];
        }

        return next;
    }

    public static int getIndex(String haystack, String needle) {
        int haystackLen = haystack.length();
        int needleLen = needle.length();

        if (needleLen == 0) return 0;
        int haystackCur = 0, needleCur = 0;
        int[] next = getNextTable(needle);

        while (haystackCur < haystackLen && needleCur < needleLen) {
            if (haystack.charAt(haystackCur) == needle.charAt(needleCur)) {
                // 对比两个字符串, 各位相同时两指针右移
                haystackCur++;
                needleCur++;
            } else {
                // 不相同则根据 next 表查找 needleCur 移向的位置
                // needleCur 移动到了开头, 退无可退, 主串指针继续后移
                if (needleCur == 0) haystackCur++;
                else needleCur = next[needleCur];
            }
        }

        return needleCur == needleLen ? haystackCur - needleCur : -1;
    }
}

class Program {
    int start;
    int end;

    public Program(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class BestArrange {
    public static int bestArrange(Program[] programs, int start) {
        Arrays.sort(programs, (a, b) -> a.end - b.end);
        int result = 0;

        for (Program program : programs) {
            if (start <= program.start) {
                result++;
                start = program.end;
            }
        }

        return result;
    }
}

public class LowestLexicography {
    public static String lowestString(String[] strs) {
        if (strs == null || strs.length == 0) {
            return null;
        }

        Arrays.sort(strs, (a, b) -> (a + b).compareTo(b + a));

        String result = "";
        for (String str : strs) {
            result += str;
        }

        return result;
    }
}

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 
             滑动窗口的位置              最大值
[ 1   3   -1 ] -3   5   3   6   7        3
  1 [ 3   -1   -3 ] 5   3   6   7        3
  1   3 [ -1   -3   5 ] 3   6   7        5
  1   3   -1 [ -3   5   3 ] 6   7        5
  1   3   -1   -3 [ 5   3   6 ] 7        6
  1   3   -1   -3   5 [ 3   6   7 ]      7

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k < 1 || nums.length < k) {
            return null;
        }

        LinkedList<Integer> maxQueue = new LinkedList<>();
        // 共有 arr.length - k + 1 个窗口, 即共有arr.length - win + 1个最大值
        int[] result = new int[nums.length - k + 1];
        int index = 0;

        // 用 i 表示 R
        for (int i = 0; i < nums.length; i++) {
            while (!maxQueue.isEmpty() && nums[maxQueue.peekLast()] <= nums[i]) {
                maxQueue.pollLast();
            }
            maxQueue.addLast(i);

            // i - k 为过期的索引, 即窗口的 L 已越过该位置, 需弹出头结点维持窗口大小为 k
            if (maxQueue.peekFirst() == i - k) {
                System.out.println(i + " " + k);
                maxQueue.pollFirst();
            }
            if (i >= k - 1) {
                result[index++] = nums[maxQueue.peekFirst()];
            }
        }

        return result;
    }
}

public class MaxSumOfSubarray {
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int current = 0;
        int maxSum = Integer.MIN_VALUE;

        for (int num : nums) {
            current += num;
            maxSum = Math.max(current, maxSum);
            current = Math.max(current, 0);
        }

        return maxSum;
    }
}

public class TrapRainWater {
    public static int trap(int[] heightArr) {
        if (heightArr == null || heightArr.length < 0)
            return 0;

        int arrLen = heightArr.length;
        int[] help1 = new int[arrLen];
        int[] help2 = new int[arrLen];
        int result = 0;

        help1[0] = heightArr[0];
        help2[arrLen - 1] = heightArr[arrLen - 1];

        for (int i = 1; i < arrLen; i++) {
            help1[i] = Math.max(help1[i - 1], heightArr[i]);
            help2[arrLen - i - 1] = Math.max(help2[arrLen - i], heightArr[arrLen - i - 1]);
        }

        for (int i = 1; i < arrLen - 1; i++) {
            int tmp = Math.min(help1[i - 1], help2[i + 1]) - heightArr[i];
            result += Math.max(tmp, 0);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] heightArr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap(heightArr));
    }
}

6

public class TrapRainWater {
    public static int trap(int[] heightArr) {
        if (heightArr == null || heightArr.length < 3)
            return 0;

        int arrLen = heightArr.length;
        int leftMax = heightArr[0];
        int rightMax = heightArr[arrLen - 1];
        int L = 1;
        int R = arrLen - 2;
        int result = 0;

        while (L <= R) {
            if (leftMax <= rightMax) {
                result += Math.max(0, leftMax - heightArr[L]);
                leftMax = Math.max(leftMax, heightArr[L++]);
            } else {
                result += Math.max(0, rightMax - heightArr[R]);
                rightMax = Math.max(rightMax, heightArr[R--]);
            }
        }

        return result;
    }
}

public class ReverseStackUsingRecursive {
    public static void reverse(Stack<Integer> stack) {
        if (stack.isEmpty()) return;

        int ele = getAndRemoveLastElement(stack);
        reverse(stack);
        stack.push(ele);
    }

    public static int getAndRemoveLastElement(Stack<Integer> stack) {
        int result = stack.pop();
        if (stack.isEmpty()) {
            return result;
        } else {
            int last = getAndRemoveLastElement(stack);
            stack.push(result);
            return last;
        }
    }
}

public class CowNumber {
    public static int getCowNum(int N) {
        if (N <= 2) return N + 1;
        return getCowNum(N - 1) + getCowNum(N - 3);
    }

    public static void main(String[] args) {
        System.out.println(getCowNum(8));
    }
}

28

public class PrintPermutations {
    public static void printPermutations(String str) {
        char[] chars = str.toCharArray();
        process(chars, 0);
    }

    public static void process(char[] chars, int i) {
        if (i == chars.length) {
            System.out.println(String.valueOf(chars));
        }

        for (int j = i; j < chars.length; j++) {
            swap(chars, i, j);
            process(chars, i + 1);
        }
    }

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