Binary Search 二分法
374. Guess Number Higher or Lower 猜數(shù)字大小
有人會在1至n之間選一個數(shù)字悴务，你來根據(jù)那個人的提示猜數(shù)字，那個人返回-1铲掐，說明我們猜的小了 拾弃，1說明猜大了，0說明我們找到了那個數(shù)組
“那個人”在題目里用函數(shù)guess(int num) 表示
使用到的思想：二分法
class Solution {
public:
int guessNumber(int n) {
if (guess(n) == 0) return n;
int left = 1, right = n;
while (left < right)
{
int mid = left + (right - left) / 2, t = guess(mid);
if (t == 0) return mid;
else if (t == 1) left = mid;
else right = mid;
}
return left;
}
};
33. Search in Rotated Sorted Array 在旋轉(zhuǎn)有序數(shù)組中搜索
給一個升序的數(shù)組摆霉，這個數(shù)組的一部分元素可能被旋轉(zhuǎn)：
例如 [0,1,2,4,5,6,7] 旋轉(zhuǎn)完后可能變?yōu)?[4,5,6,7,0,1,2]豪椿。
現(xiàn)在去查找給出的一個元素是否在數(shù)組中存在，存在則返回下標(biāo)携栋，否則返回-1.
使用到的數(shù)據(jù)結(jié)構(gòu)：vector
使用到的思想：二叉搜索
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
if (n == 0) return -1;
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) return mid;
//如果mid值小于right值搭盾，說明數(shù)組右半部分是遞增的，例如7 8 1 2 3 4 5 6
else if (nums[mid] < nums[right]) {
//如果target值為5婉支，則把left設(shè)置為mid+1
if (nums[mid] < target && nums[right] >= target)
left = mid + 1;
//如果target值為8鸯隅，則把right值設(shè)置為mid-1
else right = mid - 1;
//如果mid值大于right值，說明數(shù)組右半部分是有旋轉(zhuǎn)的磅摹，例如4 5 6 7 8 1 2
} else {
//這時如果target為4滋迈，把right設(shè)置為mid-1
if (nums[left] <= target && nums[mid] > target)
right = mid - 1;
//如果target為1，則把left設(shè)置為mid+1
else left = mid + 1;
}
}
return -1;
}
};
Hash Table 哈希表
49. Group Anagrams 分組錯位圖
將單詞進行分組户誓，不同單詞分在一組的依據(jù)是組成單詞的字母是一樣的饼灿，順序可以不一致。例如：
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
使用到的數(shù)據(jù)結(jié)構(gòu)：unordered_map
使用到的算法技巧：先排序
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string, vector<string>> mv;
for (int i= 0; i < strs.size(); ++i) {
string t = strs[i];
//將strs中的元素排序帝美，排序完的t作為key碍彭，原本的strs[i]作為value
sort(t.begin(), t.end());
mv[t].push_back(strs[i]);
}
//c++中一種遍歷map的快捷方式
for (auto a : mv) {
res.push_back(a.second);
}
return res;
}
};
如果不使用排序，我們就要把strs中的元素映射到一個26位的數(shù)組中悼潭，然后重新按照26位字母順序組成key值
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string> >res;
unordered_map<string,vector<string>> mv;
for(int i= 0; i < strs.size(); ++i)
{
vector<int> cnt(26,0);
string t = "";
for(char c: strs[i])
{
++cnt[c-'a'];
}
for(int d:cnt)
{
t += to_string(d)+"/";
}
mv[t].push_back(strs[i]);
}
for(auto a:mv)
{
res.push_back(a.second);
}
return res;
}
};
347. Top K Frequent Elements 前k個高頻元素
給一個整數(shù)數(shù)組庇忌，讓我們統(tǒng)計元素出現(xiàn)次數(shù)，并按出現(xiàn)次數(shù)從高到低排序舰褪，讓我們返回前k個頻次最高的元素皆疹。例如：
Given [1,1,1,2,2,3] and k = 2, return [1,2].
使用到的數(shù)據(jù)結(jié)構(gòu)：unordered_map priority_queue vector
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> um;
priority_queue<pair<int, int>> p;
vector<int> res;
for (auto a : nums)
++um[a];
for (auto it : um)
p.push({it.second, it.first});
for (int i = 0; i < k; ++i)
{
res.push_back(p.top().second);
p.pop();
}
return res;
}
};`
怎樣應(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面試與筆試-（十六）
