Implement atoi which converts a string to an integer

Implement atoi which converts a string to an integer

Example 1:

Input: "42"
Output: 42

Example 2:

Input: "   -42                    "
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

class Solution {
public:
    int myAtoi(string str) {

        str.erase(0, str.find_first_not_of(' '));
        str.erase(str.find_last_not_of(' ')+1);

        int len = str.length();
        long long res = 0;
        bool isnegative = str[0] == '-' ? true : false;
        bool ispositive = str[0] == '+' ? true : false;
        int i;
        if (isnegative || ispositive)
            i = 1;
        else
            i = 0;
        long check = isnegative ? 2147483648 : 2147483647;

        for (; i < len; i++)
        {
            if ((str[i] == ' ') || (str[i] - '0' < 0) || (str[i] - '0' > 9))
                break;
           
            if (((res * 10) < check) && (((res * 10 + str[i] - '0') < check)))
            {
                res =  (res * 10 + str[i] - '0');
            }
            else
            {
                res = (true == isnegative) ? INT_MIN : INT_MAX;
                return res;
            }
        }
       
        if (true == isnegative)
        {
            res = -res;
        }
       
        return res;
    }
};

Best time to buy and sell the stock - Multiple Transaction

Best time to buy and sell the stock : 

Multiple Transaction : 

If you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note:  you must sell the stock before you buy again

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buyIdx     = 0;
        int currProfit = 0;
        int profit     = 0;
        int maxProfit  = 0;
        
        for (int i = 1; i < prices.size(); i++)
        {
            currProfit = prices[i] - prices[buyIdx];
            
            if (currProfit > profit)
            {
                profit = currProfit;
            }
            else 
            {
                buyIdx = i;
                maxProfit += profit;
                profit = 0;
            }
        }
        
        maxProfit += profit;

        return maxProfit;
    }
};

Flip an Image / 2 D matrix

Flip an Image / 2 D matrix

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
        for (int row = 0; row < A.size(); row++)
        {
            int numCol = A[row].size();
            int col;
            for (col = 0; col <  (numCol + 1) / 2; col++)
            {
                int temp = A[row][col] ^ 1;
                A[row][col] = A[row][numCol -1 - col] ^ 1;
                A[row][numCol - 1 - col] = temp;     
            }
        }
        return A;
    }
};

Trigonometric Identities and matrix operations

Rotation matrix :

R = [{cos θ , -sin θ},
         {sinθ , cosθ}]

{X1, Y1} = R x {X0, Y0}
       

Pythagoras theorem:

sin^2 θ + cos^2 θ = 1

1 + cot^2 θ = cosec^2 θ = 1/sin^2θ

tan^2 θ + 1 = sec^2 θ = 1/cos^2θ

Odd and even properties

cos(−x) = cos(x),  sin(−x) = − sin(x),  tan(−x) = − tan(x)

Compound Angle Formula:

cos(A + B) = cos A cos B − sin A sin B
cos(A − B) = cos A cos B + sin A sin B
sin(A + B) = sin A cos B + cos A sin B
sin(A − B) = sin A cos B − cos A sin B
tan(A + B) = (tan A + tan B) / (1 − tan A tan B)
tan(A − B) = (tan A − tan B) / (1 + tan A tan B)

cos 2θ = cos^2 θ − sin^2 θ = 2 cos^2 θ − 1 = 1 − 2 sin^2 θ
 sin 2θ = 2 sin θ cos θ
tan 2θ = 2 tan θ / (1 − tan^2 θ)