leetcode ----Trie/stack专题

清疚 2022-08-05 04:28 127阅读 0赞

一：[Implement Trie (Prefix Tree)][Implement Trie _Prefix Tree]

题目：

Implement a trie with `insert`, `search`, and `startsWith` methods.

Note:  
You may assume that all inputs are consist of lowercase letters `a-z`.

分析：此题是典型的trie树，可以参见：http://blog.csdn.net/lu597203933/article/details/44227431

代码：

class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode() {
            for(int i = 0; i < 26; i++)
                next[i] = NULL;
            isString = false;
        }
        TrieNode *next[26];
        bool isString;
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
            
        }
    
        // Inserts a word into the trie.
        void insert(string s) {
            TrieNode *p = root;
            for(int i = 0; i < s.size(); i++){
                if(p->next[s[i]-'a'] == NULL){
                    p->next[s[i]-'a'] = new TrieNode();
                }
                p = p->next[s[i]-'a'];
            }
            p->isString = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string key) {
            TrieNode *p = root;
            for(int i = 0; i < key.size(); i++){
                if(p == NULL) return false;
                p = p->next[key[i]-'a'];
            }
            if(p == NULL || p->isString == false) return false;
            return true;
            
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode *p = root;
            for(int i = 0; i <= prefix.size(); i++){
                if(p == NULL) return false;
                p = p->next[prefix[i]-'a'];
            }
            return true;
        }
    
    private:
        TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

二：[Basic Calculator][]

题目：

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open `(` and closing parentheses `)`, the plus `+` or minus sign `-`, non-negative integers and empty spaces ``.

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
    " 2-1 + 2 " = 3
    "(1+(4+5+2)-3)+(6+8)" = 23

分析：这道题可以将括号里面的看做是负负得正，这样用sign记录当前数字前面得符号，是+为1，是-为-1，，然后还要它所在的括号深度的符号，用stack来标记。

同时num = num \*10 + c - '0'，， 也给出了正向计算一个字符串比如“12342”的数值方法。。。

class Solution {
    public:
        int calculate(string s) {
    		int sign = 1;         // 当前元素前是+还是-
    		stack<char> st;       // 主要是为了考虑括号的深度， 括号前面是+ 则为1否则为0
    		st.push(1); 
    		int ans = 0;
    		int tmp = 0;
    		for(int i = 0; i < s.size(); i++){
    			char c = s[i];
    			if(isdigit(c)){    // 如果是数字  则保存起来
    				tmp = tmp * 10 + s[i] - '0'; 
    			}
    			else if(c == '-' || c == '+'){  
    				ans += tmp * sign * st.top();   // 由当前符号和括号外面的符号两者决定！
    				sign = (c=='+' ? 1 : -1);
    				tmp = 0;
    			}else if(c == '('){
    				st.push(sign*st.top());   // 当前括号内元素的符号由其前面的各个外层括号符号决定
    				sign = 1;   // 括号后面首个是+
    			}else if(c ==')'){
    				ans += tmp *sign * st.top();
    				st.pop();
    				tmp = 0;
    				sign = 1;
    			}
    		}
    		ans += tmp * sign * st.top();
            return ans;
            
        }
    };

[Implement Trie _Prefix Tree]: https://leetcode.com/problems/implement-trie-prefix-tree/
[Basic Calculator]: https://leetcode.com/problems/basic-calculator/