leetcode 1025. Divisor Game

leetcode
九章

题目描述

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

leetcode
九章

题目描述

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

leetcode
九章

题目描述

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 120. Triangle

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

leetcode
九章

题目描述

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

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

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

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

leetcode
九章

题目描述

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

leetcode
九章

题目描述

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 一言句子获取中...