Studying-CodeTop | 3. 无重复字符的最宗子串、206. 反转链表、146. LRU 缓 ...

目次
3. 无重复字符的最宗子串
206. 反转链表
146. LRU 缓存 
解题过程： 

---

3. 无重复字符的最宗子串

题目：3. 无重复字符的最宗子串 - 力扣（LeetCode）

学习：本题题意很好明确，我们须要从全部不含有重复字符的子串中，找到长度最长的谁人。首先明确子串的概念：子串不是子序列，子串中的元素是连续的，因此对于示例3来说，wke连续的三个字符是子串，而pwke中心跳掉了一个字符w，因此不是子串，是子序列。
本题我们可以使用回溯算法，遍历全部字符串的全部子串，并判断是否另有重复字符，假如没有则记载一次答案，最后找到最长的长度。这是一种暴力解法，显然时间复杂度极高。
我们其实可以从实际模仿出发，采用滑动窗口的方式举行本题的求解。
以示例1为例，我们可以重新开始遍历数组，先把‘a’加入窗口，然后b与a差别，再把b加入窗口，接着再把c加入窗口。再接着就到a了，此时滑动窗口里面已经有a了，出现了重复的字符。此时我们须要将滑动窗口缩窄，也就是将窗口左边界向右移动，这里要注意，这个过程我们须要使用while举行，固然本题第四个字符是a，我们只须要左边界移动一次，但假如第四个字符是c，则我们须要把左边界一直移动到第四个字符下标，其实也就是我们须要一直缩减滑动窗口，直到其中不包罗重复字符。
统计滑动窗口内字符和找到重复字符的方法，我们可以使用哈希表举行。滑动窗口的移动则可以通过for循环来举行。
代码：

1. class Solution {
2. public:
3.     int lengthOfLongestSubstring(string s) {
4.         if(s.size() <= 1) return s.size();
5.         //滑动窗口，使用哈希表来求解
6.         unordered_set<char> ans;
7.         int result = 1;
8.         ans.insert(s[0]); //初始化哈希表
9.         for(int i = 0, j = 1; j < s.size(); j++) {
10.             while(i < j && ans.find(s[j]) != ans.end()) {
11.                 ans.erase(s[i]);
12.                 i++;
13.             }
14.             ans.insert(s[j]);
15.             result = max(result, j - i + 1);
16.         }
17.         return result;
18.     }
19. };

复制代码

---

206. 反转链表

题目：206. 反转链表 - 力扣（LeetCode）

学习：本题是一道经典的使用双指针方法来办理的题型。

 

我们可以界说一个cur指针，指向头结点，再界说一个pre指针，初始化为null。然后开始举行反转。
首先我们要把cur->next节点用tmp指针保存一下，也就是保存一下这个节点。这是由于接下来要改变cur->next的指向，后续我们还须要回到原先的cur->next的节点举行下一步操作。
接着就是将cur->next = pre；然后pre = cur； cur = next 举行下一轮反转。
代码：

1. class Solution {
2. public:
3.     ListNode* reverseList(ListNode* head) {
4.         ListNode* tmp;
5.         ListNode* pre = nullptr;
6.         ListNode* cur = head;
7.         while (cur != nullptr) {
8.             tmp = cur->next;
9.             cur->next = pre;
10.             pre = cur;
11.             cur = tmp;
12.         }
13.         return pre;
14.         
15.     }
16. };

复制代码

---

146. LRU 缓存 

题目：146. LRU 缓存 - 力扣（LeetCode）

学习：本题很难，我们须要从两个函数出发。
1. get() 函数
该函数，要求我们判断关键字key是否在缓存中，假如在返回关键字的值，假如不在返回-1。显然这是一个map的布局，并且要求我们时间复杂度为O(1)，因此，我们应该采取哈希表来举行存储。同时这里还包罗了，假如存在，则代表该节点被访问了的信息。
2.put() 函数
该函数除了要求我们判断key是否存在以外。还要求我们在不存在的时间，将一个新的结点插入到该组中，假如导致节点数目超过了capacity，则须要删除最久未使用的关键字。这里就两个任务须要我们去实现：①找到最久为使用的节点，并将其删除；②将新节点插入到组中，并且是最新的。
上述两个函数的操作都要求O(1)的时间复杂度举行，而对于删除节点和插入节点，我们能想到的O(1)时间复杂度的布局就是链表（数组的插入删除时间复杂度是O(n)) 。
因此本题须要使用 哈希表 和 链表来举行办理。
解题过程：

