項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】C++ – [1] Two Sum 個人解法筆記 (內含 C++ map find 方法補充 (dict find)) #easy #Array #HashTable

題目出處

https://leetcode.com/problems/two-sum/

難度

easy

題目分類

Array, HashTable

個人範例解法 – 一刷 (2021/10/18)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        map<int,int> dict;
        map<int,int>::iterator iter;
        vector<int> ans;

        for (int i=0; i<nums.size();i++){

            iter = dict.find(target-nums[i]);
            // cout<<iter;
            // printf("(%d,%d)",iter->first,iter->second);
            if (iter != dict.end()){ // num found
                ans.push_back(iter->second); //nums find in dict (smaller)
                ans.push_back(i); // current index (bigger)                
                return ans;     
            }
            else{ //iter == dict.end(), not found
                dict[nums[i]]=i;    
            }
        }
        return ans;
    }
};

個人範例解法 – 二刷 (2022/02/24)

第二次要順便複習一下如何找 map 的 keys 的方法
(python 寫太多都忘了)

補充附於文末

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mymap;
        vector<int> ans;
        for(int i=0; i < nums.size(); i++){
            if(mymap.find(nums[i]) != mymap.end()){ // found
                ans.push_back(mymap[nums[i]]);
                ans.push_back(i);
                return ans;
            }
            else{
                mymap[target - nums[i]] = i;
            }
        }
        return ans;      
    }
};

解法重點

這題主要考的是 DP,
需要先建立一張表
(此處利用 map<int,int>,建立 int -> int 對應的 dict),
利用 「key->value」 的特性保存 「值->index」
因此就能快速反查表得到 index

動態規劃 (Dynamic programming,DP) 可參考:

【演算法筆記 #1】動態規劃 (Dynamic programming,DP)

map find 的方法

被 python 寵壞的我,整個 dict find 了起來 Orz
來我們回到一下 C++ map 的世界。

根據 iterator 找到元素

既然是特殊的資料型態,我們自然要靠 iterator 來幫助我們遍歷一下,
思考的方式很簡單,iterator 會幫助我們一直看資料,

那什麼情況會一直看到最後呢?
就是「沒找到」的時候啦!!!

map<int, int> mymap;
if(mymap.find(nums[i]) != mymap.end()){ 
    // found
}
else{
    // not found
}

或不喜歡逆邏輯 (使用’不等於’符號) 的人,我們也可以正向的來

map<int, int> mymap;
if(mymap.find(nums[i]) == mymap.end()){ 
    // not found
}
else{
    // found
}

Reference

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order Traversal