Reverse Linked List II

Given a rotated sorted array, recover it to sorted array in-place.

Example

[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

Challenge

In-place, O(1) extra space and O(n) time.

Clarification

What is rotated array:

    - For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

class Solution {
public:
    /**
     * @param head: The head of linked list.
     * @param m: The start position need to reverse.
     * @param n: The end position need to reverse.
     * @return: The new head of partial reversed linked list.
     */
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode dummy(0);
        dummy.next = head;
        int i = 1;
        
        ListNode *p = &dummy;
        
        while(i < m && p) {
            p = p->next; 
            i++;
        }
        
        head = p;
        ListNode *tail = p->next;
        
        while(i < n) {
            ListNode *next = tail->next;
            tail->next = next->next;
            next->next = head->next;
            head->next = next; 
            i++;
        }
    
        return dummy.next;    
    }
};

Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example

For s1 = "aabcc" s2 = "dbbca"

    - When s3 = "aadbbcbcac", return true.

    - When s3 = "aadbbbaccc", return false.

Challenge

O(n^2) time or better

class Solution {
    bool helper(string s1, string s2, string s3)
    {
        if (s1.length() == 0) return s2 == s3;
        if (s2.length() == 0) return s1 == s3;
        
        return (s3[0] == s1[0] && helper(s1.substr(1), s2, s3.substr(1))) ||
                (s3[0] == s2[0] && helper(s1, s2.substr(1), s3.substr(1)));
    }
public:
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true of false.
     */
    bool isInterleave(string s1, string s2, string s3) {
        char map[256] = {0};
        if (s1.length() + s2.length() != s3.length()) return false;
        for(char c: s1) map[c]++;
        for(char c: s2) map[c]++;
        for(char c: s3) {
            map[c]--;
            if (map[c] < 0) return false;
        }
        return helper(s1, s2, s3);
    }
};

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length();
        int n = s2.length();
        int k = s3.length();
        if (k != m + n) return false;
        if (s1.empty()) return s2 == s3;
        if (s2.empty()) return s1 == s3;
        
        vector<vector<bool>> map(m+1, vector<bool>(n+1, false));
        map[0][0] = true;
        
        for(int i =1;i<=m; i++) 
            map[i][0] = s1[i-1]== s3[i-1] && map[i-1][0];
        for(int j =1;j<=n; j++) 
            map[0][j] = s2[j-1]== s3[j-1]&& map[0][j-1];            
            
        
        for (int i = 1; i <= m; i++)
           for (int j = 1; j <= n; j++)
               map[i][j]= (s3[i+j-1]==s1[i-1] && map[i-1][j]) ||(s3[i+j-1]==s2[j-1] && map[i][j-1]);
           
        return map[m][n];
    }
};

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length();
        int n = s2.length();
        int k = s3.length();
        if (k != m + n) return false;
        if (s1.empty()) return s2 == s3;
        if (s2.empty()) return s1 == s3;
        
        vector<bool> map(n+1, false);
   
        map[0] = 1;
        for(int i = 1; i <=n; i++) 
            map[i] = map[i-1] && s2[i-1] == s3[i-1];
        
        for (int i = 1; i <= m; i++) {
           for (int j = 1; j <= n; j++) {
               map[j]= (s3[i+j-1]==s1[i-1] && map[j]) ||(s3[i+j-1]==s2[j-1] && map[j-1]);
           }
        }
           
        return map[n];
    }
};

Product of Array Exclude Itself

Given an integers array A.

Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B without divide operation.

Example

For A=[1, 2, 3], B is [6, 3, 2]

   vector<long long> productExcludeItself(vector<int> &nums) {
        int n = nums.size();
        vector<long long> output1;
        if (n < 2) return output1;
        
        vector<long long> output(n);
        
        long long left =1;
        for(int i = 0; i < n; i++) {
            output[i] = left; 
            left *= nums[i];
        }
        
        long long right = nums[n-1];
        for(int i = n-2; i >=0; i--){ 
            output[i] *= right; 
            right *= nums[i];
        }
        
        return output;
    }

vector<long long> productExcludeItself(vector<int> &nums) {
        int n = nums.size();
        vector<long long> output1;
        if (n < 2) return output1;
        
        vector<long long> output(n, 1);
        
        long long left =1, right = 1;
        for(int i = 0; i < n; i++) {
            output[i] *= left; 
            left *= nums[i];
            
            output[n-1-i] *= right;
            right *= nums[n-1-i];
        }
        
        return output;
    }

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example

Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

