Posts published in August 2018

花花酱 LeetCode 70. Climbing Stairs

By zxi on August 27, 2018

Problem

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution: DP

Time complexity: O(n)

Space complexity: O(n)

C++ O(n)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int climbStairs(int n) {

// f[i] = climbStairs(i)

vector<int> f(n + 1, 0);

f[0] = f[1] = 1;

// f[i] = f[i-1] + f[i-2]

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

f[i] = f[i - 1] + f[i - 2];

return f[n];

}

};

C++ O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int climbStairs(int n) {

int two = 1;

int one = 1;

int curr = 1;

// curr = two + one

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

curr = two + one;

two = one;

one = curr;

}

return curr;

}

};

花花酱 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;

}

};

Posts published in August 2018

花花酱 LeetCode 70. Climbing Stairs

Problem

Solution: DP

C++ O(n)

C++ O(1)

花花酱 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)