mycuteguineapig / leetcode Goto Github PK

/*
kmp的逻辑比如 
   text: a b c d a b x a b c d a b c d a b c y
pattern: a b c d a b c y
                     ^
                     |
                  not match 
check if any suffix is also preffix, 发现 abcdab 中 ab 即是prefix 也是suffix 
就可以不用从头搜寻从 a b 开始, move pattern like this
   text: a b c d a b x a b c d a b c d a b c y
pattern:         a b c d a b c y  then check if x and a are the same

   text: a b c d a b x a b c d a b c d a b c y
pattern:               a b c d a b c y
                                     ^
                                     |
                                not match 
check if any suffix is also preffix, 发现 abc即是prefix 也是suffix , 
no reason to compare abc again move pattern like this
   text: a b c d a b x a b c d a b c d a b c y
pattern:                       a b c d a b c y 


calculate pattern's longgest prefix which is a suffix. lps[i]表示在index i结束 prefix也是suffix最大长度

For the pattern “AAAA”, lps[] is [0, 1, 2, 3]
For the pattern “AABAACAABAA”, lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4] 
For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
For the pattern "aacaabdaacaac: lps is [0, 1, 0, 1, 2, 0, 0, 1, 2, 3, 4, 5, 3]

a a c a a b d a a c a a c -> 到 c, j = 5, 不match, pattern[j]!=pattern[i] => j = prefix[j-1] = prefix[4] = 2 => ve pattern[2] == pattern[i] 
0 1 0 1 2 0 0 1 2 3 4 5  


*/

int kmp(const string &text, const string & pattern){
    vector<int>prefix = computeLps(pattern);
    int j = 0; 
    for(int i = 0; i<text.size(); i++){  //i start from 0
        while(j>0 && pattern[j]!=text[i])
            j = prefix[j-1];
        if(pattern[j] == text[i])
            j++;
        if(j == pattern.size()){
            cout<<" pattern match at index="<<i - j + 1<<endl;
            j = lps[j-1]; //注意j 跳到上lps[j-1]
            /*
            比如  text = a b a b a b a b
             pattern  = a b a b 
                              |  => move j to 2 
                              v
                   pattern  a b a b 
            
            */
        }
    }
}

vector<int>computeLps(const string& pattern){
    vector<int>lps(pattern.size()); //p 记录 longest proper prefix which is also a suffix. 
    //A proper prefix is a prefix with a whole string not allowed. 
    // For example, prefixes of “ABC” are “”, “A”, “AB” and “ABC”. Proper prefixes are “”, “A” and “AB”. Suffixes of the string are “”, “C”, “BC”, and “ABC”.
    int j = 0; //表示最长prefix 也是suffix的index
    for(int i = 1; i<pattern.size(); i++){ // ** i start from 1
        while(j>0 && pattern[j]!= pattern[i]){
            j = lps[j-1];
        }
        if(pattern[j] ==pattern[i])
            j++;
        //else j = 0;
        lps[i] = j;
    }
    return lps;
}

vector<int>computeLps(const string& pattern){
    vector<int>lps(pattern.size()); //p 记录 longest proper prefix which is also a suffix. 
    for(int i = 1; i<pattern.size(); i++){ // ** i start from 1
        while(j>0 && pattern[j]!= pattern[i]){
            j = lps[j-1];
        }
        j = lps[i] = j+ (pattern[j] ==pattern[i]);
    }
    return lps;
}


void kmp2(const string& pattern, const string& text, vector<int>&res){
    string combine = pattern + "@" + text;
    int pattern_size = pattern.size();
    vector<int>lps(combine.size(), 0);
    
    int j = 0; 
    for(int i = 1; i < combine.size(); ++i){
        while(j > 0 && combine[i]!=combine[j])
            j = lps[j-1];
        if (combine[i] == combine[j])
            ++j;
        lps[i] = j;
    }
    for(int i = pattern.size()+1; i<combine.size(); ++i){
        if(lps[i] == pattern.size()){
            cout<<"find match at text index "<< i - 2*pattern_size<<endl;
            res.push_back(i-2*pattern_size);
        }
    }
    return;
}

