---
Author: 白居易 Bone
---
### HW1 白居易 Bone
## [1796. Second Largest Digit in a String](https://leetcode.com/problems/second-largest-digit-in-a-string/)

# R

ER: This question asks you to find the second largest digit in an alphanumeric string consisting of lowercase letters and digits. If a second largest digit exists, you should return it; otherwise, return -1.

EE: I want to check the question again, it asks me to find the second largest numerical digit in an alphanumeric string and return it, or return -1 if the answer does not exist, so what can the string contain?

ER: An alphanumeric string consists of lowercase English letters and digits from 0 to 9.

EE: All right, what about the length of the string?

ER: The size is greater than or equal to 1 and less than or equal to 500, and it is not a null or empty string.

EE: I got it!

# E

EE: I want to try some examples to verify whether my understanding is correct. Example one is the string “a4bht5qw19”, the digits that appear are 4, 5, 1 and 9, it is obvious that the second largest is 5.
And the second string is “r44444er”, there is only one distinct digit, which is 4. Since there is no second largest digit in the string, the function should return -1.
The final example is “qwerasd”. This string contains only lowercase letters and no digit, so, the function should return -1.

ER: Sure, go ahead!

# A

EE: And let me talk about my approach first. I want to maintain a boolean array of length ten to record what digits have appeared, the next step is to find the second largest digit. We can traverse the array from back to front to find the second largest number, we can maintain a counter whose initial value is 0, when we check the digit that appears, the counter increments, and if the counter is equal to 2, which means that the digit is the second largest digit, and then we return the digit, else return -1.
So I think the complexity of my approach is O(n), where n is the size of the string. This is because we first traverse the string to build the boolean array, and then traverse the fixed-length array(size 10) to find the second largest digit. Thus, the total time complexity is O(n) + O(1) = O(n).
The space complexity is O(1), since we only need a boolean array of fixed size (10).

ER: Sounds great! Please go on.

# C

class Solution {
public:
    int secondHighest(string s) {
        vector<bool> seen(10, false);

        for(auto c : s) {
            if(isdigit(c)) {
                seen[c - '0'] = true;
            }
        }

        int count = 0;
        for(int i = 9; i >= 0; i--) {
            if(seen[i])
                count++;
            if(count == 2) return i;
        }
        return -1;
    }

    bool isdigit(char c) {
        return c <= '9' && c >= '0';
    }
};

# O

ER: Can you think of an approach that uses no extra memory or only traverses the string once?

EE: Hmm… sure. We can achieve the same result without using a boolean array.

ER: How would you do that?

EE: We can maintain just two variables, largest and secondLargest, both initialized to -1. We then traverse the array once. For each character, if it is a digit, we check whether it is larger than the current largest and the secondLargest, and update accordingly.

This way, we can only traverse the string once to find the second largest digit and need no additional memory space apart from the two variables.

ER: Great! Code it up!

# C
---

class Solution {
public:
    int secondHighest(string s) {
        int first = -1, second = -1;

        for (char c : s) {
            if (c >= '0' && c <= '9') {
                int num = c - '0';
                if (num > first) {
                    second = first;
                    first = num;
                } else if (num < first && num > second) {
                    second = num;
                }
            }
        }

        return second;
    }
};

ER: Well done! Please wait for the next interview!
EE: Thanks!

# 初步檢討自己的表現
1. 講解optimized code的部分，邏輯觀念講得不夠清晰
2. examples的時候應該挑更簡單直觀的例子，導致我trace的時候不容易講清楚
## [125. Valid Palindrome](https://leetcode.com/problems/valid-palindrome/description/)
# R

ER: 給定一個字串，將數字字母以外的字符去除，檢查得到的新字串是否是Palindrome。

EE: 再跟您確認一次題目的要求，要求檢查給定字串是否為Palindrome，需要先去除非數字以及字母的符號，然後檢查新字串從頭開始讀是否會跟從後面開始讀一樣?

ER: 沒錯。

EE: 字串中會包含什麼?

ER: 字串中只會有可以印出來的ASCII 字符，也可以是空字串。

EE: 了解，大寫小寫視為相同嗎?

ER: 沒錯，你需要將大寫給轉換成小寫。

EE: 我明白了。
# E

EE: 我想通過幾個例子來確認我的理解是否正確，第一是正常組成有各種printable ascii characters的string "**Was it a car or a cat I saw?**"，第二個則是空字串" "，
第三個則是全部由非alphanumeric組成的string",#^^"。

