Posts published in “Uncategorized”

花花酱 LeetCode 964. Least Operators to Express Number

By zxi on December 28, 2018

Given a single positive integer x, we will write an expression of the form x (op1) x (op2) x (op3) x ... where each operator op1, op2, etc. is either addition, subtraction, multiplication, or division (+, -, *, or /). For example, with x = 3, we might write 3 * 3 / 3 + 3 - 3 which is a value of 3.

When writing such an expression, we adhere to the following conventions:

The division operator (/) returns rational numbers.
There are no parentheses placed anywhere.
We use the usual order of operations: multiplication and division happens before addition and subtraction.
It’s not allowed to use the unary negation operator (-). For example, “x - x” is a valid expression as it only uses subtraction, but “-x + x” is not because it uses negation.

We would like to write an expression with the least number of operators such that the expression equals the given target. Return the least number of operators used.

Example 1:

Input: x = 3, target = 19 
Output: 5 
Explanation: 3 * 3 + 3 * 3 + 3 / 3.  The expression contains 5 operations.

Example 2:

Input: x = 5, target = 501 
Output: 8 
Explanation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.  The expression contains 8 operations.

Example 3:

Input: x = 100, target = 100000000 
Output: 3 
Explanation: 100 * 100 * 100 * 100.  The expression contains 3 operations.

Note:

2 <= x <= 100
1 <= target <= 2 * 10^8

Solution: Dijkstra

Find the shortest path from target to 0 using ops.

Time complexity: O(nlogn)
Space complexity: O(nlogn)
n = x * log(t) / log(x)

C++/set

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

set<pair<int, int>> q; // # x -> number

unordered_set<int> s;

q.emplace(0, target);

while (!q.empty()) {

const auto it = begin(q);

const int c = it->first;

const int t = it->second;

q.erase(it);

if (t == 0) return c - 1;

if (s.count(t)) continue;

s.insert(t);

int n = log(t) / log(x);

int l = t - pow(x, n);

q.emplace(c + (n == 0 ? 2 : n), l);

int r = pow(x, n + 1) - t;

q.emplace(c + n + 1, r);

}

return -1;

}

};

C++/heap

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

unordered_set<int> s;

q.emplace(0, target);

while (!q.empty()) {

const int c = q.top().first;

const int t = q.top().second;

q.pop();

if (t == 0) return c - 1;

if (s.count(t)) continue;

s.insert(t);

int n = log(t) / log(x);

int l = t - pow(x, n);

q.emplace(c + (n == 0 ? 2 : n), l);

int r = pow(x, n + 1) - t;

q.emplace(c + n + 1, r);

}

return -1;

}

};

Solution 2: DFS + Memoization

Time complexity: O(x * log(t)/log(x))
Space complexity: O(x * log(t)/log(x))

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

return dp(x, target);

}

private:

unordered_map<int, int> m_;

int dp(int x, int t) {

if (t == 0) return 0;

if (t < x) return min(2 * t - 1, 2 * (x - t));

if (m_.count(t)) return m_.at(t);

int k = log(t) / log(x);

long p = pow(x, k);

if (t == p) return m_[t] = k - 1;

int ans = dp(x, t - p) + k; // t - p < t

long left = p * x - t;

if (left < t) // only rely on smaller sub-problems

ans = min(ans, dp(x, left) + k + 1);

return m_[t] = ans;

}

};

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

}

};