多刷題

LeetCode 熱題100

哈希

兩數之和

• 思路分析：
  • 暴力做法：每一個數字都與剩余的數字作比較，時間復雜度是$O(n^2)$
  • 哈希做法：我們可以使用一個哈希表存儲已經檢查過的數字，每次遍歷到新的數字的時候，就在哈希表里面檢查，target-num是否在這個哈希表里面；如果不存在，則將當前元素加入哈希表，哈希表存儲的是{值：索引}

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();// 使用哈希表map<int,int> store;for(int i = 0 ; i < n ;i++){int tar = target - nums[i];if (store.find(tar) != store.end()){return {store.find(tar)->second,i};}else{store[nums[i]] = i; }}return {};}
};

字母異位詞分組

• 思路分析：
  • 首先，如何判斷哪些單詞是等價的，也就是可以通過重新排列變為一樣的？那么我們肯定會說，只要這個對應字符的個數和種類一樣即可，但是我們實際上，并不會真正的去統計比較每一個字符串的字符的具體情況，然后進行一一對比
  • 既然都可以進行重新排序，為什么不直接將全部的字符串進行排序，我們將排序之后的字符作為鍵，原本的字符串作為值，這樣就可以實現$O(n)$的時間復雜度進行統計，最后只需將這個值匯總一下即可

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {// 存儲{排序后字符串：原本字符串}unordered_map<string,vector<string>> store;for(auto& s:strs ){string tmp = s ;sort(s.begin(),s.end()); // 升序排序store[s].push_back(tmp);}// 整理答案vector<vector<string>> result;for (auto& p:store){result.push_back(p.second);}return result;}
};

最長連續序列

• 思路分析：
  • 暴力做法：直接對全部的整數數組進行一個排序，然后進行遍歷一遍即可，但是這個排序的時間復雜度為$O(nlogn)$
  • 哈希表：題目要求的是使用$O(n)$的時間復雜度進行計算，所以就不能進行這個排序操作，這里有幾點操作技巧
    • 重復的元素，我們只需遍歷一次即可
    • 找到以元素num開始的最大情況，當存在num-1在哈希表的時候，就直接跳過（因為以num-1會比以num開頭的序列長1）
    • 然后我們就可以一直查找，看看是否num+1在哈希表，然后進行統計更新

class Solution {
public:int longestConsecutive(vector<int>& nums) {    int ans = 0;unordered_set<int> store(nums.begin(),nums.end()); // 把nums轉成哈希集合for (int x : store){if (store.contains(x-1)){continue;}// 以 x 為序列起點int y = x + 1;while (store.contains(y)){y++;}// 此時的y-1是序列的最后一個數,那么從x開始到y-1，一共y-x個數字ans = max(ans,y-x);}return ans;}
};

雙指針

雙指針有多種類型，常見來說，就有正向雙指針和對向雙指針

移動零

• 思路分析：
  *

盛最多水的容器

滑動窗口

子串