Day 19, 70,80 Climbing Stairs, Remove Duplicates from Sorted Array II

Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
------------------------------
-- Fibonacci number --
Solution #1 straight forward recursion

class Solution {
public:
    int climbStairs(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 0;   
        }
        return climbStairs(n-1) + climbStairs(n-2);        
    }
};

Solution #2 DP, memoization

class Solution {
public:
    
    int climb (int n,int ma[]) {
        if (n == 0) {
            return 1;
        }
        if (ma[n-1] == -1) {
            ma[n-1] = climb(n-1,ma);
        }
        if (n == 1) {   // eliminate n-2
            return ma[n-1];
        }
        if (ma[n-2] == -1) {
            ma[n-2] == climb(n-2,ma);
        }
        return ma[n-1] + ma[n-2]; 
    }


    int climbStairs(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ma[n+2];
        for (int i=0;i<n+2;i++) {
            ma[i] = -1;
        }
        return climb(n,ma);
    }
};

Solution #3 DP, bottom u (can be optimized to O(1) space by using int a[3])

class Solution {
public:

    int climbStairs(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ma[n+1];
        ma[n] = 1;
        ma[n-1] = 1;
        for (int i=n;i>1;i--) {
            ma[i-2] = ma[i] + ma[i-1];
        }
        return ma[0]; 
    }
};

Remove Duplicates from Sorted Array II 
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].
-----------------
Similar to  Remove Duplicates from Sorted Array
add a flag to track the first duplicate

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n == 0) {
            return 0;
        } 
        bool flag = false;  // duplicates are allowed at most twice
        int start = 0;
        for (int i=1;i<n;i++) {
            if (A[start] == A[i]) {
                if (!flag) {    // found first duplicate
                    start++;
                    A[start] = A[i];
                    flag = true;
                }
            }else {
                start++;
                A[start] = A[i];
                flag = false;
            }
            
        }
        return start + 1;
    }
};

Update on Sep-05-2014
This can handle arbitrary number of dups

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if (n == 0) return n;
        int count = 1;
        int indexOfLastElement = 0;
        
        for (int i = 1; i < n; i++) {
            if (A[indexOfLastElement] == A[i]) {
                if (count < 2) {
                    indexOfLastElement++;    
                    A[indexOfLastElement] = A[i]; // watch out for this line
                    count++;
                }
            }else {
                indexOfLastElement++;
                A[indexOfLastElement] = A[i];
                count = 1;
            }
        }
        
        return indexOfLastElement + 1;
    }
};