Best time to buy and sell stock 2

Problem:

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.

Solution:

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (prices.size() < 2) {
            return 0;
        }
        int minSoFar = prices[0];
        int maxSoFar = prices[0];
        int bestBuy = 0;
        int maxBestBuy = 0;
        int sum = 0;
        int it;
        for(it = 1; it < prices.size(); it++) {
            if (prices[it] >= maxSoFar) {
                maxSoFar = prices[it];
                bestBuy = maxSoFar - minSoFar;
                maxBestBuy = max(bestBuy, maxBestBuy);
            } else {
                sum += maxBestBuy;
                maxBestBuy = 0;
                minSoFar = prices[it];
                maxSoFar = prices[it];
            }
        }
        return sum + maxBestBuy;
    }
};

Add Binary

Problem:

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Solution:


class Solution {
public:
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       string solution;
       int size1 = a.size() - 1, size2 = b.size() - 1;
       char carry;
     
       while (size1 >= 0 && size2 >= 0) {
           if (a[size1] == b[size2] && a[size1] != '0') {
                if (carry != '1') {
                    solution += '0';
                } else {
                    solution += '1';
                }
                carry = '1';
           }
           else if (a[size1] == '1') {
               if (b[size2] == '0')
                    if (carry == '1') {
                        solution += '0';
                        carry = '1';
                    } else {
                        solution += '1';
                    }
           } else {
                    if (carry == '1') {
                        if (b[size2] == '1') {
                            solution += '0';
                            carry = '1';
                        } else {
                            solution += '1';
                            carry = '0';
                        }
                    } else {
                        solution += b[size2];
                    }
           }
           size1--;
           size2--;
       }
       if (size2 >= 0 ) {
            size1 = size2;
            a = b;
       }
       while (size1 >= 0) {
               if (carry == '1') {
                   if (a[size1] == '1') {
                         solution += '0';
                        carry = '1';
                   } else {
                       solution += '1';
                       carry = '0';
                   }
               } else {
                   solution += a[size1];
               }
               size1--;
        }
        if (carry == '1')
            solution += carry;

        if (solution.size() > 1)
            reverse(solution);
     
        return solution;
    }
 
    void reverse(string &s) {
        int end = s.size() - 1, i = 0;
        for (i = 0; i < end;  i++,end--) {
            char temp = s[i];
            s[i] = s[end];
            s[end] = temp;
        }
    }
};

 ======== Second time =====
class Solution {
public:
    char oper(char a, char b, char *carry) {
        char to_ret;
        if (*carry == '1') {
            if (a == '1')
                if (b == '1') {
                    to_ret = '1';
                } else {
                    to_ret = '0';
                }
            else
                if (b == '1') {
                    to_ret = '0';
                } else {
                    to_ret = '1';
                    *carry = '0';
                }
        } else {
            if (a == '1')
                if (b == '1') {
                    to_ret = '0';
                    *carry = '1';
                } else {
                    to_ret = '1';
                }
            else
                if (b == '1') {
                    to_ret = '1';
                } else {
                    to_ret = '0';
                }
        }
        return to_ret;
                
    }
    
    char oper_on_remaining(char a, char *carry) {
        char to_ret;
        if (*carry == '1') {
            if (a == '1')
                to_ret = '0';
            else {
                to_ret = '1';
                *carry = '0';
            }
        } else {
            if (a == '1')
                to_ret = '1';
            else
                to_ret = '0';
        }
        return to_ret;
                
    }
    string addBinary(string a, string b) {
        string bigger;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        
        int size_a = a.size();
        int size_b = b.size();
        
        if (size_a > size_b)
            bigger = a;
        else
            bigger = b;
        
        string sol(bigger);

        char carry = '0';        
        for (int i = 0; i < min(size_a, size_b); i++)
            sol[i] = oper(a[i], b[i], &carry);
        for (int i = min(size_a, size_b); i < max(size_a, size_b); i++)
            sol[i] = oper_on_remaining(bigger[i], &carry);
            
        if (carry == '1')
            sol.push_back(carry);
        reverse(sol.begin(), sol.end());
        return sol;
    }
};