class Solution{
public:
    /**
     * @param head: The first node of linked list.
     * @return: head node
     */
    ListNode * deleteDuplicates(ListNode *head) {
        ListNode dummy(0);
        
        dummy.next = head;
        ListNode *p = &dummy;
        
        while(p->next && p->next->next) {
            if (p->next->val == p->next->next->val) {
                int val = p->next->val;
                while(p->next && p->next->val == val) {
                    ListNode *next = p->next->next;
                    delete p->next;
                    p->next = next;
                }
            }
            else
               p = p->next;
        }
        return dummy.next;
    }
};

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.

This matrix has the following properties:

    * Integers in each row are sorted from left to right.

    * Integers in each column are sorted from up to bottom.

    * No duplicate integers in each row or column.

Example

Consider the following matrix:

[

    [1, 3, 5, 7],

    [2, 4, 7, 8],

    [3, 5, 9, 10]

]

Given target = 3, return 2.

Challenge

O(m+n) time and O(1) extra space

class Solution {
public:
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    int searchMatrix(vector<vector<int> > &matrix, int target) {
        int m = matrix.size();
        if (m == 0) return false;
        int n = matrix[0].size();
        if  (n==0) return false;
        int count = 0;
        
        int i = 0, j = n-1;
        while(i < m && j >= 0) {
            if (matrix[i][j] == target) {
                count++;
                i++;j--;
            }
            else if (matrix[i][j] > target)
               j--;
            else 
               i++;
        }
        
        return count;
    }
};

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

    * Integers in each row are sorted from left to right.

    * The first integer of each row is greater than the last integer of the previous row.

Example

Consider the following matrix:

[

    [1, 3, 5, 7],

    [10, 11, 16, 20],

    [23, 30, 34, 50]

]

Given target = 3, return true.

Challenge

O(log(n) + log(m)) time

class Solution {
public:
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int m = matrix.size();
        if (m == 0) return false;
        int n = matrix[0].size();
        if  (n==0) return false;
        
        int i = 0, j = m-1;
        while(i < j) {
            int k = (i + j + 1)/2;
            if (matrix[k][0] == target)  return true;
            if(matrix[k][0] > target) j = k - 1;
            else i = k; 
        }
        
        if (matrix[i][n-1] < target) return false;
        
        int row = i;
        i = 0, j = n-1;
        while(i <= j) {
            int m = (i+j)/2;
            if (matrix[row][m] == target) return true;
            if (matrix[row][m] > target) j = m-1;
            else i = m+1;
        }
        return false;
    }
};

Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

Example

Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

class Solution {
    vector<TreeNode *> generateTrees(int start, int end) {
        vector<TreeNode *> output;
        if (start > end) {
            output.push_back(NULL);
            return output;
        }
        
        for(int i = start; i <=end; i++) {
            vector<TreeNode *> leftSubTrees = generateTrees(start, i-1);
            vector<TreeNode *> rightSubTrees = generateTrees(i+1, end);
            for(TreeNode *left : leftSubTrees)
                for(TreeNode *right : rightSubTrees) {
                     TreeNode *root = new TreeNode(i);
                     root->left = left;
                     root->right = right;
                     output.push_back(root);
                }
             
        }
        return output;
    }
    
public:

    /**
     * @paramn n: An integer
     * @return: A list of root
     */
    vector<TreeNode *> generateTrees(int n) {
        return generateTrees(1, n);
    }
};

class Solution {
    TreeNode * clone(TreeNode *root, int adjust) {
         TreeNode *newRoot = NULL;
         
         if (root) {
             newRoot = new TreeNode(root->val + adjust);
             newRoot->left = clone(root->left, adjust);
             newRoot->right = clone(root->right, adjust);
         }
         
         return newRoot;
    }
    
public:

    /**
     * @paramn n: An integer
     * @return: A list of root
     */
    vector<TreeNode *> generateTrees(int n) {
        vector<vector<TreeNode *>> Gens(n+1);
        Gens[0].push_back(NULL);
        
        for(int i = 1; i <=n; i++) {
            for(int j = 1; j <= i; j++) {
                    for(TreeNode *left : Gens[j-1])
                        for(TreeNode *right : Gens[i-j]) {
                            TreeNode *root = new TreeNode(j);
                            root->left = clone(left, 0);
                            root->right = clone(right, j);
                            Gens[i].push_back(root);
                        }
            }
        }
        
        return Gens[n];
    }
};

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

