067. Add Binary

Difficulty: Easy

Frequency: N/A

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".


My solution:
Data structure:
string
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
class Solution {
public:
    string addBinary(string a, string b) {
        string result = "";
        int i = a.size() - 1, j = b.size() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry) {
            int sum = ((i >= 0 ? (a[i] - '0') : 0) + (j >= 0 ? (b[j] - '0') : 0) + carry) % 2;
            carry = ((i >= 0 ? (a[i] - '0') : 0) + (j >= 0 ? (b[j] - '0') : 0) + carry) / 2;
            result = to_string(sum) + result;
            i--;
            j--;
        }
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:
Advertisements

058. Length of Last Word

Difficulty: Easy

Frequency: N/A

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.


 

My solution:

Data structure:
string
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
class Solution {
public:
    int lengthOfLastWord(string s) {
        int length = 0;
        if (s.empty()) return length;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] != ' ') length++;
            else if (length == 0) {
                continue;
            } else break;
        }
        return length;
    }
};

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

Things to learn:

038. Count and Say

Difficulty: Easy

Frequency: N/A

 

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.


My solution:
Data structure:
string
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    string countAndSay(int n) {
        if (n <= 0) return string();
        string result;
        result.push_back('1');
        for (int i = 1; i < n; i++) {
            string tmp;
            int count = 1;
            for (int j = 0; j < result.size(); j++) {
                while (j + 1 < result.size() && result[j + 1] == result[j]) {
                    j++;
                    count++;
                }
                tmp = tmp + char(count + '0') + result[j];
                count = 1;
            }
            result = tmp;
        }
        return result;
    }
};

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

Things to learn:
1. How to convert int to char, char to string, etc.