STL

1. vector

會自動allocate memory的array

example

vector<int> vec;
vec.push_back(2);
cout << vec[0] << endl; //2
int lastElement = vec.back(); //2
vec.pop_back(); //vec become empty

可以一開始先allocate好一些空間, 並給予init value

vector<int> initWithOne(10, 1); //size = 10, value = 1

也可以是nested

vector<vector<int>> twoDimVec;

應用: 存Graph
例如說有一堆edge存在 vector\<int\> edges, 以及node數量n, 我們可以轉成Adj list

void SomeGraphProblem(vector<vector<int>> edges, int n)
{
vector<vector<int>> Graph(n); //allocate n vectors
for(auto edge : edges)
{
//Assume graph is undirected
Graph[edge[0]].push_back(edge[1]);
Graph[edge[1]].push_back(edge[0]);
}
}

STL的element通常都可以混合使用, 比如說

vector<unordered_map<int, int>> hashMapVec(n);

應用: DP, 當state不一定都在整數, 或者數字可能過大
https://leetcode.com/problems/target-sum/description/

class Solution {
public:
vector<unordered_map<int, int>> index2Target2Ans;
int CountWays(vector<int>& nums, int target, int curIndex)
{
int n = nums.size();
if(curIndex == n && target == 0)
{
return 1;
}
if(curIndex == n)
{
return 0;
}
if(index2Target2Ans[curIndex].find(target) != index2Target2Ans[curIndex].end())
{
return index2Target2Ans[curIndex][target];
}
int plus = target - nums[curIndex];
int minus = target + nums[curIndex];
return index2Target2Ans[curIndex][target] = (CountWays(nums, plus, curIndex + 1) + CountWays(nums, minus, curIndex + 1));
}

int findTargetSumWays(vector<int>& nums, int target) {
index2Target2Ans.resize(nums.size());
return CountWays(nums, target, 0);
}
};

2. queue

宣告, 同樣可塞其他STL/Type

queue<int> intQueue;
queue<pair<int,int>> pairQueue;
queue<vector<int>> vecQueue;
queue<TreeNode*> treeNodeQueue;

Member function

queue<int> intQueue;
intQueue.push(1);
intQueue.push(2);
intQueue.push(3);
while(!intQueue.empty()) //intQueue.size() > 0
{
int cur = intQueue.front();
intQueue.pop();
cout << cur ;
}
// 1, 2, 3

應用: BFS

example1. BFS on tree
https://leetcode.com/problems/binary-tree-level-order-traversal/

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> leverOrderResult;
if(!root)
{
return leverOrderResult;
}
queue<TreeNode*> NodeQueue;
NodeQueue.push(root);

while(!NodeQueue.empty())
{
queue<TreeNode*> nextRoundQueue;
vector<int> curLevel;
while(!NodeQueue.empty())
{
TreeNode* cur = NodeQueue.front();
NodeQueue.pop();
curLevel.push_back(cur->val);
if(cur->left)
{
nextRoundQueue.push(cur->left);
}
if(cur->right)
{
nextRoundQueue.push(cur->right);
}
}
leverOrderResult.push_back(curLevel);
NodeQueue = nextRoundQueue;
}
return leverOrderResult;
}
};

example2. BFS on graph/state
https://leetcode.com/problems/keys-and-rooms/

class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
int n = rooms.size();
vector<vector<int>> graph(n);
for(int i = 0 ; i < n ; i++)
{
vector<int> &keys = rooms[i];
for(int key : keys)
{
graph[i].push_back(key);
}
}

queue<int> roomQueue;
roomQueue.push(0);
vector<bool> visted(n, false);
visted[0] = true;
int roomRemain = n;
while(!roomQueue.empty())
{
int curRoom = roomQueue.front();
roomQueue.pop();
roomRemain --;
for(int nextRoom : graph[curRoom])
{
if(!visted[nextRoom])
{
visted[nextRoom] = true;
roomQueue.push(nextRoom);
}
}
}
return roomRemain == 0;

}
};

