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:
Advertisements

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: