# leetcode 1025. Divisor Game

## 题目描述

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number `N` on the chalkboard. On each player’s turn,
that player makes a move consisting of:

• Choosing any `x` with `0 < x < N` and `N % x == 0`.
• Replacing the number `N` on the chalkboard with `N - x`.

Also, if a player cannot make a move, they lose the game.

Return `True` if and only if Alice wins the game, assuming both players play
optimally.

Example 1:

``````Input: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.``````

Example 2:

``````Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.``````

Note:

1. `1 <= N <= 1000`

Tags: Math, Dynamic Programming

Difficulty: Easy



# leetcode 95. Unique Binary Search Trees II

## 题目描述

Given an integer n , generate all structurally unique BST ‘s (binary
search trees) that store values 1 … n.

Example:

``````Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3``````

Tags: Dynamic Programming, Tree

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]   -->    --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167``````

Tags: Divide and Conquer, Dynamic Programming

Difficulty: Hard



# leetcode 120. Triangle

## 题目描述

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 264. Ugly Number II

## 题目描述

Write a program to find the `n`-th ugly number.

Ugly numbers are positive numbers whose prime factors only include ```2, 3, 5```.

Example:

``````Input: n = 10
Output: 12
Explanation:1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.``````

Note:

1. `1` is typically treated as an ugly number.
2. `n` does not exceed 1690.

Tags: Math, Dynamic Programming, Heap

Difficulty: Medium



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

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 62. Unique Paths

## 题目描述

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 63. Unique Paths II

## 题目描述

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 10. Regular Expression Matching

## 题目描述

Given an input string (`s`) and a pattern (`p`), implement regular expression
matching with support for `'.'` and `'*'`.
‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

• `s` could be empty and contains only lowercase letters `a-z`.
• `p` could be empty and contains only lowercase letters `a-z`, and characters like `.` or `*`.

Example 1:
Input: s = “aa” p = “a” Output: false Explanation: “a” does not match the entire string “aa”.

Example 2:
Input: s = “aa” p = “a*” Output: true Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

Example 3:
Input: s = “ab” p = “.*” Output: true Explanation: “.*” means “zero or more (*) of any character (.)”.

Example 4:
Input: s = “aab” p = “cab” Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”.

Example 5:
Input: s = “mississippi” p = “misis*p.” Output: false

Tags: String, Dynamic Programming, Backtracking

Difficulty: Hard



# leetcode 44. Wildcard Matching

## 题目描述

Given an input string (`s`) and a pattern (`p`), implement wildcard pattern
matching with support for `'?'` and `'*'`.

``````'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).``````

The matching should cover the entire input string (not partial).

Note:

• `s` could be empty and contains only lowercase letters `a-z`.
• `p` could be empty and contains only lowercase letters `a-z`, and characters like `?` or `*`.

Example 1:

``````Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".``````

Example 2:

``````Input:
s = "aa"
p = "*"
Output: true
Explanation:  '*' matches any sequence.``````

Example 3:

``````Input:
s = "cb"
p = "?a"
Output: false
Explanation:  '?' matches 'c', but the second letter is 'a', which does not match 'b'.``````

Example 4:

``````Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation:  The first '*' matches the empty sequence, while the second '*' matches the substring "dce".``````

Example 5:

``````Input:
s = "acdcb"
p = "a*c?b"
Output: false``````

Tags: String, Dynamic Programming, Backtracking, Greedy

Difficulty: Hard



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