Blind 75 LeetCode Questions

Blind 75 LeetCode Questions

1. Array

• Two Sum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int sum=0;
        int i,j;
        vector<int> matches;
        for ( i=0; i< nums.size(); i++ ) {
            sum = nums[i];
            for ( j=0; j< nums.size(); j++ ) {
                if ( j != i){
                    if ( sum + nums[j] == target ) {
                        matches.push_back(i);
                        matches.push_back(j);
                        return matches;
                    }
                }
            }
        }
        return matches;
    }
};    
    

• Best Time to Buy and Sell Stock
• Contains Duplicate
• Product of Array Except Self
• Maximum Subarray
• Maximum Product Subarray
• Find Minimum in Rotated Sorted Array
• Search in Rotated Sorted Array
• 3 Sum
• Container With Most Water

2. Binary

• Sum of Two Integers

int complement(int n){
        n = ~n;
        n++;
        return n;
}

class Solution {
public:
    int getSum(int a, int b) {
        int mask = 1;
        int bits=10;
        int carry=0;
        int sum = 0;
        int complemented=0;
        if ( complement(a) == b )
            return 0;
        if ( a == 0 )
            return b;
        if ( b == 0 )
            return a;
        if ( ( a < 0 ) && ( b < 0 ) ) {
            a = complement(a);
            b = complement(b);
            complemented = 1;
        }
        while (bits > 0){
            cout << (a&mask) << "," << (b&mask) << ":" << mask << "\n";
            if ( (a&mask) && (b&mask) ) {// 1 + 1 + carry
                if ( carry == 1 ){
                    sum = sum | mask;
                } 
                carry =1;
            } else if ( (a&mask) || (b&mask) ) { // 1 + carry
                if ( carry == 0 ){
                    sum = sum | mask;
                    carry =0;
                } else {
                    carry =1;
                }
            }else { // 0 + carry
                if ( carry == 1 ) {
                    sum = (sum & (~mask)) | mask;
                }
                carry = 0;
            }
            bits--;
            mask = mask << 1;
        }
        if ( complemented ) {
            sum = complement(sum);
        }
        return sum;
    }
};  
    

• Number of 1 Bits
• Counting Bits
• Missing Number
• Reverse Bits

3. Dynamic Programming

• Climbing Stairs
The following can't pass because time expired:

#include <iostream>

using namespace std;

int leaf_count=0;

class Tree {
    int count;
    Tree *node_1;
    Tree *node_2;
public:
    Tree(int count) {
        this->count = count;
        this->node_1 = NULL;
        this->node_2 = NULL;
    }
    void insert_node_1(int count) {
        this->node_1 = new Tree(count+1);
    }
    void insert_node_2(int count) {
        this->node_2 = new Tree(count+2);
    }
    void build_tree(int n){
        cout << "current count:" << this->count << " < " << n << endl; 
        if ( this->count < n ) {
            cout << "-1\n"; 
            this->insert_node_1(this->count);
            this->node_1->build_tree(n);
            if ( (this->count +2 ) <= n ) {
                cout << "-2\n"; 
                this->insert_node_2(this->count);
                this->node_2->build_tree(n);
            }
        }else {
            leaf_count++;
            cout << "\tLeaf:" << leaf_count << endl;
        }
    }  
    void get_leaf_count(int n, int *count){
        if ( this->count != n ) {
            if ( this->node_1 )
                this->node_1->get_leaf_count(n, count);
            if ( this->node_2 )
                this->node_2->get_leaf_count(n, count);        
        } else
            *count = *count +1;
    }    
};


class Solution {
public:
    int climbStairs(int n) {
        Tree *root= new Tree(0);
        int count=0;

        root->build_tree(n);
        root->get_leaf_count(n, &count);
        return count;
    }
};
int main(){
    Solution test;

    cout <<  test.climbStairs(35) ; //14930352

    return 0;
}    
    

Analyze the problem by drawing the tree. W can know the answer can be obtained by the previous 2 answers:


    F(n) = F(n-1) + F(n-2)
    

Use the dynamic programing:

#include <iostream>
using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        int i = 0;
        int last_1=0, last_2=0, count=0;
        
        if ( n == 1 )
            return 1;
        else if ( n == 2 )
            return 2;

        last_2 = 1;
        last_1 = 2;
        //return ( climbStairs(n-1) + climbStairs(n-2) );
        for ( i = 2; i<n ; i++) {
            count = last_1 + last_2;
            last_2 = last_1;
            last_1 = count;
        }
        return count;
    }
};

int main(){
    Solution test;
                      //  32 bits Max = 4294967295
    //cout <<  test.climbStairs(35) ; //14930352
    //cout <<  test.climbStairs(44) ; //1134903170
    cout <<  test.climbStairs(45) ;   //1836311903
    return 0;
}    
    

• Coin Change
• Longest Increasing Subsequence
• Longest Common Subsequence
• Word Break Problem
• Combination Sum
• House Robber
• House Robber II
• Decode Ways
• Unique Paths
• Jump Game

4. Graph

• Clone Graph
Deep copy is a process in which the copying process occurs recursively.
It means first constructing a new collection object and then recursively populating it with copies of the child objects found in the original.
In case of deep copy, a copy of object is copied in other object.
It means that any changes made to a copy of object do not reflect in the original object.


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
#include <queue>
#include <iostream>
using namespace std;