/*
https://segmentfault.com/a/1190000008484167

manacher 算法：
建一个新的string 开头用$, 结尾用^(为了防止越界), 中间用#
这样可以把偶回文 和 奇回文 都转化成奇数，比如
如此，s 里起初有一个偶回文abba和一个奇回文opxpo，被转换为#a#b#b#a#和#o#p#x#p#o#，长度都转换成了奇数。

p[i] 表示以i为中小心的最长回文半径

i	        0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19  20 
s_new[i]	$	#	a	#	b	#	b	#	a	#	h	#	o	#	p	#	x	#	p	#   ^
p[i]		1	1   2	1	2	5	2	1	2	1	2	1	2	1	2	1	4	1	2	1   
两个int mx，和id, right 代表以 center 为中心的最长回文的右边界，也就是mx = center + p[center]。
mx是在当前回文右侧外的第一个点 mx点不包括在当前回文内


假设我们现在求p[i]，也就是以 i 为中心的最长回文半径，如果i < mx：
if (i < right)  
    p[i] = min(p[2 * center - i], right - i);

2 * center - i为 i 关于 center 的对称点 ( j+i = 2*center)，而p[j]表示以 j 为中心的最长回文半径，
因此我们可以利用p[j]来加快查找。

e.g1 . min(p[2 * center - i], right - i);
比如  c b c d c b z
           -   - | right 
          center     
       p[第一个b] = 3
第二个b的
    p[2 * center - i] =  p [第一个b] = 3， 现在以b 作为中心，右侧没有c，所以 不能等于 3
    right - i = 1   ✅

e.g2. min(p[2 * center - i], right - i);
比如  a b c d c b a d
           -   _   | right 
          center     
还是在 第二个b 点    
p[2 * center - i] =  p [第一个b] = 1，✅
right - i =  2 
*/ 

string manacher(const string& s){
    string s_new;
    init(s, s_new);
    vector<int>p(s_new.size());
    int right = -1, center = -1; 
    int max_len = -1, max_center = -1;
    for(int i = 1; i<s_new.size()-1; ++i){
        if(i < right){
            p[i] = min(p[2*center - i], right - i);
        } else{
            p[i] = 1;
        }
        while(s_new[i + p[i]] == s_new[i-p[i]] )
            ++p[i];
        if (p[i] > right){
            right = p[i];
            center = i;
        }
        if (p[i] > max_len){
            max_len = p[i];
            max_center = i;
        }
    }
    return s.substr((max_center - max_len)/2, max_len - 1);
}

void init(const string& s, string& res){
    res = "$#";
    for(auto c: s){
        res  +=  c;
        res += '#';
    }
    res += "^";
}

//
void helper(TreeNode* root, vector<int>&res){
    if(!root) {return;}
    //res.push_back(root->val); pre order
    helper(root->left, res);
    //res.push_back(root->val); in order
    helper(root->right, res);
    //res.push_back(root->val); post order
    return;
}


//Inorder Traversal
//stack, 
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode *cur = root;
        if(!root) return {};
        vector<int>res;
        stack<TreeNode *>stk;
        while(cur || !stk.empty()){ //cur 比如只有右面的，stack只存之后需要返回的 ； !stk.empty() 是看是不是有接下来返回的node，比如到最左侧node 需要返回
            if(cur){
                //res.push_back(cur->val); pre order, post order
                stk.push(cur);
                cur = cur->left;
            }else{//切换到之前的top
                cur = stk.top(); stk.pop();
                res.push_back(cur->val); // in order;
                cur = cur->right;
            }
        }
        return res;
    }
};

//Postorder: 先right 再left 最后reverse
//postorder 是把tree mirror后的pre order
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int>res;
        TreeNode* cur = root;
        while(cur ||!stk.empty()){
            if(cur){
                res.push_back(cur->val);
                stk.push(cur);
                cur = cur->right;
            }else{
                cur = stk.top(); stk.pop();
                cur = cur->left;
            }
        }
        
        reverse(res.begin(), res.end());
        return res;
    }
};