# A

EE: 我的想法是利用一個vector以及for loop來把所有alphanumeric characters給存入，將其他字符給篩除，接下來就是檢查此vector是否是palindrome，我會將分析三種可能的情況，第一種是此string非palindrome，第二種則是此vector是palindrome，且是偶長度，第三種就是此vector是palindrome，且是奇長度。
利用std::reverse方法產生顛倒順序的vector rev，再用for loop一一比較即可。
我先分析時間複雜度，我會對string s進行一次遍歷，這個過程中會進行判斷是不是英文字母、是不是數字，這花了O(1)，如果是字母則一律把它給轉成小寫，這花了O(1)，所以共用了O(n) * O(1) = O(n)，其中n是string s 的length。
接著複製一份rev，將過濾過的字串完全複製，最多可花O(n)，n同樣是s的size。
再來是反轉rev的順序，這也花了O(n)。
最後是比較str是否等於rev，因為是一一比較，所以花了O(n)，將上述4步驟加總，所以total time complexity是 O(n) + O(n) + O(n) + O(n) = O(n)。
再來分析空間複雜度， array str大小最大會達到string s的length，所以是O(n)，n是s的size。
rev則是複製一份str，所以也是O(n)，而其他的區域變數與指標則是O(1)，所以total space complexity是O(n) + O(n) + O(1) = O(n)。

ER: 分析得沒錯!

EE: 接下來我直接進行coding。

# C

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.empty()) return true;

        vector<char> str;

        for(auto c : s) {
            if(isDigit(c) || isLetter(c)) {
                str.push_back(toLower(c));
            }
        }

        vector<char> rev = str;
        std::reverse(rev.begin(), rev.end());

        return str == rev;
    }

    bool isDigit(char c) {
        return c >= '0' && c <= '9';
    }

    bool isLetter(char c) {
        return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
    }

    char toLower(char c) {
        if(c >= 'A' && c <= 'Z')
            return c - 'A' + 'a';
        return c;
    }
};

# T

EE: 來驗證example 1: "Was it a car or a cat I saw?"

# O
ER: 可不可以不使用額外的rev，只使用一份str來完成?

EE: 可以，這樣的話，我要修改我的方法，不複製str，而是直接在 str 上做雙指標檢查。同樣會先遍歷string s去篩除非英文字母以及數字字符，得到目標字串str後，利用兩個指標 l以及r，還有while loop從str的頭以及尾部進行check，不過這樣做就要小心while loop的終止條件了，我先說明l以及r，l的初始值是0，代表從str的開頭開始，r的初始值是str的size-1，代表str的最後一個字符，每個pass檢查完後l的值會+1，r的值會-1，那這個loop會在什麼情況終止? 也就是當l跟r碰在一起時我們就必須結束了，因為palindrome可能長度是3，例如"lol"為例，l初值為0，r初值為2，第一輪str[0] == str[2]，所以可以進到下一輪，l+1變成1，r-1變成1，因為lol是palindrome，代表此時str[l] 是否等於 str[r] 就不重要了，不需要比較，因此while loop的終止條件是l < r。如果過程中有str[l] != str[r] 則可以判定不是palindrome，直接return false即可，如果執行完while loop，則代表是palindrome，即return true。
分析時間複雜度，因為同樣要遍歷string s一次，同上一次的分析花了O(n)，第二部分從str的頭尾進行check，最多會花O(n/2)=O(n)，因此total time complexity是O(n) + O(n) = O(n)，n是string s的size。
再來是空間複雜度的分析，因為我們這次只使用了一個vector str，不會使用到rev，因此最多會花O(n)，空間複雜度仍是O(n)。

ER: 沒錯，空間複雜度不變。

EE: 我接著coding。

class Solution {
public:
    bool isPalindrome(string s) {
        if (s.empty()) return true;

        vector<char> str;
        for (auto c : s) {
            if (isDigit(c) || isLetter(c)) {
                str.push_back(toLower(c));
            }
        }

        int l = 0, r = (int)str.size() - 1;
        while (l < r) {
            if (str[l] != str[r]) return false;
            l++;
            r--;
        }

        return true;
    }

private:
    bool isDigit(char c) {
        return c >= '0' && c <= '9';
    }

    bool isLetter(char c) {
        return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
    }

    char toLower(char c) {
        if (c >= 'A' && c <= 'Z') return c - 'A' + 'a';
        return c;
    }
};

