杂记-LeetCode中部分题思路详解与笔记-HOT100篇-其四

那今天我们就把Hot100的所有题都完结了吧，Hot100作为大多数人笔试题的入门之选，可以说是非常的经典了，但是俗话说得好，书读百遍，其意自现，我不支持反复地只刷部分算法题，但是我支持周期性地刷刷写过的题，会有新收获的。

这个题其实有非常多种做法，我们可以用动态规划做，可以用双指针做，甚至还有非常高级的马拉车算法，但是在这里我们不做讨论了。

我就介绍最简单直观的双指针做法吧：

回文子串问题中，往往避免不了一个问题就是要考虑子串长度的奇偶性，所以我们也要考虑这个子串是奇和偶的情况。我们从下标为i处开始从中间向两边扩张，如果是奇长度子串我们的左指针和右指针从同一个点出发，如果是偶长度子串我们的左指针和右指针分别从相邻的两个点出发，判断两个指针是否相等即可，最后返回两个指针的差值，我们不断维护这个差值即可。

class Solution {
public:pair<int,int> helper(string s,int l,int r){while(l>=0&&r<s.size()&&s[l]==s[r]){--l;++r;}return {l+1,r-1};}string longestPalindrome(string s) {int start=0,end=0;for(int i=0;i<s.size();++i){auto [start1,end1]=helper(s, i, i);auto [start2,end2]=helper(s, i, i+1);if(end-start<end1-start1){start=start1;end=end1;}if(end-start<end2-start2){start=start2;end=end2;}}return s.substr(start,end-start+1);}
};

可以看到这个算法的复杂度来到ON2，所以其实不是很理想，可是假如我们想降重，就只能使用传说中的马拉车算法--或者叫曼切斯特算法。

这个题非常有意思，我们要去找只出现了一次的元素，注意这里要求我们的时间复杂度和空间复杂度都非常严格，事实上就是想让我们使用：

class Solution {
public:int singleNumber(vector<int>& nums) {int res=0;for(auto num:nums){res ^=num;}    return res;}
};

是的，就是异或：

综上，我们只需要用0去和数组内所有元素进行异或，出现两次的数与自己的异或自然会抵消，而只有出现一次的数才会和0异或后保留自己，那也就是我们想要的数。

这个题让我们找出现次数大于n/2的元素，首先显然这样的数只有一个，其次是我们有没有什么办法非常快速地找到这个数呢？

第一次写的时候我是直接对数组进行排序后返回数组中间的值，客观地说这个做法没什么问题，复杂度也不会很高，但是如果是面试的时候这样写大概率面试官要挑刺。所以要请出我们真正的主角：摩尔投票算法。

其实摩尔算法的核心思想就是让不同的元素的“选票”互相抵消，这样出现次数超过n/2的元素就一定能胜出。

class Solution {
public:int majorityElement(vector<int>& nums) {int res=0,vote=0;for(int num:nums){if(vote==0)res=num;vote+=num==res?1:-1;}return res;}
};

这里的res和num在vote==0时就代表是“初选”，每个元素在答案揭晓之前都有可能是候选人，因此当我们发现vote==0时就假设当前Num为候选人，然后每次循环都要执行的是选票的抵消（或则自增）。

荷兰国旗问题：

这题我们可以用双指针来写，应该会是效率最高的写法：

class Solution {
public:void sortColors(vector<int>& nums) {int p0=0,p1=0;for(int i=0;i<nums.size();i++){if(nums[i]==1){swap(nums[i], nums[p1]);p1++;}else if(nums[i]==0){swap(nums[i], nums[p0]);if(p0<p1){swap(nums[i], nums[p1]);}p0++;p1++;}}    }
};

我们的p0和p1分别是0和1的边界，显然我们的p1会始终在p0右边（当然也有可能重合（数组内无0的时候）），有1我们就移动p1，有0的话我们移动p0的同时还要检查p1的位置，因为如果有1的话我们移动的p0的值就是1（这是一定的），所以我们swap值为0的值时还要多一层考虑。

