LeetCode 高频题目 Hot100 习题笔记(一)Top10

一、 前言

LeetCode Hot100 习题，在官网上看热度需要会员，推荐codetop网站，是微软的一位大佬设计的网站，按照大厂习题热度排了序。
安利一波。

每日更新Hot习题~，如果本博文对你有帮助，麻烦动动小手指头，关注，点赞，收藏一下啦。??
不行，绷不住了，一天刷一点吧

以下是更新最近更新的一些博文：

3.11 LeetCode 高频题目 Hot100 习题笔记(二) Hot10-21
3.12 LeetCode 高频题目 Hot100 习题笔记(三)
后续更新可以关注我的专栏欧，会在LeetCode专栏里进行更新的！

二、习题

206 翻转链表

class Solution {
    
public:ListNode* reverseList(ListNode* head) {
    ListNode* new_head = nullptr;while (head){
    ListNode* next = head->next; //备份 head->next  = new_head; // 更新new_head new_head = head;//移动new_head head = next;}return new_head;}
};

146 LRU缓存机制

测试用例

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

完整代码

#include<iostream>
#include<unordered_map> 
#include<algorithm>
using namespace std;//这里放你的代码
struct DKLinkNode{
    int key,value;DKLinkNode* next;DKLinkNode* pre;DKLinkNode():key(0),value(0),pre(nullptr),next(nullptr){
    }DKLinkNode(int _key, int _val):key(_key),value(_val),pre(nullptr),next(nullptr){
    }
};class LRUCache {
    
private:// 借助哈希表来查询存储的位置，key value(链表节点)unordered_map<int, DKLinkNode*> cache;int capacity;int size;DKLinkNode* head;DKLinkNode* tail;
public:LRUCache(int _capacity):capacity(_capacity),size(0) {
    // 创建头尾 伪节点 便于定位head = new DKLinkNode();tail = new DKLinkNode();head->next = tail;tail->pre = head;}~LRUCache(){
    if(head != nullptr){
    delete head;head = nullptr;}if(tail != nullptr){
    delete tail;tail = nullptr;}for(auto& c : cache){
    if(c.second != nullptr){
    delete c.second;c.second = nullptr;}}}int get(int key) {
    // 如果双向链表中没有这个节点则直接返回if(!cache.count(key)){
    return -1;}// 如果有节点 则通过哈希表获取这个节点的地址，将这个节点移到前面DKLinkNode* node = cache[key];moveToHead(node);return node->value;}void put(int key, int value) {
    // 如果哈希表查找不到这个key 则插入新的值到哈希表中// 将新的值插入双向链表的头部if(!cache.count(key)){
    DKLinkNode* node = new DKLinkNode(key, value);cache[key] = node;addHeadNode(node);++size;// 如果当前的容量大于缓存的最大容量，则移除某段节点if(size > capacity){
    DKLinkNode* rNode = removeTail();cache.erase(rNode->key);delete rNode;--size;}}else{
    // 如果查找得到key，则将该节点移动到头部DKLinkNode* moveNode = cache[key];// 更新当前key对应的value 并移动链表moveNode->value = value;moveToHead(moveNode);}}void addHeadNode(DKLinkNode* node){
    node->pre = head;node->next = head->next;head->next->pre = node;head->next  = node;}void removeNode(DKLinkNode* rNode){
    rNode->pre->next = rNode->next;rNode->next->pre = rNode->pre;}DKLinkNode* removeTail(){
    DKLinkNode* rNode = tail->pre;removeNode(rNode);return rNode; }void moveToHead(DKLinkNode* node){
    // 删除当前节点removeNode(node);// 在头结点处添加进去addHeadNode(node);}
};int main(){
    LRUCache* cache = new LRUCache(2);cache->put(1, 1);cache->put(2, 2);int res = cache->get(1);       // 返回 1cout<<res<<endl;cache->put(3, 3);    // 该操作会使得密钥 2 作废res = cache->get(2);       // 返回 -1 (未找到)cache->put(4, 4);    // 该操作会使得密钥 1 作废res = cache->get(1);       // 返回 -1 (未找到)cout<<res<<endl;res = cache->get(3);       // 返回 3cout<<res<<endl;res = cache->get(4);       // 返回 4cout<<res<<endl;return 0;
} 

3 无重复字符的最长子串

//这里放你的代码
//注意图片要挪到```的外部才能正常显示~
class Solution {
    
public:int lengthOfLongestSubstring(string s) {
    // 无重复字符的最长子串,借助set哈希表来完成滑动串口unordered_set<char> charSet;int left = 0;// 滑动窗口左边界int maxLen = 0;if(s.length() == 0) return 0;for(int i = 0; i < s.length(); ++i){
    while(charSet.find(s[i]) != charSet.end()){
    // 如果在set中找到了相等的，也就是重复的，则移动窗口charSet.erase(s[left++]);}// 添加无重复的字符charSet.insert(s[i]);// 判断最长的跨度长度maxLen = max(maxLen, i - left + 1);}return maxLen;}
};

215 数组中的第k个最大元素

大跟堆

按顺序扫描这10000个数，先取出K个元素构建一个大小为K的最小堆。每扫描到一个元素，如果这个元素大于堆顶的元素（这个堆最小的一个数），就放入堆中，并删除堆顶的元素，同时整理堆。如果这个元素小于堆顶的元素，就直接pass。最后堆中剩下的元素就是最大的前Top K个元素，最右的叶节点就是Top 第K大的元素。

class Solution 
{
    
public:int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, less<int>> maxHeap;for (int x : nums)maxHeap.push(x);for (int i = 0; i < k - 1; i++)maxHeap.pop();return maxHeap.top();}
};

class Solution 
{
    
public:int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();int l = 0;int r = n - 1;while (true){
    int idx = partition(nums, l, r);if (idx == k - 1)return nums[idx];else if (idx < k - 1)l = idx + 1;else    r = idx - 1;}}//----单向遍历int partition(vector<int> & nums, int l, int r){
    int pivot = nums[l];int idx = l;for (int i = l + 1; i < r + 1; i ++){
    if (nums[i] >= pivot){
    idx ++;swap(nums[idx], nums[i]);}}swap(nums[l], nums[idx]);return idx;}
};

