2019-07-21刷题-3

题目序号：1，167，125

• 1. 两数之和
     思路：本题采用简单的暴力算法，其复杂度是O(n^2)。可采用哈希表，达到O(n)的复杂度。将数组元素作为key，下标作为value，如果target-当前元素存在于哈希表中，则返回；否则，找不到。
     （待补充：map，vector用法）
• 2. 两数之和（有序数组）
     思路：跟1相比，本题多了数组是有序的这一条件。因此，可以设首尾指针，依次向中间移动，直到找到或两指针重叠。
• 3. 验证回文串
     思路：本题比较简单，只要设首尾指针，依次向中间移动即可。需要调用algorithm中的transform函数，如果自己实现，耗时应该会更少。
     （待补充：transform函数）

class Solution {
public:
    bool isPalindrome(string s) {
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        // cout << s << endl;
        int str_size = s.size();
        int i = 0, j = str_size;
        bool FLAG = true;
        while(i < j){
            while((i<str_size) && !isalpha(s[i]) && !isdigit(s[i]))
                i++;
            // cout << "here";
            while((j>=0) && !isalpha(s[j]) && !isdigit(s[j]))
                j--;
            // cout << "here";
            if(i >= j)
                break;
            if(s[i] != s[j]){
                cout << s[i] << " " << s[j] << endl;
                FLAG = false;
                break;
            }
            i++;
            j--;
        }
        return FLAG;
    }
};