3. stack

宣告

stack<int> intStack;
stack<pair<int,int>> pairStack;

Member function

stack<int> intStack;
intStack.push(1);
intStack.push(2);
intStack.push(3);
while(!intStack.empty())
{
int cur = intStack.top();
intStack.pop();
cout << cur;
}
//3 2 1

應用:monotonic stack
在一個array中, 往左/右找第一個比自己大/小的

以Next Greater Element I為例, 題目要求:
對於每個nums1的數, 找到他在nums2裡面, 第一個往右找比他大的數
我們可以用一個hash map: unordered_map<int, int> num2NextGreater來存在nums2中
每個數, 第一個往右比較更大的數字為何

比如說nums2 = [1,3,4,2]
1往右比第一個比他大的是3
3往右比第一個比他大的是4
4往右比找不到比他大的數字, 依照題目要求, 答案為-1
2有右比找不到更大, 答案為-1

我們可以maintain一個stack, 從array的右邊開始掃, 如果目前stack最上方的數字
比目前看到的數字小, 則我們從stack pop該數字, 最後再push目前的數字
跑一下上面的範例
i = 3, original stack = [] , updated stack = [2]
i = 2, original stack = [2], stack = [4]
i = 1, original stack = [4], 此時在我們發現3無法讓4 pop出去, 這代表從右掃過來, 4是第一個比3大的數字, stack = [4,3]
i = 0, original stack = [4,3], 此時我們發現1無法讓3 pop出去, 這代表從右邊掃過來, 3是第一個比1大的數字
stack = [4,3,1]

我們發現最後stack的內容是單調的

https://leetcode.com/problems/next-greater-element-i/

class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> num2NextGreater;
stack<int> monoStack;
int n = nums2.size();
for(int i = n - 1 ; i >= 0 ; i --)
{
while(!monoStack.empty() && nums2[i] > monoStack.top() )
{
monoStack.pop();
}
if(!monoStack.empty())
{
num2NextGreater[nums2[i]] = monoStack.top();
}
else
{
num2NextGreater[nums2[i]] = -1;
}
monoStack.push(nums2[i]);
}
vector<int> ret(nums1.size());
for(int i = 0; i < nums1.size() ; i++)
{
ret[i] = num2NextGreater[nums1[i]];
}
return ret;
}
};

4. unordered_map/map

unordered_map: implementation為hash, average O(1), key必須能算hash
map: implementation為red-black tree, O(logn), key必須能比大小

map的用法會跟vector/array類似, 都是用operator [] , 但vector/array的[]代表offset,
map的[]代表access/update某個key

宣告

unordered_map<int, int> num2num;
unordered_map<char, int> char2num;
unordered_map<string, int> string2num;
unordered_map<int, string> num2string;

Member function

num2string[5] = "abcdefg";
num2num[0] = 5;
if(num2num.find(2) == num2num.end())
{
cout << "Key 2 not exist\n";
}

if(num2num.find(5) == num2num.end())
{
cout << "Key 5 not exist\n";
} //Will NOT output this line, find based on key

num2num.erase(2) // Remove key 2 from map

應用: DP存state (參考vector)

應用: 用string當成key
https://leetcode.com/problems/group-anagrams/

class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> ana2Group;
for(string &str : strs)
{
string tmp = str;
sort(tmp.begin(), tmp.end());
ana2Group[tmp].push_back(str);
}
vector<vector<string>> ret;
for(auto it : ana2Group)
{
ret.push_back(it.second);
}
return ret;
}
};

應用: 用char當成key
https://leetcode.com/problems/longest-substring-without-repeating-characters/

class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> word2Count;
int n = s.size();
int left = 0;
int ans = 0;
for(int i = 0 ; i < n ; i++)
{
if(word2Count.find(s[i]) == word2Count.end())
{
word2Count[s[i]] = 1;
}
else
{
word2Count[s[i]] ++;
}
while(word2Count[s[i]] > 1)
{
word2Count[s[left]] --;
left ++;
}
ans = max(ans, i - left + 1);
}
return ans;
}
};