25 K个一组翻转链表

class Solution {
    
public:ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* dummy =  new ListNode(0);dummy->next = head;ListNode* pre = dummy;ListNode* tail = dummy;while(tail->next !=nullptr){
    for(int i = 0; i < k && tail != nullptr; i++) tail = tail->next;if(tail == nullptr) break;ListNode* start = pre->next;ListNode* next = tail->next;tail->next = nullptr;pre->next = reverseNode(start);start->next = next;pre = start;tail = pre;}return dummy->next;}
private:ListNode* reverseNode(ListNode* head){
    ListNode* pre = nullptr;ListNode* cur = head;while(cur != nullptr){
    ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}};

15 三数之和

图片源自leetcode用户
作者：guanpengchn
链接：https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/

class Solution {
    
public:vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());vector<vector<int>> res;if(nums.size() < 3) return res;int left = 0, right = 0;for(int i = 0; i < nums.size(); ++i){
    if(nums[i] > 0) continue;left = i + 1;right = nums.size() -1;if(i>0 && nums[i] == nums[i-1]) continue;// 注意这里去重while(left < right){
    if(nums[right] + nums[left] + nums[i] == 0){
    // 添加到res后 对以后的情况要判断是否有重的，去重res.push_back({
    nums[i],nums[left], nums[right]});while(left < right && nums[left] == nums[left + 1]) left++;while(left < right && nums[right] == nums[right - 1]) right--;left++;right--;}else if(nums[right] + nums[left] + nums[i] < 0){
    left++;}else if(nums[right] + nums[left] + nums[i] > 0){
    right--;}}}return res;}
};

补充题4. 手撕快速排序

注意快速排序在没有优化之前，最差的时间复杂度是o(n^{2})，无法通过全部用例，只需要优化一下中枢点就可以
int p = round(1.0 * rand() / RAND_MAX * (end - begin) + begin);

class Solution {
    
private:void quickSort(vector<int> &nums, int begin, int end){
    // 判断是否是有序的 如果有序的话，直接退出 if(begin >= end) return ; // 优化部分为中枢点的选择 int p = round(1.0 * rand() / RAND_MAX * (end - begin) + begin);swap(nums[begin], nums[p]);	int low = begin, high = end, key = nums[begin];while(low < high){
    while(low < high && nums[high] >= key){
    high--;}if(low < high) nums[low++] = nums[high];while(low < high && nums[low] <=key){
    low++;}if(low < high) nums[high--] = nums[low];}nums[low] = key;quickSort(nums,begin, low - 1);quickSort(nums, low + 1, end);}
public:vector<int> sortArray(vector<int>& nums) {
    quickSort(nums, 0, nums.size()-1);return nums;}
};

53 最大子序和

class Solution {
    
public:int maxSubArray(vector<int>& nums) {
    // addMax累加和， 最大和int addMax = nums[0], subMax = nums[0];if(nums.size() <2) return nums[0];for(int i = 0; i< nums.size(); ++i){
    if(addMax < 0) addMax = nums[i];else addMax += nums[i];if(addMax > subMax) subMax = addMax;}return subMax;}
};

动态规划的方法

class Solution
{
public:int maxSubArray(vector<int> &nums){//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值int result = INT_MIN;int numsSize = int(nums.size());//dp[i]表示nums中以nums[i]结尾的最大子序和vector<int> dp(numsSize);dp[0] = nums[0];result = dp[0];for (int i = 1; i < numsSize; i++){dp[i] = max(dp[i - 1] + nums[i], nums[i]);result = max(result, dp[i]);}return result;}
};作者：pinku-2
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

21 合并两个有序链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode *p1=l1;ListNode *p2=l2;ListNode *result=new ListNode(0);ListNode *r=result;while(p1 && p2){if(p1->val > p2->val){r->next=p2;r=r->next;p2=p2->next;}else{r->next=p1;r=r->next;p1=p1->next;}}if(p1){r->next=p1;}else if(p2){r->next=p2;}return  result->next;}
};

1 两数之和

class Solution {
    
public:vector<int> twoSum(vector<int>& nums, int target) {
    // 哈希表unordered_map<int,int> umap;for(int i = 0; i<nums.size(); i++){
    // 如果保证其不会和自身进行比较 查找完再插入auto it = umap.find(target - nums[i]);if(it != umap.end()){
    //找到 则直接返回return vector<int>{
    it->second,i};}umap[nums[i]] = i;}return vector<int>{
     };}
};

三、参考资料

1. CodeTop100
2. https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/