Posts tagged as “hard”

花花酱 LeetCode 68. Text Justification

By zxi on October 1, 2019

Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

Note:

A word is defined as a character sequence consisting of non-space characters only.
Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.

Example 1:

Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Example 2:

Input:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
Explanation: Note that the last line is "shall be    " instead of "shall     be",
             because the last line must be left-justified instead of fully-justified.
             Note that the second line is also left-justified becase it contains only one word.

Example 3:

Input:
words = ["Science","is","what","we","understand","well","enough","to","explain",
         "to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
Output:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

Solution: Simulation

Time complexity: O(sum(len(s))
Space complexity: O(sum(len(s))

C++

// Author: Huahua

class Solution {

public:

vector<string> fullJustify(vector<string> &words, int L) {

size_t i = 0, n = words.size();

vector<string> ans;

while (i < n) {

bool last_line = false;

int ll = 0;

vector<string_view> tw;

while (ll <= L && i < n) {

size_t wl = words[i].length();

int tll = ll + (tw.size() ? 1 : 0) + wl;

if (tll > L) break;

ll = tll;

tw.push_back(string_view(words[i]));

if (++i == n) last_line = true;

if (ll == L) break;

}

string line;

if (!last_line) {

int tl = 0;

for(const auto& w : tw) tl += w.length();

int avg_space = tw.size()==1 ? 0 : ((L-tl) / (tw.size() - 1));

int extra_space = tw.size()==1 ? 0 : (L - avg_space * (tw.size() - 1) - tl);

for (const auto& w : tw) {

if (line.length() > 0) {

line.append(avg_space, ' ');

if (extra_space > 0) {

line += ' ';

--extra_space;

}

line += w;

}

} else {

for (const auto& w : tw) {

if (line.length() > 0)

line += ' ';

line += w;

}

line.append(L - line.length(), ' ');

ans.push_back(std::move(line));

}

return ans;

}

};

花花酱 LeetCode 99. Recover Binary Search Tree

By zxi on September 29, 2019

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

Solution: Inorder traversal

Using inorder traversal to find two nodes that have val < prev.val

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

C++

// Author: Huahua

class Solution {

public:

void recoverTree(TreeNode *root) {

inorder(root);

swap(first->val, second->val);

}

void inorder(TreeNode* root) {

if (!root) return;

inorder(root->left);

if (prev && prev->val > root->val) {

if (!first) first = prev;

second = root;

}

prev = root;

inorder(root->right);

}

private:

TreeNode* first;

TreeNode* second;

TreeNode* prev;

};

花花酱 LeetCode 1210. Minimum Moves to Reach Target with Rotations

By zxi on September 29, 2019

In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).

In one move the snake can:

Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Rotate clockwise if it’s in a horizontal position and the two cells under it are both empty. In that case the snake moves from (r, c) and (r, c+1) to (r, c) and (r+1, c).
Rotate counterclockwise if it’s in a vertical position and the two cells to its right are both empty. In that case the snake moves from (r, c) and (r+1, c) to (r, c) and (r, c+1).

Return the minimum number of moves to reach the target.

If there is no way to reach the target, return -1.

Example 1:

Input: grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].

Example 2:

Input: grid = [[0,0,1,1,1,1],
               [0,0,0,0,1,1],
               [1,1,0,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,0]]
Output: 9

Constraints:

2 <= n <= 100
0 <= grid[i][j] <= 1
It is guaranteed that the snake starts at empty cells.

Solution1: BFS

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

C++

// Author: Huahua, 48 ms, 18.1 MB

class Solution {

public:

inline int pos(int x, int y) {

return y * 100 + x;

}

inline int encode(int p1, int p2) {

return (p1 << 16) | p2;

}

int minimumMoves(vector<vector<int>>& grid) {

int n = grid.size();

queue<pair<int, int>> q;

unordered_set<int> seen;

q.push({pos(0, 0), pos(1, 0)}); // tail, head

seen.insert(encode(pos(0, 0), pos(1, 0)));

int steps = 0;

auto valid = [&](int x, int y) {

bool v = x >= 0 && x < n && y >= 0 && y < n && !grid[y][x];

return v;

};

while (!q.empty()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int y0 = p.first / 100;

int x0 = p.first % 100;

int y1 = p.second / 100;

int x1 = p.second % 100;

if (x0 == n - 2 && y0 == n - 1 &&

x1 == n - 1 && y1 == n - 1) {

return steps;

}

bool h = y0 == y1;

for (int i = 0; i < 3; ++i) {

int tx0 = x0;

int ty0 = y0;

int tx1 = x1;

int ty1 = y1;

int rx = x0;

int ry = y0;

switch (i) {

case 0: // down

++ty0;

++ty1;

break;

case 1: // right

++tx0;

++tx1;

break;

case 2: // rotate

++rx;

++ry;

if (h) { // clockwise

--tx1;

++ty1;

} else { // counterclockwise

++tx1;

--ty1;

}

break;

}

if (!valid(tx0, ty0) || !valid(tx1, ty1) || !valid(rx, ry)) continue;

int key = encode(pos(tx0, ty0), pos(tx1, ty1));

if (seen.count(key)) continue;

seen.insert(key);

q.push({pos(tx0, ty0), pos(tx1, ty1)});

}

++steps;

}

return -1;

}

};

Solution 2: DP

dp[i][j].first = min steps to reach i,j (tail pos) facing right
dp[i][j].second = min steps to reach i, j (tail pos) facing down
ans = dp[n][n-1].first

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

C++

// Author: Huahua, 16 ms, 12.1MB

class Solution {

public:

int minimumMoves(vector<vector<int>>& grid) {

constexpr int kInf = 1e9;

const int n = grid.size();

vector<vector<pair<int, int>>> dp(n + 1,

vector<pair<int, int>>(n + 1, {kInf, kInf}));

dp[0][1].first = dp[1][0].first = -1;

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

for (int j = 1; j <= n; ++j) {

bool h = false;

bool v = false;

if (!grid[i - 1][j - 1] && j < n && !grid[i - 1][j]) {

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

h = true;

}

if (!grid[i - 1][j - 1] && i < n && !grid[i][j - 1]) {

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

v = true;

}

if (v && j < n && !grid[i][j])

dp[i][j].second = min(dp[i][j].second, dp[i][j].first + 1);

if (h && i < n && !grid[i][j])

dp[i][j].first = min(dp[i][j].first, dp[i][j].second + 1);

}

return dp[n][n - 1].first >= kInf ? -1 : dp[n][n - 1].first;

}

};

花花酱 LeetCode 1192. Critical Connections in a Network

By zxi on September 15, 2019

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some server unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Constraints:

1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections[i][0] != connections[i][1]
There are no repeated connections.

Solution: Tarjan

Time complexity: O(v+e)
Space complexity: O(v+e)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {

vector<vector<int>> g(n);

vector<int> ts(n, INT_MAX);

vector<vector<int>> ans;

int t = 0;

function<int(int, int)> tarjan = [&](int i, int p) {

int min_i = ts[i] = ++t;

for (int j : g[i]) {

if (ts[j] == INT_MAX) {

int min_j = tarjan(j, i);

min_i = min(min_i, min_j);

if (ts[i] < min_j)

ans.push_back({i, j});

} else if (j != p) {

min_i = min(min_i, ts[j]);

}

return min_i;

};

for (const auto& e : connections) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

tarjan(0, -1);

return ans;

}

};

花花酱 LeetCode 1187. Make Array Strictly Increasing

By zxi on September 7, 2019

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

Solution: DP

Time complexity: O(mn)
Space complexity: O(mn) -> O(m + n)

C++

// Author: Huahua

class Solution {

public:

int makeArrayIncreasing(vector<int>& a, vector<int>& c) {

constexpr int kInf = 1e9;

int m = a.size();

// Sort b and make it only containing unique numbers.

sort(begin(c), end(c));

vector<int> b;

for (int i = 0; i < c.size(); ++i) {

if (!b.empty() && c[i] == b.back()) continue;

b.push_back(c[i]);

}

int n = b.size();

// min steps to make a[0~i] valid by keeping a[i]

vector<int> keep(m, kInf);

keep[0] = 0;

// swap[i][j] := min steps to make a[0~i] valid by a[i] = b[j]

vector<int> swap(n, 1);

for (int i = 1; i < m; ++i) {

int min_keep = kInf;

int min_swap = kInf;

vector<int> temp(n, kInf);

for (int j = 0; j < n; ++j) {

if (j > 0) min_swap = min(min_swap, swap[j - 1] + 1);

if (a[i] > b[j]) min_keep = min(min_keep, swap[j]);

if (a[i] > a[i - 1]) keep[i] = keep[i - 1];

if (b[j] > a[i - 1]) temp[j] = keep[i - 1] + 1;

temp[j] = min(temp[j], min_swap);

keep[i] = min(keep[i], min_keep);

}

temp.swap(swap);

}

int s = *min_element(begin(swap), end(swap));

int k = keep.back();

int ans = min(s, k);

return ans >= kInf ? -1 : ans;

}

};