# Learning knowledge
###### tags: `Study_aboard`
## STL
https://www.geeksforgeeks.org/the-c-standard-template-library-stl/
STL can help implement data structures more easily
### Vector
```cpp
vector<> v(size, val) // Initialize
vector<> v({element}) // Initialize
vector.push_back // time complexity O(1)
vector.insert(position(iterator), val) // time complexity O(N)
sort(vector.begin(), vector.end())
vector<>::iterator it = find(vector.begin(), vector.end()) // it==vector.end() if not found
vector.clear() // clean the vector
```
### Unordered_map (HashMap)
Timing: $O(1)$ access time
```cpp
unordered_map<Key,T> m;
unordered_map<int,int> second = {{1,10},{2,20},{3,30}};// initialize
m->first // the key value
m->second // the mapped value
m.count(key) // find with a specific key, =0 if not found
m.erase ( m.begin() ); // erase by iterator
m.erase(m.begin()+3, m.end() ) // erase by a range of iterator
m.clear()
```
### Queue (BFS)
```cpp
queue<> q // Initialzie
q.front() // the top of a queue
q.pop() // pop out top element
q.push() // push to the end of the queue
```
### Priority Queue (Heap)
https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji/stl/priority
https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/
優先隊列，資料預設由大到小排序，大的資料會先被取出
- push
- top
- auto
- size
```cpp
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
```
Can define cmp by yourself
```cpp
example:
// use priority queue to implement min heap
auto cmp = [](ListNode*& a, ListNode*& b) {
return (a->val>b->val);
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp) > q(cmp);
//有時候難以得知一些物件的type，此時就可以透過auto或decltype來解決這個問題。
```
### Doubled linked list
[More Linked list stl](https://www.geeksforgeeks.org/list-cpp-stl/)
Timing: $O(1)$ remove time and add time
But hard to access it and uses extra memories
```cpp
list<pair<int, int>> l; // initialize
l.front()
l.back()
l.push_front(pair<int,int>) // push to the front
l.push_back(pair<int,int>) // push to the back
l.pop_front()
l.pop_back()
list<pair<int, int>>::iterator l.begin(),l.end(), l.rbegin(),l.rend()
l.reverse() // reverse the linked list
l.clear() // clean the linked list
l.splice
/*
*
* The splice() function can be used in three ways:
1.Transfer all the elements of list x into another list at some position.
2.Transfer only the element pointed by i from list x into the list at some position.
3.Transfers the range [first, last) from list x into another list at some position.
*/
list1_name.splice (iterator position, list2)
or
list1_name.splice (iterator position, list2, iterator i)
or
list1_name.splice (iterator position, list2, iterator first, iterator last)
```
### Iterator
Iterators are something which is used to point at the memory addresses of STL containers’ elements. Thus providing a means to access the data stored within the container and ability to modify them. They can be simply thought of as pointers.
**Syntax : container <data-type> :: iterator iterator_name;**
example:
```cpp
vector<int>::iterator it;
```
**Syntax : container <data-type> :: reverse_iterator iterator_name;**
example:
```cpp
vector<int>::reverse_iterator it;
```
```cpp
it = v.begin()
it = v.end()
it= v.rbegin()
it = v.rend()
/*
The r means reverse container
begin, rbegin ++
end, rend --
*/
example
for(it=vector.rbegin();it!=vector.rend();it++)
//this will iterate the vector by reverse order
```
### Auto
auto : x (vector) -> can iterate through x for(auto : x)
auto 可用於自動判定變數的聲明 ex: auto x = 1 -> equal to int x = 1
[auto reference](https://blog.gtwang.org/programming/cpp-auto-variable-tutorial/)
## Algorithm
### ==Divide and conquer==
1. divide problem into small problem and make sure they can obtain the same rule
2. conqure (recursively sovle the small problem)
3. merge small problem into the final answer
[reference](https://medium.com/brandons-computer-science-notes/divide-and-conquer-algorithms-4e83d9999ffa)
### ==Dynamic Programming==
Divide and conquer will generate same subproblems. To avoid extraneous computing, we have to remember the subproblem that we had done before, which is dynamic program.
#### Top-down or bottom up
Take fabonacci sequence as an example
F(n) = F(n-1) + F(n-2)
top-down : plus an memo array to remember things that had finish computing
```cpp
memo = {}
def fibonacci(n):
if n == 0 or n == 1:
return n
else:
if n in memo:
return memo[n]
else:
memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
return memo[n]
```
bottom-up :
add from F(1) to F(2) to F(1000)
```cpp
def fibonacci(n):
if n == 0 or n == 1:
return n
dp = [None for _ in range(n + 1)]
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
```
[reference](https://medium.com/@ryanyang1221/dynamic-programming-explanation-with-fibonacci-%E7%94%A8%E8%B2%BB%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B8%E5%88%97%E4%BE%86%E8%A7%A3%E9%87%8B%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83-8ce318601d0f)
### ==Binary search==
Timing : To search a sorted array
Complexity : $log{_2}{N}$
Specify left, right, mid, compare mid with the target and change right or left continuously (夾擊法)
[C++ code implementation](https://hackmd.io/@chentzj/S1efSWY0d#Binary-search-algorithm)
### ==KMP Algorithm==
https://binary-baba.medium.com/string-matching-kmp-algorithm-27c182efa387
https://www.youtube.com/watch?v=BXCEFAzhxGY&t=881s
objection: 加速尋找 substring p 在 string s 的位置
example:
s = adsgwadsxdsgwadsg , p = dsgwadsg
prefix: 從第一位開始的一串substring
suffix: 包含最後一位的substring
主要加速方法是當mismatch時，檢查match的字串中是否有prefix=suffix的可能，若有則可以從suffix開始做下一次的比較
檢查的方式是建立一個prefix, suffix table
table[i] : 1. 表 string 0~i suffix==prefix的長度 2. the repeated char's position
example: table[5] = dsgwad 's longest length of suffix and prefix = 1
三種可能情形，可見code
==若比對不相等 W[i]!= W[j]，從前一個相等的char的prefix來找==
[C++ code implement](https://hackmd.io/@chentzj/H1BHDRPfu#Implement-strStr)
### ==Topological sort==
Timing: Sorting orders for strange order things
Topological sort is only for DAG (directed acyclic graph). For every edge u->v, we out put node u before v
For Example:
405231 is a valid output, but 450231 is not
Topological sort can be implement by two ways, modified BFS and modified DFS
#### Modified DFS
The output order is decided by the number of outgoing edges. We start from nodes that do not have outgoing edges (0,1 in this case)
Therefore, we start from nodes with the least outgoing edges, and we do recursive to its outgoing edges and output them before the node.
An additional stl to record nodes that are visited already, so that we do not output same nodes again.
```cpp
// A C++ program to print topological
// sorting of a DAG
#include <iostream>
#include <list>
#include <stack>
using namespace std;
// Class to represent a graph
class Graph {
// No. of vertices'
int V;
// Pointer to an array containing adjacency listsList
list<int>* adj;
// A function used by topologicalSort
void topologicalSortUtil(int v, bool visited[],
stack<int>& Stack);
public:
// Constructor
Graph(int V);
// function to add an edge to graph
void addEdge(int v, int w);
// prints a Topological Sort of
// the complete graph
void topologicalSort();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
// Add w to v’s list.
adj[v].push_back(w);
}
// A recursive function used by topologicalSort
void Graph::topologicalSortUtil(int v, bool visited[],
stack<int>& Stack)
{
// Mark the current node as visited.
visited[v] = true;
// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
// Push current vertex to stack
// which stores result
Stack.push(v);
}
// The function to do Topological Sort.
// It uses recursive topologicalSortUtil()
void Graph::topologicalSort()
{
stack<int> Stack;
// Mark all the vertices as not visited
bool* visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function
// to store Topological
// Sort starting from all
// vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
// Print contents of stack
while (Stack.empty() == false) {
cout << Stack.top() << " ";
Stack.pop();
}
}
// Driver Code
int main()
{
// Create a graph given in the above diagram
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
cout << "Following is a Topological Sort of the given "
"graph \n";
// Function Call
g.topologicalSort();
return 0;
}
```
Sign in with Wallet
Connect another wallet