//Morris: 流程图见,  094. Binary Tree Inorder Traversal.cpp
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        TreeNode* cur = root;
        while(cur){
            if(!cur->left)
            {
                //res.push_back(cur->val); //Inorder, preorder
                cur = cur->right; //cover所有没有left tree的点
            }else{
                TreeNode* pre = cur->left;
                while(pre->right && pre->right!=cur)
                    pre = pre->right;
                if(pre->right){ //表示cur的left 已经全部visit完成，又回到cur了
                    //res.push_back(cur->val); //Inorder
                    pre->right = NULL;  //cover剩下其他的点
                    cur = cur->right;
                }
                else{
                    //res.push_back(cur->val); //Pre-order
                    pre->right = cur;
                    cur = cur->left;
                }
            }
        }
        return res;
    }
};


//PostOrder
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        TreeNode* cur = root;
        while(cur){
            if(!cur->right){
                res.push_back(cur->val);
                cur = cur->left;
            }else{
                TreeNode* pre = cur->right;
                while(pre->left && pre->left != cur)
                    pre = pre->left;
                if(pre->left){
                    pre->left = NULL;
                    cur = cur->left;
                }else{
                    res.push_back(cur->val);
                    pre->left = cur;
                    cur = cur->right;
                }
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};


//如果有right child, 经过root 两次 
//112. Path Sum  https://leetcode.com/problems/path-sum/
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        stack<TreeNode*>stk;
        TreeNode* cur = root, *pre = nullptr;
        while(cur || !stk.empty()){
            if(cur){
                stk.push(cur);
                sum -= cur->val;
                cur = cur->left;       
            }else{
                cur = stk.top();
                if(!cur->right && !cur->left && sum == 0)
                     return true;
                
                if(cur->right && cur->right != pre){
                    cur = cur->right;
                }
                else{
                    pre = cur;
                    sum += cur->val;
                    cur = nullptr;
                    stk.pop();
                }
            }
        }
        return false;
    }
};


//In order traversal, 不同于之前的iterative 解, 这是每个node 都先被push 进stack, 只有return back时候才pop
/*
详见  236. Lowest Common Ancestor of a Binary Tree
https://github.com/beckswu/Leetcode/blob/master/DFS/236.%20Lowest%20Common%20Ancestor%20of%20a%20Binary%20Tree.cpp#L32，
     1
    /
    2 
     \
      3  

最上面的inorder 的 stack 到3时候是  [1，3 
        下面解的stack 是 到3是   [1,2,3]

*/

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //iterative, path comparing
        if(!root ) return root;
        vector<TreeNode*> path;
        if(root)
            path.push_back(root); //temp是stack，元素是从root到现在node上的路径
        TreeNode *prev = nullptr;
        while(!path.empty()){
            root=temp.back();
            if(!root->left && !root->right || !root->right && prev==root->left || root->right && prev==root->right){
                path.pop_back();
                prev=root;
            }
            else{
                if(!root->left || prev==root->left) path.push_back(root->right);
                else path.push_back(root->left);
            }
        }
    }
};


TreeNode* helper(TreeNode** head ){
        int val = *head; //获取值, 比如值是5,
        TreeNode** cur = head; //
        head = &((*head)->left); //不会影响之前cur的值， 把head assign 一个新object, 之前绑定head的地址(cur)的object 并没有删除 
        *head = (*head)->left; //会影响cur的值， *head 取地址, 改变head这个地址绑定的值, 因为cur 和head地址一样 , 所以cur的值也改变
        return cur;
    }

//比如: 
 void helper(int *p){
     int *newp = p;
     *p = 5; //会影响newp的值, 因为newp 和 p地址一样，更改的p的值， newp自动会更改
     p = new int(10); // 不会更改newp 的值, 因为p的地址被换掉了, 之前绑定p的地址并没有删除
 }

