2019-02-11 第八天（#14, #58, #387）

上周无论是身体还是精神状态都不佳，加之事情很多，中断了一整周的刷题，这周不能这样啦！

#14 Longest Common Prefix

题目地址：https://leetcode.com/problems/longest-common-prefix/

初见 (垂直扫描，O(S)复杂度）

说实在话初见做的一塌糊涂，踩了一堆坑，最后的代码也难看得很。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty()) return string("");
        int shortest_length = INT_MAX;
        for(auto it = strs.begin(); it != strs.end(); it++){
            if(it->length() < shortest_length)
                shortest_length = it->length();
        }
        int longest_prefix = -1;
        for(int str_i = 0; str_i < shortest_length; str_i++){
            for(int vec_i = 0; vec_i < strs.size(); vec_i++){
                if(strs.at(vec_i).at(str_i) != strs.at(0).at(str_i)){
                    longest_prefix = str_i-1;
                    string ret_str (string(strs.begin()->begin(), strs.begin()->begin()+longest_prefix+1));
                    return ret_str;
                    
                }
                longest_prefix = str_i;
                
            }
        }
        
        
       string ret_str (string(strs.begin()->begin(), strs.begin()->begin()+longest_prefix+1));
       return ret_str; 
    }
};

#58 Length of Last Word

题目地址：https://leetcode.com/problems/length-of-last-word/

初见（Python）

这题明摆着就是要我用Python哈哈哈，split()瞬间解决，注意base case就好。

class Solution:
    def lengthOfLastWord(self, s: 'str') -> 'int':
        k = s.split()
        if len(k) == 0:
            return 0
        else:
            return len(k[-1])

要注意的是如果数组为空，k[-1]是会报错的。一定要注意这个边界条件。

C++实现

C++实现实际上更简单，从后往前扫描，遇到空格跳出即可。切记这种从后往前的遍历一定要使用rbegin()和rend()的迭代器，可以避免很多不必要的麻烦。

class Solution {
public:
    int lengthOfLastWord(string s) {
        int len = 0;
        for(auto it = s.rbegin(); it != s.rend(); it++){
            if(*it != ' ')
                len++;
            else if(len == 0);
                // Do nothing
            else
                break;
        }
        return len;
    }
};

中间那个len == 0的条件是为了应对像"a "这样空格打头的testcase（这个真的有意义吗……）。

#387 First Unique Character in a String

题目地址：https://leetcode.com/problems/first-unique-character-in-a-string/

地球人都知道用hash map做，问题是怎么缩小体积和怎么用Signle Pass就解决问题

初见 (Char数组, two pass)

两次遍历，由于只需要用三个状态，用char数组即可。实际上C++里的bool也是用char实现的（都是8个bit），所以本质上和用bool数组也差不多。

class Solution {
public:
    int firstUniqChar(string s) {
        char hash[26] = {0};
        for(auto it = s.begin(); it != s.end(); it++){
            if(hash[*it - 'a'] == 0)
                hash[*it - 'a'] = 1;
            else if(hash[*it - 'a'] == 1)
                hash[*it - 'a'] = 2;
        }
        for(int i = 0; i < s.length(); i++){
            if(hash[s[i] - 'a'] == 1)
                return i;
        }
        
        return -1;
    }
};

LeetCode表示占用内存比int数组还多，这不是搞笑吗？

Single Pass

顺便保存下标就能做到Single Pass。要注意这种情况在遍历Hash map的时候要只能返回下标的最小值，不然要悲剧的。

class Solution {
public:
    int firstUniqChar(string s) {
        char hash[26] = {0};
        for(auto it = s.begin(); it != s.end(); it++){
            if(hash[*it - 'a'] == 0)
                hash[*it - 'a'] = 1;
            else if(hash[*it - 'a'] == 1)
                hash[*it - 'a'] = 2;
        }
        for(int i = 0; i < s.length(); i++){
            if(hash[s[i] - 'a'] == 1)
                return i;
        }
        
        return -1;
    }
};

理论最小空间

理论上来说26个字母，三个状态，总共有3^26种状态，log2( 3^26 )=41.2，也就是说这道题最少可以用4个int（64bits）或者6个char（48bits）解决。4个int的做法是映射为4进制，相对来说好存取一些，思路也很清晰。