# Posts published in “Uncategorized”

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

• If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
• Otherwise, it becomes vacant.

(Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

Example 1:

Input: cells = [0,1,0,1,1,0,0,1], N = 7Output: [0,0,1,1,0,0,0,0]Explanation: The following table summarizes the state of the prison on each day:Day 0: [0, 1, 0, 1, 1, 0, 0, 1]Day 1: [0, 1, 1, 0, 0, 0, 0, 0]Day 2: [0, 0, 0, 0, 1, 1, 1, 0]Day 3: [0, 1, 1, 0, 0, 1, 0, 0]Day 4: [0, 0, 0, 0, 0, 1, 0, 0]Day 5: [0, 1, 1, 1, 0, 1, 0, 0]Day 6: [0, 0, 1, 0, 1, 1, 0, 0]Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

Example 2:

Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000Output: [0,0,1,1,1,1,1,0]

Note:

1. cells.length == 8
2. cells[i] is in {0, 1}
3. 1 <= N <= 10^9

# Solution: Simulation

Simulate the process, since there must be loops, record the last day when a state occurred.

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

# Problem

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.


Note:

1. 2 <= A.length <= 20000
2. A.length % 2 == 0
3. 0 <= A[i] <= 1000

# Solution 1: Brute Force

Time complexity: O(n)

Space complexity: O(n)

## C++

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

• It is the empty string, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:

Input: "())"
Output: 1


Example 2:

Input: "((("
Output: 3


Example 3:

Input: "()"
Output: 0


Example 4:

Input: "()))(("
Output: 4

Note:

1. S.length <= 1000
2. S only consists of '(' and ')' characters.

# Solution: Counting

Time complexity: O(n)

Space complexity: O(1)

# Problem

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5


Example 2:

Input: 3
Output: False


# Solution: Math

Time complexity: O(sqrt(c))

Space complexity: O(1)

# Problem

https://leetcode.com/problems/unique-binary-search-trees-ii/description/

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

# Idea: Recursion

for i in 1..n: pick i as root,
left subtrees can be generated in the same way for n_l = 1 … i – 1,
right subtrees can be generated in the same way for n_r = i + 1, …, n
def gen(s, e):
return [tree(i, l, r) for l in gen(s, i – 1) for r in gen(i + 1, e) for i in range(s, e+1)

# of trees:

n = 0: 1
n = 1: 1
n = 2: 2
n = 3: 5
n = 4: 14
n = 5: 42
n = 6: 132

Trees(n) = Trees(0)*Trees(n-1) + Trees(1)*Trees(n-2) + … + Tress(n-1)*Trees(0)

Time complexity: O(3^n)

Space complexity: O(3^n)

# Related Problems

Mission News Theme by Compete Themes.