====== Shorter solution ====

string addBinary(string a, string b) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      string result;  
5:      int maxL = a.size() > b.size()? a.size():b.size();  
6:      std::reverse(a.begin(), a.end());  
7:      std::reverse(b.begin(), b.end());  
8:      int carry=0;  
9:      for(int i =0; i<maxL;i++)  
10:      {  
11:        int ai = i<a.size()? a[i]-'0':0;  
12:        int bi = i<b.size()?b[i]-'0':0;  
13:        int val = (ai+bi+carry)%2;  
14:        carry = (ai+bi+carry)/2;  
15:        result.insert(result.begin(), val+'0');  
16:      }  
17:      if(carry ==1)  
18:      {  
19:        result.insert(result.begin(), '1');  
20:      }  
21:      return result;  
22:    }  

=== Third time =====
string addBinary(string a, string b) {
        string ans;
       
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
       
        int carry = 0, sum = 0, i = 0;
        while (i < a.size() || i < b.size()) {
            sum = (i < a.size() ? a[i] - '0': 0) +
                  (i < b.size() ? b[i] - '0': 0) +
                  carry;
            carry = sum / 2;
            ans += to_string(sum % 2);
            i++;
        }
        if (carry == 1) {
            ans += "1";
        }
       
        reverse(ans.begin(), ans.end());
        return ans;
    }

========== Best one ========

class Solution { public: string addBinary(string a, string b) { string str = ""; int i = a.size()-1, j = b.size()-1; int c=0; while(i>=0||j>=0||c==1) { c+=(i>=0)?a[i--]-'0':0; c+=(j>=0)?b[j--]-'0':0; str = char(c%2+'0')+str; c/=2; } return str; } };

Subsets

Problem:

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution:

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > solution;
        int size = S.size();
     
        if (size == 0)
            return solution;

        sort(S.begin(), S.end());
        vector<int> subset;
        solution.push_back(subset);
     
        for (int i = 0; i < size; i++) {
            int subset_count = solution.size();
            for (int sln_idx = 0; sln_idx < subset_count; sln_idx++) {
                subset = solution[sln_idx];
                subset.push_back(S[i]);
                solution.push_back(subset);
            }
        }
        return solution;
    }
};

=============== Alternate (Small one)=======================

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        // Start typing your C/C++ solution below
    sort(S.begin(), S.end());
    vector<vector<int> > v(1);
    for(int i = 0; i < S.size(); ++i) {
        int j = v.size();
        while(j-- > 0) {
            v.push_back(v[j]);
            v.back().push_back(S[i]);
        }
    }
    return v;
    }
};

=================== Alternate (Bitwise) ========================

class Solution {

public:

    vector<vector<int> > subsets(vector<int> &S) {

sort(S.begin(), S.end());

int n = S.size();

vector<vector<int> > result;

for (int i = 0; i < (1 << n); i++) {

vector<int> s;

for (int j = 0; j < n; j++) {

if ((i >> j) & 1) {

s.push_back(S[j]);

}

}

result.push_back(s);

}

return result;

    }

};

============ Another attempt =========

vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > ans;
        ans.push_back(vector<int>());
        
        if (nums.size() == 0) {
            return ans;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                vector<int> tmp = ans[j];
                tmp.push_back(num);
                ans.push_back(tmp);
            }
        }
        
        return ans;
    }

=============================== Another =========

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        ans.push_back(vector<int>());
        
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                vector<int> tmp = ans[j];
                tmp.push_back(num);
                ans.push_back(tmp);
            }
        }
        
        return ans;
    }
};

Longest Palindromic subsequence

Problem:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Solution:

class Solution {
public:
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string max_string , ans_string;
        int size = s.size();
       
        if (size < 2)
            return s;
       
