Posts published in “Uncategorized”

花花酱 LeetCode 957. Prison Cells After N Days

By zxi on December 19, 2018

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 = 7
Output: [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 = 1000000000
Output: [0,0,1,1,1,1,1,0]

Note:

cells.length == 8
cells[i] is in {0, 1}
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)

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> prisonAfterNDays(vector<int>& cells, int N) {

vector<int> seen(1 << 8, -1);

auto getKey = [] (const vector<int>& cells) {

int key = 0;

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

key |= cells[i] << i;

return key;

};

while (N > 0) {

const int key = getKey(cells);

if (seen[key] > 0)

N %= seen[key] - N;

seen[key] = N--;

if (N < 0) break;

vector<int> c(8);

for (int i = 1; i < 7; ++i)

c[i] = cells[i - 1] == cells[i + 1];

cells.swap(c);

}

return cells;

}

};

花花酱 LeetCode 922. Sort Array By Parity II

By zxi on October 13, 2018

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:

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

Solution 1: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArrayByParityII(vector<int>& A) {

vector<int> evens;

vector<int> odds;

for (int a : A)

if (a % 2 == 0)

evens.push_back(a);

else

odds.push_back(a);

auto it1 = begin(evens);

auto it2 = begin(odds);

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

A[i] = *it1++;

swap(it1, it2);

}

return A;

}

};

花花酱 LeetCode 921. Minimum Add to Make Parentheses Valid

By zxi on October 13, 2018

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:

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

Solution: Counting

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minAddToMakeValid(string S) {

int l = 0;

int m = 0;

for (char c : S) {

if (c == '(') ++l;

if (c == ')' && l > 0) {

--l;

++m;

}

return S.size() - m * 2;

}

};

花花酱 LeetCode 633. Sum of Square Numbers

By zxi on August 22, 2018

Problem

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a² + b² = 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)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool judgeSquareSum(int c) {

int m = sqrt(c);

for (int a = 0; a <= m; ++a) {

int b = round(sqrt(c - a * a));

if (a * a + b * b == c) return true;

}

return false;

}

};

花花酱 LeetCode 95. Unique Binary Search Trees II

By zxi on March 7, 2018

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.

1 3 3 2 1

\ / / / \ \

3 2 1 1 3 2

/ / \ \

2 1 2 3

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)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<TreeNode*> generateTrees(int n) {

if (n == 0) return {};

const auto& ans = generateTrees(1, n);

cout << ans.size() << endl;

return ans;

}

private:

vector<TreeNode*> generateTrees(int l, int r) {

if (l > r) return { nullptr };

vector<TreeNode*> ans;

for (int i = l; i <= r; ++i)

for (TreeNode* left : generateTrees(l, i - 1))

for (TreeNode* right : generateTrees(i + 1, r)) {

ans.push_back(new TreeNode(i));

ans.back()->left = left;

ans.back()->right = right;

}

return ans;

}

};

Java

// Author: Huahua 4 ms

class Solution {

public List<TreeNode> generateTrees(int n) {

if (n == 0) return new ArrayList<TreeNode>();

return generateTrees(1, n);

}

private List<TreeNode> generateTrees(int l, int r) {

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

if (l > r) {

ans.add(null);

return ans;

}

for (int i = l; i <= r; ++i)

for (TreeNode left : generateTrees(l, i - 1))

for (TreeNode right: generateTrees(i + 1, r)) {

TreeNode root = new TreeNode(i);

root.left = left;

root.right = right;

ans.add(root);

}

return ans;

}

Python 3

"""

Author: Huahua

Running time: 84 ms

"""

class Solution:

def generateTrees(self, n):

def newTree(x, l, r):

t = TreeNode(x)

t.left = l

t.right = r

return t

def gen(s, e):

return [newTree(i, l, r) for i in range(s, e + 1) for l in gen(s, i - 1) for r in gen(i + 1, e)] or [None]

return gen(1, n) if n > 0 else []

Solution 2: DP

Java

// Author: Huahua, 3 ms

class Solution {

public List<TreeNode> generateTrees(int n) {

if (n == 0) return new ArrayList<TreeNode>();

List<TreeNode>[] dp = new List[n + 1];

dp[0] = new ArrayList<TreeNode>();

dp[0].add(null);

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

dp[i] = new ArrayList<TreeNode>();

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

for (TreeNode left : dp[j])

for (TreeNode right: dp[i - j - 1]) {

TreeNode root = new TreeNode(j + 1);

root.left = left;

root.right = clone(right, j + 1);

dp[i].add(root);

}

return dp[n];

}

private TreeNode clone(TreeNode root, int delta) {

if (root == null) return root;

TreeNode node = new TreeNode(root.val + delta);

node.left = clone(root.left, delta);

node.right = clone(root.right, delta);

return node;

}

Posts published in “Uncategorized”

花花酱 LeetCode 957. Prison Cells After N Days

Solution: Simulation

C++

花花酱 LeetCode 922. Sort Array By Parity II

Problem

Solution 1: Brute Force

C++

花花酱 LeetCode 921. Minimum Add to Make Parentheses Valid

Solution: Counting

C++

花花酱 LeetCode 633. Sum of Square Numbers

Problem

Solution: Math

花花酱 LeetCode 95. Unique Binary Search Trees II

Problem

Idea: Recursion

C++

Java

Python 3

Solution 2: DP

Java

Related Problems