花花酱 LeetCode 120. Triangle

By zxi on August 27, 2018

Problem

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Solution: DP

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

// [[2] [[2]

// [3, 4]] [5, 6]

// [6, 5, 7]] [11, 10, 11]

// [4, 1, 8, 3]] [15, 11, 18, 14]]

int minimumTotal(vector<vector<int>>& t) {

int n = t.size();

// t[i][j] := minTotalOf(i,j)

// t[i][j] += min(t[i - 1][j], t[i - 1][j - 1])

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

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

if (i == 0 && j == 0) continue;

if (j == 0) t[i][j] += t[i - 1][j];

else if (j == i) t[i][j] += t[i - 1][j - 1];

else t[i][j] += min(t[i - 1][j], t[i - 1][j - 1]);

}

return *std::min_element(begin(t.back()), end(t.back()));

}

};

花花酱 LeetCode 893. Groups of Special-Equivalent Strings

By zxi on August 26, 2018

Problem

You are given an array A of strings.

Two strings S and T are special-equivalent if after any number of moves, S == T.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].

Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.

Return the number of groups of special-equivalent strings from A.

Example 1:

Input: ["a","b","c","a","c","c"]
Output: 3
Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]

Example 2:

Input: ["aa","bb","ab","ba"]
Output: 4
Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]

Example 3:

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]

Example 4:

Input: ["abcd","cdab","adcb","cbad"]
Output: 1
Explanation: 1 group ["abcd","cdab","adcb","cbad"]

Note:

1 <= A.length <= 1000
1 <= A[i].length <= 20
All A[i] have the same length.
All A[i] consist of only lowercase letters.

Solution: Signature

All Special-Equivalent Strings should have the same signature if we sort all the odd-index characters and all the even-index characters.

E.g. [“abcd”,”cdab”,”adcb”,”cbad”] are all in the same graph.

“abcd”: odd “ac”, even: “bd”
“cdab”: odd “ac”, even: “bd”
“adcb”: odd “ac”, even: “bd”
“cbad”: odd “ac”, even: “bd”

We can concatenate the odd and even strings to create a hashable signature.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int numSpecialEquivGroups(vector<string>& A) {

unordered_set<string> s;

for (const string& a : A) {

string odd;

string even;

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

if (i % 2)

odd += a[i];

else

even += a[i];

}

sort(begin(odd), end(odd));

sort(begin(even), end(even));

s.insert(odd + even);

}

return s.size();

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public int numSpecialEquivGroups(String[] A) {

Set<String> groups = new HashSet<>();

for (String a: A) {

char[] odd = new char[(a.length() + 1) / 2];

char[] even = new char[(a.length() + 1) / 2];

for (int i = 0; i < a.length(); ++i) {

if (i % 2 == 0)

even[i / 2] = a.charAt(i);

else

odd[i / 2] = a.charAt(i);

}

Arrays.sort(odd);

Arrays.sort(even);

String s = new String(odd) + new String(even);

groups.add(s);

}

return groups.size();

}

Python

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def numSpecialEquivGroups(self, A):

s = set()

for a in A:

odd = ""

even = ""

for i, c in enumerate(a):

if i % 2 == 0:

odd += c

else:

even += c

s.add(''.join(sorted(odd) + sorted(even)))

return len(s)

Python (1-linear)

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def numSpecialEquivGroups(self, A):

return len(set([''.join(sorted(a[0::2]) + sorted(a[1::2])) for a in A]))

花花酱 LeetCode 895. Maximum Frequency Stack

By zxi on August 26, 2018

Problem

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

push(int x), which pushes an integer x onto the stack.
pop(), which removes and returns the most frequent element in the stack.
- If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

Input: 
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
The total number of FreqStack.push calls will not exceed 10000 in a single test case.
The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

Solution 1: Buckets

We have n stacks. The i-th stack has the of elements with freq i when pushed.

We keep tracking the freq of each element.

push(x): stacks[++freq(x)].push(x) # inc x’s freq and push it onto freq-th stack

pop(): x = stacks[max_freq].pop(), –freq(x); # pop element x from the max_freq stack and dec it’s freq.

Time complexity: O(1) push / pop

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 144 ms

class FreqStack {

public:

FreqStack() {}

void push(int x) {

auto it = freq_.find(x);

if (it == freq_.end())

it = freq_.emplace(x, 0).first;

int freq = ++it->second;

if (stacks_.size() < freq) stacks_.push_back({});

stacks_[freq - 1].push(x);

}

int pop() {

int x = stacks_.back().top();

stacks_.back().pop();

if (stacks_.back().empty())

stacks_.pop_back();

auto it = freq_.find(x);

if (!(--it->second))

freq_.erase(it);

return x;

}

private:

vector<stack<int>> stacks_;

unordered_map<int, int> freq_;

};

