package y2019.Algorithm.divideandconquer.medium;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.divideandconquer.medium

 * @ClassName: FindKthLargest

 * @Author: xiaof

 * @Description: 215. Kth Largest Element in an Array

 * Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order,

 * not the kth distinct element.

 *

 * Example 1:

 *

 * Input: [3,2,1,5,6,4] and k = 2

 * Output: 5

 *

 * Example 2:

 * Input: [3,2,3,1,2,4,5,5,6] and k = 4

 * Output: 4

 *

 * 这题可以直接排序，然后获取第K个位置的数据即可，但是这不是本题的考察点

 * 本地用快排，直接找到第k个坑的值

 *

 * @Date: 2019/8/13 8:59

 * @Version: 1.0

 */

public class FindKthLargest {

    public int solution(int[] nums, int k) {

        int l = 0, r = nums.length - 1; //定义快排的左右边界

        while (l <= r) {

            int pos = partition(nums, l, r);

            //找到中间的位置

            if (pos == k - 1) {

                //找到对应的值

                return nums[pos];

            } else if (pos > k - 1) {

                //如果位置比第k个数要大，那么说明第k位再左边

                r = pos - 1;

            } else {

                l = pos + 1;

            }

        }

        return -1;

    }

    public int partition(int[] nums, int l, int r) {

        int init = nums[l], l1 = l + 1, r1 = r;

        while (l1 <= r1) {

            //遍历交换数据

            if (nums[l1] < init && nums[r1] > init) {

                //交换位置数据

                int temp = nums[l1];

                nums[l1++] = nums[r1];

                nums[r1--] = temp;

            }

            if (nums[l1] >= init) {

                ++l1;

            }

            if (nums[r1] < init) {

                --r1;

            }

        }

        //当r1越过l1的时候，交换回来

        nums[l] = nums[r1];

        nums[r1] = init;

        return r1;

    }

    public static void main(String[] args) {

        int s[] = {3,2,3,1,2,4,5,5,6};

        int k = 4;

        int s1[] = {1};

        int k1 = 1;

        int s2[] = {99,99};

        int k2 = 1;

        int s3[] = {2,1};

        int k3 = 1;

        int s4[] = {-1, 2, 0};

        int k4 = 1;

        FindKthLargest fuc = new FindKthLargest();

        fuc.solution(s4, k4);

    }

}

package y2019.Algorithm.divideandconquer.hard;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.divideandconquer.hard

 * @ClassName: MaxCoins

 * @Author: xiaof

 * @Description: 312. Burst Balloons

 * Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums.

 * You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins.

 * Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

 * Find the maximum coins you can collect by bursting the balloons wisely.

 *

 * Note:

 * You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.

 * 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

 * Example:

 *

 * Input: [3,1,5,8]

 * Output: 167

 * Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []

 *              coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

 * @Date: 2019/8/13 9:43

 * @Version: 1.0

 */

public class MaxCoins {

    public int solution(int[] nums) {

        //逆向思维，我们发现每次都是再已经存在的气球中进行爆破，这里尝试改变想法为，本来没有气球，加入气球进行爆破

        //我们从最后一步开始思考，每次只需要递归到上一层有+1个气球的时候，进行爆破得到当前环节

        //1.首先创建长度+1的数组，因为起始和结束的位置默认为1

        int[] resarray = new int[nums.length + 2];

        int n = 1;

        for (int x : nums) {

            //这里排除掉为0的数据

            if (x > 0) {

                resarray[n++] = x;

            }

        }

        resarray[0] = resarray[n++] = 1;

        //这个数组表示，再i,j区间内进行爆破的最大值

        int[][] back = new int[n][n];

        return burst(back, resarray, 0, n - 1);

    }

    public int burst(int[][] back, int[] nums, int left, int right) {

        //如果是边界，或两个索引之间没有空隙了，那么就不用插入了

        if (left + 1 == right) return 0;

        if (back[left][right] > 0) {

            //如果已经计算过了，不做重复计算

            return back[left][right];

        }

        //计算每个位置作为最后一个爆破点的时候值

        int ans = 0;

        for (int i = left + 1; i < right; ++i) {

            ans = Math.max(ans, nums[left] * nums[i] * nums[right] + burst(back, nums, left, i) + burst(back, nums, i, right));

        }

        //修改值内容，继续递归

        back[left][right] = ans;

        return ans;

    }

    /**

     *

     * @program: y2019.Algorithm.divideandconquer.hard.MaxCoins

     * @description: https://leetcode.com/problems/burst-balloons/discuss/76228/Share-some-analysis-and-explanations

     * @auther: xiaof

     * @date: 2019/8/13 11:20

     */

    public int maxCoins(int[] iNums) {

        int[] nums = new int[iNums.length + 2];

        int n = 1;

        for (int x : iNums) if (x > 0) nums[n++] = x;

        nums[0] = nums[n++] = 1;

        int[][] memo = new int[n][n];

        return burst2(memo, nums, 0, n - 1);

    }

    public int burst2(int[][] memo, int[] nums, int left, int right) {

        if (left + 1 == right) return 0;

        if (memo[left][right] > 0) return memo[left][right];

        int ans = 0;

        for (int i = left + 1; i < right; ++i)

            ans = Math.max(ans, nums[left] * nums[i] * nums[right]

                    + burst2(memo, nums, left, i) + burst2(memo, nums, i, right));

        memo[left][right] = ans;

        return ans;

    }

    public static void main(String[] args) {

        int s[] = {3,1,5,8};

        int[] s1 = {8,2,6,8,9,8,1,4,1,5,3,0,7,7,0,4,2,2,5};

        int[] s2 = {8,3,4,3,5,0,5,6,6,2,8,5,6,2,3,8,3,5,1,0,2};

        MaxCoins fuc = new MaxCoins();

//        fuc.solution(s2);

        fuc.maxCoins(s2);

    }

}