# 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
:::

### 題目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所儲存的值。
>>

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

>>而 =="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的值==
>>

#### 2. Vector 的基本用法
>vector 是 C++ 的一種container ，可以視為比較好操作的陣列，能有類似python那樣的操作，以循序 (Sequential) 的方式維護變數集合，可以隨機的進行存取，並能很快的增加與刪除頭尾的元素O(1)，但要中間增加與刪除元素則較費時O(n)(因為位置都要往前移)，u 一個vector<int> vec可以如 int vect[] 一樣使用，但多了幾種基本的方法，
:::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的值。

#### 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/

### 題目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;
}

};
:::