Example

Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

 
class Solution {
public:
    /**
     * @paramn n: An integer
     * @return: An integer
     */
    int numTrees(int n) {
       if (n < 2) return 1;
       int ret = 0;
       for(int i = 0; i <n; i++)
           ret += numTrees(i)*numTrees(n-i-1);
       return ret;
    }
};



 
class Solution {
public:
    /**
     * @paramn n: An integer
     * @return: An integer
     */
    int numTrees(int n) {
        vector<int> count(n+1, 0);
        count[0] = 1;
        for(int i = 1; i <= n; i++) 
            for(int j = 0; j <i; j++)
                count[i] += count[j]*count[i-j-1]; 
        
        return count[n];
    }
};

Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note

m and n will be at most 100.

Example

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

 
class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */ 
     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
         int m = obstacleGrid.size();
         if (m == 0) return 0;
         int n = obstacleGrid[0].size();
         if (n ==0) return 0;
         vector<vector<int>> map(m, vector<int>(n, 0));
         if (obstacleGrid[m-1][n-1]== 1 || obstacleGrid[0][0]) return 0;
              
         for(int i = m-1; i >=0; i--)
          for(int j = n-1; j >=0; j--) 
              if (i== m-1 && j == n-1) 
                 map[i][j] = 1;
              else if (i == m-1) // special on last row
                 map[i][j] =  (obstacleGrid[i][j] == 1)? 0:map[i][j+1];
              else if (j == n-1) // special on last column
                 map[i][j] =  (obstacleGrid[i][j] == 1)? 0:map[i+1][j];
              else
                 map[i][j] = (obstacleGrid[i][j] == 1)? 0:map[i+1][j]+ map[i][j+1];
        
         return map[0][0];
    }
};

 
class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */ 
     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
         int m = obstacleGrid.size();
         if (m == 0) return 0;
         int n = obstacleGrid[0].size();
         if (n ==0) return 0;
         
         if (obstacleGrid[m-1][n-1]== 1 || obstacleGrid[0][0]) return 0;
         vector<int> map(n, 1);
         
              
         for(int i = m-1; i >=0; i--)
          for(int j = n-1; j >=0; j--) 
              if (i== m-1 && j == n-1) 
                 map[j] = 1;
              else if (i == m-1) // special on last row
                 map[j] =  (obstacleGrid[i][j] == 1)? 0:map[j+1];
              else if (j == n-1) // special on last column
                 map[j] =  (obstacleGrid[i][j] == 1)? 0:map[j];
              else
                 map[j] = (obstacleGrid[i][j] == 1)? 0:map[j]+ map[j+1];
        
         return map[0];
    }
};

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Note

m and n will be at most 100.

Example

1,1	1,2	1,3	1,4	1,5	1,6	1,7
2,1
3,1						3,7

Above is a 3 x 7 grid. How many possible unique paths are there

class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    int uniquePaths(int m, int n) {
        vector<vector<int>> UP(m, vector<int>(n, 1));
        
        for(int i = m-2; i >= 0; i--)
          for(int j = n-2; j >= 0; j--)
              UP[i][j] = UP[i+1][j] + UP[i][j + 1];
        return UP[0][0];
        
    }
};

class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    int uniquePaths(int m, int n) {
        vector<int> UP(n, 1);
        
        for(int i = m-2; i >= 0; i--)
          for(int j = n-2; j >= 0; j--)
              UP[j] = UP[j] + UP[j + 1];
        return UP[0];
        
    }
};

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example

An example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

class Solution {
public:
    
   bool isValidBST(TreeNode *root, TreeNode *&prev)
   {
       if (!root) return true;
       if (!isValidBST(root->left, prev)) return false;
       if (prev && prev->val >= root->val) return false;
       prev = root;
       if (!isValidBST(root->right, prev)) return false;
       return true;
   }
  
