[关闭]
@Yano 2015-12-30T03:25:13.000000Z 字数 4195 阅读 4953

LeetCode之Divide and Conquer题目汇总

LeetCode

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


LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总


文章目录:


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分成两部分(不包括这个运算符号)。分别计算出两部分的结果,再运用这个运算符号进行运算。

  1. public List<Integer> diffWaysToCompute(String input) {
  2. List<Integer> rt = new LinkedList<Integer>();
  3. int len = input.length();
  4. for (int i = 0; i < len; i++) {
  5. if (input.charAt(i) == '-' || input.charAt(i) == '*'
  6. || input.charAt(i) == '+') {
  7. String part1 = input.substring(0, i);
  8. String part2 = input.substring(i + 1);
  9. List<Integer> part1Ret = diffWaysToCompute(part1);
  10. List<Integer> part2Ret = diffWaysToCompute(part2);
  11. for (Integer p1 : part1Ret) {
  12. for (Integer p2 : part2Ret) {
  13. int c = 0;
  14. switch (input.charAt(i)) {
  15. case '+':
  16. c = p1 + p2;
  17. break;
  18. case '-':
  19. c = p1 - p2;
  20. break;
  21. case '*':
  22. c = p1 * p2;
  23. }
  24. rt.add(c);
  25. }
  26. }
  27. }
  28. }
  29. if (rt.size() == 0) {
  30. rt.add(Integer.valueOf(input));
  31. }
  32. return rt;
  33. }

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)的时间复杂度。

  1. public int findKthLargest(int[] nums, int k) {
  2. return findK(nums, nums.length - k, 0, nums.length - 1);
  3. }
  4. int findK(int[] nums, int k, int low, int high) {
  5. if (low >= high) {
  6. return nums[low];
  7. }
  8. int p = partition(nums, low, high);
  9. if (p == k) {
  10. return nums[p];
  11. } else if (p < k) {
  12. // 求第k大的,所以要反过来
  13. return findK(nums, k, p + 1, high);
  14. } else {
  15. return findK(nums, k, low, p - 1);
  16. }
  17. }
  18. int partition(int[] nums, int low, int high) {
  19. int privotKey = nums[low];
  20. while (low < high) {
  21. while (low < high && nums[high] >= privotKey) {
  22. high--;
  23. }
  24. swap(nums, low, high);
  25. while (low < high && nums[low] <= privotKey) {
  26. low++;
  27. }
  28. swap(nums, low, high);
  29. }
  30. return low;
  31. }
  32. private void swap(int[] nums, int low, int high) {
  33. int t = nums[low];
  34. nums[low] = nums[high];
  35. nums[high] = t;
  36. }

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)的情况下完成。

  1. public int majorityElement(int[] nums) {
  2. int m = nums[0];
  3. int c = 1;
  4. for (int i = 1; i < nums.length; i++) {
  5. if (m == nums[i]) {
  6. c++;
  7. } else if (c > 1) {
  8. c--;
  9. } else {
  10. m = nums[i];
  11. }
  12. }
  13. return m;
  14. }

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。

  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和maxSum 的计算公式如下:

  1. public int maxSubArray(int[] nums) {
  2. if (nums == null || nums.length == 0) {
  3. return 0;
  4. }
  5. int curSum = nums[0];
  6. int maxSum = nums[0];
  7. for (int i = 1; i < nums.length; i++) {
  8. curSum = Math.max(curSum + nums[i], nums[i]);
  9. maxSum = Math.max(curSum, maxSum);
  10. }
  11. return maxSum;
  12. }

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注