今天的題單：

• Best Time to Buy and Sell Stock

• Valid Palindrome

121. Best Time to Buy and Sell Stock

一開始寫了 O(n^2) time brute force 解，比對每兩天的差值。

// TLE
class Solution {
public:
    // no profit: profit <= 0
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        
        for (int i=0; i<prices.size(); i++) {
            for (int j=0; j<i; j++) {
                profit = max(prices[i]-prices[j], profit);
            }
        }
        return profit;
    }
};

在想 O(n) 解法的時候卡了很久，參考了別人的方法才想通。

我原本的思路：

從第一天開始往後看，遇到 local min 記起來後繼續往後看，遇到 local max 後計算獲利。之後在遇到 local min 需要更新最低點紀錄，再往後看遇到 local max 計算獲利，如此往復。

這裡卡住的點在：

如果前一個低點比後一個低點低，這樣最低點被更新後，會不會漏掉最大獲利？

在參考了別人的解法後，發現思路方向大致是對的，差了一點點：

從第一天開始往後看，遇到 local min 記起來後繼續往後看，遇到 local max 後計算獲利。之後在遇到更低的 local min 需要更新最低點紀錄，再往後看遇到 local max 計算獲利，如此往復。

用後者思路來分析，假設有兩個低點：

• 前一個較高，後一個較低

  • 遇到後一個低點會更新最低買進點，之後的獲利會用新的最低點算。

  • 獲利大於歷史最大獲利才會更新

• 前一個較低，後一個較高

  這裡產生一個直覺問題：我需要去記住前一個低點，才不會漏掉最大獲利。這也就是原本卡住的地方。但是其實最低買進點只會在遇到更低點的時候更新，所以計算獲利時會是用前一個低點算，所以漏掉的狀況不會發生

// O(n) solution
class Solution {
public:
    // no profit: profit <= 0
    int maxProfit(vector<int>& prices) {

        int min_price = 10000;
        int max_profit = 0;

        for (int i=0; i<prices.size(); i++) {
            // find the min price
            if (prices[i] < min_price) {
                min_price = prices[i];
            }

            if ((prices[i] - min_price) > max_profit) {
                max_profit = prices[i] - min_price;
            }

        }
        return max_profit;
    }
};

125. Valid Palindrome

判斷一個句子去掉非字母數字（non-alphanumeric）字符剩下的部分是不是回文。

Non-alphanumeric characters refer to those characters that are neither alphabets (a-z) nor numbers(0-9)

解法很單純，只要去掉字母數字以外的字符再判斷是不是回文就好了。判斷回文可以用 two pointer 的方法，從兩端一個一個字比對到中間看有沒有都一樣即可。

需要處理的事有兩件：一是去除 non-alphanumeric 字符的部分，二是大寫轉小寫。

本來想說要用 ascii code 編碼去判斷，沒想到發現有 isalnum() 和 tolower() 這個函數可以用！省下很多工夫。

class Solution {
public:
    bool isPalindrome(string s) {
        // A-Z: 65 - 90
        // a-z: 97 - 122
        // 0-9: 48 - 57
        
        string new_s = s;
        
        // news_s.lower()
        for (string::iterator it=new_s.begin(); it!=new_s.end();) {
            if (*it >= 65 && *it <= 90)
                *it += 32;
            // remove non-alphanumeric characters
            if (!isalnum(*it)) {
                it = new_s.erase(it);
            } else {
                it++;
            }
        }

        // check if s is palindrome by two pointer

        string::iterator left = new_s.begin();
        string::iterator right = new_s.end();

        right--;

        int len = new_s.size();

        if (len <= 1)
            return true;

        if (len % 2 == 1) { // the length of the string is odd
            while (left != right) {
                if (*left != *right)
                    return false;
                left++;
                right--;
            }
            return true;
        } else { // the length of the string is odd even
            while (right-left != 1) {
                if (*left != *right)
                    return false;
                left++;
                right--;
            }
            if (*left != *right)
                return false;
            else
                return true;
        }
    }
};

提交之後發現速度比較慢，參考了較快的 sample code

• 直接在檢查時跳過非字母數字字符速度會比較快一些。

• 原本寫法依據長度把奇數和偶數分開處理，可以迴圈條件的部分改成 left <= right 簡化實作。

class Solution {
public:
    bool isPalindrome(string s) {
        // A-Z: 65 - 90
        // a-z: 97 - 122
        // 0-9: 48 - 57

        int left = 0;
        int right = s.size() - 1;

        while (left <= right) {
            if (!isalnum(s[left])) {
                left++;
                continue;
            }
            if (!isalnum(s[right])) {
                right--;
                continue;
            }
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};