Number & String

[sync-by-unito[bot]]

FB Questions: //415. Add Strings //273. Integer to English Words //297. Serialize and Deserialize Binary Tree [Hard] //560. Subarray Sum Equals K [Med]

Classic:

#include <algorithm>
#include <sstream>
s.erase(
            std::remove(s.begin(), s.end(), '*') //remove all '*', get the end ptr.
            , s.end()); //trim s, from pend to s.end().

Bit Manipulation:

1. Sum of Two Integers (no '+', '-') (a^b), ((a&b) & 0xFFFFFFFF)<<1 because '0xffffffff' (8 fs) is an unsigned int. Note that 0x0fffffff (7 fs) is an int https://leetcode.com/problems/sum-of-two-integers/discuss/302977/C%2B%2B%3A-the-evil-runtime-error%3A-left-shift-of-negative-value-reason-and-how-to-solve

More bit tricks: https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently

https://www.learncpp.com/cpp-tutorial/converting-between-binary-and-decimal/ http://www.cplusplus.com/doc/boolean/

┆Issue is synchronized with this Trello card by Unito ┆Attachments: https://leetcode.com/problems/sum-of-two-integers/discuss/302977/C%2B%2B%3A-the-evil-runtime-error%3A-left-shift-of-negative-value-reason-and-how-to-solve

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//273. Integer to English Words

class Solution { public: string X[10] = {"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"}; string I[20] = {"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};

string util(unsigned int num){
    string ret;
    if(num < 20)              ret = I[num%20];
    else if(num < 100)        ret = X[num/10] + " " + util(num%10);
    else if(num < 1000)       ret = util(num/100) + " Hundred " + util(num%100);
    else if(num < 1000000)    ret = util(num/1000) + " Thousand " + util(num%1000);
    else if(num < 1000000000) ret = util(num/1000000) + " Million " + util(num%1000000);
    else                      ret = util(num/1000000000) + " Billion " + util(num%1000000000);

    size_t found = ret.find_last_not_of(" \t\f\v\n\r");
    if (found!=std::string::npos)
        ret.erase(found+1);
    else
        ret.clear(); 
    return ret;
}

string numberToWords(unsigned int num){
    if(num == 0) return "Zero";
    return util(num);
}

};// 12 Integer to Roman [Med]

class Solution_q12 { public: std::string intToRoman(int num) { std::string M[4] = { "", "M", "MM", "MMM" }; std::string C[10] = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" }; std::string X[10] = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" }; std::string I[10] = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };

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

};// 13 Roman to integer [Easy]

class Solution_q13 { public: int RomanToInt(std::string s) { if (s.size() <= 0) return 0; std::unordered_map<char, int> table = { { 'I', 1 }, { 'V', 5 }, { 'X', 10 }, { 'L', 50 }, { 'C', 100 }, { 'D', 500 }, { 'M', 1000 } }; int result = 0; for (int i = 0; i < s.size() - 1; ++i) { if (s[i] < s[i + 1]) { result += table[s[i + 1]] - table[s[i]]; ++i; } else { result += table[s[i]]; } } return result + table[s.back()]; } };

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//415. Add Strings

class Solution { public: string addStrings(string num1, string num2) { int n1 = num1.size(), n2 = num2.size(), carry = 0; string res; for(int i=0; i<max(n1, n2); ++i){ // step 1. check if num1 or num2 size is smaller than i, retrieve digit of num1 and num2 int d1 = (i>=n1)? 0 : num1[n1-1-i]-'0'; int d2 = (i>=n2)? 0 : num2[n2-1-i]-'0';

        // step 2. Align digits and sum them together.
        int sum = d1 + d2 + carry;
        res.push_back( (sum%10)+'0');
        carry = sum / 10;
    }
    if(carry == 1) res.push_back('1');
    reverse(res.begin(), res.end());
    return res;
}

};//2. Add Two Numbers

class Solution { public: ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode res = new ListNode(0), *ptr = res; int carry = 0; while(l1 || l2 || carry){ int d1 = l1? l1->val : 0; int d2 = l2? l2->val : 0; int sum = d1 + d2 + carry; carry = sum / 10;

        ListNode* newNode = new ListNode(sum % 10);
        ptr->next = newNode;
        ptr = ptr->next;

        l1 = (l1 ? l1->next : nullptr);
        l2 = (l2 ? l2->next : nullptr);
    }
    return res->next;
}

};//445. Add Two Numbers II

class Solution { public: ListNode addTwoNumbers(ListNode l1, ListNode* l2) { // step 1. align two numbers by using two runner pointers // step 2. put values into two stack (by putting into stack, they align with each other) stack s1, s2; while(l1){ s1.push(l1->val); l1=l1->next; } while(l2){ s2.push(l2->val); l2=l2->next; }

    // step 3. pop stack and add carry if have
    // step 4. transform it to linked list.
    int carry = 0;
    ListNode *res = new ListNode(0);
    while(!s1.empty() || !s2.empty() || carry){
        int sum = carry;
        if(!s1.empty()){ sum += s1.top(); s1.pop(); }
        if(!s2.empty()){ sum += s2.top(); s2.pop(); }
        carry = sum / 10;

        ListNode* tmp = new ListNode(sum % 10);
        tmp->next = res->next;
        res->next = tmp;
    }
    return res->next;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//371. Sum of Two Integers //https://leetcode.com/problems/sum-of-two-integers/solution/ //https://leetcode.com/problems/sum-of-two-integers/discuss/302977/C%2B%2B%3A-the-evil-runtime-error%3A-left-shift-of-negative-value-reason-and-how-to-solve

class Solution { public: long getSum(int a, int b) { while(b != 0){ int sum = (unsigned int)(a ^ b); //sum of a & b without considering carry, and make it 2's complement int carry = (unsigned int)(a & b) << 1; //calculate carry
a = sum; b = carry; } return a < INT_MAX ? a : ~((unsigned int)a); } };

class Solution { public: long getSum(int a, int b) { long mask = 0xFFFFFFFF; //this is for 2's complement, e.g.: conver 1 to -1, // first we invert all bits from 1 to 0XFFFFFFFE, // and then add 1 to make it 0XFFFFFFFF

    while(b != 0){
        int sum = (a ^ b) & mask; //sum of a & b without considering carry, and make it 2's complement
        int carry = ((a & b) & mask) << 1; //calculate carry     
        a = sum;
        b = carry;
    }
    return a < INT_MAX ? a : ~(a ^ mask);
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//560. Subarray Sum Equals K [Med]

class Solution { public: //Crack the coding interview, p274. //https://leetcode.com/problems/subarray-sum-equals-k/discuss/190674/Python-O(n)-Based-on-%22running_sum%22-concept-of-%22Cracking-the-coding-interview%22-book int subarraySum(vector& nums, int k) { int res = 0, running_sum = 0; unordered_map<int, int> map; for(size_t i = 0; i < nums.size(); ++i){ // Step 1. calculate running sum running_sum += nums[i];

        // Step 2. x = running_sum(y) - k(target), find how many time can reach x
        int x = running_sum - k;
        if(map[x]) res += map[x];

        // Step 3. include when we match the target value.
        if(running_sum == k) ++res;

        // Step 4. update the number of running_sum appears
        map[running_sum]++;
    }
    return res;
}

};