1.2 第二階段-常用算法技巧
第一階段主要是幫小伙伴們熟悉了基本的數(shù)據(jù)結(jié)構(gòu)，第二階段我們的關(guān)注點(diǎn)在于怎么利用這些數(shù)據(jù)結(jié)構(gòu)去解決面試題目惩琉。這個過程中小伙伴們會看到一些常用的解題“套路”荷辕，學(xué)會這些“套路”會一定程度上提升你的解題效率。
- Note 第二階段我們先出給代碼，再用實(shí)例去解釋，小伙伴們可以嘗試先自己閱讀分析下代碼喷舀，希望通過這階段學(xué)習(xí)，能提升小伙伴們讀懂代碼的能力。
暴力搜索元咙，先排序（sort ）和 哈希表Hash table（unordered_set）
217. Contains Duplicate
判斷一個整數(shù)數(shù)組是否包含重復(fù)元素梯影，包含返回true巫员，否則返回false
重新回憶下217的解題思路：
（1）題目要求尋找數(shù)組中的循環(huán)元素庶香，按照一般思路，我們自然會想到從數(shù)組第一個元素開始循環(huán)比較简识，窮舉情況來看是否有符合題目要求的組合赶掖。循環(huán)遍歷窮舉可能性這就是一種暴力搜索的算法思想。
（2）在優(yōu)化部分七扰，分析發(fā)現(xiàn)數(shù)組本身的無序?qū)е铝艘秒p重循環(huán)O(N^2)才能完成窮舉奢赂。如果數(shù)組是有序狀態(tài)，那么窮舉可以在一遍循環(huán)O(N)就完成颈走，這樣就大大節(jié)省了搜索時間膳灶。所以在一些情況下，處理前先排序也是一種算法技巧立由，能提高暴力搜索的效率轧钓。
（3）現(xiàn)在我們介紹第三種做法，利用基于哈希表實(shí)現(xiàn)的unorderd_set容器來處理
- C++ 11中對unordered_set描述大體如下：無序集合容器（unordered_set）是一個存儲唯一(unique锐膜，即無重復(fù)）的關(guān)聯(lián)容器（Associative container）毕箍，容器中的元素?zé)o特別的秩序關(guān)系，該容器允許基于值的快速元素檢索道盏，同時也支持正向迭代而柑。
- 在一個unordered_set內(nèi)部，元素不會按任何順序排序荷逞，而是通過元素值的hash值將元素分組放置到各個槽(Bucker媒咳，也可以譯為“桶”），這樣就能通過元素值快速訪問各個對應(yīng)的元素（均攤耗時為O（1））种远。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if(nums.size() <= 1)
return false;
unordered_set<int> temp;
for(int i = 0; i < nums.size(); ++i)
{
//利用unordered_set的count方法可以判斷當(dāng)前元素是否已經(jīng)在容器中
if(temp.count(nums[i]) != 0)
return true;
else
//將元素放到容器中
temp.insert(nums[i]);
}
return false;
}
};
以5,6,7,6為例
（1）i=0時涩澡，temp中找不到5（nums[0），將5放到temp中
（2）i=1時院促，temp中找不到6筏养，temp中包含5,6
（3）i=2時，temp中找不到7常拓，temp中包含5,6,7
（4）i=3時渐溶，temp中找到了6，直接返回true
哈希表Hash table（unordered_map）
除了unordered_set弄抬，還有一種更為常用的基于哈希表的數(shù)據(jù)結(jié)構(gòu)unordered_map
- 無序映射表（Unordered Map）容器是一個存儲以鍵值對組合而成的元素的關(guān)聯(lián)容器（Associative container）茎辐，容器中的元素?zé)o特別的次序關(guān)系。該容器允許基于主鍵地快速檢索各個元素。
1. Two Sum
給一個數(shù)組和一個目標(biāo)值target拖陆，要求在數(shù)組中找到兩個元素相加等于target弛槐，返回這兩個元素的下標(biāo)。我們可以假設(shè)每個數(shù)組只有一個解依啰。
例如：
nums = [2, 7, 11, 15], target = 9乎串，
nums[0] + nums[1] = 2 + 7 = 9，
return [0, 1].
能直接想到的解題思路類似做過的217題目速警，可以用暴力搜索來解決：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
if(nums.size() < 2)
return nums;
for(int i=0; i < nums.size();++i)
{
for(int j=i+1; j < nums.size(); ++j)
{
if(nums[i] + nums[j] == target)
{
result.push_back(j);
result.push_back(i);
return result;
}
}
}
}
};
來一起看下unordered_map解題思路叹誉。仍舊以2, 7, 11, 15（下標(biāo)依次為0,1,2,3）為例：
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target)
{
unordered_map<int, int> hash;
vector<int> result;
for (int i = 0; i < numbers.size(); i++) {
int numberToFind = target - numbers[i];
if (hash.count(numberToFind) != 0) {
result.push_back(hash[numberToFind]);
result.push_back(i);
return result;
}
hash[numbers[i]] = i;
}
return result;
}
};
（1）ordered_map中的key是數(shù)組中的元素，value是元素對應(yīng)的下標(biāo)闷旧，例如2是key长豁，0是value
（2）i = 0時候，numberToFind =9-2 = 7忙灼，hash里沒有key為7的元素匠襟，所以把鍵值對（2---0）放入hash
（3）i = 1時候，numberToFind = 9-7 = 2该园，hash里通過count方法查到有key為2的元素酸舍，并且知道2對應(yīng)的索引為0，至此把找到的索引放入vector中
Tow Pointers（輔助指針）
167. Two Sum II - Input array is sorted（類似題目還有141）
上面那道1.Tow Sum題目的衍生題目爬范，數(shù)組變?yōu)樯蚺帕懈竿螅页鰞蓚€元素和等于target，并返回元素的下標(biāo)（從1開始青瀑，而不是從0開始）璧亮，題中限定只有一個解。
例子：
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l = 0, r = numbers.size() - 1;
while (l < r) {
int sum = numbers[l] + numbers[r];
if (sum == target) return {l + 1, r + 1};
else if (sum < target) ++l;
else --r;
}
return {};
}
};
以2,7,11,15為例
（1）l=0斥难，r=3枝嘶，sum=2+15=17，17>9哑诊，r=2
（2）l=0群扶，r=2，sum=2+11=13镀裤，13>9竞阐，r=1
（3）l=0，r=1暑劝，sum=2+7=9骆莹，9==9，return 0+1,1+1
怎樣應(yīng)對IT面試與筆試-（一）
怎樣應(yīng)對IT面試與筆試-（二）
怎樣應(yīng)對IT面試與筆試-（三）
怎樣應(yīng)對IT面試與筆試-（四）
怎樣應(yīng)對IT面試與筆試-（五）
怎樣應(yīng)對IT面試與筆試-（五-1）
怎樣應(yīng)對IT面試與筆試-（六）
怎樣應(yīng)對IT面試與筆試-（七）
怎樣應(yīng)對IT面試與筆試-（八）
怎樣應(yīng)對IT面試與筆試-（九）
怎樣應(yīng)對IT面試與筆試-（十）
怎樣應(yīng)對IT面試與筆試-（十一）
怎樣應(yīng)對IT面試與筆試-（十二）
怎樣應(yīng)對IT面試與筆試-（十三）
怎樣應(yīng)對IT面試與筆試-（十四）
怎樣應(yīng)對IT面試與筆試-（十五）
怎樣應(yīng)對IT面試與筆試-（十六）
