[leetcode] Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

My Code:

 int sumNumbers(TreeNode *root) {
        if(!root) return 0;
        queue q;
        q.push(root);
        int sum = 0;
        while(!q.empty()){
            TreeNode* cur = q.front();
            if(!cur->left && !cur->right){
                sum = sum + cur->val;
            }
            else{
                if(cur->left){
                    cur->left->val = cur->val*10 + cur->left->val;
                    q.push(cur->left);
                }
                if(cur->right){
                    cur->right->val = cur->val*10 + cur->right->val;
                    q.push(cur->right);
                }
            }
            q.pop();
        }
        return sum;
    }

[leetcode] Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Basic:
Definition of Median:
The median of a finite list of numbers can be found by arranging all the observations from lowest value to highest value and picking the middle one (e.g., the median of {3, 3, 5, 9, 11} is 5). If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values (the median of {3, 5, 7, 9} is (5 + 7) / 2 = 6), which corresponds to interpreting the median as the fully trimmed mid-range. 

Algorithm:
This problems seems to be easy, it can be done by O((n+m)log(m+n)) and O((m+n)). However, when it comes to O(log(m+n)), it becomes difficult. We can do this via "find kth largest in a sorted array" and do this separately on odd and even.
1. For odd, just find (m+n)/2 +1 th number. For eve, find (m+n)/2 th and find (m+n)/2+1 th and get the average of these two.
2. For findkth function, we should keep the smaller one as m always and then then it will balanced to be log(m+n).

My Code:

[leetcode] Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Algorithm:

The difference here is that how to handle when A[mid] == A[right]!

then we can not decide the pivot location when A[mid] == A[right]. My solution is that when this happens, just move right to left until A[mid] != A[right].

There may be better solutions, can update later.

My Code:

bool RS(int A[], int left, int right, int target){
        if(right < left) return false;
        if(left == right) {
            if(A[left] == target) return true;
            else return false;
        }
        int mid = (left+right)/2;
        if(A[mid] == target) return true;
        if(A[mid] == A[right]){
            while(A[mid] == A[right] && right >= 0){
                right--;
            }
            return RS(A, left, right, target);
        }
        else if(A[mid] < A[right]){
            // rotated pivot on the left
            if(target < A[mid]) return RS(A, left, mid-1, target);
            else{
              if(target > A[right]) return RS(A, left, mid-1, target);
              else return RS(A, mid+1, right, target);
            }
        } else {
            //rotated pivot on the right
            if(target > A[mid]) return RS(A, mid+1, right, target);
            else{
              if(target > A[right]) return RS(A, left, mid-1, target);
              else return RS(A, mid+1, right, target);
            }
        }
    }
bool search(int A[], int n, int target) {
        if(n <= 0) return false;
        return RS(A, 0, n-1, target);
}

[leetcode] Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Algorithm:

1. This can be done by bisection recursion method, the time complexity would be O(logn).

2. The key point is to see if the pivot of the rotation is on the left of mid point or right.

3. Pay attention to the termination of recursion, 1) when left == right and 2) when A[mid] == target.

4. When do recursion, should make (left, mid), and (mid+1, right). Otherwise, it will go to an endless recursion loop.

My code:

int RSearch(int A[], int left, int right, int target){
   if(left == right) {
            if(A[left] == target) return left;
            else return -1;
        }
        int mid = (left+right)/2;
        if(target == A[mid]) return mid;
        if(A[mid] < A[right]){
            // rotated pivot on the left
            if(target < A[mid]) return RSearch(A, left, mid, target);
            else{
              if(target > A[right]) return RSearch(A, left, mid, target);
              else return RSearch(A, mid+1, right, target);
            }
        } else {
            //rotated pivot on the right
            if(target > A[mid]) return RSearch(A, mid+1, right, target);
            else{
              if(target > A[right]) return RSearch(A, left, mid, target);
              else return RSearch(A, mid+1, right, target);
            }
        }
    }
    int search(int A[], int n, int target) {
        if(n <= 0) return -1;
        return RSearch(A, 0, n-1, target);
    }

[leetcode] 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].

Algorithm.

This is the same as the previous removeDup one. The difference is that, we need to make 

A[cur] = A[cur] - A[cur - 2].

For the next scan, when meet A[j] != 0, means now A[i] = A[i-2] + A[j] and ++i;

My Code:

int removeDuplicates(int A[], int n) {
        if(n < 3) return n;
        for(int cur = n-1; cur > 1; --cur)
            A[cur] = A[cur] - A[cur - 2];
        int i = 2;
        for(int j = 2; j < n; ++j){
            if(A[j]){
                A[i] = A[i-2] + A[j];
                ++i;
            }
        }
        return i;
    }

[Basic Knowledge] Memset, sizeof, Template

1.  memset:
You should include<string.h> if you want use memset.
void memset(void* ptr, int val, size_t num);
    val: unsigned char conversion.
    num: number of bytes.
So, memset can only be used while setting value to zero.

2. sizeof
Yields the size of its operand with respect to the size of type char.

char - 8 bit
byte - 8 bit
int - 32 bit


3. If you want to declare a template function.

template<class TYPE>
void PrintTwice(TYPE data)
{
    cout<<"Twice: " << data * 2 << endl;
}

template<class T1, class T2, class T3>
T2 DoSomething(const T1 tArray[], T2 tDefaultValue, T3& tResult)
{
   ... 
}
For class:
template<class T>
class Item
{
    T Data;
public:
    Item() : Data( T() )
    {}

    void SetData(T nValue)
    {
        Data = nValue;
    }

    T GetData() const
    {
        return Data;
    }

    void PrintData()
    {
        cout << Data;
    }
};
If you want to use Item: Item<int> intitem;

[leetcode] Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Idea:

If use the native idea, it will cost O(n^2) time and constant space. But will lead to time limit exceed. The code is below:

int removeDuplicates(int A[], int n) {
  if(n < 2) return n;
  int i = 0;
  while(i < n - 1){
    int j = i;
    while(A[j] == A[j+1]){
     j++;
    }
    if(j!=i){
      int s = i+1;
      for(int k = j; k < n; k ++){
        A[s] = A[k];
        s++;
      }
      n = n - (j-i);
    }
    i++;
  }
  return n;
}

============================================================================

Then I changed to another method and it passed the tests: Time complexity is O(n)

1. make each value in the array = current val - previous val;(This part need to be done from the end.)

2. find zeros and change that to valid values.

 int removeDuplicates(int A[], int n) {
       if(n < 2) return n;
       for(int cur = n-1; cur > 0; --cur) 
          A[cur] -= A[cur-1];
       int i = 1;
       for (int j = 1; j < n; ++ j)
        if (A[j]) {
            A[i] = A[i - 1] + A[j];
            ++ i;
        }
       return i;
    }