---
# System prepended metadata

title: Leet code 筆記
tags: [Linked List, backtracking, vector, twosum, call by reference, C++, array, math, hashtable, string]

---

# Leet code 筆記


## Array

###  題目1: Two Sum (2021/4/7)
>Example 1:
>Input: nums = [2,7,11,15], target = 9
>Output: [0,1]
>Output: Because nums[0] + nums[1] == 9, we return [0, 1].
###### tags: `hashtable` `array` `C++` `twosum`

 #### 1. std::unordered_map  與  std::map 的區別
 
 >  map的資料是有序的，對應的資料結構是 =="紅黑樹(redblack-tree)"== 
 :memo:*紅黑樹:  時間複雜度(Ologn)*
 
 >unordered_map的資料是無序的，對應的資料結構是 =="Hash Table"==
 :memo:*hash table:鍵值與雜湊函數(hash function)計算出雜湊值而快速的查找到對應的元素，時間複雜度為常數級別O(1)*
:::info
> 兩者的使用方式相當類似，使用方式參考: https://shengyu7697.github.io/blog/2019/12/13/std-unordered-map/
:::


#### 2. 解題想法
> "建立HASH TABLE 以INDEX為KEY，並迴圈計算TARGET與array NUMS裡面的值的差，當hash table內有該差值，則回傳key與迴圈的參數(i)"
:::info