        for (int i = 0; i < size - 1; i++) {
            if (s[i] == s[i+1]) {
                ans_string = palindrom(s, i, i+1);
                if (ans_string.size() > max_string.size())
                    max_string = ans_string;
            }

            if (i != size - 1 && s[i] == s[i+2]) {
                ans_string = palindrom(s, i, i+2);
                if (ans_string.size() > max_string.size())
                    max_string = ans_string;
            }
        }
        return max_string;
    }
   
    string palindrom(string s, int i, int j) {
        string ret_string;
        int size = s.size();
        while (i >= 0 && j < size  && s[i] == s[j]) {
            i--;
            j++;
        }
        for (int iter = i + 1; iter < j; iter++) {
            ret_string += s[iter];
        }
        return ret_string;
    }
};

========= Another attempt ======

class Solution {

public:

    string longestPalindrome(string s) {

        string ans;

        if (s.size() < 2) {

            return s;

        }

        

        for (int i = 0; i < s.size(); i++) {

            // odd length.

            int left = i;

            int right = i;

            while (left >= 0 && right < s.size()) {

                if (s[left] != s[right]) {

                    break;

                }

                left--;

                right++;

            }

            left++;

            right--;

            // length check.

            if (right - left + 1 > ans.size()) {

                ans = s.substr(left, right - left + 1);

            }

            

            // even length.

            left = i;

            right = i + 1;

            while (left >= 0 && right < s.size()) {

                if (s[left] != s[right]) {

                    break;

                }

                left--;

                right++;

            }

            left++;

            right--;

            // length check.

            if (right - left + 1 > ans.size()) {

                ans = s.substr(left, right - left + 1);

            }

        }

        return ans;

    }

};

Reverse Nodes in K Groups

Problem:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Solution:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *cur = head, *prev = NULL, *next, *temp = head;
        int count = k;

        if (head == NULL)
            return NULL;
        while(k > 0 && temp != NULL) {
            temp = temp->next;
            k--;
        }

        if (temp == NULL && k != 0)
            return head;

        k = count;

        while (k > 0 && cur != NULL) {
            next = cur->next;
            if (prev == NULL)
                cur->next = reverseKGroup(temp, count);
            else
                cur->next = prev;
            prev = cur;
            cur = next;
            k--;
        }
        return prev;  
    }
};




============== Another attempt =========
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverse(ListNode *head, int k) {
        if (head == NULL) {
            return head;
        }
        ListNode *prev = NULL, *curr = head, *next = head -> next;
        int count = 0;
        while (curr != NULL && count < k) {
            count++;
            curr -> next = prev;
            prev = curr;
            curr = next;
            if (next != NULL) {
                next = next -> next;
            }
        }
        return prev;
    }
   
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k < 2 || head == NULL) {
            return head;
        }
        ListNode *trav = head, *prev_head = head;
        ListNode *dummy = new ListNode(INT_MIN), *ans = dummy;
        int count = 0;
       
        while (trav != NULL) {
            count++;
            trav = trav -> next;
            if (count == k) {
                dummy -> next = reverse(prev_head, k);
                count = 0;
                prev_head = trav;
                while (dummy -> next != NULL) {
                    dummy = dummy -> next;
                }
            }
        }
        if (count != 0) {
            dummy -> next = prev_head;
        }
        return ans -> next;
    }
};


============= Another recursive one ========
class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode* cur = head; int l=k; while(l--){ if(!cur) return head; cur = cur->next; } ListNode* new_head = reverse(head, cur); head->next = reverseKGroup(cur, k); return new_head; } ListNode* reverse(ListNode* head, ListNode* tail){ ListNode *pre=tail; while(head != tail){ ListNode* t = head->next; head->next = pre; pre = head; head = t; } return pre; } };

permutations

Solution: Recursive:

class Solution {
public:
    //vector<vector<int> > answer;
    vector<vector<int> > permute(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > answer;
        int n = num.size();
        perm(num,n-1, 0,answer);
        return answer;
    }

