Huahua’s Tech Road

花花酱 LeetCode 224. Basic Calculator

By zxi on March 9, 2020

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

Solution: Recursion

Make a recursive call when there is an open parenthesis and return if there is close parenthesis.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int calculate(string s) {

function<int(int&)> eval = [&](int& pos) {

int ret = 0;

int sign = 1;

int val = 0;

while (pos < s.size()) {

const char ch = s[pos];

if (isdigit(ch)) {

val = val * 10 + (s[pos++] - '0');

} else if (ch == '+' || ch == '-') {

ret += sign * val;

val = 0;

sign = ch == '+' ? 1 : -1;

++pos;

} else if (ch == '(') {

val = eval(++pos);

} else if (ch == ')') {

++pos;

break;

} else {

++pos;

}

return ret += sign * val;

};

int pos = 0;

return eval(pos);

}

};

Python3

# Author: Huahua

class Solution:

def calculate(self, s: str) -> int:

self.pos = 0

def eval():

val = 0

sign = 1

ret = 0

while self.pos < len(s):

ch = s[self.pos]

if ch == ' ':

self.pos += 1

elif ch == '(':

self.pos += 1

val = eval()

elif ch == ')':

self.pos += 1

ret += sign * val

return ret

elif ch == '+' or ch == '-':

ret += sign * val

val = 0

sign = 1 if ch == '+' else -1

self.pos += 1

else:

val = val * 10 + (ord(ch) - ord('0'))

self.pos += 1

ret += val * sign

return ret

return eval()

花花酱 LeetCode 165. Compare Version Numbers

By zxi on March 9, 2020

Compare two version numbers version1 and version2.
If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.

The . character does not represent a decimal point and is used to separate number sequences.

For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.

Example 1:

Input: version1 = "0.1", version2 = "1.1"
Output: -1

Example 2:

Input: version1 = "1.0.1", version2 = "1"
Output: 1

Example 3:

Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1

Example 4:

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both “01” and “001" represent the same number “1”

Example 5:

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to "0"

Note:

Version strings are composed of numeric strings separated by dots . and this numeric strings may have leading zeroes.
Version strings do not start or end with dots, and they will not be two consecutive dots.

Solution: String

Split the version string to a list of numbers, and compare two lists.

Time complexity: O(l1 + l2)
Space complexity: O(l1 + l2)

C++

// Author: Huahua

class Solution {

public:

int compareVersion(string version1, string version2) {

const auto& v1 = parseVersion(version1);

const auto& v2 = parseVersion(version2);

int i1 = 0, i2 = 0;

while (i1 < v1.size() || i2 < v2.size()) {

int n1 = i1 < v1.size() ? v1[i1++] : 0;

int n2 = i2 < v2.size() ? v2[i2++] : 0;

if (n1 < n2) return -1;

else if (n1 > n2) return 1;

}

return 0;

}

private:

vector<int> parseVersion(const string& version) {

vector<int> v;

int s = 0;

for (char c : version) {

if (c == '.') {

v.push_back(s);

s = 0;

} else {

s = s * 10 + (c - '0');

}

v.push_back(s);

return v;

}

};

花花酱 LeetCode 365. Water and Jug Problem

By zxi on March 9, 2020

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous “Die Hard” example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

Solution: Math

special case 1: x == z or y == z or x + y == z: return True
special case 2: x + y < z: return False
normal case: z must be a factor of gcd(x, y)

Time complexity: O(log(min(x, y))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool canMeasureWater(int x, int y, int z) {

if (x == z || y == z || x + y == z) return true;

if (x + y < z) return false;

return z % gcd(x, y) == 0;

}

};

花花酱 LeetCode 258. Add Digits

By zxi on March 9, 2020

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38
Output: 2 
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. 
             Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Solution 1: Simulation

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int addDigits(int num) {

int n = num;

while (n >= 10) {

int t = n;

n = 0;

while (t) {

n += t % 10;

t /= 10;

}

return n;

}

};

Solution 2: Math

https://en.wikipedia.org/wiki/Digital_root#Congruence_formula

Digit root = num % 9 if num % 9 != 0 else min(num, 9) e.g. 0 or 9

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int addDigits(int num) {

return num % 9 ? num % 9 : min(num, 9);

}

};

花花酱 LeetCode 1377. Frog Position After T Seconds

By zxi on March 8, 2020

Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from the vertex 1. In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices it jumps randomly to one of them with the same probability, otherwise, when the frog can not jump to any unvisited vertex it jumps forever on the same vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [from_i, to_i] means that exists an edge connecting directly the vertices from_i and to_i.

Return the probability that after t seconds the frog is on the vertex target.

Example 1:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
Output: 0.16666666666666666 
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and then jumping with 1/2 probability to vertex 4 after second 2. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666.

Example 2:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
Output: 0.3333333333333333
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1.

Example 3:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
Output: 0.16666666666666666

Constraints:

1 <= n <= 100
edges.length == n-1
edges[i].length == 2
1 <= edges[i][0], edges[i][1] <= n
1 <= t <= 50
1 <= target <= n
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: BFS

key: if a node has children, the fog jumps to to children so the probability at current node will become 0.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {

vector<double> p(n + 1);

p[1] = 1.0;

vector<vector<int>> g(n + 1);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<int> seen(n + 1);

seen[1] = 1;

queue<int> q{{1}};

while (t--) {

int size = q.size();

while (size--) {

int cur = q.front(); q.pop();

int children = 0;

for (int nxt : g[cur])

if (!seen[nxt]) ++children;

for (int nxt : g[cur])

if (!seen[nxt]++) {

q.push(nxt);

p[nxt] += p[cur] / children;

}

// key: fog jumps this node has children

if (children > 0) p[cur] = 0.0;

}

return p[target];

}

};

python3

class Solution:

def frogPosition(self, n: int, edges: List[List[int]],

t: int, target: int) -> float:

p = [0] + [1] + [0] * (n - 1)

seen = [False] + [True] + [False] * (n - 1)

q = [1]

g = [[] for _ in range(n + 1)]

for i, j in edges:

g[i].append(j)

g[j].append(i)

for _ in range(t):

q2 = []

for cur in q:

children = sum([not seen[nxt] for nxt in g[cur]])

for nxt in g[cur]:

if seen[nxt]: continue

seen[nxt] = True

q2.append(nxt)

p[nxt] = p[cur] / children

if children > 0: p[cur] = 0

q = q2

return p[target]

Huahua's Tech Road

花花酱 LeetCode 224. Basic Calculator

Solution: Recursion

C++

Python3

花花酱 LeetCode 165. Compare Version Numbers

C++

花花酱 LeetCode 365. Water and Jug Problem

Solution: Math

C++

花花酱 LeetCode 258. Add Digits

Solution 1: Simulation

C++

Solution 2: Math

C++

花花酱 LeetCode 1377. Frog Position After T Seconds

Solution: BFS

C++

python3