   bool isValidBST(TreeNode *root) {
        TreeNode *prev = NULL;
        return isValidBST(root, prev);
   }
};

 
class Solution {
public:
   bool isValidBST(TreeNode *root, long long mn, long long mx)
   {
       if (!root) return true;
       if (root->val <= mn) return false;
       if (root->val >= mx) return false;
       
       return isValidBST(root->left, mn, root->val) &&isValidBST(root->right, root->val, mx);
       
   }
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        return isValidBST(root, (long long)INT_MIN-1, (long long)INT_MAX+1);
    }
};

 
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        stack<TreeNode *> st;
        pushLeft(root, st); 
        
        TreeNode *prev = NULL;
        while(st.size() > 0)
        {
            root = st.top();
            st.pop();
            if (prev && prev->val >= root->val) return false;
            prev = root;
            pushLeft(root->right, st);
        }
        
        return true;
    }
    void pushLeft(TreeNode *root, stack<TreeNode *> &st)
    {
        while(root)
        {
            st.push(root);
            root = root->left;
        }
    }
};

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        stack<TreeNode *> st;
        
        TreeNode *prev = NULL;
        while(!st.empty() || root)
        {
            if (!root)
            {
                root =  st.top();
                st.pop();
                
                if (prev && prev->val >= root->val) return false;
                prev = root;
                root = root->right;
            }
            else {
                st.push(root);
               root = root->left;
            }
        }
        return true;
    }
};

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Example

Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

 
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int> > output;
        if (root == NULL ) return output; 
    
        // Create two stacks to store alternate levels
        stack<TreeNode*> s1;  // For levels to be printed from right to left
        stack<TreeNode*> s2;  // For levels to be printed from left to right
 
        // Push first level to first stack 's1'
        s1.push(root);
        while(!s1.empty() || !s2.empty())
        {
          vector<int> v1, v2;
          while (!s1.empty())
          {
              TreeNode *p = s1.top();
              s1.pop();
              v1.push_back(p->val);
              if (p->left) s2.push(p->left);
              if (p->right) s2.push(p->right);
          }
          while (!s2.empty())
          {
              TreeNode *p = s2.top();
              s2.pop();
              v2.push_back(p->val);
              if (p->right) s1.push(p->right);
              if (p->left) s1.push(p->left);
          }
          if (v1.size()) output.push_back(v1);
          if (v2.size()) output.push_back(v2);
        }
        
        return output;
    }
};

Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

Example

For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

 
class Solution {
public:
     ListNode *reverse( ListNode *list)
     {
          ListNode *prev = NULL;
          while(list) {
               ListNode *tmp = list->next;
               list->next = prev;
               prev = list;
               list = tmp;
          }
          
          return prev;
     } 
     
     void reorderList(ListNode *head) {
        if (!head) return;
        
        ListNode *fast = head;
        ListNode *slow = head;
        
        while(fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        } 
        
        ListNode *second = slow->next;
        slow->next = NULL;
        
        ListNode *reversed = reverse(second);
        
        ListNode dummy(0);
        ListNode *p = &dummy;
        while(head || reversed)
        {
            if (head) {
                p->next = head;
                p = p->next;
                head = head->next;
            }
            if (reversed) {
                p->next = reversed;
                p = p->next;
                reversed = reversed->next;
            }
            
        }
    }
};

 
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: void
     */
    void reorderList(ListNode *head) {
        if (!head) return;
        stack<ListNode *> st;
        
        ListNode *p = head;
        int count = 0;
        while(p) {
            st.push(p);
            p = p->next;
            count++;
        }
        p = head;
        count /= 2;
        while(count >0)
        {
            ListNode *next = p->next;
            p->next = st.top();
            st.pop();
            p->next->next = next;
            p = next;
            count--;
        }
        p->next = NULL;
    }
};

Sort Colors II

Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.

Note

You are not suppose to use the library's sort function for this problem.

Example

GIven colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4]. 

Challenge

A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory.

Can you do it without using extra memory?

 
class Solution{
public:
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */    
    void sortColors2(vector<int> &colors, int k) {
        int n = colors.size();
        sort(colors, 0, n-1, 1, k);
    }
    
    void swap(vector<int> &colors, int i, int j) 
    {
        int t = colors[i];
        colors[i] = colors[j];
        colors[j] = t;
    }
    void sort(vector<int> &colors, int left, int right, int low, int high)
    {
        if (high == low || left >= right) return;
        
        int L = left, R = right;
        
        int mid = (low+high)/2;
        
        while(L <= R){
            while( L <= R && colors[L] <= mid) L++;
            while( L <= R && colors[R] > mid) R--;
            if (L < R) swap(colors, L, R);   
        }
        
        sort(colors, left, R, low, mid);
        sort(colors, R+1, right, mid+1, high);
    }
};

