Posts tagged as “medium”

花花酱 LeetCode 890. Find and Replace Pattern

By zxi on August 19, 2018

Problem

You have a list of words and a pattern, and you want to know which words in words matches the pattern.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

(Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)

Return a list of the words in words that match the given pattern.

You may return the answer in any order.

Example 1:

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
since a and b map to the same letter.

Note:

1 <= words.length <= 50
1 <= pattern.length = words[i].length <= 20

Solution: Remember the last pos of each char.

Time complexity: O(n*l)

Space complexity: O(128) -> O(26)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

vector<string> findAndReplacePattern(vector<string>& words, string pattern) {

vector<string> ans;

for (const string& w : words)

if (match(w, pattern)) ans.push_back(w);

return ans;

}

private:

bool match(const string& w, const string& p) {

vector<int> last_pos_w(128, INT_MIN); // last pos of x in w

vector<int> last_pos_p(128, INT_MIN); // last pos of x in p

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

if (last_pos_w[w[i]] != last_pos_p[p[i]]) {

return false;

} else {

last_pos_w[w[i]] = last_pos_p[p[i]] = i;

}

return true;

}

};

花花酱 LeetCode 617. Merge Two Binary Trees

By zxi on August 17, 2018

Problem

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

Note: The merging process must start from the root nodes of both trees.

Solution: Recursion

Reuse t1/t2

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

if (t1 == nullptr) return t2;

if (t2 == nullptr) return t1;

auto root = t1;

root->val += t2->val;

root->left = mergeTrees(t1->left, t2->left);

root->right = mergeTrees(t1->right, t2->right);

return root;

}

};

Create a copy

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

if (t1 == nullptr) return copyTree(t2);

if (t2 == nullptr) return copyTree(t1);

TreeNode* root = new TreeNode(t1->val + t2->val);

root->left = mergeTrees(t1->left, t2->left);

root->right = mergeTrees(t1->right, t2->right);

return root;

}

private:

TreeNode* copyTree(TreeNode* root) {

if (root == nullptr) return nullptr;

TreeNode* r = new TreeNode(root->val);

r->left = copyTree(root->left);

r->right = copyTree(root->right);

return r;

}

};

花花酱 LeetCode 655. Print Binary Tree

By zxi on August 17, 2018

Problem

Print a binary tree in an m*n 2D string array following these rules:

The row number m should be equal to the height of the given binary tree.
The column number n should always be an odd number.
The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
Each unused space should contain an empty string "".
Print the subtrees following the same rules.

Example 1:

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

Example 2:

Input:
     1
    / \
   2   3
    \
     4
Output:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]

Example 3:

Input:
      1
     / \
    2   5
   / 
  3 
 / 
4 
Output:

[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

Note: The height of binary tree is in the range of [1, 10].

Solution: Recursion

Compute the layers h of the tree.

shape of the output matrix: h * w (w = 2^h – 1)

pre-order to fill the output matrix

first layer’s root: y1 = 0, x1 = (l1 + r1) / 2 = (0 + w – 1) / 2 (center)

first layer’s left child (2nd layer): y2 = 1, x2 = (l2 + r2) = (l1 + (x1 – 1)) / 2 (center of the left half)

first layer’s right child(2nd layer): y1 = 2, x2 = (l2′ + r2′) = ((x1+1) + r1) / 2 (center of the right half)

…

Time complexity: O(m*n)

Space complexity: O(m*n)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<vector<string>> printTree(TreeNode* root) {

int h = getHeight(root);

int w = (1 << h) - 1; // 2 ^ h - 1

vector<vector<string>> ans(h, vector<string>(w, ""));

fill(root, ans, 0, 0, w - 1);

return ans;

}

private:

int getHeight(TreeNode* root) {

if (!root) return 0;

return max(getHeight(root->left), getHeight(root->right)) + 1;

}

void fill(TreeNode* root, vector<vector<string>>& ans, int h, int l, int r){

if (!root) return;

int mid = (l + r) / 2;

ans[h][mid] = std::to_string(root->val);

fill(root->left, ans, h + 1, l, mid - 1);

fill(root->right, ans, h + 1, mid + 1, r);

}

};

