String 1 (Time 1)

Counters

657 Judge Route Circle

Define two counter and loop over each char in the string, if encounter char 'U' increase counter1 by 1, if encounter char 'D' decrease counter 1 by 1. Similarly for 'L', 'R' using counter2. Finally check whether both the two counters are equal to 0.

383 Ransom Note
(1) Loop over all the chars in the magazine and count all the char frequency in the magazine incrementally
(2) Loop over all the chars in the  ransom note and then decrease the char frequency in the ransom note, if eventually all the char frequency still greater or equal than zero, meaning we can construct the ransom note from the magazine, otherwise we cannot.

387 First Unique Character in a String
Define a hashMap (unordered_map in C++)
Loop the string twice, the first loop count the frequency of each char and save the result in the map
The second loop, loop each char from the beginning, once find a char has frequency 1 in the map, return its index. If after the second loop, no char has frequency 1, then return -1.


520.  Detect Capital
(1) for loop the string to count the number of lower case chars using countLower, if counterLower is exactly the string size then it is legal
(2) for loop the string to count the number of upper case chars using countUpper, if counterUpper is exactly the string size then it is legal too
(3)  Otherwise, the only remaining legal word is staring with capital and the other are lower cases
       check the first char of the word if it is not capital, return false. Otherwise, check all the other chars, if they are all not all lower case,  return false. Otherwise, return true.

551	Student Attendance Record I

Solution 1:
(1) Count the frequency of char 'A' in the string
(2) check whether we could find sub string "LLL" in the string
(3) If the frequency of 'A' >= 2 or we could find "LLL" in step 2, then the student couldn't be awarded,  otherwise could be awarded.

Solution 2:
In one loop keep two counters, one track the frequency of char 'A', the other save the size of continuous 'L'  (need reset the second counter if found continuous 'L' size <= 2), in the loop return false if either frequency of 'A' >= 2 or the size of continuous 'L'  >= 3). After the loop if not returned, then that means the student is a good student could be awarded.  (:-D)

stringstream usage

537 Complex Number Multiplication (Y)
Nothing, but how to use stringstream in C++ to split the real part and the image part of a complex number.
 string complexNumberMultiply(string a, string b) {
        int ra, ia, rb, ib;
        char buf;
        stringstream aa(a), bb(b), res;
        aa >> ra >> buf >> ia >> buf;
        bb >> rb >> buf >> ib >> buf;
        res << ra * rb - ia * ib << '+' << ra * ib + rb * ia << 'i';
   
        return res.str();
    }

58	Length of Last Word

Use stringstream to split the word separated by space. Define a last string, keep update it with the current word until the stringstream hit the end of the input string. Return size of the last string.

 
 int lengthOfLastWord(string s) {
        stringstream ss(s);
        string last;
        while (ss >> s)
            last = s;
     
        return last.size();
    }

Reverse

344  Reverse String
Use two pointer to loop from the beginning and the end, keep swap the pairs at from the first pointer and the second pointer until the two pointers meet.

345
Reverse Vowels of a String
Similar with 344 Reverse String,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not.


557 Reverse Words in a String III
(1) Using stringstream to split the string separated with space. O(N) time O(N) space

    string reverseWords(string s) {
        stringstream ss(s);
        string str;
        string res;
        while (ss >> str)
            res += string(str.rbegin(), str.rend()) + ' ';
        res[res.size() - 1] = '\0';
        return res;
    }

(2)  Check space to split the string manually (node the reverse function is left close and right open, so for the last word, we need check i == s.size())

