leetcode 刷题记录（倒序）

本文最后更新于 <span id="expire-date"></span> 天前，文中部分描述可能已经过时。

15. 三数之和

复制粘贴

25. K 个一组翻转链表

复制粘贴

215. 数组中的第K个最大元素

复制粘贴

LRU 缓存机制

提交记录

是先去b站看了解析视频然后自己写的，很多cpp的内容还是不熟悉，要继续。

状态	日期	语言	时间	空间	优化
通过	2023.10.10	C++	372 ms	161.7 MB	官方题解
通过	2023.10.10	C++	372 ms	161.4 MB	ai 优化
通过	2023.10.10	C++	476 ms	170.7 MB
通过	2023.10.10	C++	488 ms	170.8 MB
超出时间限制	2023.10.10	C++	N/A	N/A
超出时间限制	2023.10.10	C++	N/A	N/A
执行出错	2023.10.09	C++	N/A	N/A
执行出错	2023.10.09	C++	N/A	N/A

自己的最终代码

class LRUCache {
public:
    LRUCache (int capacity) {
        __cap = capacity;
    }
    
    int get (int key) {
        //key = 0;
        if (hashmap.find (key) == hashmap.end ()){ // 没找到
            return -1;
        } else {
                        // 添加
            key_value kv;
            kv.key = key;
            kv.value = hashmap [key]->value;



            value_list.erase (hashmap [key]);
            value_list.push_front (kv);
            hashmap [key] = value_list.begin ();
            return kv.value;
        }
        return key;
    }
    
    void put (int key, int value) {
        if (hashmap.find (key) == hashmap.end ()){ // 没找到
            // 满了吗？

            if (__cap == hashmap.size ()){
                hashmap.erase ( value_list.back ().key);
                value_list.pop_back ();
            }
            // 添加
            key_value kv;
            kv.key = key;
            kv.value = value;
            value_list.push_front ( kv);
            hashmap [key] = value_list.begin ();




        } else { // 找到了
            // 删除并添加到头

            value_list.erase (hashmap [key]);
            // 添加
            key_value kv;
            kv.key = key;
            kv.value = value;
            value_list.push_front ( kv);
            hashmap [key] = value_list.begin ();

        }
    }
private:
    int __cap;
    struct key_value {
        int key;
        int value;
        bool operator==(const key_value& kv){
            return key == kv.key;
        }
    };
    map<int, list<key_value>::iterator> hashmap;
    list<key_value> value_list;

};

ai优化

#include <iostream>
#include <unordered_map>
#include <list>

class LRUCache {
public:
    LRUCache (int capacity) : capacity (capacity) {
    }

    int get (int key) {
        if (cache_map.find (key) == cache_map.end ()) {
            return -1; // 未找到
        } else {
            // 将键值对移到链表头部表示最近使用
            moveToFront (key);
            return cache_map [key]->second;
        }
    }

    void put (int key, int value) {
        if (cache_map.find (key) == cache_map.end ()) {
            if (cache_map.size () >= capacity) {
                // 缓存已满，删除最久未使用的项目
                int lru_key = lru_list.back ().first;
                cache_map.erase (lru_key);
                lru_list.pop_back ();
            }
            // 添加新项目到链表头部
            lru_list.push_front (std::make_pair (key, value));
            cache_map [key] = lru_list.begin ();
        } else {
            // 更新已存在的键值对的值，然后移到链表头部表示最近使用
            cache_map [key]->second = value;
            moveToFront (key);
        }
    }

private:
    int capacity;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache_map;
    std::list<std::pair<int, int>> lru_list;

    // 将键值对移到链表头部
    void moveToFront (int key) {
        auto it = cache_map [key];
        lru_list.splice (lru_list.begin (), lru_list, it);
        cache_map [key] = lru_list.begin ();
    }
};

206. 反转链表

看了下提交记录，应该是复制粘贴，主要是cpp不熟，改天重写一遍

这里就记录一下官方答案吧

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* ret = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
};

3 无重复字符的最长子串

独立编写

代码

int lengthOfLongestSubstring(string s)
{
    string temp;
    int ftemp = 0;
    for(int i = s.length(); i > 0; i--)
    {
        if (temp.find(s[s.length() - i]) > temp.length()) // 无重复  temp.find(s[s.length() - i]) == -1 但会很大 所以
        {
            // 无重复
            temp.push_back(s[s.length() - i]);
            ftemp = temp.length() > ftemp ? temp.length() : ftemp;
        }
        else
        {
            // 有重复
            i += (temp.length() - temp.find(s[s.length() - i]) - 1);
            temp.clear();
            temp.push_back(s[s.length() - i]);
            ftemp = temp.length() > ftemp ? temp.length() : ftemp;
        }
    }
    return ftemp;
}

使用到的函数

string::find(char c) // 返回c在string中的位置 无则返回string::npos
string::length() // 返回string的长度
string::push_back(char c) // 在string的末尾添加c
string::clear() // 清空string

思路

刚开始看错了题

做完去看评论发现这个题的思路是滑动窗口然鹅我不知道那是什么东东只是大概理解字面意思

这道题主要用到思路是：滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)O(n)O(n)

作者：powcai
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-dong-chuang-kou-by-powcai/

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

c++ 很多特性还不会用要继续学习

本文作者：wxy

本文链接： https://c.undf.top/posts/d444c6c7/

文章默认使用 CC BY-NC-SA 4.0 协议进行许可，使用时请注意遵守协议。
本站不设评论,网站底部邮件图标可以联系博主

文章写于2023-06-08 文章更新于2023-06-08

😄leetcode

15. 三数之和

25. K 个一组翻转链表

215. 数组中的第K个最大元素

LRU 缓存机制

提交记录

自己的最终代码

ai优化

206. 反转链表

3 无重复字符的最长子串

代码

使用到的函数

思路

总结

评论

如评论失效，请点击最下方的邮件图标联系作者。