2022. Convert 1D Array Into 2D Array
題目網址:https://leetcode.cn/problems/convert-1d-array-into-2d-array/
題意:將 1d array original 轉成 m 列 n 行的 2d array。
Solution:
想法:每次塞 1 x n 的 vector
class Solution {public: vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) { if (m * n != original.size()) { return {}; } vector<vector<int>> res; for (int i = 0; i < m * n; i += n) { res.emplace_back(vec ...
338. Counting Bits
題目網址:https://leetcode.cn/problems/counting-bits/
題意:給一整數 n, 對於 0 ≤ i ≤ n 中的每個 i, 計算其在二進制中 1 的個數, 返回一個長度為 n + 1 的 array 作為答案。
Solution 1:
想法:判斷 i 最靠右的 bit 是否為 1。若是的話, 則 cnt++, 每次判斷完後就將 i 右移一位, 直到 i = 0(沒有 1-bit)為止
class Solution {public: vector<int> countBits(int n) { vector<int> res(n + 1, 0); for (int i = 0; i <= n; ++i) { int cnt = 0; for (int val = i; val > 0; val >>= 1) { const int rightmost ...
271. Encode and Decode Strings
題目網址:https://leetcode.cn/problems/encode-and-decode-strings/
題意:給一 string list strs, 請設計一演算法, 讓 encode 後的 string 可以透過網路高效傳輸, 並透過 decode 還原回原本的 string list。
注意:
string 可能會包含所有的 ASCII char, 所以你設計的演算法要能處理任何可能出現的 char
請勿使用 class member、global variable、static variable 來儲存額外的狀態
Solution:
想法:不能只在兩個 string 間只用一個分隔符 (delimiter) 隔開, 因為也有可能 input 中恰好有該分隔符組成的 string
e.g. delimiter = '#', strs = ['1', '2#3']
這樣會得到錯誤的答案 ['1', '2', '3'], 而非 ['1', ...
49. Group Anagrams
題目網址:https://leetcode.cn/problems/group-anagrams/
題意:給一 string list strs, 其中 strs[i] 僅由小寫字母所組成, 將 strs 中的字母異位詞 (Anagram) 進行分組, 可按任意順序返回。
字母異位詞 (Anagram) 定義 :若 s 和 t 中每個字母的出現次數都相同, 則 s 和 t 互為字母異位詞。
Solution 1:
想法:利用 Sorting + hash table, 遍歷每個 string s, 並對其進行排序得到 string key, 將 key 和對應的 s 加入到 hash table 中。最後再根據 key 取出整個 group 即可
class Solution {public: vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string, vector<string ...
202. Happy Number
題目網址:https://leetcode.cn/problems/happy-number/
題意:判斷整數 n 是否為快樂數。
快樂數的定義為:
對於一正整數, 每次將該數轉換為它每一位數的平方和
重複此步驟直到該數為 1, 也有可能進入無窮迴圈(始終無法變成 1 )
如果該數能變成 1, 則它就是快樂數
若 n 為快樂數, 則返回 true; 否則, 返回 false。
Solution 1:
想法:利用 hash table 來記錄出現過的數, 一旦重複出現, 代表會無限循環
class Solution {public: bool isHappy(int n) { unordered_set<int> s{n}; while (n != 1) { n = squareSum(n); if (s.find(n) != s.end()) { return false; ...