ER: 做得好，請你等待下一輪面試!

EE: 謝謝您。

# 初步檢討自己的表現
1. trace examples時，講解的方法不太好，用頭尾兩邊同時消除的方式會讓人誤解我的解決方法
2. 也是例子舉的不太好，我覺得我舉的太長了，會造成trace的時候的麻煩
## [113. Valid Palindrome](https://leetcode.com/problems/path-sum-ii/description/)

# R

ER: 給定一個binary tree 的 root，以及整數 targetSum，回傳所有根節點到葉節點和為targetSum的路徑。

EE: 跟您確認一下題目，我需要對於一個binary tree，確認它的根節點到所有葉節點的路徑總和等於targetSum的路徑，我需要回傳什麼?

ER: 回傳所有的符合的路徑，路徑內容是節點的值。

EE: 葉節點是沒有左子點以及右子點的節點?

ER: 沒錯。

# E

EE: 好，我想舉幾個例子確認我的理解是否與您相符，binary tree為 [1, null, 2]，targetSum為1，這樣我會return null，因為雖然root的值是1，但是因為1不是葉節點，需要繼續往下傳遞值，需要繼續計算葉節點2，因此不存在root到leaf的值符合targetSum的路徑，沒錯吧?

ER: 沒錯! 繼續下去吧。
# A

EE: 再開始coding之前，我想要先說明我的方法，我主要會使用dfs遞迴方法來遍歷binary tree，先檢查當前節點是否為空，不是nullptr就把當前節點push進path vector，再來檢查是否是葉節點，這可以使用判斷node->left 是否等於nullptr，node->right 是否等於nullptr，如果是葉節點就檢查當前節點的值+current Sum是否等於targetSum，等於就把path加到回傳的vector中，不等於就繼續做，更新currentSum的值，傳到node的左右子樹中，最後則是會把path給pop，也就是把當前節點從path中去除。

接著探討一下時間複雜度，因為是使用dfs方法遞迴地遍歷所有節點，所以time complexity是O(n)，n是binary tree的節點數。再來是space complexity，因為遞迴深度最多到H，所以path的長度最多也是H，H是樹的高度，因此total space complexity是O(H)。

ER: 聽起來不錯，寫成程式吧!
# C

class Solution {
public:
    vector<vector<int>> ans;

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        int currentSum = 0;
        vector<int> path;
        toLeaf(path, root, targetSum, currentSum);
        return ans;
    }

    void toLeaf(vector<int> path, TreeNode* node, int targetSum, int currentSum) {
        if (!node) return;

        path.push_back(node->val);
        currentSum += node->val;

        if (currentSum == targetSum && !node->left && !node->right) {
            ans.push_back(path);
        }

        toLeaf(path, node->left, targetSum, currentSum);
        toLeaf(path, node->right, targetSum, currentSum);

        path.pop_back();
    }
};

# T

EE: 來驗證我之前舉的binary tree，
# O

ER: 很好，看起來程式功能正確了。但是對於空間利用度還可以再改善，你有想到什麼地方可以改善嗎?

EE: 我想我可以改善currentSum的部分，我只要將程式的引數直接修改就可以不用用到currentSum了。

ER: 沒錯，currentSum的部分其實是不必要的。 還有嗎?

EE: 還有函數引入的部分，我可以改用&，直接用call by reference的形式，這樣所有遞迴都只會用到同一個path vector，不會額外浪費記憶體，這是我原本忽略的。

ER: 很好，寫成程式吧!

class Solution {
public:
    vector<vector<int>> ans;

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        dfs(root, targetSum, path);
        return ans;
    }

private:
    void dfs(TreeNode* node, int remainingSum, vector<int>& path) {
        if (!node) return;

        path.push_back(node->val);
        remainingSum -= node->val;

        if (remainingSum == 0 && !node->left && !node->right) {
            ans.push_back(path);
        }

        dfs(node->left, remainingSum, path);
        dfs(node->right, remainingSum, path);

        path.pop_back();
    }
};

# 初步檢討自己的表現
1. 我在optimization的部分講得不好，詞不達意，我應該更有條理的組織好語言再說
2. 我在coding的部分應該要注意跟面試官的互動，而非只有打程式而已
3. 講解空間複雜度的時候也沒有說明清楚，我應該說是在怎麼樣的情況會達到O(H)，並且是worst case，而且實際上的worst case也非O(H)
4. Coding速度以及解題速度可以再加快