Solution2: Priority Queue

Use a max heap with key: (freq, seq), the max freq and closest to the top of stack element will be extracted first.

Time complexity: O(logn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 132 ms

class FreqStack {

public:

FreqStack() {}

void push(int x) {

int key = (++f_[x] << 16) | (++seq_);

q_.emplace(key, x);

}

int pop() {

int x = q_.top().second; q_.pop();

if (--f_[x] == 0)

f_.erase(x);

return x;

}

private:

int seq_ = 0;

unordered_map<int, int> f_; // {x -> freq}

priority_queue<pair<int, int>> q_; // {freq | seq_, x}

};

Problem

On a N * N grid, we place some 1 * 1 * 1 cubes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Return the total surface area of the resulting shapes.

Example 1:

Input: [[2]]
Output: 10

Example 2:

Input: [[1,2],[3,4]]
Output: 34

Example 3:

Input: [[1,0],[0,2]]
Output: 16

Example 4:

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

Example 5:

Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 46

Note:

1 <= N <= 50
0 <= grid[i][j] <= 50

Solution: Geometry

3D version of 花花酱 LeetCode 463. Island Perimeter

Ans = total faces – hidden faces.

each pile with height h has the surface area of 2 (top/bottom) + 4*h (sides)

\(ans = ans + 2 + 4 * h\)

if a cube has a neighbour, reduce the total surface area by 1

For each pile, we check 4 neighbours, the number of total hidden faces of this pile is sum(min(h, neighbour’s h)).

\(ans = ans – \Sigma min(h, n.h)\)

Time complexity: O(mn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

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

static const vector<int> dirs{0, -1, 0, 1, 0};

int m = grid.size();

int n = grid[0].size();

int ans = 0;

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

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

int h = grid[i][j];

if (h == 0) continue;

ans += 2 + 4 * h;

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

int tx = j + dirs[k];

int ty = i + dirs[k + 1];

if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;

int th = grid[ty][tx];

ans -= (th <= 0 ? 0 : min(h, th));

}

return ans;

}

};

C++ (opt)

Since the neighbor relationship is symmetric, we can only consider the top and left neighbors and double the hidden faces.

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

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

int m = grid.size();

int n = grid[0].size();

int ans = 0;

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

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

int h = grid[i][j];

if (h == 0) continue;

ans += 2 + 4 * h;

if (i) ans -= 2 * min(h, grid[i - 1][j]);

if (j) ans -= 2 * min(h, grid[i][j - 1]);

}

return ans;

}

};

花花酱 LeetCode 894. All Possible Full Binary Trees

By zxi on August 26, 2018

Problem

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Example 1:

Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:

Note:

1 <= N <= 20

Solution: Recursion

Key observations:

n must be odd, If n is even, no possible trees
ans is the cartesian product of trees(i) and trees(n-i-1). Ans = {Tree(0, l, r) for l, r in trees(i) X trees(N – i – 1)}.

w/o cache

C++

// Author: Huahua

// Running time: 72 ms

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

if (N == 1) return {new TreeNode(0)};

vector<TreeNode*> ans;

