lintcode Trie树、二叉树、堆等

前言

第四周刷的是Trie树、二叉树、堆等。

此次参与刷题的共五人（嘟嘟、琼琼、东东、大智、博主）。

正题

442.实现Trie树

关于Trie树，刷的第一道题是 107.单词拆分1。

实现相对比较简单，实现插入、搜索和以什么开头即可。

473.单词的添加与查找

插入和普通的一样，查询的时候带有.的模糊查找，把所有的都找一遍，有一个满足条件的就返回True。

132.单词搜索2

有一个字母矩阵和一个词典。找出同时在词典和矩阵（上下左右）中出现的单词。

方法：

1.先对词典每个词建立Trie树。

2.对矩阵进行搜索，满足条件的放入map中（为了避免重复）

AC代码：

struct TrieTreeNode{
    TrieTreeNode *child[26];
    bool isEnd;
    TrieTreeNode(){
        memset(child,0,sizeof(child));
        isEnd = false;
    }
};

class Solution {
public:
    /*
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //搜索的四个方向
    int m,n;  //board的长和宽
    TrieTreeNode *root = new TrieTreeNode(); //Trie的根结点
    vector<vector<bool> > vis;  //board的访问数组
    map<string,int> mp; //结果的map
    
    void insertTrie(vector<string> &words){
        int w_cnt = words.size(), w_len; //代表word的个数和每个word的长度.
        
        for(int i=0;i<w_cnt;++i){
            w_len = words[i].length();
            TrieTreeNode *p = root; 
            for(int j=0;j<w_len;++j){
                if(p->child[words[i][j]-'a']==NULL)   
                    p->child[words[i][j]-'a'] = new TrieTreeNode();
                p = p->child[words[i][j]-'a'];
            }
            p->isEnd=true;
        }
    }
    
    void dfs(vector<vector<char> > &board, int x, int y, TrieTreeNode *p,string s){
        if(p->isEnd) mp[s]=1;
        int cx,cy;
        for(int i=0;i<4;++i){
            cx=x+dir[i][0],cy=y+dir[i][1];
            if(cx>=0&&cx<m&&cy>=0&&cy<n&&!vis[cx][cy]&&(p->child[board[cx][cy]-'a'])){
                vis[cx][cy] = true;
                string tmp=s;
                tmp.push_back(board[cx][cy]);
                dfs(board,cx,cy,p->child[board[cx][cy]-'a'],tmp);
                vis[cx][cy] = false;
            }
        }
    }
    
    vector<string> wordSearchII(vector<vector<char> > &board, vector<string> &words) {
        // write your code here
        insertTrie(words);
        
        vector<string> res;
        m = board.size();
        if(m==0) return res;
        n = board[0].size();
        
        for(int i=0;i<m;++i)
            vis.push_back(vector<bool>(n,false));
        
        mp.clear();
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                if(root->child[board[i][j]-'a']){
                    vis[i][j]=true;
                    string s;
                    s.push_back(board[i][j]);
                    dfs(board,i,j,root->child[board[i][j]-'a'],s);
                    vis[i][j]=false;
                }
                
        for(map<string,int>::iterator it=mp.begin();it!=mp.end();++it)
            res.push_back(it->first);
        return res;
    }
};

97.二叉树的最大深度

简单DFS。

if(!root) return 0;

return max(maxDepth(root->left),maxDepth(root->right))+1;

175.翻转二叉树

有两种翻转方法。

一种先翻转好下层的，再翻转当前的。（自底向上）

一种是先翻转当前的，再翻转下层的。（自顶向下）

class Solution {
public:
    /*
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    
    //从上往下的做法
    void invertBinaryTree(TreeNode * root) {
        // write your code here
        if(!root) return;
        swap(root->left,root->right);
        invertBinaryTree(root->left);
        invertBinaryTree(root->right);
    }
    /*从下往上的做法
    TreeNode *dfs(TreeNode *p){
        if(!p) return NULL;
        TreeNode *l = dfs(p->left);
        TreeNode *r = dfs(p->right);
        p->left=r;
        p->right=l;
        return p;
    }
    
    void invertBinaryTree(TreeNode * root) {
        // write your code here
        root =  dfs(root);
    }*/
};

469.等价二叉树

简单DFS。

95.验证二叉查找树