    void perm(vector<int> &num, int n, int i, vector<vector<int> > &answer) {
        int j;
        if(n==i) {
            answer.push_back(num);
        } else {
            for(j = i; j <= n; j++) {
                swap(num[i], num[j]);
                perm(num,n,i+1, answer);
                swap(num[i], num[j]);
            }
        }
    }

    void swap (int &x, int &y) {
        int temp;
        temp = x;
        x = y;
        y = temp;
    }

};

=========== Second time ============
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > sol;
        vector<int> single_vec;
        if (num.size() == 0)
            return sol;

        permute_helper(num, sol, single_vec, 0);
        return sol;
    }
    
    void permute_helper(vector<int> &num,
                        vector<vector<int> > &sol,
                        vector<int> &single_vec,
                        int index) {
        int size = num.size();
        int single_vec_size = single_vec.size();

        if (index == (size - 1)) {
            single_vec.push_back(num[index]);
            sol.push_back(single_vec);
            return;
        }
        for (int i = index; i < size; i++) {
            swap(num, i, index);
            single_vec.push_back(num[index]);
            permute_helper(num, sol, single_vec, index + 1);
            swap(num, index, i);
            single_vec.erase(single_vec.begin() + index, single_vec.end());
        }
        return;
    }
    
    void swap(vector<int> &num, int id1, int id2) {
        int temp = num[id1];
        num[id1] = num[id2];
        num[id2] = temp;
    }
};
===== Without additional vector =======
class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > sol;
        if (num.size() == 0)
            return sol;

        permute_helper(num, sol, 0);
        return sol;
    }
    
    void permute_helper(vector<int> &num,
                        vector<vector<int> > &sol,
                        int index) {
        int size = num.size();

        if (index == (size - 1)) {
            sol.push_back(num);
            return;
        }
        for (int i = index; i < size; i++) {
            swap(num, i, index);
            permute_helper(num, sol, index + 1);
            swap(num, index, i);
        }
        return;
    }
    
    void swap(vector<int> &num, int id1, int id2) {
        int temp = num[id1];
        num[id1] = num[id2];
        num[id2] = temp;
    }
};

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

Iterative: (small judge)

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > sol;
     
        int size = num.size();
        if (size > 0) {
            sort(num.begin(), num.end());
            sol.push_back(num);
        } else {
            return sol;
        }
        int totalCount = fact(size);
        for (int count = 0; count < totalCount - 1; count++) {
            vector<int> single;
            int justSmallerIndex;
            for (int iter = size - 1; iter > 0; iter--) {
                justSmallerIndex = min(num, iter);
                if (justSmallerIndex != -1) {
                    swap(num[iter], num[justSmallerIndex]);
                    sort(num.begin() + justSmallerIndex + 1, num.end());
                    break;
                }
            }
            for (int i = 0; i < size; i++) {
                single.push_back(num[i]);
            }
            sol.push_back(single);
        }
        return sol;
    }
 
    int min(vector<int> & num, int index) {
        int justSmallerIndex = index - 1;
        int numberToCompared = num[index];
        for (int i = index - 1; i >= 0; i--)
            if (num[i] < numberToCompared)
                return i;
        return -1;
    }

    void swap(int &first, int &second) {
        int temp = first;
        first = second;
        second = temp;
    }
 
    int fact(int num) {
        if (num == 0 || num == 1)
            return 1;
        else
            return num * fact(num - 1);
    }
};

Populate next right pointer - 2

Problem:

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

Solution:

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) {
            return;
        }
        queue<TreeLinkNode *> queueTree;
        TreeLinkNode *popedNode;
     
        queueTree.push(root);
     
        while (!queueTree.empty()) {
            popedNode = queueTree.front();
            queueTree.pop();
         
            if (popedNode->left) {
                popedNode->left->next = popedNode->right != NULL ? popedNode->right :
                    getNextRightNode(popedNode->next);
                queueTree.push(popedNode->left);
            }
            if (popedNode->right) {
                popedNode->right->next = getNextRightNode(popedNode->next);
                queueTree.push(popedNode->right);
            }
        }
        return;
    }
 
    TreeLinkNode * getNextRightNode(TreeLinkNode* node) {
        if (node == NULL) {
            return NULL;
        }

        while (node != NULL) {
            if (node->left != NULL) return node->left;
            if (node->right != NULL) return node->right;
            node = node->next;
        }
        return NULL;
    }
};

