leetcode
九章

题目描述

Given a triangle, find the minimum path sum from top to bottom. Each step you
may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [ **2** ],
    [ **3** ,4],
   [6, **5** ,7],
  [4, **1** ,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5
+ 1 = 11).

Note:

Bonus point if you are able to do this using only O ( n ) extra space,
where n is the total number of rows in the triangle.

Tags: Array, Dynamic Programming

Difficulty: Medium

答案



leetcode
九章

题目描述

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.

Follow up:

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
九章

题目描述

A robot is located at the top-left corner of a m x n grid (marked ‘Start’
in the diagram below).

The robot can only move either down or right at any point in time. The robot
is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the
diagram below).

How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

Tags: Array, Dynamic Programming

Difficulty: Medium

答案



leetcode
九章

题目描述

A robot is located at the top-left corner of a m x n grid (marked ‘Start’
in the diagram below).

The robot can only move either down or right at any point in time. The robot
is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the
diagram below).

Now consider if some obstacles are added to the grids. How many unique paths
would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input: [
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Tags: Array, Dynamic Programming

Difficulty: Medium

答案



leetcode
九章

题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to
you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

Tags: Array, Binary Search

Difficulty: Medium

答案



leetcode
九章

题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to
you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.
• Would allow duplicates affect the run-time complexity? How and why?

Tags: Array, Binary Search

Difficulty: Hard

答案



leetcode
九章

题目描述

Given two integer arrays A and B, return the maximum length of an subarray
that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

Tags: Array, Hash Table, Binary Search, Dynamic Programming

Difficulty: Medium

答案



leetcode
九章

题目描述

Given an array of n positive integers and a positive integer s , find
the minimal length of a contiguous subarray of which the sum ≥ s. If
there isn’t one, return 0 instead.

*Example: *

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:

If you have figured out the O ( n ) solution, try coding another solution
of which the time complexity is O ( n log n ).

Tags: Array, Two Pointers, Binary Search

Difficulty: Medium

答案



leetcode
九章

题目描述

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O ( n ) time and uses constant extra space.

Tags: Array

Difficulty: Hard

答案



leetcode
九章

题目描述

Given an array nums of n integers, are there elements a , b , c in
nums such that a + b + c = 0? Find all unique triplets in the array
which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Tags: Array, Two Pointers

Difficulty: Medium

答案