这个题要求我们找到当前数组的下一个字典序排列，这里我们首先要理解什么是字典序：字典序（Lexicographical Order）又称词典序、字母序，是一种基于字符或元素自然顺序的排列规则，广泛应用于字符串比较、算法设计、数据库索引等领域。其核心逻辑模仿了字典中单词的排列方式

而一般来说的做法就是从后往前遍历找到第一个符合nums[i]<nums[i+1]的下标为i的数字，这个数字就是我们进行更改的基准：我们再在这个数字的基础上去找到第一个符合nums[i]<nums[j]的数字，然后swap(nums[i],nums[j])即可，最后我们要翻转i以后的部分（swap之后我们要保证最小字典序）。

class Solution {
public:void nextPermutation(vector<int>& nums) {int n=nums.size();int i=n-2;while(i>=0&&nums[i]>=nums[i+1])--i;if(i>=0){int j=n-1;while(j>=0&&nums[i]>=nums[j])--j;swap(nums[i], nums[j]);}reverse(nums.begin()+i+1, nums.end());}
};

这个题的做法也非常经典：针对不修改原数组且只给O1的额外空间的条件来说，找重复数我们也不能用哈希表或者数组，只能用一些比较巧妙的做法。

如果大家还记得环形链表二中的题目：他要求我们如果链表有环则返回入环点，我们会用快慢指针来做，具体解析我就不介绍了，本质上是数学的一些取巧，而这个题我们依然可以使用这个思路：我们把数组构建出链表，然后也使用快慢指针来做：

class Solution {
public:int findDuplicate(vector<int>& nums) {int s=0,f=0;do{s=nums[s];f=nums[nums[f]];}while(s!=f);s=0;while(s!=f){s=nums[s],f=nums[f];}return s;}
};

之所以一开始要使用do while是因为我们的判断条件是s!=f，但其实一开始的时候我们的s和f是相等的，所以不适用；原题中我们是移动head和slow，但是这里其实没有差别，我们没有head的话就拿s和f来移动咯（f一开始和s在相同位置上）。

烂橘子，经典题目。这个题反而就不多说了，因为确实要说的话东西太多了，只能说多练。

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();int total = 0, org = 0, res = -1;queue<pair<int, int>> q;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] != 0) total++;if (grid[i][j] == 2) {q.push({i, j});org++;}}}vector<pair<int, int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};int temp = 0;while (!q.empty()) {res++;int size = q.size();temp += size;for (int i = 0; i < size; ++i) {auto [x, y] = q.front();q.pop();for (auto [dx, dy] : dirs) {int nx = x + dx, ny = y + dy;if (nx >=0 && nx < m && ny >=0 && ny < n && grid[nx][ny] == 1) {grid[nx][ny] = 2;q.push({nx, ny});}}}}return (temp == total) ? max(res, 0) : -1;}
};

这个题是一个经典的无权无向图，我们只用图的流通性即可，总的来说是比较简单的，主要涉及到的知识点就是图的构建和查找。HOT100关于图的题目并不多，更多的可以去代码随想录上去看：

图论理论基础 | 代码随想录 (programmercarl.com)

class Solution {
public:vector<vector<int>> edges;vector<int> visited;bool vaild=true;bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses),visited.resize(numCourses);for(auto info:prerequisites){edges[info[1]].push_back(info[0]);}for(int i=0;i<numCourses;++i){if(visited[i]==0)dfs(i);}return vaild;}void dfs(int i){visited[i]=1;for(int num:edges[i]){if(visited[num]==0){dfs(num);if(!vaild)return;}if(visited[num]==1){vaild=false;return;}}visited[i]=2;}
};

我们需要去实现前缀树，可以看到前缀树中主要的功能就是插入和查找。

用比较简单的话来介绍的话就是，前缀树就是我们输入法一个键一个键输入的数据结构，不同单词之间会共享相同的前缀。

