簡單記錄以下本周刷題用到的C++知識點和演算法，
知識點一：異或演算法 \(\bigoplus\)
概念
參與運算的兩個值，如果兩個相應位相同，則結果為0，否則為1，C++運算子號為 ^
比如
0^ 0=0， 1^ 0=1， 0^ 1=1， 1^1=0
性質
1.任何數和 0 做異或運算，結果仍然是原來的數，即 \(a \oplus 0=a\)，
2.任何數和其自身做異或運算，結果是 0，即 \(a \oplus a=0\)，
3.異或運算滿足交換律和結合律，即
\(a \oplus b \oplus a=b \oplus a \oplus a=b \oplus (a \oplus a)=b \oplus0=b\)
基于以上性質，看題目leetcode136
可以通過異或運算給定的陣列中的每一個元素，元素個數為2時，異或運算(\(\oplus\))得到結果為0
0與每一個元素進行異或運算結果為0，所以最終結果只剩下個數為1的元素，
知識點二：C++ STL 之哈希表(unordered_map)
參考博客C++ STL 之哈希表 | unordered_map
概述
哈希表是根據關鍵碼值(key value)而直接進行訪問的資料結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，這個映射函式叫做散列函式，
template:key和T是必須要有的，分別對應hashmap中的鍵和值
template < class Key, // unordered_map::key_type
class T, // unordered_map::mapped_type
class Hash = hash<Key>, // unordered_map::hasher
class Pred = equal_to<Key>, // unordered_map::key_equal
class Alloc = allocator< pair<const Key,T> > // unordered_map::allocator_type
> class unordered_map;
STL中，map 對應的資料結構是 紅黑樹，紅黑樹是一種近似于平衡的二叉查找樹，里面的資料是有序的，在紅黑樹上做查找操作的時間復雜度為 O(logN)，
unordered_map 對應哈希表，哈希表的特點就是查找效率高，時間復雜度為常數級別 O(1)， 而額外空間復雜度則要高出許多，所以對于需要高效率查詢的情況，使用 unordered_map 容器，而如果對記憶體大小比較敏感或者資料存盤要求有序的話，則可以用 map 容器，unorder_map是無序的，所以在C++中通常使用指標來定位，
用法
需要引入的頭檔案: <unordered_map>
\\C++
\\初始化
std::unordered_map<std::string, std::string> map = {{"key","value"}};
\\插入元素
map['key']=value; /*map初始化時回分配很大的空間*/
\\移出元素
map.erase(map.begin()); /*引數：指向map的指標*/
\\清空元素
map.clear();
\\查找元素：通過key查找，存在則回傳key對應的指標，不存在則回傳指向map的最后一個單元+1的指標(map.end())
map.find('key')
知識點三：vector<>容器
參考博客C++ vector 容器淺析
概述
可以簡單的認為，向量是一個能夠存放任意型別的動態陣列，類似于java、python中的陣列list，
用法
常用的用法
1.push_back()在陣列的最后添加一個資料
2.pop_back()去掉陣列的最后一個資料
3.size()當前使用資料的大小
4.reserve 改變當前vecotr所分配空間的大小，該方法沒有回傳值 ，
5.erase 洗掉指標指向的資料項
6.empty 判斷vector是否為空
7.clear 清空當前的vector
8.at()得到編號位置的資料
9.begin()得到陣列頭的指標
10.end()得到陣列的最后一個單元+1的指標
11.front()得到陣列頭的參考
12.back()得到陣列的最后一個單元的參考
13.swap 與另一個vector交換資料
知識點四：二分查找
概念
二分查找應用于已經排序之后的陣列，每次查找陣列中間的數，與待查找的數已經比較大小，陣列中間的數字的下標分為以下兩種情況：假設陣列長度為n;
(1) n為偶數時，中間數是 下標\((\frac{0+n}{2}-1)、(\frac{0+n}{2})\)兩者之和的平均值；
(2)n為奇數時，中間數是下標\(\frac{n+1}{2}\)的值，
例題：leetcode4
用法
時間復雜度：O(\(n\ln(n)\))
/*
*C++代碼的實作
*/
public binarySearch(vector<int> nums,int target)
{
int low = 0;
int high = num.size();
int mid = (low+high)/2
while(low<=nums.size()-1&&high<=nums.size()
&&low<=high)
{
mid = (low+high)/2
if(nums[mid]=target){return mid;}
else if(nums[mid]<target){
low = mid+1;
return low;}
else{
high = mid-1;
return high;}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/252419.html
標籤：C++