/*

array 3 2 -1 6 5 4 -3 3 7 2 3
index 0 1  2 3 4 5  6 7 8 9 10

BIT Tree �Visulation (tree 的index = array index + 1)

                0 (0)
        /      |        |      \
    /       /         \         \           
3 (0,0)  5 (0,1)    10 (0,3)         19 (0,7)     -> 存的是它左侧所有属于同一个parent的leaf 和 
    1         2         4                 8            比如 tree index = 6 存的是 array (4,5) 的点
            |        |     \          |     \
        -1 (2,2)  5(4,4)   9 (4, 5) 7 (8,8)  9 (8, 9)
            3        5       6      9          10        
                                |                 | 
                            -3 (6,6)         3 (10,10)
                                7               11
            

Get Parent (把最右侧的bit remove掉，比如 1010 -> 1000, 111->110)
1) 2's complement (= negate 所有bit + 1)
2) AND it with original number 
3) subtract from original number

Parent(7) 
1) 7 (111) complement + 1 = 000 + 1 = 001 
2) 111 & 001 = 001 
3) 111 - 001 = 110 (6) 

Get Next: 
1) 2's complement  (= negate 所有bit + 1)
2) AND it with original number 
3) Add from original number

Get Next(2) move 到最右侧的bit + 1位，且把后面bit 全部抹掉  0011 -> 0100, 0101 -> 0110, 0110 -> 1000
1) 的 2's complement 0011 的negate 是1100  + 1 = 1101
2) 1100 & 0011 = 1
3） 0011 + 1 = 0100


*/

// 438. Find All Anagrams in a String
//s2: "cbaebabacd"  s1: "abc"
//Output: 0, 6]

//固定windows长度
class Solution {
public:
    vector<int> findAnagrams(string s2, string s1) {
        vector<int>map(26,0);
        for(auto i: s1)
            map[i-'a']++;
        int len = s1.size(), count = s1.size();
        vector<int>res;
        for(int i = 0; i<s2.size();i++){
            if(map[s2[i]-'a']-->0) count--;
            if(count == 0) res.push_back(i-len+1);
            if(i>=len-1){
                if(++map[s2[i-len+1]-'a'] > 0) count++;
            }
        }
        return res;
    }
};

//不固定windows长度, 方法一:

class Solution {
public:
    vector<int> findAnagrams(string s2, string s1) {
        vector<int>map(26,0);
        for(auto i: s1)
            map[i-'a']++;
        int len = s1.size(), left = 0;
        vector<int>res;
        for(int i = 0; i<s2.size();i++){
            map[s2[i]-'a']--;
            if(map[s2[i] - 'a'] <0)
                while( map[s2[i]-'a'] < 0) map[s2[left++]-'a']++;
                /* or

                //correct
                while( map[s2[left] - 'a']++ >= 0 )
                    ++left;
                ++left;

                //wrong: 比如 ab: eabc,  left  会一直停在0(e)
                while( map[s2[left] - 'a'] >= 0 )
                    map[s2[left++]- 'a']++

                */

            if(i-left+1 == len){
                res.push_back(left);
            }
        }
        return res;
    }
};

//不固定windows长度 方法二:

class Solution {
public:
    vector<int> findAnagrams(string s2, string s1) {
        vector<int>map(26,0);
        for(auto i: s1)
            map[i-'a']++;
        int len = s1.size(), left = 0;
        vector<int>res;
        for(int i = 0; i<s2.size();i++){
            map[s2[i]-'a']--;
            if(map[s2[i] - 'a'] <0)
                while(map[s2[left++]-'a']++ >= 0);
            //cout<<i <<" left "<<left<<endl;
            if(i-left+1 == len){
                res.push_back(left);
            }
        }
        return res;
    }
};
/*
"cbaebabacd"
"abc"
DEBUG stdout
0 left 0
1 left 0
2 left 0
3 left 4
4 left 4
5 left 4
6 left 5
7 left 6
8 left 6
9 left 10
*/