# NTU leetcode 程式解題基礎班
# 11/9
## C++ 基礎複習
- create無名物件 這行結束 就歸還記憶體空間
```C++
cout<< sol().lowercase << endl ;
```
- 字元與字串
- `" "` 雙引號本意 是字元陣列
- `" "` 字串
- `' '` 字元
- C++文件網站
- 文件寫得很詳細很囉唆 挑要看的就好
- http://www.cplusplus.com
```C++
string s;
// operator overload C++ 提供operator函式
s[i] => s.operator[].(i) // 所以這其實是個函式呼叫!!
```
```C++
// to be avoid to recursive
char tolower(char c){
return ::tolower(c); // iostream內的 global
}
```
```C++
// 小心unsigned vs signed
for(size_t i = 0 ; i<str.size(); i++)
// & :ref 要改到本尊 str: container
// ":" 有begin() end()都可以用
for(char&c : str){
c = towlower(c);
}
```
## 基本演算法題有三種類型
- 三種類型分別為
- linear search 是最基本的款式
- 動過手腳的 pocker 就是更進階的方法
- count problem : 計數問題
- maximum value or minimum value : 極值問題
- 陣列元素索引對應，*映射* 是其中一種技巧
```C++
int count['Z'-'A'+1] = {}
// c-'A' 這動作叫映射
for(char c : s){
count[c-'A']++;
}
```
:::info
遇到很雜的資料 可以先**normalize**
:::
# 11/10
- 刷題: 一題超過5分鐘想不出來 就去看答案
- 聰明才智不是寫多快，是看到答案你也寫不出來。
- 題目一定要自己打字，不可以複製上。
- 把同樣的題目砍掉重寫一次。
- 不要在一個迴圈做太多事，事情會變很複雜，寧願拆三個
## 502 Detect Capital(counting problem)
Given a word, you need to judge whether the usage of capitals in it is right or not.
We define the usage of capitals in a word to be right when one of the following cases holds:
All letters in this word are capitals, like "USA".
All letters in this word are not capitals, like "leetcode".
Only the first letter in this word is capital, like "Google".
Otherwise, we define that this word doesn't use capitals in a right way.
```
Example 1:
Input: "USA"
Output: True
Example 2:
Input: "FlaG"
Output: False
```
- 這邊一樣用divide and conquer的概念，把題目拆成很多小問題。
- 本題屬於**計數問題**:
```C++
class Solution {
public:
bool allCapital(string word) {
for(char c:word){
if(!isupper(c))
return false;
}
return true;
}
bool firstCapital(string word) {
int count = 0;
for(auto c:word){
if(islower(c))
count++;
}
return count == word.size()-1 && isupper(word[0]);
}
bool alllowercase(string word) {
for(char c:word){
if(!islower(c))
return false;
}
return true;
}
bool detectCapitalUse(string word) {
return allCapital(word) || firstCapital(word) || alllowercase(word);
}
};
```
## 387.First Unique Chacter in a String(linear search)
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
```
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
```
Note: You may assume the string contain only lowercase letters.
```C++
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<int,int> count;
for(char c:s)
count[c]++;
for(size_t i=0; i<s.size(); i++){
if(count[s[i]]==1)
return i;
}
return -1;
}
```
- C為何index從0開始?
- ans: 0代表從起始點的元素距離。
- 有begin() , end() 就可以用 for(auto c: )
# 11/16
## 896. Monotonic Array
An array is monotonic if it is either monotone increasing or monotone decreasing.
An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j].
Return true if and only if the given array A is monotonic.
kenyilee_322
- divide amd conquer
我們把大問題，拆成很多小問題(通常指寫成很多小函式)，這是原始寫法。
```C++
class Solution {
public:
bool isMonotonic(vector<int>& A) {
const size_t n = A.size();
//corner case. edge case
if(n==1)
return true;
// detect increased
bool increased = false, decreased = false;
for (size_t i=0; i<n-1; i++) {
if(A[i+1]-A[i] >= 0)
increased = true;
else{
increased = false;
break;
}
}
if(increased)
return true;
// detect decreased
for (size_t i=0; i<n-1; i++) {
if(A[i+1]-A[i] <= 0)
decreased = true;
else{
decreased = false;
break;
}
}
if(decreased)
return true;
return false;
}
};
```
- 依照題目思路，我們可以拆成兩小問題
- 1.如何判斷遞增?
- 2.如何判斷遞減?
最後把兩個小問題透過邏輯符號來合併:
```C++
return increase(A) || decrease(A);
```
新寫法如下:
```C++
class Solution {
public:
bool increase(vector<int>& A) {
for (size_t i=0;i<A.size() -1 ;i++){
if(A[i] > A[i+1])
return false;
}
return true;
}
bool decrease(vector<int>& A) {
for (size_t i=0;i<A.size() -1 ;i++){
if(A[i] < A[i+1])
return false;
}
return true;
}
bool isMonotonic(vector<int>& A) {
return increase(A)||decrease(A) ;
}
};
```
- leetcode要小心**相減變大的狀況**
- **arithmetic overflow**
```C++
cout << v.size() << endl;
// 184464.... 有號數 - 無號數
cout << 1 - v.size() << endl;
// 強制轉型計算比較不會出問題 有號數 - 有號數
cout << 1 - (int)v.size() << endl;
```
## iterator and algorithm
### iterator
- iterator還有分種類
- input iterator
- output iterator
- forward iterator
- bidirectional iterator
- `++` 向後移動
- `--` 向前移動
- random access iterator
- `++`
- `--`
- `+=` 可以向後多個元素
- `-=` 向前多個元素
- C++ standard iterator and container
### C++ algorithm內常見標準演算法
#### 136. Single Number
```C++
```
#### 344. Reverse String
```C++
```
#### 189. Rotate Aray
- function name is repeated , using namespace
```C++
```
## 窮舉陣列索引號
- 知道iterator去減他的begin 就會得到他的索引號
### 136. Single number
## 演算法複雜度
### Big O
- asmyptopic notation
O(m+n) 因為不知道哪一個大
- Big O 是上界，這邊其實是O(n)，就是複雜度不會超過n，但是如果你說O(n^2)，O(n^3) 也是可以，只是不夠精準。
```C
vector<int> nums;
for(int i=0;i<nums.size();i++)
```
# 11/23
### 常見單位
### 172. Factorial Trailing Zeros
Given an integer n, return the number of trailing zeroes in n!.
Example 1:
```
Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.
```
Example 2:
```
Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Note: Your solution should be in logarithmic time complexity.
```
- 1 * 2 * 3 * 4 ...* N
- 一個2 和 一個5 相乘 就會有一個0
- 因為2的個數必大於5的個數
- 算有幾個5相乘就好
- 25 = 5 * 5
```C++
class Solution {
public:
int trailingZeroes(int n) {
//if(!n)
// return 0;
long denominator = 5;
int ans = 0;
while(n >= denominator){
ans += n/denominator;
// signed integer overflow: 1220703125 * 5 cannot be represented in type 'int' (solution.cpp)
denominator *= 5;
}
return ans;
}
};
```
#### Time Complexity
- 一開始會認為時間複雜度是**O(logn)**
- 但是其實n是整數type，最多4 bytes，所以其實是**O(1)**，基本上有**範圍**幾乎就是常數時間。
- 所以前提很重要，fucntion input的參數很重要。
- 要注意會有**溢位問題**。
#### Space Complexity
- 輸入不算空間複雜度。
- 要注意 s = r，這段其實時間複雜度是n
### Standard Libs 演算法的時間複雜度
- 用別人東西，要知道他跑多快。
## Ch6. Two Pointer
- 通常這兩個pointer沒有任何關係。
### increasing vs non-decreasing
Increasing - 1 2 3 4
- x(n+1), x(n+1) > x(n)
Nondecreasing - 1 1 2 3
- x(n+1) >= x(n)
### 循環偵測
#### 龜兔賽跑
#### 202 Happy number
方法一:紀錄走過的數字
方法二:雙指標法
# 11/24
two pointer
- 先cretate new vector去計算
- 如果寫出來，在想說要怎麼移除Vector，Space Complexity O(1)。
- slow pointer, fast pointer
### 283. Move Zeroes
- 先考慮create 一個vector的方法。
```C++
class Solution {
public:
void moveZeroes(vector<int>& nums) {
vector<int> ans(nums.size()); // if we don't give vector initial value, default value is zero
int i = 0;
for(int j=0;j<nums.size();j++){
if(nums[j] != 0){
ans[i] = nums[j] ;
i++;
}
}
nums = ans;
}
};
```
- 觀察以後發現 i 永遠小於j，可以把`vector<int> ans`拿掉。
- 記得後面要補0
```C++
class Solution {
public:
void moveZeroes(vector<int>& nums) {
//vector<int> nums(nums.size()); // if we don't give vector the initial value, element's default value is zero
int i = 0;
for(int j=0;j<nums.size();j++){
if(nums[j] != 0){
nums[i] = nums[j] ;
i++;
}
}
while(i!=nums.size()){
nums[i++] = 0;
}
}
};
```
### Practices Two Pointer
125.Valid Palindrome
977.Squares of a sorted array
167.Two sum II - input array is sorted
925.Long Pressed Name
922.Sort Array By Parity II
1089.Duplicate Zeros
## Ch7.Linked List
- 一開始的故事
```C++
struct ListNode{
int val;
ListNode *next;
ListNode(int v) : val(v), next(nullptr){}
}
int main(){
ListNode a = ListNode(1);
ListNode b = ListNode(2);
ListNode c = ListNode(3);
ListNode *head = &a;
a.next = &b;
b.next = &c;
for(auto p = head; p!=nulptr; p = p->enxt){
cout << p->val << endl;
}
}
```
- 改成pointer
```C++
struct ListNode{
int val;
ListNode *next;
ListNode(int v) : val(v), next(nullptr){}
}
int main(){
ListNode a = new ListNode(1);
ListNode b = new ListNode(2);
ListNode c = new ListNode(3);
ListNode *head = a;
a->next = b;
b->next = c;
for(auto p = head; p!=nulptr; p = p->enxt){
cout << p->val << endl;
}
}
```
- 1.如何用最少的操作實現**操作後畫出來的圖**?
- 2.snapshot or back up起來我們要的點。
### 237 Delete Node in Linked List
- 為何不用head也可以畫出來?
- **因為你結果的圖畫錯了**
- 取巧: next node可以用assign的
```C++
class Solution {
public:
void deleteNode(ListNode* node) {
if(node){
node->val = node->next->val;
node->next = node->next->next;
}
}
};
```
### C++ forward_list 單向Linked List
- 可以用*p拿到答案 ，不用管他的儲存型態，其實這理念就是泛型。
- **itreator**
```C++
#include <iostream>
#include <forward_list>
int main(){
forward_list<int> a = {1,2,3};
for(auto p = a.begin(); p!= a.end(); p++){
cout << *p << endl;
}
return 0;
}
```
### Double Linked List
### Practices Linked List
876.middle of the Linked List
21.Merge Two Sorted Lists
160.Intersection of Two Linked Lists
234.palindrome Linked List
## Ch8. Tree
- Root Node
- Tree height : O(log(n))
- 樹沒有循環(Acyclic)
- 到任一節點path唯一
- 複雜度有限制
- 樹沒有保證平衡，平衡其實是非常複雜的。
- 設一種tree，insert node or delete node都可以保持平衡。
- AVL Tree
- C++ 內建red black tree
- 非常難寫，證明也很複雜。
- 其實就是**map**
### Balance Tree
- 盡量把點往上塞
- 高度為o(logn)
- 最常用的是 Balanced Binary Search Tree
### Heap
- Balance Tree
- Max-heap or Min Heap
- Max Heap : 最大值只要O(1)
- 因為root即為最大值
- 如果把最大的root拿掉
- 更新必從左子點或右子點挑一個往上。
https://visualgo.net/training?diff=Medium&n=7&tl=0&module=heap
### Binary Search Tree
https://visualgo.net/en/bst?slide=1
### Balanced Binary Search Tree
- 最常用的
- Balanced Binary Search Tree != Binary Search Tree
### mapping 映射
- Array
- Array是一種mapping
- 但是key(鍵值)不好處理，只能用非負整數(0~N-1)。
- O(1)
- Map
- 透過Binary Search Tree去實作mapping
- 透過比較**Key 鍵值**來比較大小。
- 不用像array需要create很大的空間，才能access這段index
- key(inedx)可以亂取。
- 複雜度比array高
```C++
map<int,string> a;
a[-3] = "Mary";
a[50000] = "John";
cout<< a[-3] << endl;
cout<< a.size() << endl;
```
- 想和array一樣快，可以用雜湊表。
```C++
unordered_map<int,string> a;
```
### Balanced Binary Tree Practices
804.UNique Morse Code Words
961.N-Repeated Element in Size 2N array
387.First Unique Character in a String
575.Distribute Candies
409.Longest Palindrome
1002.Find Common Charcaters
599.Minimum index Sum of Two Lists
350.intersection of Two Arrays II
509.Fibonacci Number
953.Verifying an Alien Dictionary
929.Unique Email Address
# 11/30
## 隨堂練習
### 771 Jewels and Stones
#### Brute Force
```C++
int numJewelsInStones(string J, string S) {
int count = 0;
for(auto s:S){
for(auto j:J){
if(s==j){
count++;
break;
}
}
}
return count;
}
```
#### count
```C++
int numJewelsInStones(string J, string S) {
int count = 0;
for(auto s:S){
count += std::count(begin(J), end(J), s);
}
return count;
}
```
#### find
```C++
int count = 0;
for(auto s:S){
count += std::find(begin(J), end(J), s) != end(J);
}
return count;
```
#### map
- red black tree
- find O(logn) - tree height
- insert O(1)
- O((m+n) * logn)
#### unodered_map
- hash table
- find O(1)：average為O(1) ，worst case為O(n)
- insert O(1)
- O((m+n) * 1)
```C++
unordered_map<int,int> count;
int ans = 0;
for(auto j:J){
count[j]++;
}
for(auto s:S){
ans+=count[s];
}
return ans;
```
## 如何用一樣的code 印不同的資料結構
- Iterator
- vector, map ....
```C++
forward_list<int> a= = {3,7,2,5,4};
for(auto i = begin(a); i!=end(a) ;i++){
cout<<*i<<endl;;
}
```
- auto
- 只要有begin(), end()
```C++
for(auto i:a){
cout<<i<<end;
}
```
- 用剛剛的map為例
```C++
for(auto i = begin(a); i!=end(a) ;i++){
// key value
cout<<i->first<<": "<<i->second<<endl;;
}
```
```C++
for(auto [k,v]:a) {
// key value
cout<<k<<": "<<v<<endl;;
}
```
## Hash Table
- 給一個key 透過一個**hash function**運算得到對應的index
- 需要設計hash function可以讓key對應到 *非負整數index*
- c++ std algo 逐位元( murmur3_32)
- 如果碰撞(collision)，就接在後面，所以要存key(人名)值
- worst case
### 常用的conatiner
- vecotr
- map
- set(map的特化 效率比較好)
- string
- begin(), end(), find() , count()
### Hash Table Practices
771.jewels and Stones
349.Intersection of Two Arrays
961.N-repeated Element in Size 2N array
1.Two Sum
350.Intersection of Two Arrays II
389.Find the difference
804.unique Morse Code Words
1002.Find common Characters
575.Distribute Candies
409.Longest alindrome
387.First Unique Character in a String
599.Minimum index Sum of Two Lists
509.Fibonacci Number
953.Verifying an Alien Dictionary
# 12/1
## divide and conquer(分治法)
### 用Tree去學最好
### 求樹高
```C++
int maxDepth(TreeNode *root){
if(root == nullptr) return 0;
return max(
maxDepth(root->left),
maxDepth(root->right)) + 1;
}
```
### Search in a BST
```C++
TreeNode* searchBST(TreeNode* root, int val){
if(root == nullptr) return nullptr;
auto l = searchBST(root->left, val);
auto r = searchBST(root->right, val);
if(l != nullptr ) return l;
if(r != nullptr ) return r;
if(root->val == val) return root;
else return nullptr;
}
```
### Divide and Conquer Practices
很多題都會用DFS或是用BFS去優化 找時間學一下
938.Range Sum of BST
965.Univalued Binary Tree
559.Maximum Depth of N-ary Tree
144.Binary Tree Preorder Traversal
- VLR: Preorder
- LVR: Inorder
- LRV: PostOrder
590.N-ary Tree Postorder Traversal
589.N-ary Tree Preorder Traversal
- for(auto child:root->children)
617.Merge Two Binary Trees
100.Same Tree
101.Symmetric Tree
897.increasing Order Search Tree
- 可以用inorder Traversal
226.invert Binary Tree
1022.Sum of Root to Leaf Binary Numbers
#### 559. Maximum Depth of N-ary Tree
```C++
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
int maxDepth(Node* root) {
if(!root) return 0;
int maxValue = 0;
for(vector<Node*>::iterator pChild = root->children.begin();
pChild != root->children.end();
pChild++){
maxValue = max(maxValue ,maxDepth(*pChild));
}
return maxValue + 1;
}
```
## 169. Majority Element
### map
```C++
int majorityElement(vector<int>& nums) {
map<int,int> count;
// map: O(nlogn)
// unordered_map : O(n)
for(auto n:nums){
count[n]++;
}
for(auto iter=count.begin();iter!=count.end();iter++)
if(iter->second > nums.size()/2)
return iter->first;
return 0;
}
```
### divide and conquer
- 幹 這到底是什麼鬼...
```C++
int majorityElement(auto left, auto right) {
if(left+1 == right) return *left;
auto mid = left + (right-left)/2;
auto l = majorityElement(left , mid);
auto r = majorityElement(mid , right);
if (l == r)
return l;
if (count(left, right, l) >= count(left, right, r))
return l;
else
return r;
}
int majorityElement(vector<int>& nums) {
return majorityElement(nums.begin(), nums.end());
}
```
## Sort
### Merge Sort
類似two pointer去合併
### Quick Sort
- 不用像Merge Sort 搞合併。
- 挑的**哨兵**，會有不平衡的問題。
### Counting Sort
- 挑數值範圍小的
### Radix Sort
- 如果數值範圍很大 我們要怎麼小?
- 從低的位數先排
- 個位 十位 百位
- First In, First out
## C++ Sorting
Quick Sort => Inserting Sort(修毛毛邊)
### Descending Order(由大到小)
#### Reverse iterator
```C++
int A[10] = {1,2,3,4,5,6,7,8,9,0};
sort(rbegin(A), rend(A));
```
#### cmp function
`bool cmp(int a, int b)` : **a 放在 b 前面的條件是什麼?**
- 符合條件，什麼都可以排!!
```C++
bool cmp(int a, int b){
return a > b;
}
int A[10] = {1,2,3,4,5,6,7,8,9,0};
sort(begin(A), end(A)), cmp) ;
```
### stable_sort
- stability : 排完之後，保持原本順序的sort，C++ 為了保持原本順序，用merge sort去實作。
- UI 介面排序很容易遇到
把0全部移到右邊的leet code，改用cmp解。
```C++
```
### 記數問題 <=> Sorting Problem
兩者等價，看那個好寫挑那一個。
### Summary
https://en.wikipedia.org/wiki/Sorting_algorithm
## Binary Search
- 前提: 資料要先sort好。
### 尾遞廻
符合這種方式的recursive，都可以寫成loop。
### Binary Search Tree vs Binary Search
- 如果常常需要**新增 insert , 刪除 delete **，用Tree比較便宜。
- 兩個其實都排好序了
#### Practices Binary Search
167.Two Sum II- input array is sorted
367.Valid Perfect Square
441.Arranging Coins
852.Peak Index in a Mountain Array
392.Is Subsequence
### Summary
- 其實解題最常用的是unodered_map
- 可以用Tree的題目去練習Recursive，如何去分治它。
# 12/7
## 隨堂練習
### 905. Sort Array By Parity
- Tow pointer: O(n)
```C++
int i = 0;
for(int& a : A){
if(a%2 == 0){
swap(A[i], a);
i++;
}
}
```
### cmp() function
- 如果放在member function這邊，我們要加static，
```C++
static bool cmp(int a, int b){
return a%2==0 && b%2!=0;
}
```
- lambda
```C++
sort(A.begin(), A.end(), [](int a, int b) {return a%2==0 && b%2!=0;} );
```
### 35. Search Insert Position
### lower_bound
- 通常用在binary search，因為是itreator，所以沒這麼好用，要先sort過後才能放進去
- Binary Search一定要練習
- **第十章 Recursive 以後會是個門檻**
### 1122. Relative Sort Array
## Recursive(top-down)
### 1+2+...n
- 會錯，為什麼?
```
Sum(n) := Sum(n-1) + N
Sum(3) = Sum(2) + 3
= Sum(1) + 2 + 3
= Sum(0) + 1 + 2 + 3
= Sum(-1) + 1 + 2 + 3
```
- 需要給終止條件
```
Sum(n) := Sum(n-1) + N , N > 1
:= 1 , N =1
Sum(3) = Sum(2) + 3
= Sum(1) + 2 + 3
= 1 + 2 + 3
```
- C++ sample code
```C++
int Sum(int n){
if(n>1) return Sum(n-1) + n;
if(n==1) return 1;
}
```
- 習慣上的寫法
```C++
int Sum(int n){
if(n==1) return 1;
return Sum(n-1) + n;
}
```
### Extend
- 因為通常不知道N的上界，所以偏好越來越小的下界，但是這也是不一樣的思路:
```C++
// Sum(N) := Sum(N+1) - (N+1)
// Sum(N) := 5050 , N = 100;
//
int Sum(N)(int N){
if(N==100) return 5050;
return Sum(N+1) - (N+1)
}
cout<< Sum(10) << endl;
```
:::info
- 所以你一次**跳兩格**，就會有**兩個邊界條件**!
- 要先推出數學定義規則，再去寫recursive 。
- 別人看很難懂，因為他不知道你怎麼推導的。
```C++
// Sum(N) := Sum(N-2) + (N-1) + N
// Sum(1) = 1 , N = 1
// Sum(2) = 3 , N = 2
int Sum(int N){
if(N == 1) return 1;
if(N == 2) return 3;
return Sum(N-2) + (N-1) + N;
}
```
:::
### 求解過程
- 本身是一個樹狀，會有先後順序的問題，但是答案不會變。
- 想要變快
- 把算過的結果存起來。
## Mermorize(記憶法)
- 如果N已經算過了，就直接回傳之前的答案。
- 如果N還沒算過，就遞迴算，但是記得把答案記起來。
- unordered_map find an insert o(1)
```C++
unodered_map<int, int> cache; // N => f(N), cache[N] == f(N)
inf f(int N){
if(N == 1) return 1;
if(N == 2) return 2;
if(cache.find(N) != cache.end())
return cache[N];
// 下面這段不會每次都執行
cache[N] = f(N-1) + f(N-2);
return cache[N];
}
```
## DP(bottom up)
- 拿掉if的檢查
- 1.先寫邊界條件 `cache[1] = 1, cache[2] = 2`
- 2.慢慢的逼近條件 `for(int i=3; i<=N ; i++)`
```C++
vector<int, int> cache(N+1);
inf f(int N){
cache[1] = 1;
cache[2] = 2;
for(int i=3; i<=N ; i++){
cache[i] = cache[i-1] + cache[i-2];
}
return cache[N];
}
```
### 如何節省memory ?
```
now = two + one
now = two + one
```
## Dynamic Programming(Bottom up)
### Concept
### 198. House Robber
- 正攻法很難寫
- 把所有的搶法列出來 **2^n**:
- 排容原理
``` 2^n - 扣掉不符合條件的 ```
- DP分**搶**或**不搶**誰可以拿到比較大的值。
#### Recursive
- 兩個fn，需要兩個邊界條件。
#### Memorize
- unodered_map
#### DP
- 用到的算出來(bottom up)
- 節省空間
### 121 Best Time to Buy and Sell Stock
:::info
精神:只要考慮最後一天，可以做不同決定要怎麼算。
:::
#### recursive
```C++
class Solution {
public:
int maxProfit(vector<int>& prices) {
const int N = prices.size();
if(N==0) return 0;
return maxProfit(prices, N-1);
}
int maxProfit(vector<int>& prices, int i) {
if(i==0) return 0;
int min = *min_element(prices.begin(), prices.begin()+i);
return max(prices[i]-min, maxProfit(prices, i-1));
}
};
```
#### cache
```C++
class Solution {
public:
int maxProfit(vector<int>& prices) {
const int N = prices.size();
if(N==0) return 0;
return maxProfit(prices, N-1);
}
unordered_map<int,int> cache;
int maxProfit(vector<int>& prices, int i) {
cache[0] = 0;
if(i==0) return cache[0];
for(int k=1; k<=i; k++){
int min = *min_element(prices.begin(), prices.begin()+k);
cache[k] = max(prices[k]-min, cache[k-1] );
}
return cache[i];
}
};
```
#### DP
```C++
int maxProfit(vector<int>& prices) {
const int N = prices.size();
if(N==0) return 0;;
vector<int> cache(N);
cache[0] = 0;
for(int k=1; k<=N-1; k++){
int min = *min_element(prices.begin(), prices.begin()+k);
cache[k] = max(prices[k]-min, cache[k-1] );
}
return cache[N-1];
}
```
#### Save Memory
```C++
```
#### Practices DP
392.Is Subsequence
338.Counting Bits
# 12/8
## 1137. N-th Tribonacci Number
The Tribonacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.
:::info
有幾個function就有幾個終止條件
:::
### Recursive
- 答案對，但是會 Time Limit Exceeded
```C++
int tribonacci(int n) {
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 1;
return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
}
```
### Cache(Memorize)
用unordered_map開table，去記憶我們算過的結果。
- 用count()函式
```C++
unordered_map<int, int> cache;
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 1;
// n does not exist in map?
if(cache.count(n) == 0){
cache[n] = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
}
return cache[n];
```
- 也可以用itreator
```C++
// n does not exist in map?
auto p = cache.find(n);
if(p == cache.end()){
cache[n] = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
}
}
```
### DP
- 最終連空間都需要優化
```C++
int tribonacci(int n) {
if(n==0) return 0;
int k3 = 0 ;
if(n==1) return 1;
int k2 = 1;
if(n==2) return 1;
int k1 = 1;
int answer;
for(int i =3; i <=n; i++){
answer = k3 + k2 + k1;
k3 = k2;
k2 = k1;
k1 = answer;
}
return answer;
}
```
### 746. Min Cost Climbing Stairs
## queue
## Stack
### Valid Parentheses
- 遇到左邊的符號，就產生一個tree node。
- 遇到右邊的符號，就把node的符號填完，之後回去parent。
### 語法樹
- 後來發現用stack就可以把tree走完，就不需要真的畫樹了。
#### Practices Stack
1047.Remove all Adjacenct Duplicates in String
844.Backspace String Compare
1021.Remove Outermost Parentheses
682.Baseball Game
496.Next Greater Element I
## 回朔法 Backtracking
### BinaryRepresentation
- 函式呼叫本質就是複製貼上。
- 
### House Rober again
### 可以準備問題問老師 ^皿^
# 12/14
## Ch15. backtracking
## House Robber
- 先用二進制列出全部可能( backtracking
- 把相鄰的case全部砍掉
- 巢狀迴圈
- 搜尋的深度由程式碼決定
- 不容易彈性改變或處理很深的問題
- 用recursive
- 用stack + for (DFS)
- 用queue + for (BFS)
### Recursive
```C++
for(int i=0; i<=1; i++){
for(int j=0; j<=1; j++){
for(int k=0; k<=1; k++){
cout<< i << j << k << endl;
}
}
}
```
```C++
void f(vector<int> v){
for(v[0]=0; v[0]<=1; v[0]++){
for(v[1]=0; v[1]<=1; v[1]++){
for(v[2]=0; v[2]<=1; v[2]++){
cout<< v[0] << v[1] << v[2] << endl;
}
}
}
}
int main(){
vector<int> v(3);
f(v);
}
```
```C++
void f(vector<int> v, int i){
if(i== (int)v.size()){
for(auto e:v)
cout<<e;
cout<<"\n";
// Don't forget it
return;
}
for(v[i]=0; v[i]<=1; v[i]++){
f(v,i+1);
}
}
int main(){
vector<int> v(3);
f(v,0);
}
```
### 展開for步驟
```C++
vector<int> v(3);
for(v[0]=0; v[0]<=1; v[0]++){
f(v,0+1);
}
```
```C++
vector<int> v(3);
for(v[0]=0; v[0]<=1; v[0]++){
for(v[1]=0; v[1]<=1; v[1]++){
f(v,1+1);
}
}
```
```c++
vector<int> v(3);
for(v[0]=0; v[0]<=1; v[0]++){
for(v[1]=0; v[1]<=1; v[1]++){
for(v[2]=0; v[2]<=1; v[2]++){
f(v,2+1);
}
}
}
```
- 在 v.size()==3 停止
```c++
vector<int> v(3);
for(v[0]=0; v[0]<=1; v[0]++){
for(v[1]=0; v[1]<=1; v[1]++){
for(v[2]=0; v[2]<=1; v[2]++){
for(auto e:v)
cout<<e;
cout<<"\n";
}
}
}
```
### 改1,2,3排列(Permutation)?
```C++
// 1 到3 中選一個
for(v[i]=1; v[i]<=3; v[i]++){
f(v,i+1);
}
```
### 更泛用?
```C++
// 1 到3 中選一個
for(int n: {3,7,5}){
v[i] = n;
f(v,i+1);
}
```
### 改組合(Combination)
- 加在條件內，但是time complexity不變
```C++
void f(vector<int> v, int i){
if(i== (int)v.size()){
if(v[0]==v[1] || v[1] ==v[2] || v[0]==v[2])
return;
for(auto e:v)
cout<<e;
cout<<"\n";
// Don't forget it
return;
}
// 1 到3 中選一個
for(int n: {3,7,5}){
v[i] = n;
f(v,i+1);
}
```
### 剪枝 Pruning
- 剪枝，我們不要無條件呼叫遞迴。
- find()
### 改a b c組合
```C++
for(auto n:{a,b,c,d,,e}){
if(count(begin(v),begin(v)+i,n)!=0)
continue;
v[i] = n;
f(v,i+1)
}
```
## 有o(n)的演算法嗎?
### C++ STL next_permutation()
- 使用前一定要先排好序
- 發現是**遞增**就會**停止**
```C++
vector<int> v = {2,4,7,8,9};
// we have to sort it!
sort(begin(v), end(v));
do{
for(char n:v){
cout<< n << " ";
}
cout<<endl;
}while(next_permutation(begin(v),end(v)))
```
### bitset
```C++
for(int i=0; i<0; i++){
cout << bitset<3>(i) <<endl;
}
```
## Ch16 Greedy 貪心法
- 這其實是數學的領域，最常用**反證法**。
- 比賽時通常是先想一個做法，如果找不到反例，就是答案。
:::info
每次選都直接考慮最好的選擇，迭代到最後變成是全部最好的選擇。
- 真的這麼簡單? 我們怎麼知道現在犧牲一點將來不會變更好?
- 很直覺，好實作，但是不好證明。
:::
### Best Time to Buy and Sell Stock II
- Diff相鄰兩元素，如果是正值，就累加。
#### Practices Greddy
122.Best time to Buy and Sell Stock II
1029.Two City Scheduling
1005.maximize Sum of Array After K Negations
455.Assign Cookies
561.Array Partition I
944.Delete columns to Make Sorted
## leetcode以外的世界
- 要自己處理input, output
## ch17.回顧
### DS
- Vector
- Linked List
- Tree
- Map
### Algo
- Divide and Conquer
- recursive
- Tree
- Sort
- 同一件事 可以用不同角度思考
- 求最大最小也是一種排序
- 不要只會某種寫法 同一題要有很多方法 選其中一個
- Binary Sarch
- Dynamic Programming
- Backtracking
- Greedy
### C++
- 每三年改版一次 真的超難
- 大部分人都只會皮毛
- 之後無法登入 在寄信給老師 說自己的名單322?
- google面試要leetcode 4題可以全部都寫出來
Google Drive
Gist
Clipboard
Sign in with Wallet