链表我们须要使用双向链表布局，如许更方便我们举行节点的删除了插入。

1. struct Linknode {
2.     Linknode* prev;
3.     Linknode* next;
4.     int key;
5.     int val;
6.     Linknode(): key(0), val(0), prev(nullptr), next(nullptr) {}
7.     Linknode(int _key, int _val): key(_key), val(_val), prev(nullptr), next(nullptr) {}
8. };

复制代码

接着我们须要一个哈希表，来举行节点的映射。同时可以设置两个虚拟头结点和尾节点，方便我们插入最新的节点，和找到最久的节点。固然我们也须要保存该组的容量和当前大小。

1. private:
2.     unordered_map<int, Linknode*> map;
3.     Linknode* dummyhead; //虚拟头尾节点
4.     Linknode* dummytail;
5.     int _capacity; //容量
6.     int _size; //当前所用容量

复制代码

接着在实现get() 和 put() 函数之前，我们须要实现两个额外的函数，插入头节点的函数和删除节点的函数。 

1. void addtohead(Linknode* node) { //将节点加入到头结点
2.     node->prev = dummyhead;
3.     node->next = dummyhead->next;
4.     dummyhead->next->prev = node;
5.     dummyhead->next = node;
6. }
7. void remove(Linknode* node) { //删除一个节点
8.     node->prev->next = node->next; //将该节点的前一个节点的next指向该节点的next
9.     node->next->prev = node->prev; //将该节点的下一个节点的prev指向该节点的prev
10. }

复制代码

我们还可以对其举行封装，以实现，将访问过的节点，重新插入到头结点（最新的节点）的方法：

1. void movetohead(Linknode* node) {
2.     remove(node);
3.     addtohead(node);
4. }

复制代码

下面我们就可以对get()函数举行实现了，判断两种情况，存在key或者不存在key

1. int get(int key) {
2.     if(!map.count(key)) {
3.         return -1;
4.     }
5.     Linknode* node = map[key];
6.     movetohead(node);
7.     return node->val;
8. }

复制代码

put()函数则还须要插入新的节点，并判断容量：

1. void put(int key, int value) {
2.     if(!map.count(key)) {
3.         Linknode* node = new Linknode(key, value);
4.         map[key] = node;
5.         addtohead(node);
6.         ++_size;
7.         if(_size > _capacity) {
8.             Linknode* removenode = dummytail->prev;
9.             remove(removenode);
10.             map.erase(removenode->key);
11.             delete removenode;
12.             removenode = nullptr;
13.             --_size;
14.         }
15.     }
16.     else {
17.         Linknode* node = map[key];
18.         node->val = value;
19.         movetohead(node);
20.     }
21. }

复制代码

最后得到代码：

1. class LRUCache {public:    //界说双向链表布局体    struct Linknode {        Linknode* prev;        Linknode* next;        int key;        int val;        Linknode(): key(0), val(0), prev(nullptr), next(nullptr) {}        Linknode(int _key, int _val): key(_key), val(_val), prev(nullptr), next(nullptr) {}    };    LRUCache(int capacity) : _capacity(capacity), _size(0) {        dummyhead = new Linknode();        dummytail = new Linknode();        dummyhead->next = dummytail;        dummytail->prev = dummyhead;    }        int get(int key) {        if(!map.count(key)) {            return -1;        }        Linknode* node = map[key];        movetohead(node);        return node->val;    }        void put(int key, int value) {        if(!map.count(key)) {            Linknode* node = new Linknode(key, value);            map[key] = node;            addtohead(node);            ++_size;            if(_size > _capacity) {                Linknode* removenode = dummytail->prev;                remove(removenode);                map.erase(removenode->key);                delete removenode;                removenode = nullptr;                --_size;            }        }        else {            Linknode* node = map[key];            node->val = value;            movetohead(node);        }    }    void addtohead(Linknode* node) { //将节点加入到头结点        node->prev = dummyhead;        node->next = dummyhead->next;        dummyhead->next->prev = node;        dummyhead->next = node;    }    void remove(Linknode* node) { //删除一个节点        node->prev->next = node->next; //将该节点的前一个节点的next指向该节点的next        node->next->prev = node->prev; //将该节点的下一个节点的prev指向该节点的prev    }    void movetohead(Linknode* node) {        remove(node);        addtohead(node);    }private:
2.     unordered_map<int, Linknode*> map;
3.     Linknode* dummyhead; //虚拟头尾节点
4.     Linknode* dummytail;
5.     int _capacity; //容量
6.     int _size; //当前所用容量};

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。