文章目錄
- 1、字母異位分組
-
- 題目
- 分析
-
- 複雜度
- 2、無重複字元的最長子串
-
- 分析
-
- 複雜度
- 3、重複的DNA序列（187）
-
- 題目
- 分析
-
- 複雜度
- 4、最小子覆寫串&找到字元串中的所有異位詞
-
- 題目
- 分析
-
- 複雜度
- 5、LRU緩存機制
-
- 題目
- 分析
-
- 複雜度
- 6、數組中重複的數字&缺失的第一個正數
-
- 分析
- 分析
-
- 複雜度
- 7、前K個高頻元素
-
- 題目
- 分析
-
- 複雜度
- 8、最長連續序列
-
- 題目
- 分析
-
- 複雜度
- 9、LFU
-
- 題目
- 分析
1、字母異位分組
題目
分析
本題可以維護一個map，儲存字元串和在輸出的vector中的下标，難點在于怎麼去确認字元是否在這一數組中。
關鍵在于存在map中的string，這裡我們存在裡面的應該排序後的字元串，然後把傳入的每個字元串先保留一個副本，然後排序了後在map中count。
複雜度
時間複雜度：O（n）
空間複雜度：O（n）
2、無重複字元的最長子串
分析
這題是很标準的hash題，關鍵在于這裡的 set 要以字元為鍵值。
維護一個指針 left 指向不重複子串的開始位置，當 right 移動到出現重複的字元處時就更新 left 的位置和 set 中的記錄，然後用 ret 記錄無重複子串長度，也即目前位置減 left 然後加1。如下所示：
int lengthOfLongestSubstring(string s) {
int n=s.size();
if(n==0) return 0;
unordered_set<char> us;
int left=0,right=0;
int ret=0;
while(right<n){
if(us.count(s[right])){
while(s[left]!=s[right]){
us.erase(s[left++]);
}
//因為這裡s[left]==s[right]，是以left應當再加1
++left;
}
else{
us.insert(s[right]);
}
ret=max(ret,right-left+1);
++right;
}
return ret;
}
複雜度
時間複雜度：O（n）
空間複雜度：O（n）
3、重複的DNA序列（187）
題目
分析
這裡先記錄下string的substr函數，他可以從指定位置截取指定長度的子字元串，如：
a就是s從i位置開始（包括他自己）截取長度為10的字元串。
這裡維護兩個hash_set，一個記錄每個子字元串，一個記錄重複的字元串，然後從頭開始周遊即可。
注：記錄重複的字元串的hash_set是很有必要的，因為如果遇到13個a，不進行查重的話，結果會輸出4個10個a的字元串。
複雜度
時間複雜度：O（n）
空間複雜度：O（n）
4、最小子覆寫串&找到字元串中的所有異位詞
題目
分析
下面這個老哥針對滑動視窗相關的題，提出了如下的解法，寫的相當好
https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-tong-yong-si-xiang-by-/
他為這個類型的題寫了一個模闆如下：
/* 滑動視窗算法架構 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入視窗的字元
char c = s[right];
// 右移視窗
right++;
// 進行視窗内資料的一系列更新
...
/*** debug 輸出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判斷左側視窗是否要收縮
while (window needs shrink) {
// d 是将移出視窗的字元
char d = s[left];
// 左移視窗
left++;
// 進行視窗内資料的一系列更新
...
}
}
}
以438題為例，代碼如下：
vector<int> findAnagrams(string s, string p) {
int n = s.size();
if(n==0||p.empty()) return {};
unordered_map<char, int> need, window;
for(int i=0;i<p.size();++i) ++need[p[i]];
int left = 0, right = 0, vaild = 0;
vector<int> out;
while (right < n) {
char c = s[right];
++right;
if (need.count(c)) {
++window[c];
if (window[c] == need[c]) ++vaild;
}
if (right - left == p.size()) {
char d = s[left];
if (vaild == need.size()) out.push_back(left);
++left;
if (window.count(d)) {
if (window[d] == need[d]) --vaild;
--window[d];
}
}
}
return out;
}
複雜度
時間複雜度：O（n）
空間複雜度：O（n）
5、LRU緩存機制
題目
分析
這題算是道人氣題目了，與其說是做題，倒不如說是在hash_map的基礎上創造出一個新的資料結構。這裡結合了hash_map的快速查找性和list的有序性。
在map中以key為鍵值，實值是list的疊代器，然後在list中存放一個由key和value組成的pair，如下圖：
hashmap應當以int和list的疊代器作為值建立，如下：
注意：
（1）因為連結清單是前閉後開的，即end指向最後一個節點的下一位，即end指向最後一個節點的下一個節點。是以插入應該放在開頭，因為在插入後要将疊代器存入map中，從首部插入，可直接傳回begin()函數。取出操作則在結尾執行。
（2）因為删除時需要從連結清單尾部的節點定位到map，是以list中應該儲存有key值。
複雜度
時間複雜度：O（1）
空間複雜度：O（n）
6、數組中重複的數字&缺失的第一個正數
分析
分析
這兩題都使用了原地哈希的方法，即把數組視為哈希表。
1）由于數組元素的值都在指定的範圍内，這個範圍恰恰好與數組的下标可以一一對應。
2）看到數值，就可以知道它應該放在什麼位置，這裡數字nums[i] 應該放在下标為 i 的位置上，這就像是我們人為編寫了哈希函數。
3）找到重複的數就是發生了哈希沖突。
數組中重複的數字
代碼如下：
int findRepeatNumber(vector<int>& nums) {
int temp;
for(int i=0;i<nums.size();i++){
while (nums[i]!=i){
if(nums[i]==nums[nums[i]]){
return nums[i];
}
swap(nums[i],nums[nums[i]]);
}
}
return -1;
}
缺失的第一個正數
這裡的思路是把 1 這個數放到下标為 0 的位置， 2 這個數放到下标為 1 的位置，按照這種思路整理一遍數組。然後我們再周遊一次數組，第 1個遇到的它的值不等于下标的那個數，就是我們要找的缺失的第一個正數。
代碼如下：
int firstMissingPositive(vector<int>& nums) {
int n=nums.size();
for(int i=0;i<n;++i){
while(nums[i]!=i+1){
//下面三種情況都表示nums[i]是無效數，其中nums[i]==nums[nums[i]-1]表示出現重複
if(nums[i]>n||nums[i]<1||nums[i]==nums[nums[i]-1]) break;
//将nums[i]換到它應該待的位置上
swap(nums[i],nums[nums[i]-1]);
}
}
for(int j=0;j<n;++j){
if(nums[j]!=j+1) return j+1;
}
return n+1;
}
複雜度
時間複雜度：O（N）
空間複雜度：O（1）
7、前K個高頻元素
題目
分析
這題拿到手後首先肯定要進行統計的，這裡使用map來完成，
unordered_map<int,int> um;
for(int a:nums){
++um[a];
}
統計完成後，對于TOP K問題，可以使用優先隊列來處理，
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
for(auto a:um){
if(pq.size()==k){
if(a.second>pq.top().first){
pq.pop();
pq.push(make_pair(a.second,a.first));
}
}
else pq.push(make_pair(a.second,a.first));
}
注意，這裡由于要按照出現次數進行排序，是以make_pair要把map的實值作為first，鍵值作為second。
另外，這裡priority_queue中使用的greater<pair<int,int>表示構造小頂堆，等同于使用，
struct cmp{
bool operator()(pair<int,int> a,pair<int,int> b){
//大的往下移
return a.first>b.first;
}
};
最後，将K個元素從優先隊列中取出，
vector<int> ret;
for(int i=0;i<k;++i){
ret.push_back(pq.top().second);
pq.pop();
}
複雜度
時間複雜度：O（NlgK）
空間複雜度：O（N）
8、最長連續序列
題目
分析
這裡因為時間複雜的限制，我們沒辦法使用排序。
這裡的思路是先用哈希表把所有的數都存下來，然後再次周遊，然後根據哈希表查找最長的連續序列。這裡為了避免重複查找，關鍵在于每次查詢都從連續序列中最小的那個數開始。代碼如下：
int longestConsecutive(vector<int>& nums) {
int n=nums.size();
unordered_set<int> us;
for(int a:nums) us.insert(a);
int maxlen=0;
for(int a:nums){
//這一步是關鍵，它避免了重複的查找。
if(us.count(a-1)) continue;
int len=1;
while(us.count(a+1)){
++a;
++len;
}
maxlen=max(len,maxlen);
}
return maxlen;
}
複雜度
時間複雜度：O（N）
空間複雜度：O（N）
9、LFU
題目
分析
這題的O（1）過于繁瑣，是以我選擇放棄。
這裡采取官解提出的哈希map+紅黑樹set的O（lgN）的組合進行求解，先上官解代碼，
struct Node {
int cnt, time, key, value;
Node(int _cnt, int _time, int _key, int _value):cnt(_cnt), time(_time), key(_key), value(_value){}
bool operator < (const Node& rhs) const {
return cnt == rhs.cnt ? time < rhs.time : cnt < rhs.cnt;
}
};
class LFUCache {
// 緩存容量，時間戳
int capacity, time;
unordered_map<int, Node> key_table;
set<Node> S;
public:
LFUCache(int _capacity) {
capacity = _capacity;
time = 0;
}
int get(int key) {
if (capacity == 0) return -1;
auto it = key_table.find(key);
// 如果哈希表中沒有鍵 key，傳回 -1
if (it == key_table.end()) return -1;
// 從哈希表中得到舊的緩存
Node cache = it -> second;
// 從平衡二叉樹中删除舊的緩存
S.erase(cache);
// 将舊緩存更新
cache.cnt += 1;
cache.time = ++time;
// 将新緩存重新放入哈希表和平衡二叉樹中
S.insert(cache);
it -> second = cache;
return cache.value;
}
void put(int key, int value) {
if (capacity == 0) return;
auto it = key_table.find(key);
if (it == key_table.end()) {
// 如果到達緩存容量上限
if (key_table.size() == capacity) {
// 從哈希表和平衡二叉樹中删除最近最少使用的緩存
key_table.erase(S.begin() -> key);
S.erase(S.begin());
}
// 建立新的緩存
Node cache = Node(1, ++time, key, value);
// 将新緩存放入哈希表和平衡二叉樹中
key_table.insert(make_pair(key, cache));
S.insert(cache);
}
else {
// 這裡和 get() 函數類似
Node cache = it -> second;
S.erase(cache);
cache.cnt += 1;
cache.time = ++time;
cache.value = value;
S.insert(cache);
it -> second = cache;
}
}
};
因為同時對次數和時間都做了要求，是以這裡專門建構的一個Node的結構體，以把四個元素都儲存下來。
然後下面的對“<”的重載，涉及到紅黑樹，這裡為使時間更進一步選擇了紅黑樹而不是優先隊列，同時還是因為優先隊列不支援删除的操作。紅黑樹的頂部則應該儲存在滿的時候要删除的結點。根據題意首先先删除調用次數最少的元素，相同調用次數的情況下優先删除存在時間更短的那個元素。
這裡設定了一個全局時間time，每次操作都将其加1，同時Node中自帶一個cnt，表示到目前為止被調用的次數。