@Yano 2015-12-30T11:25:13.000000Z 字数 4195 阅读 5909

# LeetCode之Divide and Conquer题目汇总

LeetCode

LeetCode 题目汇总

# 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.

    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.

    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.

    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存储数组中连续最大的和。

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

$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;    }

• 私有
• 公开
• 删除