================ Another attempt =========
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if (root == NULL) {
            return root;
        }
       
        vector<Node*> curr, future;
        curr.push_back(root);
        curr.push_back(NULL);
       
        Node *prev = NULL;
        int i = 0;
        while (i < curr.size()) {
            if (prev == NULL) {
                prev = curr[i];
            } else {
                prev -> next = curr[i];
                prev = curr[i];
            }
            if (curr[i] != NULL && curr[i] -> left) {
                future.push_back(curr[i] -> left);
            }
            if (curr[i] != NULL && curr[i] -> right) {
                future.push_back(curr[i] -> right);
            }
            if (i == curr.size() - 1  && future.size() != 0) {
                curr = future;
                curr.push_back(NULL);
                future.clear();
                i = -1;
                prev = NULL;
            }
            i++;
        }
        return root;
    }
};

Populating Next Right pointers in each node

Problem:

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set toNULL.

Initially, all next pointers are set to NULL.

Solution:

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) {
            return;
        }
        queue<TreeLinkNode *> queueTree;
        TreeLinkNode *popedNode;
     
        queueTree.push(root);
     
        while (!queueTree.empty()) {
            popedNode = queueTree.front();
            queueTree.pop();
         
            if (popedNode->left) {
                popedNode->left->next = popedNode->right;
                queueTree.push(popedNode->left);
            }
            if (popedNode->right) {
                popedNode->right->next = (popedNode->next == NULL ? NULL : popedNode->next->left);
                queueTree.push(popedNode->right);
            }
        }
        return;
    }
};

==============
class Solution {
    public Node connect(Node root) {
       
        if (root == null) {
            return root;
        }
       
        // Start with the root node. There are no next pointers
        // that need to be set up on the first level
        Node leftmost = root;
       
        // Once we reach the final level, we are done
        while (leftmost.left != null) {
           
            // Iterate the "linked list" starting from the head
            // node and using the next pointers, establish the
            // corresponding links for the next level
            Node head = leftmost;
           
            while (head != null) {
               
                // CONNECTION 1
                head.left.next = head.right;
               
                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
               
                // Progress along the list (nodes on the current level)
                head = head.next;
            }
           
            // Move onto the next level
            leftmost = leftmost.left;
        }
       
        return root;
    }
}

POW

Solution:
Judge Small:

class Solution {
public:
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        double sol = 1;
        while (n > 0) {
            sol *= x;
            n--;
        }
     
        while (n < 0) {
            sol /= x;
            n++;
        }
        return sol;
    }
};



Judge Large:
class Solution {
public:
   double my_pow(double a, int b) {
       // Start typing your C/C++ solution below
       // DO NOT write int main() function
       if(b==0) return 1;
       if(b==1) return a;
       double temp= my_pow(a,b/2);
       temp=temp*temp;
       return ((b%2==0)? temp : temp*a);
   }

double pow(double x, int e) {
       // Start typing your C/C++ solution below
       // DO NOT write int main() function
       if(e>=0) {
           return my_pow(x, e);
       } else {
           return 1/my_pow(x,e);
       }
   }

};

=================== Updated ==========
class Solution {
public:
    double myPow(double x, int n) {
        double ans = 0;
        if (x == 1) {
            return x;
        }
        if (x == -1 && n == INT_MIN) {
            return 1;
        }
        if ((x == 0 && n <= 0) || (n == INT_MIN)) {
            return ans;
        }
        if (n == 1) {
            return x;
        }
        if (n == 0) {
            return 1;
        } else if (n > 0) {
            double partial = myPow(x, n/2);
            ans = partial * partial;
            if ((n % 2) == 1) {
                ans *= x;
            }
            return ans;
        } else {
            return 1/myPow(x, -n);
        }
    }

};