@Yano 2015-12-30T03:25:13.000000Z 字数 4195 阅读 5789

LeetCode之Divide and Conquer题目汇总

LeetCode

我的博客：http://blog.csdn.net/yano_nankai
LeetCode题解：https://github.com/LjyYano/LeetCode

文章目录：

LeetCode之Divide and Conquer题目汇总
Different Ways to Add Parentheses
Kth Largest Element in an Array
Majority Element
Maximum Subarray

Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are+, - and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

使用递归，对于每个运算符号+ - *，将string分成两部分（不包括这个运算符号）。分别计算出两部分的结果，再运用这个运算符号进行运算。

    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> rt = new LinkedList<Integer>();
        int len = input.length();
        for (int i = 0; i < len; i++) {
            if (input.charAt(i) == '-' || input.charAt(i) == '*'
                    || input.charAt(i) == '+') {
                String part1 = input.substring(0, i);
                String part2 = input.substring(i + 1);
                List<Integer> part1Ret = diffWaysToCompute(part1);
                List<Integer> part2Ret = diffWaysToCompute(part2);
                for (Integer p1 : part1Ret) {
                    for (Integer p2 : part2Ret) {
                        int c = 0;
                        switch (input.charAt(i)) {
                        case '+':
                            c = p1 + p2;
                            break;
                        case '-':
                            c = p1 - p2;
                            break;
                        case '*':
                            c = p1 * p2;
                        }
                        rt.add(c);
                    }
                }
            }
        }
        if (rt.size() == 0) {
            rt.add(Integer.valueOf(input));
        }
        return rt;
    }

Kth Largest Element in an Array

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

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

**Note: **
You may assume k is always valid, 1 ≤ k ≤ array's length.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

类似快排，能够达到O(n)的时间复杂度。

    public int findKthLargest(int[] nums, int k) {
        return findK(nums, nums.length - k, 0, nums.length - 1);
    }
    int findK(int[] nums, int k, int low, int high) {
        if (low >= high) {
            return nums[low];
        }
        int p = partition(nums, low, high);
        if (p == k) {
            return nums[p];
        } else if (p < k) {
            // 求第k大的，所以要反过来
            return findK(nums, k, p + 1, high);
        } else {
            return findK(nums, k, low, p - 1);
        }
    }
    int partition(int[] nums, int low, int high) {
        int privotKey = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= privotKey) {
                high--;
            }
            swap(nums, low, high);
            while (low < high && nums[low] <= privotKey) {
                low++;
            }
            swap(nums, low, high);
        }
        return low;
    }
    private void swap(int[] nums, int low, int high) {
        int t = nums[low];
        nums[low] = nums[high];
        nums[high] = t;
    }

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

参考：A Linear Time Majority Vote Algorithm

一个典型的算法，可以在一次遍历，时间复杂度是O(1)，空间复杂度是O(1)的情况下完成。

    public int majorityElement(int[] nums) {
        int m = nums[0];
        int c = 1;
        for (int i = 1; i < nums.length; i++) {
            if (m == nums[i]) {
                c++;
            } else if (c > 1) {
                c--;
            } else {
                m = nums[i];
            }
        }
        return m;
    }

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

设两个变量：curSum和maxSum。

curSum存储数组当前的和，maxSum存储数组中连续最大的和。

假设数组是[−2,1,−3,4,−1,2,1,−5,4]，首先curSum = -2, maxSum = -2。

当i=1时，对于数组[-2,1]，curSum + nums[1] = -1, 小于nums[1] = 1。所以以后-2就可以舍弃，计算curSum时就从i=1开始。
当i=2时，对于数组[-2,1,-3]，curSum + nums[2] = -2, 大于nums[2] = -3。虽然没有比原来大，但是至少比nums[2]大，对于以后计算更接近最优解。
以此类推。

本题只是返回连续最大和，并没有返回数组，所以没有必要记录下标。curSum和maxSum 的计算公式如下：

$curSum = \begin{cases} curSum+nums[i] \\ nums[i] \end{cases}$

$maxSum = \begin{cases} maxSum \\ curSum \end{cases}$

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int curSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curSum = Math.max(curSum + nums[i], nums[i]);
            maxSum = Math.max(curSum, maxSum);
        }
        return maxSum;
    }