Min Stack -- leetcode

Question:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Answer:

method 1:
class MinStack {
    stack<int> stk;
    int min = -1;
   
public:
    void push(int x) {
        if(stk.empty()){
            stk.push(0);
            min = x;
        }
        else{
            stk.push(x-min);
            if(x<min){
                min = x;
            }
        }
    }

    void pop() {
        if(!stk.empty()){
            if(stk.top()<0){
                min = min - stk.top();
            }
            stk.pop();
        }
    }

    int top() {
        return stk.top() + min;
    }

    int getMin() {
        return min;
    }
};

Binary Search Tree Iterator -- leetcode

Question:

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Answer:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
    stack<TreeNode*> stk;
    int index;
   
public:
    BSTIterator(TreeNode *root) {
        index = 0;
        TreeNode *p = root;
       
        while(p){
            stk.push(p);
            p = p->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
       return !stk.empty();
    }

    /** @return the next smallest number */
    int next() {
        if(!stk.empty()){
            TreeNode* top = stk.top();
            int res = top->val;
            stk.pop();
            index++;
       
            TreeNode* p = top->right;
            while(p){
                stk.push(p);
                p=p->left;
            }
            return res;
        }
    }
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

Maximum Product Subarray -- leetcode

Question:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Answer:
DP method:

maxp(i) = max(max(maxp(i-1) * A[i], minp(i-1) * A[i] ), A[i]);
minp(i) = min(min(minp(i-1) *A[i], minp(i-1) * A[i]), A[i]);
res = max(maxp(i)) for all i.

class Solution {

public:

    int maxProduct(int A[], int n) {

        int res = A[0];

        int maxp = A[0];

        int minp = A[0];

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

            int tmpmax = maxp;

            int tmpmin = minp;

            maxp = max(max(tmpmax*A[i],tmpmin*A[i]),A[i]);

            minp = min(min(tmpmax*A[i],tmpmin*A[i]),A[i]);

            res = max(maxp,res);

        }

        return res;

    }

};

Word Break II -- leetcode

Question:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

All solutions are:

 ["cats","and","dog"]

["cat","sand","dog"].

Answer:

#include <iostream>

#include <vector>

#include <iostream>

#include <unordered_set>

using namespace std;

void word_break(string str, int idx, unordered_set<string> &set, vector<vector<string>> &res, vector<string> &subres){

    

    int len = str.size();

    

    if(idx == len){             //edge case!

        res.push_back(subres);

    }

    

    for(int i = idx; i < len; ++i){

        

        if(set.count(str.substr(idx,i-idx + 1))){

            subres.push_back(str.substr(idx,i-idx + 1));

            word_break(str, i+1, set, res, subres);

            subres.pop_back();          //backtrack!

            

        }

    }

}

void printV(vector<vector<string>> str){

    for(vector<string> ss:str){

        cout<<"[";

        for(string s: ss){

            cout<<s<<",";

        }

        cout<<"]"<<endl;

    }

    cout<<endl;

};

int main(int argc, const char * argv[]) {

    vector<string> subres;

    vector<vector<string>> res;

    string s= "leetcodecab";

    

    unordered_set<string> set;

    set.insert("leet");

    set.insert("code");

    set.insert("leetcode");

    set.insert("ab");

    set.insert("c");

    

    word_break(s,0,set,res, subres);

    printV(res);

}


--------------------------------------------------------------------------------------------------------------------------

//For original code in leetcode:

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        string subres;
        wordBreakHelp(s,0,dict,subres,res);
        return res;
    }
   
    void wordBreakHelp(string s, int idx, unordered_set<string> &dict, string & subres, vector<string> & res){
        int len = s.size();
   
        if(idx == len){             //edge case!
            res.push_back(subres.substr(0,subres.length()-1));
            return;
        }
   
    for(int i = idx; i < len; ++i){
   
        int sublen = i-idx+1;
        if(dict.count(s.substr(idx,sublen))){
            subres.append(s.substr(idx,sublen));
            subres.append(" ");
           
            wordBreakHelp(s, i+1, dict, subres, res);
           
            subres.pop_back();
            subres.erase(subres.length()-sublen, sublen);          //backtrack!
        }
    }
    return;
    }

};

Longest palindromic substring -- leetcode

Question:
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.
Answer:
//Example:
//s="fgabcdcbaddeee"
//return="abcdcba"

method 1: Brute Force: Time O(n^3), Space:O(n)

class Solution {
public:
    string longestPalindrome(string s) {
     
        int len = s.length();
        int max = 1, startI=0;    //if cannot find a palindrome whose len > 1, then return s[0] for default.
        int flag[len];
     
        for(int i=0;i<len;++i){
            flag[i] = -1;
        }
     
        for(int i=0; i<len; ++i){      //for start index = i

            for(int j=len-1;j>=i+max-1;--j){
             
                if(isPalindrome(s.substr(i,j-i+1))){//find the longest palindromic substring (i,j) for substr starting from i.
                    flag[i] = j;
                    break;
                }
            }
            //have traversed all substr(i,j) for substring whose starting index = i.
            if(flag[i]-i+1 > max){
                max = flag[i]-i+1;
                startI = i;
            }
        }
        return s.substr(startI,flag[startI]-startI+1);
    }
 
    bool isPalindrome(string s){
        int len=s.length();
        for(int i=0;i<len/2;++i){
            if(s[i]!=s[len-i-1]){
                return false;
            }
        }
        return true;
    }
};




method 2: DP : Time O(n^2), Space O(n^2)

DP公式：

dp[i][j] = ( s[i] == s[j] && (dp[i+1][j-1]>0 || j-i <=1) )

             =  1,   if i==j

Code：