應用: 把pointer to list node當key
https://leetcode.com/problems/copy-list-with-random-pointer/description/

class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node*> old2New;
Node* oldCur = head;
Node* newHead = nullptr;
while(oldCur != nullptr)
{
Node* curRandom = oldCur->random;
Node* curNext = oldCur->next;
Node* newCur = nullptr;
Node* newRand = nullptr;
Node* newNext = nullptr;
if(old2New.find(oldCur) == old2New.end())
{
newCur = new Node(oldCur->val);
old2New[oldCur] = newCur;
}
if(curRandom && old2New.find(curRandom) == old2New.end() )
{
newRand = new Node(curRandom->val);
old2New[curRandom] = newRand;
}
if(curNext && old2New.find(curNext) == old2New.end())
{
newNext = new Node(curNext->val);
old2New[curNext] = newNext;
}
newCur = old2New[oldCur];
newRand = old2New[curRandom];
newNext = old2New[curNext];
newCur->next = newNext;
newCur->random = newRand;
if(!newHead)
{
newHead = newCur;
}
oldCur = oldCur->next;
}
return newHead;
}
};

5. set/unordered_set

與map/unordered_map類似, 只是只有key, 沒有value

宣告

unordered_set<int> intSet;
unordered_set<char> charSet;
unordered_set<string> strSet;

Member function

intSet.insert(0);
if(intSet.find(0) != intSet.end())
{
cout <<Key 0 found\n";
}//Will output

intSet.erase(0);
if(intSet.find(0) == intSet.end())
{
cout <<Key 0 not exist\n";
}//Will output

應用: Contain duplicated: 檢查一個array是否有重複數字

https://leetcode.com/problems/contains-duplicate/description/

class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> existedNums;
for(auto num : nums)
{
if(existedNums.find(num) != existedNums.end())
{
return true;
}
existedNums.insert(num);
}
return false;
}
};

6. priority_queue

Heap, O(logn) insert, delete, O(1) check top element.

宣告

priority_queue<int> MaxPQ; //Max heap

參數:
1. 要存的data type (int)
2. 底層的資料結構 vector<type>
3. comparetor, default: less, 要把它變成min heap要用greater<int>
priority_queue<int, vector<int>, greater<int> > MinPQ; //Min Heap

如果要存類似 (value, index) 這樣的pair
可以用pair<int, int>, 並且將value放在pair的第一個
priority_queue<pair<int, int>> MaxPQ;
priority_queue<pair<int, int>, vector<pair<int,int>, greater<pair<int,int>> > MinPQ;

Member function

MaxPQ.push(1);
MaxPQ.push(8);
MaxPQ.push(5);
while(!MaxPQ.empty())
{
int curMax = MaxPQ.top();
cout << curMax << " ";
MaxPQ.pop();
} //8, 5, 1

應用: TOP-k相關問題

https://leetcode.com/problems/top-k-frequent-elements/
1. 用一個hash map存所有element出現次數
2. apporoach 1: 用出現次數sort -> nlogn
3. apporoach 2: maintain一個min heap, 只保留前K個最大的.

當目前heap size >= k, 比較下一個number跟目前heap的top(目前最小值),

決定是否把heap的top刪除並加下一個number -> nlogk

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> number2Count;
for(int num : nums)
{
number2Count[num] ++;
}
vector<int> uniqueNums;
for(auto it : number2Count)
{
uniqueNums.push_back(it.first);
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > PQ;
int n = uniqueNums.size();
for(int i = 0 ; i < n; i++)
{
int curNum = uniqueNums[i];
int curFreq = number2Count[curNum];
if(PQ.size() >= k)
{
if(PQ.top().first < curFreq)
{
PQ.pop();
PQ.push({curFreq, curNum});
}
}
else
{
PQ.push({curFreq, curNum});
}
}
vector<int> ret;
while(!PQ.empty())
{
ret.push_back(PQ.top().second);
PQ.pop();
}
return ret;
}
};

