一：

题目：

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");

二：

题目：

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
     
       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;            }};