Python3

"""

Author: Huahua

Running time: 44 ms

"""

class Solution:

def printTree(self, root):

def height(root):

if not root: return 0

return max(height(root.left), height(root.right)) + 1

def fill(root, h, l, r):

if not root: return

mid = (l + r) // 2

m[h][mid] = str(root.val)

if root.left: fill(root.left, h + 1, l, mid - 1)

if root.right: fill(root.right, h + 1, mid + 1, r)

h = height(root)

w = 2**h - 1

m = [[""] * w for _ in range(h)]

fill(root, 0, 0, w - 1)

return m

花花酱 LeetCode 889. Spiral Matrix III

By zxi on August 13, 2018

Problem

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.

Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.

Now, we walk in a clockwise spiral shape to visit every position in this grid.

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)

Eventually, we reach all R * C spaces of the grid.

Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:

Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Note:

1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C

Solution: Simulation

We can find out the moving sequence is ESWWNNEEESSSWWWWNNNN.

The pattern is 1,1,2,2,3,3,4,4,… steps in one direction, and turn right for 90 degrees.

directions are E,S,W,N,E,S,W,N…

Time complexity: O(max(R,C)^2)

Space complexity: O(1) or O(RC) if ans included.

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {

vector<vector<int>> ans;

int k = 0;

int dirs[][2]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // ESWN

int d = 0; // E

ans.push_back({r0, c0});

if (ans.size() == R * C) return ans;

while (++k) {

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

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

c0 += dirs[d][0];

r0 += dirs[d][1];

if (c0 < 0 || c0 >= C || r0 < 0 || r0 >= R) continue;

ans.push_back({r0, c0});

if (ans.size() == R * C) return ans;

}

d = (d + 1) % 4;

}

return {};

}

};

花花酱 LeetCode 886. Possible Bipartition

By zxi on August 12, 2018

Problem

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

Example 1:

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Example 2:

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:

Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Note:

1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].

Solution: Graph Coloring

Color a node with one color, and color all it’s disliked nodes with another color, if can not finish return false.

Time complexity: O(V+E)

Space complexity: O(V+E)

C++ / DFS

// Author: Huahua

// Running time: 96 ms

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

g_ = vector<vector<int>>(N);

for (const auto& d : dislikes) {

g_[d[0] - 1].push_back(d[1] - 1);

g_[d[1] - 1].push_back(d[0] - 1);

}

colors_ = vector<int>(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors_[i] == 0 && !dfs(i, 1)) return false;

return true;

}

private:

vector<vector<int>> g_;

vector<int> colors_;

bool dfs(int cur, int color) {

colors_[cur] = color;

for (int nxt : g_[cur]) {

if (colors_[nxt] == color) return false;

if (colors_[nxt] == 0 && !dfs(nxt, -color)) return false;

}

return true;

}

};

C++ / BFS

// Author: Huahua

// Running time: 100 ms

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

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

for (const auto& d : dislikes) {

g[d[0] - 1].push_back(d[1] - 1);

g[d[1] - 1].push_back(d[0] - 1);

}

queue<int> q;

vector<int> colors(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors[i] != 0) continue;

q.push(i);

colors[i] = 1;

while (!q.empty()) {

int cur = q.front(); q.pop();

for (int nxt : g[cur]) {

if (colors[nxt] == colors[cur]) return false;

if (colors[nxt] != 0) continue;

colors[nxt] = -colors[cur];

q.push(nxt);

}

return true;

}

};

Posts tagged as “medium”

花花酱 LeetCode 890. Find and Replace Pattern

Problem

Solution: Remember the last pos of each char.

花花酱 LeetCode 617. Merge Two Binary Trees

Problem

Solution: Recursion

花花酱 LeetCode 655. Print Binary Tree

Problem

Solution: Recursion

C++

Python3

花花酱 LeetCode 889. Spiral Matrix III

Problem

Solution: Simulation

花花酱 LeetCode 886. Possible Bipartition

Problem

Solution: Graph Coloring

C++ / DFS

C++ / BFS

Related Problem