應用: Sliding window maximum
https://leetcode.com/problems/sliding-window-maximum/description/

給一個window size, window一直向右, 求每個時間點的最大值

* maintain一個max heap
* 先加入前k個number
* 在window滑行中, 檢查目前最大的是否已經不在window內 -> index <= i - k
* 加入下一個number
* 檢查目前heap最大值
*

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
priority_queue<pair<int,int>> PQ;
int n = nums.size();
for(int i = 0 ; i < k ; i++)
{
PQ.push({nums[i] , i});
}
vector<int> ret;
ret.push_back(PQ.top().first);
for(int i = k ; i < n; i++)
{
while(!PQ.empty() && PQ.top().second <= (i - k))
{
PQ.pop();
}
PQ.push({nums[i], i });
ret.push_back(PQ.top().first);
}
return ret;
}
};

應用:最短路徑Dijkstra/ 最小生成樹Prim's algorithm

7. deque

Dobule-end queue, 可以從前後push/pop

Member function

deque<int> dq;
dq.push_back(0); //0
dq.push_front(1); //1 0
dq.push_back(2); // 1 0 2
dq.push_front(3); // 3 1 0 2
dq.pop_front(); // 1 0 2
dq.pop_back(); // 1 0

應用: sliding window maximum, 題目敘述與priority_queue提到的相同, 但這次我們加入monotonic stack的做法.
https://leetcode.com/problems/sliding-window-maximum/description/

1 先加入前k個element, 當目前DQ後面有比要加入的element小的, pop back, 這樣DQ的擺放順序就會由大到小, front為目前window最大的
2 每次window滑動時, 檢查最前面的element是否已經不在window內
3 每次加入新element前, pop back掉所有比他小的
4 檢查DQ最前面的element, 就是目前window的最大值

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> DQ;
vector<int> ret;
for(int i = 0 ; i < k ; i++)
{
while(!DQ.empty() && nums[DQ.back()] < nums[i] )
{
DQ.pop_back();
}
DQ.push_back(i);
}
ret.push_back(nums[DQ.front()]);
for(int i = k ; i < n; i++)
{
while(!DQ.empty() && DQ.front() <= i - k)
{
DQ.pop_front();
}
while(!DQ.empty() && nums[DQ.back()] < nums[i] )
{
DQ.pop_back();
}
DQ.push_back(i);
ret.push_back(nums[DQ.front()]);
}
return ret;
}
};

8. string

宣告

string emptyStr = "";
string someValueStr = "abcdefg";

Member function (usage)

string curStr = "";
for(char c = 'a' ; c <= 'd' ; c++)
{
curStr += c;
} //abcd

/*
s.substr(pos, len)
pos: starting index to get substring
len: length of substring
*/

string sub = curStr.substr(0, 2); //ab

curStr.push_back('e'); //abcde
curStr.pop_back(); //abcd

int num1 = stoi("123456"); //stoi: string to integer
string num1_str = to_string(num1); //number to string

應用: 字串處理相關問題

9. Iterator

Iterator是一種object, 可以先理解為一種比較特別的指標(運算類似)

在C++一些對於container內建的algorithm, return value常常是iterator.

vector<int> vec;
for(int i = 0 ; i < 5 ; i++)
{
vec.push_back(i);
} //0 1 2 3 4

//Traverse container using iterator
for(auto it = vec.begin() ; it != vec.end() ; it ++)
{
cout << *it << " ";
}// 0 1 2 3 4

//Find specific element
//If element not existed, vec.end() will be the return value
auto it = find(vec.begin(), vec.end(), 2);
if(it != vec.end())
{
cout << *it << endl; //2
}

//Use iterator as member function argument
vec.erase(it); //0 1 3 4