// Credit to http://www.cnblogs.com/yuzhangcmu/p/4177326.html
//inplace，并且O(N)时间复杂度的算法。
// 1. 从左扫描到右边，遇到一个数字，先找到对应的bucket.比如
//    3 2 2 1 4
//    第一个3对应的bucket是index = 2 (bucket从0开始计算）
// 2. Bucket 如果有数字，则把这个数字移动到i的position(就是存放起来），然后把bucket记为-1(表示该位置是一个计数器，计1）。
// 3. Bucket 存的是负数，表示这个bucket已经是计数器，直接减1. 并把color[i] 设置为0 （表示此处已经计算过）
// 4. Bucket 存的是0，与3一样处理，将bucket设置为-1， 并把color[i] 设置为0 （表示此处已经计算过）
// 5. 回到position i，再判断此处是否为0（只要不是为0，就一直重复2-4的步骤）。
// 6.完成1-5的步骤后，从尾部到头部将数组置结果。（从尾至头是为了避免开头的计数器被覆盖）
// 例子(按以上步骤运算)：

//  3 2 2 1 4
//  2 2 -1 1 4
//  2 -1 -1 1 4
//  0 -2 -1 1 4
// -1 -2 -1 0 4
// -1 -2 -1 -1 0

class Solution{
public:
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */    
    void sortColors2(vector<int> &colors, int k) {
        
        for(int i = 0; i < colors.size(); i++){
            if (colors[i] > 0) {
                int pos = colors[i]-1;
                if (colors[pos] <= 0) {
                    colors[pos]--;
                    colors[i] = 0; 
                }
                else {
                    colors[i] = colors[pos];
                    colors[pos] = -1;
                    i--;
                }
            }
        }
        
        int i = colors.size()-1;
        int j = k-1;
        while(j >= 0) {
            while(colors[j] < 0) {
                colors[j] += 1;
                colors[i--] = j+1;
            }
            j--;
        } 
    }
};




Majority Number II

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.

Find it.

Note

There is only one majority number in the array

Example

For [1, 2, 1, 2, 1, 3, 3] return 1

Challenge

O(n) time and O(1) space

 class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: The majority number occurs more than 1/3.
     */
    int majorityNumber(vector<int> nums) {
        int a, b;
        int count1 = 0, count2 = 0;
        
        for(int i = 0; i < nums.size(); i++) {
            if (count1 == 0 || a == nums[i]) {
              a = nums[i];
              count1++;
            }
            else if (count2 == 0 || b == nums[i]) {
                b = nums[i];
                count2++;
            }
            else {
                count1--;
                count2--;
                if (count1 == 0) {
                    a = nums[i];
                    count1 = 1;
                }
                else if(count2 == 0) {
                    b = nums[i];
                    count2 = 1;
                }
            }
        }
        
        // check if which one is the true majority
        count1 = 0, count2 = 0;
        for(int i : nums) {
            if (i ==a) count1++;
            if (i == b) count2++;
        }
        
        return count1 > count2? a : b;
    }
    
};

Backpack II

Given n items with size A[i] and value V[i], and a backpack with size W. What's the maximum value can you put into the backpack?

Note

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to W.

Example

Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

 
class Solution {
public:
 
    /**
     * @param W: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    int backPackII(int W, vector<int> A, vector<int> V) {
    
        /*
         The 0/1 knapsack problem also runs in pseudo-polynomial time.
         Define m[i,w] to be the maximum value that can be attained with
         weight less than or equal to w using items up to i (first i items).
         We can define m[i,w] recursively as follows:
           m[i, w] = m[i-1,w]                       if w less than A[i]
           m[i, w] = max(m[i-1,w],m[i-1,w-w_i]+v_i) if w equal to greater than A[i].
         The solution can then be found by calculating m[n,W]. T 
       */
    
        vector<int> m(W+1, 0);
        for( int i = 0; i < A.size(); i++) 
           for(int j = W; j > 0; j--) {
              if (j >= A[i]) m[j] = max(m[j], m[j-A[i]] + V[i]);
        }
        
        return m[W];
    }
};