Huahua's Tech Road

花花酱 LeetCode 227. Basic Calculator II

By zxi on March 9, 2020

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

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

Solution: Stack

if operator is ‘+’ or ‘-’, push the current num * sign onto stack.
if operator ‘*’ or ‘/’, pop the last num from stack and * or / by the current num and push it back to stack.

The answer is the sum of numbers on stack.

3+2*2 => {3}, {3,2}, {3, 2*2} = {3, 4} => ans = 7
3 +5/2 => {3}, {3,5}, {3, 5/2} = {3, 2} => ans = 5
1 + 2*3 – 5 => {1}, {1,2}, {1,2*3} = {1,6}, {1, 6, -5} => ans = 2

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

C++

// Author: Huahua

class Solution {

public:

int calculate(string s) {

vector<int> nums;

char op = '+';

int cur = 0;

int pos = 0;

while (pos < s.size()) {

if (s[pos] == ' ') {

++pos;

continue;

}

while (isdigit(s[pos]) && pos < s.size())

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

if (op == '+' || op == '-') {

nums.push_back(cur * (op == '+' ? 1 : -1));

} else if (op == '*') {

nums.back() *= cur;

} else if (op == '/') {

nums.back() /= cur;

}

cur = 0;

op = s[pos++];

}

return accumulate(begin(nums), end(nums), 0);

}

};

python3

# Author: Huahua

class Solution:

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

nums = []

op = '+'

cur = 0

i = 0

while i < len(s):

if s[i] == ' ':

i += 1

continue

while i < len(s) and s[i].isdigit():

cur = cur * 10 + ord(s[i]) - ord('0')

i += 1

if op in '+-':

nums.append(cur * (1 if op == '+' else -1))

elif op == '*':

nums[-1] *= cur

elif op == '/':

sign = -1 if nums[-1] < 0 or cur < 0 else 1

nums[-1] = abs(nums[-1]) // abs(cur) * sign

cur = 0

if (i < len(s)): op = s[i]

i += 1

return sum(nums)

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

}

};

Huahua's Tech Road

花花酱 LeetCode 227. Basic Calculator II

Solution: Stack

C++

python3

Related Problems

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