Posts tagged as “medium”

花花酱 LeetCode 838. Push Dominoes

By zxi on May 6, 2019

here are N dominoes in a line, and we place each domino vertically upright.

In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string “S” representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:

Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Note:

0 <= N <= 10^5
String dominoes contains only 'L‘, 'R' and '.'

Solution: Simulation

Simulate the push process, record the steps from L and R for each domino.
steps(L) == steps(R) => “.”
steps(L) < steps(R) => “L”
steps(L) > steps(R) => “R”

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

C++

// Author: Huahua, running time: 24 ms, 15.2 MB

class Solution {

public:

string pushDominoes(string D) {

const int n = static_cast<int>(D.size());

vector<int> L(n, INT_MAX), R(n, INT_MAX);

for (int i = 0; i < n; ++i)

if (D[i] == 'L') {

L[i] = 0;

for (int j = i - 1; j >= 0 && D[j] == '.'; --j)

L[j] = L[j + 1] + 1;

} else if (D[i] == 'R') {

R[i] = 0;

for (int j = i + 1; j < n && D[j] == '.'; ++j)

R[j] = R[j - 1] + 1;

}

for (int i = 0; i < n; ++i)

if (L[i] < R[i]) D[i] = 'L';

else if (L[i] > R[i]) D[i] = 'R';

return D;

}

};

花花酱 LeetCode 279. Perfect Squares

By zxi on April 17, 2019

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++

// Author: Huahua, running time: 104 ms

class Solution {

public:

int numSquares(int n) {

vector<int> dp(n + 1, INT_MAX >> 1);

dp[0] = 0;

for (int i = 1; i <= n; ++i)

for (int j = 1; j * j <= i; ++j)

dp[i] = min(dp[i], dp[i - j * j] + 1);

return dp[n];

}

};

花花酱 LeetCode 54. Spiral Matrix

By zxi on April 12, 2019

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Solution: Simulation

Keep track of the current bounds (left, right, top, bottom).

Init: left = 0, right = n – 1, top = 0, bottom = m – 1

Each time we move in one direction and shrink the bounds and turn 90 degrees:
1. go right => –top
2. go down => –right
3. go left => ++bottom
4. go up => ++left

C++

class Solution {

public:

vector<int> spiralOrder(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

int l = 0;

int t = 0;

int r = matrix[0].size();

int b = matrix.size();

const int total = (r--) * (b--);

int d = 0;

int x = 0;

int y = 0;

vector<int> ans;

while (ans.size() < total - 1) {

if (d == 0) {

while (x < r) ans.push_back(matrix[y][x++]);

++t;

} else if (d == 1) {

while (y < b) ans.push_back(matrix[y++][x]);

--r;

} else if (d == 2) {

while (x > l) ans.push_back(matrix[y][x--]);

--b;

} else if (d == 3) {

while (y > t) ans.push_back(matrix[y--][x]);

++l;

}

d = (d + 1) % 4;

}

if (ans.size() != total) ans.push_back(matrix[y][x]);

return ans;

}

};

花花酱 LeetCode 394. Decode String

By zxi on April 10, 2019

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Solution 1: Recursion

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

C++

// Author: Huahua, 4ms

class Solution {

public:

string decodeString(string s) {

if (s.empty()) return "";

string ans;

int i = 0;

int n = s.length();

int c = 0;

while (isdigit(s[i]) && i < n)

c = c * 10 + (s[i++] - '0');

int j = i;

if (i < n && s[i] == '[') {

int open = 1;

while (++j < n && open) {

if (s[j] == '[') ++open;

if (s[j] == ']') --open;

}

} else {

while (j < n && isalpha(s[j])) ++j;

}

// "def2[ac]" => "def" + decodeString("2[ac]")

// | |

// i j

if (i == 0)

return s.substr(0, j) + decodeString(s.substr(j));

// "3[a2[c]]ef", ss = decodeString("a2[c]") = "acc"

// | |

// i j

string ss = decodeString(s.substr(i + 1, j - i - 2));

while (c--)

ans += ss;

// "3[a2[c]]ef", ans = "abcabcabc", ans += decodeString("ef")

ans += decodeString(s.substr(j));

return ans;

}

};

花花酱 LeetCode 1011. Capacity To Ship Packages Within D Days

By zxi on March 16, 2019

A conveyor belt has packages that must be shipped from one port to another within D days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], D = 3
Output: 6
Explanation: 
A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], D = 4
Output: 3
Explanation: 
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Note:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

Solution: Binary Search

Find the smallest capacity such that can finish in D days.

Time complexity: O(n * log(sum(weights))
Space complexity: O(1)

C++

// Author: Huahua, running time: 52 ms, 11.9 MB

class Solution {

public:

int shipWithinDays(vector<int>& weights, int D) {

int l = *max_element(begin(weights), end(weights));

int r = accumulate(begin(weights), end(weights), 0) + 1;

while (l < r) {

int m = l + (r - l) / 2;

int d = 1;

int t = 0;

for (int w : weights)

if ((t += w) > m) {

t = w;

++d;

}

d > D ? l = m + 1 : r = m;

}

return l;

}

};