Press "Enter" to skip to content

Posts published in October 2018

花花酱 LeetCode 931. Minimum Falling Path Sum

Problem

Given aĀ squareĀ array of integersĀ A, we want theĀ minimumĀ sum of aĀ falling pathĀ throughĀ A.

A falling path starts at any element in the first row, and chooses one element from each row.Ā  The next row’s choice must be in a column that is different from the previous row’s column by at most one.

 

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:
  • [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
  • [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
  • [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

The falling path with the smallest sum isĀ [1,4,7], so the answer isĀ 12.

Note:

  1. 1 <= A.length == A[0].length <= 100
  2. -100 <= A[i][j] <= 100

Solution: DP

Time complexity: O(mn)

Space complexity: O(mn)

C++

C++/in place

花花酱 LeetCode 929. Unique Email Addresses

Every email consists of a local name and a domain name, separated by the @ sign.

For example, inĀ alice@leetcode.com,Ā aliceĀ is the local name, andĀ leetcode.comĀ is the domain name.

Besides lowercase letters, these emails may containĀ '.'s orĀ '+'s.

If you add periods ('.') between some characters in theĀ local nameĀ part of an email address, mail sent there will be forwarded to the same address without dots in the local name.Ā  For example,Ā "alice.z@leetcode.com"Ā andĀ "alicez@leetcode.com"Ā forward to the same email address.Ā  (Note that this rule does not apply for domain names.)

If you add a plus ('+') in theĀ local name, everything after the first plus sign will beĀ ignored. This allows certain emails to be filtered, for exampleĀ m.y+name@email.comĀ will be forwarded toĀ my@email.com.Ā  (Again, this rule does not apply for domain names.)

It is possible to use both of these rules at the same time.

Given a list ofĀ emails, we send one email to each address in the list.Ā Ā How many different addresses actually receive mails?

Example 1:

Input: ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation:Ā "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails

 

Note:

  • 1 <= emails[i].lengthĀ <= 100
  • 1 <= emails.length <= 100
  • EachĀ emails[i]Ā contains exactly oneĀ '@'Ā character.

 

Solution:Ā 

Time complexity: O(n*l)
Space complexity: O(n*l)

C++

花花酱 LeetCode 927. Three Equal Parts

Problem

Given an arrayĀ AĀ ofĀ 0s andĀ 1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, returnĀ anyĀ [i, j]Ā withĀ i+1 < j, such that:

  • A[0], A[1], ..., A[i]Ā is the first part;
  • A[i+1], A[i+2], ..., A[j-1]Ā is the second part, and
  • A[j], A[j+1], ..., A[A.length - 1]Ā is the third part.
  • All three parts have equal binary value.

If it is not possible, returnĀ [-1, -1].

Note that the entire part is used when considering what binary value it represents.Ā  For example,Ā [1,1,0]Ā representsĀ 6Ā in decimal,Ā notĀ 3.Ā  Also, leading zeros are allowed, soĀ [0,1,1]Ā andĀ [1,1]Ā represent the same value.

 

Example 1:

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

Example 2:

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

Note:

  1. 3 <= A.length <= 30000
  2. A[i] == 0Ā orĀ A[i] == 1

Solution:

each part should have the same number of 1 s.

Find the suffix (without leading os) of the last part which should have 1/3 of the total ones.

Time complexity: O(n^2) in theory but close to O(n) in practice

Space complexity: O(n)

C++

花花酱 LeetCode 926. Flip String to Monotone Increasing

Problem

A string ofĀ '0's andĀ '1's isĀ monotone increasingĀ if it consists of some number ofĀ '0's (possibly 0), followed by some number ofĀ '1's (also possibly 0.)

We are given a stringĀ SĀ ofĀ '0's andĀ '1's, and we may flip anyĀ '0'Ā to aĀ '1'Ā or aĀ '1'Ā to aĀ '0'.

Return the minimum number of flips to makeĀ SĀ monotone increasing.

Example 1:

Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.

Note:

  1. 1 <= S.length <= 20000
  2. SĀ only consists ofĀ '0'Ā andĀ '1'Ā characters.

Solution: DP

l[i] := number of flips to make S[0] ~ S[i] become all 0s.

r[i] := number of flips to make S[i] ~ S[n – 1] become all 1s.

Try all possible break point, S[0] ~ S[i – 1] are all 0s and S[i] ~ S[n-1] are all 1s.

ans = min{l[i – 1] + r[i]}

Time complexity: O(n)

Space complexity: O(n)

C++

C++ v2

C++ v2 / O(1) Space

 

花花酱 LeetCode 925. Long Pressed Name

Problem

Your friend is typing hisĀ nameĀ into a keyboard.Ā  Sometimes, when typing a characterĀ c, the key might getĀ long pressed, and the character will be typed 1 or more times.

You examine theĀ typedĀ characters of the keyboard.Ā  ReturnĀ TrueĀ if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it wasn't in the typed output.

Example 3:

Input: name = "leelee", typed = "lleeelee" 
Output: true

Example 4:

Input: name = "laiden", typed = "laiden"
Output: true
Explanation: It's not necessary to long press any character.

Note:

  1. name.length <= 1000
  2. typed.length <= 1000
  3. The characters ofĀ nameĀ andĀ typedĀ are lowercase letters.

Solution: Two Pointers

Time complexity: O(n)

Space complexity: O(1)

C++

C++ / Iterator