# 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)

# 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)

# 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.

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


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)

# 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)

# 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)

# 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++ (opt)

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

Mission News Theme by Compete Themes.