>class Solution {
public:

    vector<int> twoSum(vector<int> &numbers, int target)
{

    //Key is the number and value is its index in the vector.   
    unordered_map<int, int> hash;
	vector<int> result;
	for (int i = 0; i < numbers.size(); i++) {
		int numberToFind = target - numbers[i];

            //if numberToFind is found in map, return them
		if (hash.find(numberToFind) != hash.end()) {
                    //+1 because indices are NOT zero based
			result.push_back(hash[numberToFind] );
			result.push_back(i );			
			return result;
		}

            //number was not found. Put it in the map.
		hash[numbers[i]] = i;
	}
	return result;
}
:::

###  題目7: Reverse Integer (2021/4/14)
Example 1:

Input: x = 123
Output: 321
###### tags:  `array` `C++` `math` `string`

 #### 1. 字串處理 anttype to string
 >std:string str = std::to_string(int);
 //宣告char array
 char *array;
 array = new char[str.size()]
 //複製str給array()
 strcpy(array,num_str.c_str()); //c_str()轉換是一個const char只能複製
 
 >//str轉換int
 int   ans= atoi(num_char); 
 long  ans= atol(num_char);
 
 
  #### 2. 解題想法(字串)
  >這題的正常解法是使用數學來解決，突發奇想想使用字串的方式來處理，所以特別繞了一大圈，中間卡在int overflow的問題很久 因為對字串來說處理起來是沒問題的，但轉換int後的數字會overflow，才知道原來超出範圍的數字要return 0，將input 轉為long 型態來處理後比較 INT_MAX 與 INT_MIN 的大小就沒問題了:
  :::info
  class Solution {
  
public:

    int reverse(int x) {
        int sign;
       char tmp;
        long check = x;
        
        if(x<0)
            sign=-1;
        else
            sign=1;
                  
        std::string num_str=std::to_string(check);
        char *num_char;
        num_char = new char[num_str.size()+1];
        strcpy(num_char,num_str.c_str());
        
        
        for(int i=0;i<num_str.size()/2;i++){                
            tmp = num_char[i];
            num_char[i] = num_char[num_str.size()-1-i];
            num_char[num_str.size()-1-i] = tmp;            
        }
       
               
        long  ans= atol(num_char);
        ans = ans*sign;
        if(ans > INT_MAX || ans<INT_MIN) 
            return 0;
        else
            return ans;
        }
};
:::
#### 3.數學解法
>正常解法則是純數學的解法，需準備一個long的變數來做處理，將res加上x取10的餘數並*10
>然後將x消去最後一位數(除以10)，直到x=0
:::info
![](https://i.imgur.com/QTi26hB.png)
:::

###  題目26: Remove Duplicates from Sorted Array 
>Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
>Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
=="Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.
Internally you can think of this:"==
>>>// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
     print(nums[i]);
}

>Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.
###### tags:  `array` `C++` `vector` `call by reference`

#### 1. Call by reference V.S Call by Value
>這題的題目很簡單，但回傳的結果很特別，只需回傳去除重複的陣列長度即可，因為這題的陣列是用Call by reference 呼叫的，順便回顧call by value的定義。
>>=="call by value"== 是取的該記憶體位置內的值，如宣告一個函式void function(int a)並在主程式中呼叫該函式->function (b)，fuction便會呼叫b記憶體位置的值，給a的記憶體位置儲存，對a的更動並不會影響b所儲存的值。
>>![](https://i.imgur.com/PuNairT.png)

>>但這種呼叫方式不代表，無法更改b的值，只要用call by value 呼叫b的記憶體位置，便能夠透過==指標==更改該記憶體位置當中的值，
>>以void function(int *a) 與 function(&b)為例: 即是將指標a指向b的記憶體位置，已更改變數b的值(ex. *a=3,則b的值會變為3)，這種方式也有人稱為 =="call by address"==
![](https://i.imgur.com/gWUdYZf.png)


>>而 =="call by reference"== 是==C++獨有==的呼叫方式，即是在呼叫變數前面加上  =="&"== 就能在函式內使用函式外的變數，這個方式的效果與前面提到呼叫指標的方式是相同的。
>>以function(int &a)  function(b)為例 :a與b可以視為同一個變數，只是在function與主程式中中有了不同的名稱(ex. a+3，則b的值也會+3)，==即是兩個變數名稱共用一個記憶體位置，這是與call by value呼叫指標的不同之處，後者是透過指標*a改變主程式中b的值，而reference則是直接更改a就能更改b的值==
>>![](https://i.imgur.com/ed8p7rp.png)

#### 2. Vector 的基本用法
>vector 是 C++ 的一種container ，可以視為比較好操作的陣列，能有類似python那樣的操作，以循序 (Sequential) 的方式維護變數集合，可以隨機的進行存取，並能很快的增加與刪除頭尾的元素O(1)，但要中間增加與刪除元素則較費時O(n)(因為位置都要往前移)，u 一個vector<int> vec可以如 int vect[] 一樣使用，但多了幾種基本的方法，
![](https://i.imgur.com/eZGEDoU.png)
![](https://i.imgur.com/RMwKeXJ.png)
:::info
詳細可以參考: 
入門:　https://mropengate.blogspot.com/2015/07/cc-vector-stl.html 
文件：　https://www.cplusplus.com/reference/vector/vector/vector/ 
:::

#### 3. 解題想法
> 由於只需要依照回傳的長度來修改給予的陣列即可，只需要將陣列獨立的數字取代重複數字的位置即可，如[1,1,2,2,2,3,3]改為[1,2,3,2,2,3,3]，回傳長度3，所以不需要到整個陣列的移動，因此沒有使用到vector的函式功能，主要想法是，迴圈比較陣列前後的值，若一樣則counter++，直到找到不同的值時讓不同的值取代(i-counter)的位置，中間的差值就是不同數字間重複數字的長度，最後回傳陣列長度減去counter的值。
![](https://i.imgur.com/K9QalAA.png)

#### 4. vector 特殊解法
這是討論看到的特殊解法，覺得挺有趣的所以紀錄下來，unique會將nums裡獨立的數字往前排序，ex[1,1,2,2,3] 會變成 [1,2,3,2,3] 然後再消除後面的數字即可，也可以取resize後的長度來回傳(nums.resize( std::distance(myvector.begin(),it) )
https://www.cplusplus.com/reference/algorithm/unique/
![](https://i.imgur.com/NDBM39h.png)


###  題目21: Merge Two Sorted Lists 
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

>Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

###### tags:  `Linked List` `C++` `vector` `call by reference`
    
###  46. Permutations 
###### tags:  `backtracking`
:::info
class Solution {
public:
    vector<vector<int>> ans;
    
    // Backtracking
    void solve(vector<int> &nums,int index,int length){
        
        if(index==length){
            ans.push_back(nums);
            return;
        }
        
        for(int j=index;j<length;j++){
            swap(nums[index],nums[j]);
            solve(nums,index+1,length);
            swap(nums[index],nums[j]);
        }
        
    }
    
    
    vector<vector<int>> permute(vector<int>& nums) {
        //123 level=i
        //i=0 j=0 123 i=1 j=1 123 i=2 j=2 123 push_back(123)
        //            i=1 j=2 132 i=2 j=2 132 push_back(132)
        //                    123  
        //        123 
        //i=0 j=1 213 i=1 j=1 213 i=2 j=2 213 push_bakc(213)
        //            i=1 j=2 231 i=2 j=2 231 push_back(213)
        //                    213  
        //        123
        //i=0 j=2 321 ....
        //123
        
        solve(nums,0,nums.size());
        return ans;
    }
};
:::
    
### 39. Combination Sum
###### tags:  `backtracking`
:::info
class Solution {

public:
    vector<vector<int>>ans;
    vector<int> tmp;//array_to_push ans
    int sum; //ex:[2,2,2,2] =8
    
    void solve(vector<int>&candidate,int target,int index){
        
            if (sum>target)
                return;
            if (sum == target)
                ans.push_back(tmp);//ex t=8 c=[2,2,2,2]
            
            for(int i = index ;i < candidate.size(); i++){
                sum+= candidate[i];
                tmp.push_back(candidate[i]);     //ex [2,2]+[2] sum=4+2
                solve(candidate,target,i);
                sum-=candidate[i]; 
                tmp.pop_back();      // ex t=7 [2,2,2,2] reutn sum-=2 [2,2,2]
            }
        /*
        [2,3,5] t=8 sum=0 c=[]
        iter 0 :
            sum=2 c=[2] 
            solve([2,3,5],8,0)
                iter 0:
                    sum=4 [2,2]
                    solve([2,3,5],8,0)....
        iter 1:
            sum=3 c=[3]
            solve ([2,3,5],8,1]);
                iter 1:
                sum = 6 c=[3,3]
                solve([2,3,5],8,1);...
        */
        //[2,2,2,2](push_back_to_ans) ->[2,2,2,3]return->[2,2,2,6]return->[2,2,2,7]return
        //[2,2,3](push_back_to_ans) -> [2,2,5]return
        
            
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            sum=0;
            solve(candidates,target,0);
            return ans;
    }
    

};
:::

###  139. Word Break  
    brute force
:::info
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //catdog [cat dog]
        //c atdog ->a tdog->t dog
        //        ->at dog  
        //ca tdog
        //cat dog
        if(find(wordDict.begin(),wordDict.end(),s)!=wordDict.end())
            return true;
    
        for(int i=1;i<s.size();i++){
            string left = s.substr(0,i);
            if(find(wordDict.begin(),wordDict.end(),left)!=wordDict.end() && wordBreak(s.substr(i),wordDict)){
                return true;
            }
        }
        return false;
    }
    
};
:::
    
    
    










