Say you have an array for which the \(i^{th}\) element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice=INT_MAX;
        int maxProfit = 0;
        
        for (int i=0; i<prices.size(); i++) {
            minPrice = min(prices[i], minPrice);
            maxProfit = max(maxProfit, prices[i]-minPrice);
        }
        
        return maxProfit;
    }
};

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        
        sort(nums.begin(),nums.end());
        int result=0;
        for (int i=0; i<nums.size(); i+=2) {
            result+=nums[i];
        }
        return result;
    }
};

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; 
        }
    }
};