11. 盛最多水的容器

题目:https://leetcode-cn.com/problems/container-with-most-water/

解法一:O(N) 双指针解法

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int i = 0;
        int j = height.size()-1;
        while(i < j){
            int shortHeight = (height[i] > height[j]) ? height[j] : height[i];
            int curMax = shortHeight * (j-i);
            res = (curMax > res) ? curMax : res;
            if(shortHeight==height[i]){
                i++;
            }else j--;
        }
        return res;
    }
};

14.最长公共前缀

题目:https://leetcode-cn.com/problems/longest-common-prefix/

解法一:Trie树

  1. 显然,满足题目条件的节点的孩子个数只有一个t->children.size()==1

    //例如 fla,flb,flc  Trie树如下
    					f
    					|
    					l
    				 /|\\
    				a b c
    //易得节点commonPrefix = "fl"
    
  2. 显然,最长公共前缀不能比最短字符串的长度长,例如["aa","a"]在Trie树中,满足孩子节点个数只有一个的结果可以得到"aa",但显然它并不是最长公共前缀,因为他比"a"长度更长

  3. 如果""存在,则最长公共前缀肯定为""

struct TrieNode{
    char val;
    unordered_map<char,TrieNode*> children;
    TrieNode(char x) : val(x) {};
};
class Trie{
    TrieNode* root;
public:
    Trie(){
        root = new TrieNode('0'); // root node
    }
    void insert(string word){
        TrieNode*p = root;
        for(int i=0;i<word.length();i++){
            if(p->children.find(word[i])==p->children.end()){
                p->children[word[i]] = new TrieNode(word[i]);
            }
            p = p->children[word[i]];
        }
    }
    string findCommonPrefix(int minLength){   // CommonPrefix在Trie树上的体现即只有一个孩子
        TrieNode* p = root;
        string res;
        if(root->children.size()!=1 || minLength==0) return "";
        p = p->children.begin()->second;
        while(p->children.size()==1 && --minLength){
            res.push_back(p->val);
            p = p->children.begin()->second;
        }
        res.push_back(p->val);
        return res;
    }
};
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        Trie t = Trie();
        int minLength = INT_MAX;
        for(string s : strs){
            minLength = minLength < s.length() ? minLength : s.length();
            t.insert(s);
        }
        return t.findCommonPrefix(minLength);     
    }
};

解法二:双指针 - 垂直扫描

  1. 以第一个元素为target,同时遍历其他字符串
  2. i表示字符串的同一个索引,j表示对应第几个字符串
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0) return "";
        for(int i=0;i<strs[0].size();i++){
            for(int j=1;j<strs.size();j++){
                if(strs[j][i]!=strs[0][i]) return strs[0].substr(0,i);
            }
        }
        return strs[0];
    }
};

解法三:只需要比较字典序最小的元素和最大的元素即可

  1. 如果字典序最小为abc,字典序最大为abcdef,则可以肯定的是中间的所有字符串都含有前缀abc