Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> result;
        vector<int> tmpResult;
        
        int p,q,tmp;
        for(int i = 0 ;i<nums.size();i++)
        {
            if(i!=0&&nums[i]==nums[i-1]) continue;
            int currentNum = nums[i];
            p = i+1;
            q = nums.size()-1;
            
            while(p<q)
            {
                if(p!=i+1&&nums[p]==nums[p-1])
                {
                    p++;
                    continue;
                }
                tmp = nums[q]+nums[p];
                if(tmp==-currentNum)
                {
                    tmpResult.push_back(currentNum);
                    tmpResult.push_back(nums[q]);
                    tmpResult.push_back(nums[p]);
                    result.push_back(tmpResult);
                    tmpResult.clear();
                    p++;
                    q--;
                }else if (tmp>-currentNum)
                {
                    q--;
                }else p++;
            }
        }
        
        return result;
    }
};

two real problems .

• how to find the sum?
  change it to a 2 sum problem. when you have one value, the sum of the other two is -value.
  2 sum problem has a O(n) solution. so the final is O(n^2).

• how to remove the duplicate?
  for same values, we only use the first one and pass the rest.

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

class Solution {
public:
    int arrangeCoins(int n) {
        return floor(-0.5+sqrt((double)2*n+0.25));
    }
};

这道题的主要考虑1+2+3+...+x<=n下，使x左边等式最接近n，并且不超过。

推导为：

-> 1+2+3+...+x = n
-> (1+x)x/2 = n
-> x^2+x = 2n
-> x^2+x+1/4 = 2n +1/4
-> (x+1/2)^2 = 2n +1/4
-> (x+0.5) = sqrt(2n+0.25)
-> x = -0.5 + sqrt(2n+0.25)

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

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

class Solution {
public:
    string addBinary(string a, string b) {
        int fw = 0;
        string result = "";
        for(int i = a.size()-1,j=b.size()-1;i>=0||j>=0;i--,j--){
            int ag = i>=0?a[i]-'0':0;
            int bg = j>=0?b[j]-'0':0;
            int tmp = (ag+bg+fw)%2;
            fw = (ag+bg+fw)/2;
            
            result = char(tmp+'0')+result;
        }
        if(fw==1){
            result = '1'+result;
        }
        
        return result;
    }
};

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0;
        int b = 0;
        while(i<bits.size()){            
            if(bits[i]==1)
            {
                i=i+2;
                b=0;
            }else{
                i++;
                b=1;
            }
        };
        if(b==0){
            return 0;
        }else {
            return 1; 
        }
    }
};

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

class Solution {
public:
    int addDigits(int num) {
        // while(num/10>0){
        //     int sum = 0;
        //     while(num>0){
        //         sum +=num%10;
        //         num /=10;
        //     }
        //     num = sum;
        // }
        return 1+ (num-1)%9;
    }
};

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

class Solution {
public:
    string addStrings(string num1, string num2) {
        int fw = 0;
        string result ="";
        for(int i = num1.size()-1,j = num2.size()-1;i>=0||j>=0;i--,j--){
            int n1 = i>=0 ? num1[i]-'0':0;
            int n2 = j>=0 ? num2[j]-'0':0;
            int tmp = (n1+n2+fw)%10;
            fw = (n1+n2+fw)/10;
            result = char(tmp+'0') + result;
        }
        if(fw){
            result = char(fw +'0')+ result;
        }
        return result;
    }
};