class Trie {
private:bool isEnd;Trie* next[26];
public:Trie() {isEnd=false;memset(next, 0, sizeof(next));}void insert(string word) {Trie* node=this;for(char ch:word){if(node->next[ch-'a']==nullptr){node->next[ch-'a']=new Trie();}node=node->next[ch-'a'];}node->isEnd=true;}bool search(string word) {Trie* node=this;for(char ch:word){if(node->next[ch-'a']==nullptr)return false;node=node->next[ch-'a'];}return node->isEnd;}bool startsWith(string prefix) {Trie* node=this;for(char ch:prefix){if(node->next[ch-'a']==nullptr)return false;node=node->next[ch-'a'];}return true;}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

本身找两个数组中的中位数并不难，但是算法复杂度只要OLOGM+N还是比较难的，显然不能合并数组后查找了（合并的时间复杂度是M+N），我们在这里要去使用分治法：

class Solution {
public:double helper(vector<int>& nums1, vector<int>& nums2, int k) {int n1 = nums1.size(), n2 = nums2.size(), idx1 = 0, idx2 = 0;while (true) {if (idx1 == n1) return nums2[idx2 + k - 1];if (idx2 == n2) return nums1[idx1 + k - 1];if (k == 1) return min(nums1[idx1], nums2[idx2]);int newidx1 = min(idx1 + k/2 - 1, n1 - 1);int newidx2 = min(idx2 + k/2 - 1, n2 - 1);int num1 = nums1[newidx1], num2 = nums2[newidx2];if (num1 <= num2) {k -= newidx1 - idx1 + 1;idx1 = newidx1 + 1;} else {k -= newidx2 - idx2 + 1;idx2 = newidx2 + 1;}}}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int totalLen = nums1.size() + nums2.size();if (totalLen % 2 == 1) {return helper(nums1, nums2, (totalLen + 1) / 2);} else {return (helper(nums1, nums2, totalLen / 2) + helper(nums1, nums2, totalLen / 2 + 1)) / 2.0;}}
};

当我们看到跟括号相关的题目是，总是难免想到栈来做，这个题也不例外。

要找到格式正确且连续的括号，我们的栈只进左括号，把右括号全部丢出去，然后如果发现栈中为空的话我们就重新开始统计长度即可。其中if(stk.empty())stk.push(i);就是负责重置边界的代码。

class Solution {
public:int longestValidParentheses(string s) {int res=0;stack<int> stk;stk.push(-1);for(int i=0;i<s.size();++i){if(s[i]=='(')stk.push(i);else stk.pop();if(stk.empty())stk.push(i);res=max(res,i-stk.top());}return res;}
};

又是一个求中位数的题，不同点在于之前是两个有序数组求中位数而这个题就是一个数组，不过这个要求得实时计算中位数。

显然，我们需要一个有序容器来帮助我们完成这个功能，自动的排序容器还得方便找到中间值，那么没有比堆更方便的了：堆自动排序的同时还可以直接访问堆顶元素，我们只需要一些小小的设计让堆顶元素始终为中位数。如何设计呢？我们知道堆分为小根堆和大根堆，小根堆是从小到大排序，大根堆是从大到小排序，那么如果我们同时用一个小根堆和一个大根堆分别存储一半的数据的话，中位数不就是这个大根堆（或者小根堆，取决于那边的数据会多一个，如果大根堆和小根堆的数据量相同则取平均）的堆顶元素吗？

class MedianFinder {
private:priority_queue<int, vector<int>, less<int>> max_heap;priority_queue<int, vector<int>, greater<int>> min_heap;
public:MedianFinder() {}void addNum(int num) {if(max_heap.empty()||num<=max_heap.top()){max_heap.push(num);if(max_heap.size()>min_heap.size()+1){min_heap.push(max_heap.top());max_heap.pop();}}else{min_heap.push(num);if(min_heap.size()>max_heap.size()){max_heap.push(min_heap.top());min_heap.pop();}}}double findMedian() {int n1=max_heap.size(),n2=min_heap.size(),sum=n1+n2;if((sum)%2==1)return max_heap.top();else return (max_heap.top()+min_heap.top())/2.0;}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/