//  O(N) time O(1) space
string reverseWords(string s) {
        int pre = 0;
        for (int i = 0; i <= s.size(); i++) {
            if (' ' == s[i] || i == s.size()) {
                // Note for reverse function, the objects in the range [first,last) are modified.
                reverse(&s[pre], &s[i]);
                pre = i + 1;
            }
        }
        return s

Other:

521.  Longest Uncommon Subsequence I

   return (a == b) ?  -1 : max(a.size(), b.size());

553 Optimal Division (Y)

Using some simple math we can find the easy solution of this problem. Consider the input in the form of [a,b,c,d], now we have to set priority of operations to maximize a/b/c/d. We know that to maximize fraction $p\mathrm{/}q$, $q$(denominator) should be minimized. So, to maximize $a\mathrm{/}b\mathrm{/}c\mathrm{/}d$ we have to first minimize b/c/d. Now our objective turns to minimize the expression b/c/d.

There are two possible combinations of this expression, b/(c/d) and (b/c)/d.

b/(c/d)        (b/c)/d = b/c/d
(b*d)/c        b/(d*c)
d/c            1/(d*c)

Obviously, $d\mathrm{/}c>1\mathrm{/}(d\ast c)$ for $d>1$.

You can see that second combination will always be less than first one for numbers greater than $1$. So, the answer will be a/(b/c/d). Similarly for expression like a/b/c/d/e/f... answer will be a/(b/c/d/e/f...).

606    Construct String from Binary Tree
If t is NULL return "" string
If t is childless node, return to_string(t->val)
Otherwise:
       add the t->val,
       add the left tree string unconditionally
       add the right tree string only when it is not NULL

13  Roman to Integer (N)

 Define a map between the char and its value:

 unordered_map<char, int> map = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
                             {'C', 100}, {'D', 500}, {'M', 1000}};

For loop  each char to calculate the total value represented by the string. If the 

current char value is greater or equal than the next one add it to  the result. Otherwise if 

it is less than the next one, minus it from the result. Return the result after the loop.

20	Valid Parentheses

Define a stack and for loop each char in the input string. case '(', '[', '{'  push on to the stack.

Case ')' ']' '}' check whether the stack is not empty and the top char on the stack matches. If not return false. After the loop, check whether the stack is empty, if it is empty then it is valid, otherwise invalid.



67. Add Binary (N)

      Same with 415  Add Strings, except sum mod  base 2 instead of sum mod base 10 to get the result digit, and divide by base 2 instead of divide by base 10 to get the carry.

14	Longest Common Prefix

Solution 1:

(a) Get the minimum size (minSize) of all the input array.

(b) compare the first minSize char in the first string with all the other string char at the same position. If all equal add to the result. If one of them not mach, return the result.

Worst case Time complexity O(S) = O(M * N), S is the number of total chars in the input array. When we have M equal n-length string, it is the worst case, need maximum # of comparision (S)

Solution 2:

Divide and Conquer. Get the common prefix of the first and half and the second half strings. Recursively do this until there is only exactly one string,  return it.

125	Valid Palindrome

Use two pointers i,j to compare char to char at the beginning and at the end. If encounter non letters and non numerical number (i.e !isalnum(c)) skip it, otherwise convert both char to upper case, if they are not equal, then this is not a valid palindrome, otherwise increase i and decrease j to continue compare next pair of chars. If after the loop, it is still not invalid. That means it is a valid palindrome.

49	Group Anagrams

Hash map O(N * Mlg(M)) time, two itearation, O(N * M) space

Where N is the number of strings, M is the maximum string length

The idea is to use an unordered_map to store those strings that are anagrams. We use the sorted string as the key and the string itself as the value. The strings are stored in a multiset since there may be duplicates. Moreover, multiset will sort them by default as we desire.

If we don't care the sort within the anagram group, we can also define a unordered_map<string, vector<string> > mp;

539	Minimum Time Difference

 Using stringstream object to get the input hours and minutes as integer. Then convert the time into minutes only and save it to an array. Sort the array in increasing order. Get the minimum value for each consecutive time. Don't forget the time diff across a day.

12	Integer to Roman

       Define number to char map using string array for 1,2,...9,  10,20, ...90, 100,200,...900,

       1000,2000,3000 as follows:

       string M[] = {"", "M", "MM", "MMM"};

        string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};

        string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};

        string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

      

        The result Roman denotation will be:

        return M[num / 1000] + C[(num % 1000) / 100] + X[(num % 100) / 10] + I[num % 10];

    }

43	Multiply Strings

Use nested for loop to calculate the multiplication of each digit from the back of both array. For each result digit, it is coming from the remainder of 10 for three parts: (1) the multiplication of the two digits from both array, the carry over from last multiplication for i*(j-1) and the existing result (the high digits) from previous i-1 loop with each j. Sum the three parts together, then sum % 10 will be the new digit, and sum / 10 will be the carry for i * j.  Remember the carry bit should be define and initialized in the outer loop before the inner loop.

8	String to Integer (atoi)

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.