# 166. Fraction to Recurring Decimal

Difficulty: Medium

Frequency: N/A

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return “0.5”.
• Given numerator = 2, denominator = 1, return “2”.
• Given numerator = 2, denominator = 3, return “0.(6)”.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if (!numerator) return "0";
string result;
if ((numerator > 0) ^ (denominator > 0)) result += '-';
long nu = numerator < 0 ? (long)numerator * (-1) : (long)numerator;
long de = denominator < 0 ? (long)denominator * (-1) : (long)denominator;
result += to_string(nu / de);
if (nu % de == 0) return result;
result += '.';
unordered_map<long, long> myMap;
for (long r = nu % de; r; r = r % de) {
if (myMap.count(r) > 0) {
result.insert(myMap[r], 1, '(');
result += ')';
break;
}
myMap[r] = result.size();
r *= 10;
result += to_string(r / de);
}
return result;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 29. Divide Two Integers

Difficulty: Medium

Frequency: N/A

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
int divide(int dividend, int divisor) {
if (!divisor) return (dividend >= 0) ? INT_MAX : INT_MIN;
if (dividend == INT_MIN && divisor == -1) return INT_MAX;
int sign = ((dividend > 0) ^ (divisor > 0)) ? -1 : 1;
unsigned long dvd = abs((long)dividend);
unsigned long dvs = abs((long)divisor);
int result = 0;
while (dvd >= dvs) {
unsigned long tmp = dvs, multiple = 1;
while (dvd >= tmp << 1) {
tmp <<= 1;
multiple <<= 1;
}
dvd -= tmp;
result += multiple;
}
return sign == 1 ? result : -result;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 149. Max Points on a Line

Difficulty: Hard

Frequency: N/A

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a point.
* struct Point {
*     int x;
*     int y;
*     Point() : x(0), y(0) {}
*     Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point>& points) {
int maxCount = 0;
for (int i = 0; i < points.size(); i++) {
int maxTmp = 0, inf = 0, same = 0;
unordered_map<float, int> myMap;
for (int j = i + 1; j < points.size(); j++) {
if (points[j].x == points[i].x) {
if (points[j].y == points[i].y) same++;
else inf++;
}
float slope = (float) (points[j].y - points[i].y) / (float) (points[j].x - points[i].x);
myMap[slope]++;
maxTmp = max(myMap[slope], maxTmp);
}
maxTmp = max(maxTmp, inf) + same + 1;
maxCount = max(maxCount, maxTmp);
}
return maxCount;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 233. Number of Digit One

Difficulty: Medium

Frequency: N/A

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:

1. Beware of overflow.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
int countDigitOne(int n) {
int count = 0;
for (long m = 1; m <= n; m *= 10) {
int a = n / m, b = n % m;
int remain = a % 10;
if (remain >= 2) {
count += (a / 10 + 1) * m;
} else count += a / 10 * m + (a % 10 == 1) * (b + 1);
}
return count;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 335. Self Crossing

Difficulty: Medium

Frequency: N/A

You are given an array x of `n` positive numbers. You start at point `(0,0)` and moves `x[0]` metres to the north, then `x[1]` metres to the west, `x[2]` metres to the south,`x[3]` metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with `O(1)` extra space to determine, if your path crosses itself, or not.

Example 1:

```Given x = `[2, 1, 1, 2]`,
┌───┐
│   │
└───┼──>
│

Return true (self crossing)
```

Example 2:

```Given x = `[1, 2, 3, 4]`,
┌──────┐
│      │
│
│
└────────────>

Return false (not self crossing)
```

Example 3:

```Given x = `[1, 1, 1, 1]`,
┌───┐
│   │
└───┼>

Return true (self crossing)```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
for (int i = 3; i < x.size(); i++) {
if (x[i] >= x[i - 2] && x[i - 3] >= x[i - 1]) return true;
if (i >= 4) {
if (x[i - 1] == x[i - 3] && x[i] + x[i - 4] >= x[i - 2]) return true;
}
if (i >= 5) {
if (x[i - 1] + x[i - 5] >= x[i - 3] && x[i - 2] >= x[i - 4] && x[i] + x[i - 4] >= x[i - 2] && x[i - 1] <= x[i - 3]) return true;
}
}
return false;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 224. Basic Calculator

Difficulty: Medium

Frequency: N/A

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 .

You may assume that the given expression is always valid.

Some examples:

```"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
```

Note: Do not use the `eval` built-in library function.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
int calculate(string s) {
int result = 0, num = 0, sign = 1;
stack<int> tmp;
for (char c : s) {
if (isdigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '+') {
result = result + sign * num;
num = 0;
sign = 1;
} else if (c == '-') {
result = result + sign * num;
num = 0;
sign = -1;
} else if (c == '(') {
tmp.push(result);
tmp.push(sign);
result = 0;
sign = 1;
} else if (c == ')') {
result = result + sign * num;
result = result * tmp.top();
tmp.pop();
result = result + tmp.top();
tmp.pop();
num = 0;
}
}
result += num * sign;
return result;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 043. Multiply Strings

Difficulty: Medium

Frequency: N/A

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
string multiply(string num1, string num2) {
string result(num1.size() + num2.size(), '0');
for (int i = num1.size() - 1; i >= 0; i--) {
int carry = 0;
for (int j = num2.size() - 1; j >= 0; j--) {
int tmp = result[i + j + 1] - '0' + (num2[j] - '0') * (num1[i] - '0') + carry;
result[i + j + 1] = tmp % 10 + '0';
carry = tmp / 10;
}
result[i] += carry;
}
int trimmed = result.find_first_not_of("0");
if (trimmed != string::npos) return result.substr(trimmed);
return "0";
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: