Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode Weekly Contest 133

LeetCode 1029 Two City Scheduling

Solution: DP

dp[i][j] := min cost to put j people into city A for the first i people
dp[0][0] = 0
dp[i][0] = dp[i -1][0] + cost_b
dp[i][j] = min(dp[i – 1][j] + cost_b, dp[i – 1][j – 1] + cost_a)
ans := dp[n][n/2]

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

1030. Matrix Cells in Distance Order

Solution: Sorting

Time complexity: O(RC*log(RC))
Space complexity: O(RC)

C++

1031. Maximum Sum of Two Non-Overlapping Subarrays

Solution: Prefix sum

Time complexity: O(n^2)
Space complexity: O(n)

C++

1032. Stream of Characters

Solution: Trie

Time complexity:

  • build O(sum(len(w))
  • query O(max(len(w))

Space complexity: O(sum(len(w))

C++

花花酱 LeetCode 38. Count and Say

Problem

https://leetcode.com/problems/count-and-say/

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

Solution: Recursion + Simulation

C++

花花酱 LeetCode 279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Solution 1: DP

dp[i] := ans
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} 1 <= j * j <= i

dp[5] = min{
dp[5 – 2 * 2] + 1 = dp[1] + 1 = (dp[1 – 1 * 1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1 * 1] + 1 = dp[3] + 1 = (dp[3 – 1 * 1] + 1) + 1 = dp[1] + 2 = dp[1 – 1*1] + 1 + 2 = dp[0] + 3 = 3
};

dp[5] = 2

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

C++

花花酱 LeetCode Weekly Contest 132 (1025,1026,1027,1028)

1025. Divisor Game

Solution: Recursion with Memoization

Time complexity: O(n^2)
Space complexity: O(n)

C++

1026. Maximum Difference Between Node and Ancestor

Solution: Resolution, pass min / max of ancestor nodes

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

C++

1027. Longest Arithmetic Sequence

Solution 1: Brute Force + Pruning

Time complexity: O(n^3) ~ O(n^2) in practice
Space complexity: O(n)

C++

1028. Recover a Tree From Preorder Traversal

Solution: Recursion

Check the current depth and expected depth, if don’t match, return nullptr.

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

C++