string longestPalindrome(string s) {
     
        int len = s.length();
        int maxLen = 1, startI=0;  
                    //if cannot find a palindrome whose len > 1, then return s[0] for default.
        int dp[len][len];

        memset(dp,0,len*len*sizeof(int));
     
        for(int j=0;j<len;++j){         //i<j,右上三角矩阵
         
            for(int i=0; i<j;++i){
             
                if(s[i]==s[j] && (dp[i+1][j-1]>0 || j-i <=1)){       //dp[i][j] >0 ,is palindrome = len(s(i,j))
                    dp[i][j] = j-i+1;
                    if(j-i+1 > maxLen){
                        maxLen = j-i+1;
                        startI = i;
                    }
                }
            }
            dp[j][j] = 1;
        }
        return s.substr(startI, maxLen);
    }

Singleton class -- Java

//http://www.javaworld.com/article/2073352/core-java/simply-singleton.html

public class ClassicSingleton {
    private static ClassicSingleton instance = null;
    protected ClassicSingleton() {
        // Exists only to defeat instantiation.
    }
    public static ClassicSingleton getInstance() {
        if(instance == null) {
            instance = new ClassicSingleton();
        }
        return instance;
    }
}

//synchronize on new;
public static Singleton getInstance() {
    if(singleton == null) {
        synchronized(Singleton.class) {
            singleton = new Singleton();
        }
    }
    return singleton;
}

//double check lock
public static Singleton getInstance() {
    if(singleton == null) {
        synchronized(Singleton.class) {
            if(singleton == null) {
                singleton = new Singleton();
            }
        }
    }
    return singleton;
}

//enum
//http://837062099.iteye.com/blog/1454934
enum Singleton implements Serializable {

    INSTANCE;

    private String name;
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    @Override
        public String toString() {
            return "[" + name + "]";
        }
}

Trie tree -- Java

import java.util.ArrayList;


class Node {
    char c;                         // the character in the node
    boolean isEnd;                  // whether the end of the words
    int count;                      // the number of words sharing this character
    ArrayList<Node> childList;      // the child list
 
 
    public Node(char c){
        this.c = c;
        isEnd = false;
        count = 0;
        childList = new ArrayList<Node>();      
    }
 
    public Node subNode(char character){
        if(childList != null){
            for(Node eachChild : childList){
                if(eachChild.c == character){
                     return eachChild;
                }
            }
        }
        return null;
    }
}



class Trie {
   private Node root;

   public Trie(){
       root = new Node(' ');
   }
   
 
   public void insertWord(String word){
       if(searchWord(word) == true) return;
       
       Node current = root;
       for(int i = 0; i < word.length(); i++){
       
           Node child = current.subNode(word.charAt(i));
         
           if(child != null){
               current = child;           //word[i] char has existed in Trie!
           }
           else {                               //word[i] char not existed in Trie! Need to create a new Node and insert.
                int j=0;
                for(; j< current.childList.size(); ++j){
            if(current.childList.get(j).c > word.charAt(i)){
            break;
            }
            }      
                current.childList.add(j, new Node(word.charAt(i)));
           
                current = current.subNode(word.charAt(i));
           }
           current.count++;
       }
                                                       // Set isEnd to indicate end of the word, important!
       current.isEnd = true;
   }
 
 
 
   public boolean searchWord(String word){
       Node current = root;
       
       for(int i = 0; i < word.length(); i++){    
           if(current.subNode(word.charAt(i)) == null)
               return false;
           else
               current = current.subNode(word.charAt(i));
       }      
                                      //If a string exists, make sure it's a word by checking its 'isEnd' flag !       
       if (current.isEnd == true) return true;
       return false;
   }
   
 
   public void deleteWord(String word){
       if(searchWord(word) == false) return;        
     
       Node current = root;
       for(char c : word.toCharArray()) {
       
           Node child = current.subNode(c);
         
           if(child.count == 1) {
                 current.childList.remove(child);
                 return;
           }
           else {
                 child.count--;
                 current = child;
           }
       }
       current.isEnd = false;
   }

 
   public ArrayList<String> listAllWord(){                                           //DFS
   
    ArrayList<String> res = new ArrayList<String>();
    StringBuilder word = new StringBuilder();
   
    Node current = root;
    listAllWordHelp(current, word, res);
          return res;
   }

   public void listAllWordHelp(Node current, StringBuilder word, ArrayList<String> res){
    Node curr = current;
   
                   //edge case : isEnd : add that word to res.
    if(curr.isEnd){
    String subres = word.toString();
    res.add(subres);
    }
   
    for(Node eachChild : curr.childList){
   
    word.append(eachChild.c);
    curr = eachChild;
                //recursive case!
    listAllWordHelp(curr, word, res);
                //for backtrack usage!
    word.deleteCharAt(word.length()-1);
    }  
        //return case: childList.size() == 0, leaf node!!!
    return;
   }
     
 
   public static void main(String[] args) {
       Trie trie = new Trie();
     
       trie.insertWord("ball");
       trie.insertWord("balls");
       trie.insertWord("sense");
       trie.insertWord("aaa");
       trie.insertWord("aab");
       trie.insertWord("aba");
       trie.insertWord("baa");
       trie.insertWord("bab");    
       trie.insertWord("ccc");
   
     
       System.out.println(trie.searchWord("balls"));
       System.out.println(trie.searchWord("ba"));
       System.out.println(trie.searchWord("sen"));
       trie.deleteWord("balls");
       System.out.println(trie.searchWord("balls"));
       System.out.println(trie.searchWord("ball"));
     
       ArrayList<String> allWord = new ArrayList<String>();
       allWord = trie.listAllWord();
       for(String str : allWord){
        System.out.println(str);
       }    
   }
}