Press "Enter" to skip to content

Posts published in “Search”

花花酱 LeetCode 909. Snakes and Ladders

Problem

On an N x NĀ board, the numbers fromĀ 1Ā toĀ N*NĀ are writtenĀ boustrophedonicallyĀ starting from the bottomĀ left of the board, and alternating direction each row.Ā  For example, for a 6 x 6 board, the numbers are written as follows:

You start on squareĀ 1Ā of the board (which is always in the last row andĀ first column).Ā  Each move, starting from squareĀ x, consists of the following:

  • You choose a destination squareĀ SĀ with numberĀ x+1,Ā x+2,Ā x+3,Ā x+4,Ā x+5, orĀ x+6, provided thisĀ number isĀ <=Ā N*N.
    • (This choice simulates the result of a standard 6-sided die roll: ie., there are always at most 6 destinations.)
  • IfĀ SĀ has a snake or ladder, you move to the destination of that snake or ladder.Ā  Otherwise, you move toĀ S.

A board square on rowĀ rĀ and columnĀ cĀ has a “snake or ladder” ifĀ board[r][c] != -1.Ā  The destination of that snake or ladder isĀ board[r][c].

Note that you only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of anotherĀ snake or ladder, you doĀ notĀ continue moving.Ā  (For example, if the board is [[4,-1],[-1,3]], and on the first move your destination square is 2, then you finish your first move atĀ 3, because you doĀ notcontinue moving to 4.)

Return the least number of moves required to reach squareĀ N*N.Ā  If it is not possible, returnĀ -1.

Example 1:

Input: [
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
At the beginning, you start at square 1 [at row 5, column 0].
You decide to move to square 2, and must take the ladder to square 15.
You then decide to move to square 17 (row 3, column 5), and must take the snake to square 13.
You then decide to move to square 14, and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
It can be shown that you need at least 4 moves to reach the N*N-th square, so the answer is 4.

Note:

  1. 2 <= board.length = board[0].lengthĀ <= 20
  2. board[i][j]Ā is betweenĀ 1Ā andĀ N*NĀ or is equal toĀ -1.
  3. The boardĀ square with numberĀ 1Ā has no snake or ladder.
  4. The board square with numberĀ N*NĀ has no snake or ladder.

Solution: BFS

Time complexity: O(n*n)

Space complexity: O(n*n)

C++

花花酱 LeetCode 10. Regular Expression Matching

Problem

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 precedengĀ 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 = "c*a*b"
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 = "mis*is*p*."
Output: false

Solution 1: Recursion

Time complexity: O((|s| + |p|) * 2 ^Ā (|s| + |p|))

Space complexity: O(|s| + |p|)

C++

花花酱 LeetCode 638. Shopping Offers

Problem

In LeetCode Store, there are some kinds of items to sell. Each item has a price.

However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay forĀ exactlyĀ certain items as given, where you could make optimal use of the special offers.

Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.

You could use any of special offers as many times as you want.

Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation: 
There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation: 
The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

  1. There are at most 6 kinds of items, 100 special offers.
  2. For each item, you need to buy at most 6 of them.
  3. You areĀ notĀ allowed to buy more items than you want, even if that would lower the overall price.

Solution: Search

Try all combinations.

 

花花酱 LeetCode 842. Split Array into Fibonacci Sequence

Problem

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

  • 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
  • F.length >= 3;
  • and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]

Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]

Example 3:

Input: "112358130"
Output: []
Explanation: The task is impossible.

Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.

Note:

  1. 1 <= S.length <= 200
  2. S contains only digits.

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

 

花花酱 LeetCode 47. Permutations II

Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

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

Solution

Time complexity: O(n!)

Space complexity: O(n + k)

Related Problems