for (int i = 1; i < N; i += 2) {

for (const auto& l : allPossibleFBT(i))

for (const auto& r : allPossibleFBT(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 20 ms

class Solution {

public List<TreeNode> allPossibleFBT(int N) {

List<TreeNode> ans = new ArrayList<>();

if (N % 2 == 0) return ans;

if (N == 1) {

ans.add(new TreeNode(0));

return ans;

}

for (int i = 1; i < N; i += 2) {

for (TreeNode l : allPossibleFBT(i))

for (TreeNode r : allPossibleFBT(N - i - 1)) {

TreeNode root = new TreeNode(0);

root.left = l;

root.right = r;

ans.add(root);

}

return ans;

}

Python

"""

Author: Huahua

Running time: 396 ms

"""

class Solution:

def allPossibleFBT(self, N):

if N % 2 == 0: return []

if N == 1: return [TreeNode(0)]

ans = []

for i in range(1, N, 2):

for l in self.allPossibleFBT(i):

for r in self.allPossibleFBT(N - i - 1):

root = TreeNode(0)

root.left = l

root.right = r

ans.append(root)

return ans

w/cache

C++

// Author: Huahua

// Running time: 68 ms

static constexpr int kMaxN = 20 + 1;

static array<vector<TreeNode*>, kMaxN> m;

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

return trees(N);

}

private:

vector<TreeNode*>& trees(int N) {

if (m[N].size() > 0) return m[N];

vector<TreeNode*>& ans = m[N];

if (N % 2 == 0) return ans = {};

if (N == 1) ans = {new TreeNode(0)};

for (int i = 1; i < N; i += 2) {

for (const auto& l : trees(i))

for (const auto& r : trees(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

Python

using itertools.product w/ cache

"""

Author: Huahua

Running time: 188 ms

"""

m = [[] for _ in range(21)]

class Solution:

def allPossibleFBT(self, N):

if N % 2 == 0: return []

if N == 1: return [TreeNode(0)]

if len(m[N]) > 0: return m[N]

ans = []

for i in range(1, N, 2):

for l, r in itertools.product(self.allPossibleFBT(i),

self.allPossibleFBT(N - i - 1)):

root = TreeNode(0)

root.left = l

root.right = r

ans.append(root)

m[N] = ans

return ans

C++

// Author: Huahua

// Running time: 100 ms

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

vector<vector<TreeNode*>> dp(N + 1);

dp[1] = {new TreeNode(0)};

for (int i = 3; i <= N; i += 2)

for (int j = 1; j < i; j += 2) {

int k = i - j - 1;

for (const auto& l : dp[j])

for (const auto& r : dp[k]) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

dp[i].push_back(root);

}

return dp[N];

}

};

Benchmark

No-cache vs cached

C++

#include <iostream>

#include <vector>

#include <array>

#include <ctime>

#include <cstdio>

using namespace std;

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

static constexpr int kMaxN = 101 + 1;

static array<vector<TreeNode*>, kMaxN> m;

class NoCache {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

if (N == 1) return {new TreeNode(0)};

vector<TreeNode*> ans;

for (int i = 1; i < N; i += 2) {

for (const auto& l : allPossibleFBT(i))

for (const auto& r : allPossibleFBT(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

class Cached {

public:

vector<TreeNode*> allPossibleFBT(int N) {

return trees(N);

}

private:

vector<TreeNode*>& trees(int N) {

if (m[N].size() > 0) return m[N];

vector<TreeNode*>& ans = m[N];

if (N % 2 == 0) return ans = {};

if (N == 1) ans = {new TreeNode(0)};

for (int i = 1; i < N; i += 2) {

for (const auto& l : trees(i))

for (const auto& r : trees(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

int main(int argc, char** argv) {

printf("N\tno-cache\tcached\n");

for (int i = 1; i <= 35; i += 2) {

printf("%02d\t", i);

{

auto start = clock();

(void)(NoCache().allPossibleFBT(i));

printf("%8.4f\t", static_cast<double>(clock() - start) / CLOCKS_PER_SEC);

}

{

// Clear the cache.

for (int j = 0; j < kMaxN; ++j)

m[i].clear();

auto start = clock();

(void)(Cached().allPossibleFBT(i));

printf("%8.4f\n", static_cast<double>(clock() - start) / CLOCKS_PER_SEC);

}

return 0;

}

花花酱 LeetCode 120. Triangle

Problem

Solution: DP

C++

花花酱 LeetCode 893. Groups of Special-Equivalent Strings

Problem

Solution: Signature

C++

Java

Python

Python (1-linear)

花花酱 LeetCode 895. Maximum Frequency Stack

Problem

Solution 1: Buckets

C++

Solution2: Priority Queue

C++

Related Problems

花花酱 LeetCode 892. Surface Area of 3D Shapes

Problem

Solution: Geometry

C++

C++ (opt)

花花酱 LeetCode 894. All Possible Full Binary Trees

Problem

Solution: Recursion

C++

Java

Python

C++

Python

C++

Benchmark

C++

Huahua's Tech Road

花花酱 LeetCode 120. Triangle

Problem

Solution: DP

C++

花花酱 LeetCode 893. Groups of Special-Equivalent Strings

Problem

Solution: Signature

C++

Java

Python

Python (1-linear)

花花酱 LeetCode 895. Maximum Frequency Stack

Problem

Solution 1: Buckets

C++

Solution2: Priority Queue

C++

Related Problems

花花酱 LeetCode 892. Surface Area of 3D Shapes

Problem

Solution: Geometry

C++

C++ (opt)

花花酱 LeetCode 894. All Possible Full Binary Trees

Problem

Solution: Recursion

C++

Java

Python

C++

Python

C++

Benchmark

C++