中序遍历有序即可。不需要额外的空间。更新最小值（最开始设置为比int最小值还小的值）

88.最近公共祖先

方法是

1.找到两个结点从根来的路径。

2.从路径的尾部找到第一个公共点即可。

AC代码：

class Solution {
public:
    /*
     * @param root: The root of the binary search tree.
     * @param A: A TreeNode in a Binary.
     * @param B: A TreeNode in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    
    vector<TreeNode *> FA,FB,tmp; //记录路径
    bool flag;
    void dfs(TreeNode *p, TreeNode *A, vector<TreeNode *> PA, vector<TreeNode *> &FA){
        if(flag) return; //如果已经找到路径，直接返回
        if(p==A){
            PA.push_back(p);
            FA=PA;
            flag=true;
            return;
        }
        if(p==NULL) return;
        PA.push_back(p);
        dfs(p->left, A, PA, FA);
        dfs(p->right, A, PA, FA);
    }
    
    TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
        // write your code here
        flag=false,tmp.clear();
        dfs(root,A,tmp,FA);
        flag=false,tmp.clear();
        dfs(root,B,tmp,FB);
        
        int lenA=FA.size(),lenB=FB.size();
        lenA = min(lenA,lenB);
        for(int i=lenA-1;i>=0;--i)
            if(FA[i]==FB[i])
                return FA[i];
    }
};

104.合并k个排序链表

我的做法是将队列每个头部元素放入优先队列中，出队一个，则入队一个相应的后继结点。

需要注意的是，我们需要自定义优先队列的判断条件。

第二种解法是进行归并排序！

AC代码：

struct Info{
    ListNode *p;
    Info(ListNode *p){
        this->p = p;
    }
    bool operator <(const Info a) const{
        return a.p->val<p->val;
    }
};

class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here
        priority_queue<Info> q;
        int len = lists.size();
        for(int i=0;i<len;++i)
            if(lists[i]) q.push(Info(lists[i]));
        ListNode *head = new ListNode(0); //带头结点
        ListNode *p = head;
        while(!q.empty()){
            Info t = q.top();
            q.pop();
            if(t.p->next) q.push(Info(t.p->next));
            t.p->next = NULL;
            p->next=t.p;
            p=p->next;
        }
        return head->next;
    }
};

518.超级丑数

第一种做法是使用优先队列（最小堆）。

class Solution {
public:
    /*
     * @param n: a positive integer
     * @param primes: the given prime list
     * @return: the nth super ugly number
     */
    int nthSuperUglyNumber(int n, vector<int> &primes) {
        // write your code here
        priority_queue<long long,vector<long long>,greater<long long>> q;
        q.push(1);
        
        int len = primes.size();
        map<long long,int> mp;  //表示是否访问过
        mp[1]=1;
        while(--n){
            long long cur = q.top();
            q.pop();
            for(int i=0;i<len;++i)
                if(!mp[cur*primes[i]]){
                    mp[cur*primes[i]] = 1;
                    q.push(cur*primes[i]);
                }
        }
        return q.top();
    }
};

第二种方法有点类似动态规划的思想。

1.我们用ugly数组来记录超级丑数。

ugly[0]=1

ugly[i]是第i+1小的超级丑数。

结果只用返回ugly[n-1]即可。

2.ugly[i]肯定是ugly[j]*某个prime(j<i)中最小的一个。

3.我们用index数组记录每个prime对应的ugly下标，如果产生的最小，则下标增加。指针游走。

我们只需要知道每个prime对应的ugly下标，如果是这个产生的，下标+1。

代码如下：

class Solution {
public:
    /*
     * @param n: a positive integer
     * @param primes: the given prime list
     * @return: the nth super ugly number
     */
    int nthSuperUglyNumber(int n, vector<int> &primes) {
        // write your code here
        int m = primes.size();
        vector<int> ugly(n,-1);
        vector<int> index(m,0);
        ugly[0]=1;
        
        for(int i=1;i<n;++i){
            ugly[i]=ugly[index[0]]*primes[0];
            for(int j=1;j<m;++j)
                ugly[i]=min(ugly[i], ugly[index[j]]*primes[j]);
            for(int j=0;j<m;++j)
                if(ugly[i]==ugly[index[j]]*primes[j])
                    index[j]++;
        }
        return ugly[n-1];
    }
};