Saturday, February 22, 2014

Rotate Image--Leetcode

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        int n=matrix.size();
        for(int layer=0;layer<n/2;++layer){
            int first=layer;
            int last=n-1-layer;
            for(int i=first;i<last;++i){
                int offset=i-first;
                //drag top unit value to top
                int top=matrix[first][i];
                //left->top
                matrix[first][i]=matrix[last-offset][first];
                //bottom->left
                matrix[last-offset][first]=matrix[last][last-offset];
                //right->bottom
                matrix[last][last-offset]=matrix[i][last];
                //top->right
                matrix[i][last]=top;
            }
        }
    }
};

Set Matrix Zeros--LeetCode

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        int row = matrix.size();
        if (row==0)return;
        int col = matrix[0].size();
        if (col==0)return;
       
        bool fc0=false;
        bool fr0=false;
       
        for (int i=0;i<col;i++){
            if (matrix[0][i]==0){fr0 = true;}
        }
        for (int i=0;i<row;i++){
            if (matrix[i][0]==0){fc0 = true;}
        }
       
        for (int i=1;i<row;i++){
            for (int j=1;j<col;j++){
                if (matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
       
        for (int i=1;i<col;i++){
            if (matrix[0][i]==0){
                for(int j=0;j<row;j++){
                    matrix[j][i]=0;
                }
            }
        }
        for (int i=1;i<row;i++){
            if (matrix[i][0]==0){
                for(int j=0;j<col;j++){
                    matrix[i][j]=0;
                }
            }
        }
       
        if (fr0){
            for (int i=0;i<col;i++){matrix[0][i]=0;}
        }
        if (fc0){
            for (int i=0;i<row;i++){matrix[i][0]=0;}
        }
        return;
    }
};

Wednesday, February 5, 2014

Anagrams--Leetcode

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        vector<string> res;
        unordered_map<string,int> mmp;
       if(strs.size()==0||strs.size()==1)return res;
     
       for(int i=0;i<strs.size();++i){
            string t=strs[i];
            sort(t.begin(),t.end());
            if(!mmp.count(t)){
                mmp[t]=1;
            }
            else{
                ++mmp[t];
            }
        }
       
        for(int i=0;i<strs.size();++i){
            string t=strs[i];
            sort(t.begin(),t.end());
            if(mmp.count(t)&&mmp[t]>1){
                res.push_back(strs[i]);
            }
        }
        return res;
    }
};

Valid Palindrome--Leetcode

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.length()==0)return true;
        else{
            string ss=parser(s);
            int i=0;
            int j=ss.length()-1;
            while(i<=j){
                if(ss[i]==ss[j]||abs(int(ss[i]-ss[j]))==('a'-'A')){
                    ++i;
                    --j;
                }
                else break;
            }
            if(i>j)return true;
            else return false;
        }
    }
    string parser(string s){
        string res;
        for(int i=0;i<s.length();++i){
            if('a'<=s[i]&&s[i]<='z'||'0'<=s[i]&&s[i]<='9'||'A'<=s[i]&&s[i]<='Z'){
                res.append(1,s[i]);
            }
        }
        return res;
    }
};

Palindrome Partitioning I -- Leetcode

class Solution {
public:
    vector<vector<string>> partition(string s) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
     vector<vector<string>> res,subres;
     vector<string> vs;
   
     if(s.length()==0){
         return res;
     }
     if(s.length()==1){
         vs.push_back(s);
         res.push_back(vs);
         return res;
     }

     for(int i=1;i<=s.length();++i){          
        if(ispalindrome(s.substr(0,i))){
            subres=partition(s.substr(i,s.length()-i));
         
            if(subres.size()==0){
                vs.push_back(s.substr(0,i));
                res.push_back(vs);
            }
            else{
                for (int j=0;j<subres.size();++j){
                     subres[j].insert(subres[j].begin(),s.substr(0,i));
                     res.push_back(subres[j]);
                }
            }            
        }          
    }
     return res;    
    }
 
    bool ispalindrome(string s){
       for(int i=0;i<s.length();++i){
        if(i<=s.length()/2){
          if(s[i]!=s[s.length()-i-1])
          return false;
        }
        else break;
       }
       return true;
    }
};

Sunday, February 2, 2014

LRU Cache--Leetcode

class LRUCache{
   
  struct Node{
    int value;
    int key;
    Node* next;
    Node* prev;
    Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){};
    Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){};
};
   int cap;
   unordered_map<int,Node*> mmap;
   Node* head;
   Node* tail;
 
public:
    LRUCache(int capacity) {
        cap = capacity;
        head=NULL;
        tail=NULL;
        mmap.clear();
    }
   
    int get(int key) {
        if(mmap.count(key)){
        DragKeyNode(mmap[key]);
        return mmap[key]->value;
        }
        else return -1;
    }
   
    void set(int key, int value) {
        if(mmap.count(key)){
        mmap[key]->value=value;
        DragKeyNode(mmap[key]);
        }
        else{
            Node *insertp=new Node(key,value);
            mmap.insert(make_pair(key,insertp));
            if(mmap.size()<=cap){
                attach(insertp);
            }
            else{
                detach();
                attach(insertp);
            }
        }
    }
   
    void DragKeyNode(Node* KeyNode){
        if(head==KeyNode){
            return;
        }
        else{
            Node* prev = KeyNode->prev;
            Node* next = KeyNode->next;
            prev->next=next;
            if(!next){
                prev->next=NULL;
                tail=prev;
            }
            else{
                next->prev=prev;
            }
            KeyNode->prev=NULL;
            KeyNode->next=NULL;
        }
        attach(KeyNode);
    }
   
    void attach(Node *p){
        if(!head||!tail){
           head=p;
           tail=p;
        }
        else{
            p->next=head;
            head->prev=p;
            head=p;
        }
    }
   
    void detach(){
        if(!head||!tail)return;
        else{
            int keydelete=tail->key;
            mmap.erase(keydelete);
            Node* p=tail->prev;
            tail->prev=NULL;
            if(p){
            p->next=NULL;
            tail=p;
            }
            else{
                head=NULL;
                tail=NULL;
            }
        }
    }
};