class Solution {
public:
    Node* cloneGraph(Node* node) {
        Node *res=nullptr, *current=nullptr, *dup=nullptr, *neighbor=nullptr;
        queue<Node *> q;
        map<int, Node *> graph;
        map<int, bool> visited;
        
        
        if ( node == nullptr ){
            return res;
        }
        q.push(node);
        while ( ! q.empty() ){
            current = q.front();
            q.pop();
            //cout << "Process: " << current->val << endl;
            if ( graph.find(current->val) == graph.end() ){// not exist
                dup = new Node(current->val);
                if ( res == nullptr ){
                    res = dup;
                }
                graph[current->val] = dup;
            } else
                dup = graph[current->val];
            if ( visited[current->val] == true )
                continue;
            visited[current->val] = true;// visited
            // process neighbors
            for ( int i=0; i< current->neighbors.size(); i++ ){
                neighbor = current->neighbors[i];
                if ( graph.find(neighbor->val) == graph.end() ){// not exist
                    //cout << "duplicate neighbor: " << neighbor->val << endl;
                    graph[neighbor->val] = new Node(neighbor->val);
                    visited[neighbor->val] = false;
                }
                if ( visited[neighbor->val] == false ){// not visited
                    //cout << "push neighbor: " << neighbor->val << endl;
                    q.push(neighbor);
                }
                // duplicate relationship
                dup->neighbors.push_back(graph[neighbor->val]);
            }
        }
        
        return res;
    }
};

• Course Schedule
• Pacific Atlantic Water Flow
• Number of Islands
• Longest Consecutive Sequence
• Alien Dictionary (Leetcode Premium)
• Graph Valid Tree (Leetcode Premium)
• Number of Connected Components in an Undirected Graph (Leetcode Premium)

5. Interval

• Insert Interval
• Merge Intervals
• Non-overlapping Intervals
• Meeting Rooms (Leetcode Premium)
• Meeting Rooms II (Leetcode Premium)

6. Linked List

• Reverse a Linked List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
#include <vector>
ListNode *root=NULL;

void reverse(ListNode* parent, ListNode *node) {
    if ( node->next == NULL ) { // last one
        root = node;
        node->next = parent;
        //cout << "\nlast one touched:" << node->val << endl;
    } else {
        //cout << node->val << "->";
        reverse(node, node->next);
        //cout << node->val << "<-";
        node->next = parent;
    }    
    return ;
}

class Solution {
public:
    ListNode* reverseList(ListNode* head) {        
        if ( !head )
            return NULL;
        reverse(NULL, head);
        return root;
    }
};    
    

• Detect Cycle in a Linked List
• Merge Two Sorted Lists
• Merge K Sorted Lists
• Remove Nth Node From End Of List
• Reorder List

7. Matrix

• Set Matrix Zeroes

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        vector<bool> r0, c0;
        int i=0, j=0;
        //cout << matrix.size() << " x " << matrix[0].size() << endl;

        for ( i =0; i < matrix.size(); i++ )
            r0.push_back(0); // reset for each row's flag
        for ( i =0; i < matrix[0].size(); i++ )
            c0.push_back(0); // reset for each column's flag
                
        for (i=0; i < r0.size(); i++) {
            for ( j=0; j < c0.size(); j++) {
                //cout << "Test: " <<i << "," << j << "=" << matrix[i][j] << endl;
                if ( matrix[i][j] == 0 ) {
                    //cout << "Set: " <<i << "," << j << endl;
                    c0[j] = 1;
                    r0[i] = 1;                    
                }
            }
        }
        //cout << "change output\n";
        for (i=0; i < r0.size(); i++) {
            //cout << "i=" << i << "-->" << endl;
            vector<int> &r=matrix[i];
            for ( j=0; j < r.size(); j++) {
                //cout << i << "," << j << endl;
                if ( r0[i] == 1 ) {
                    //cout << "Clear row#" << i << endl;
                    r[j] = 0;
                } else {
                    if ( c0[j] == 1){
                        //cout << "Clear column#" << j << endl;
                        r[j] = 0;
                    }
                }
                //cout << "<--j=" << j << endl;
            }
            //cout << "<--i=" << i << endl;
        }
        return;
    }
};

int main(){
    Solution test;
    vector<vector<int>> matrix;

    int r1[]={0,1};
    vector<int> v1(r1,r1+2);
    matrix.push_back(v1);
#if 0
    int r1[]={0,1,2,0},r2[]={3,4,5,2},r3[]={1,3,1,5};

    vector<int> v1(r1,r1+4);
    vector<int> v2(r2,r2+4);
    vector<int> v3(r3,r3+4);
    
    matrix.push_back(v1);
    matrix.push_back(v2);
    matrix.push_back(v3);
#endif

    test.setZeroes(matrix) ;   //1836311903
    return 0;
}    
    

• Spiral Matrix
• Rotate Image
• Word Search

8. String

• Longest Substring Without Repeating Characters
• Longest Repeating Character Replacement
• Minimum Window Substring
• Valid Anagram
• Group Anagrams
• Valid Parentheses
• Valid Palindrome
• Longest Palindromic Substring
• Palindromic Substrings
• Encode and Decode Strings (Leetcode Premium)

9. Tree

• Maximum Depth of Binary Tree
• Same Tree
• Invert/Flip Binary Tree
• Binary Tree Maximum Path Sum
• Binary Tree Level Order Traversal
• Serialize and Deserialize Binary Tree
• Subtree of Another Tree
• Construct Binary Tree from Preorder and Inorder Traversal
• Validate Binary Search Tree
• Kth Smallest Element in a BST
• Lowest Common Ancestor of BST
• Implement Trie (Prefix Tree)
• Add and Search Word
• Word Search II

10. Heap

• Merge K Sorted Lists
• Top K Frequent Elements
• Find Median from Data Stream

11. Important Link:

14 Patterns to Ace Any Coding Interview Question