leetcode 241. 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"
Output: [0, 2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2``````

Example 2:

``````Input:"2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: (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 ****``````

Tags: Divide and Conquer

Difficulty: Medium



leetcode 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``````

Tags: Divide and Conquer, Dynamic Programming

Difficulty: Hard



leetcode 53. Maximum Subarray

题目描述

Given an integer array `nums`, find the contiguous subarray (containing at
least one number) which has the largest sum and return its sum.

Example:

``````Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation:  [4,-1,2,1] has the largest sum = 6.``````

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

Tags: Array, Divide and Conquer, Dynamic Programming

Difficulty: Easy



leetcode 240. Search a 2D Matrix II

题目描述

Write an efficient algorithm that searches for a value in an m x n matrix.
This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

``````[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]``````

Given target = `5`, return `true`.

Given target = `20`, return `false`.

Tags: Binary Search, Divide and Conquer

Difficulty: Medium

leetcode 215. 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.

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``````

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

Tags: Divide and Conquer, Heap

Difficulty: Medium

:D 一言句子获取中...