Leetcode_20 天编程能力基础_day19

Posted on | In ,
| 4.6k | 38 mins.

倒数第二天~

1797. Design Authentication Manager

Analysis

这种设计类得题目都这么长的吗？实际问题不复杂，理解题意要想半天...
话说回来，这个题实际上是个散列题，需要用一个变量timetolive来记录验证码的“存活”时间，同时，利用 map 来保存验证码与其对应的“死亡”时刻（注意这里是时刻），也就是currentTime + timetolive。最后要注意的一点是过期事件优先于其他操作，也就是说在t = 10，某个验证码“死亡”了，同时对这个验证码执行renew操作，此时不会改变任何东西。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class AuthenticationManager {
    unordered_map<string, int> ht;
    int timetolive;
public:
    AuthenticationManager(int timeToLive) {
        timetolive = timeToLive;
    }
    
    void generate(string tokenId, int currentTime) {
        ht[tokenId] = currentTime + timetolive;
    }
    
    void renew(string tokenId, int currentTime) {
        if(ht.count(tokenId) != 0 && ht[tokenId] > currentTime) {
            ht[tokenId] = currentTime + timetolive;
        }
    }
    
    int countUnexpiredTokens(int currentTime) {
        int cnt = 0;
        for(auto &[_, time]: ht) {
            if(time > currentTime) cnt++;
        }
        return cnt;
    }
};

707. Design Linked List

Analysis

实现链表，em，老生常谈的问题，不过要实现的函数太多，最好分开思考。
首先应该明确题目的要求：

  1. 链表结点具有两个属性：val 和 next。
  2. 链表结点的下标是从 0 开始的。

Code

总共要实现 5 个函数，先大致分析一下每个函数如何实现：

  1. 获取第 index 个结点的值，这个直接遍历链表就可以得到，所以需要有链表的头指针。
  2. 链表的第一个元素之前添加结点，同样需要头指针。
  3. 链表的最后一个元素之后添加结点，可以从头遍历到尾，也可以直接用尾指针解决。
  4. 第 index 个结点之前添加结点，遍历链表，然后插入即可，需要头指针。
  5. 删除第 index 个结点，遍历链表，删除即可。

按照对函数的分析，选择用带头（哑）结点和尾指针的方式来完成这个链表。

constructor

首先是结点的构造以及对应的构造函数的书写，这里的原则是怎么方便怎么来😂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MyLinkedList {
public:
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int val): val(val), next(nullptr){};
    };
    MyLinkedList(){
        size = 0;
        dummyhead = new ListNode(0);
        tail = dummyhead;
    }
private:
    int size;
    ListNode *dummyhead;
    ListNode *tail;
}

注意私有成员得写在后面，因为ListNode的声明（declaration）和定义（definition）在 public 里面。不过，如果想要写在前面应该也能用 typedef 来完成吧？懒得尝试了...
多写一个ListNode的构造函数，这样方便新建结点，同时MyLinkedList的构造函数也需要初始化当前链表的哑结点、尾指针和结点总数了。

addAtHead

先思考 addAtHead 函数的写法，因为有了哑结点，所以在这个位置插入就很简单：

1
2
3
4
5
6
void addAtHead(int val) {
    ListNode *newnode = new ListNode(val);
    newnode->next = dummyhead->next;
    dummyhead->next = newnode;
    size++;
}

但是这里有一个问题，那就是尾指针是否会受到影响。显然，如果是第一个结点插入，那么尾指针同时也需要变成指向第一个结点。那如果插入第二个结点呢？当然就不需要在改变尾指针了。

1
2
3
4
5
6
7
void addAtHead(int val) {
    ListNode *newnode = new ListNode(val);
    newnode->next = dummyhead->next;
    dummyhead->next = newnode;
    size++;
    if(size == 1) tail = newnode;
}

addAtTail

再来思考如何在尾部插入结点。与前面的思考一样，因为有了尾指针，所以就很容易的在尾部插入结点了：

1
2
3
4
5
6
void addAtTail(int val) {
    ListNode *newnode = new ListNode(val);
    tail->next = newnode;
    tail = newnode;
    size++;
}

addAtIndex

按照题目的解释，当 index 等于链表长度时，直接在末尾插入结点；当 index 大于链表长度时，当作输入的错误，忽略掉即可；当 index 小于 0 时，在头部插入；当 index 大于 0 小于 index 时，在链表中间插入结点。对应的，针对这 4 种情况：

  1. 直接在尾部插入。
  2. 忽略。
  3. 直接在头部插入结点。
  4. 先找到要插入的位置的前一个结点，然后插入结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void addAtIndex(int index, int val) {
        if(index > size) return;
        ListNode *newnode = new ListNode(val);
        if(index == size) {
            tail->next = newnode;
            tail = newnode;
        } else {
            ListNode *cur = dummyhead;
            while(index--) cur = cur->next;
            newnode->next = cur->next;
            cur->next = newnode;    
        }
        size++;
    }

实际上，这个题并没有给 index 小于 0 的情况，所以就直接这么写了。看了下评论区，当时好像是给了的，结果被太多人吐槽，就删除了吧😂？不过，题目本身就说了 index 是从 0 开始的，出现负数确实可以当作错误的输入给 pass 掉。虽然，题目也对这个函数的功能进行了解释，但是感觉不对负数做处理，才是正常人的思考模式🤔？

另外，因为有哑结点的存在，所以寻找插入位置时，直接从哑结点开始，这样当 index 为 0，找到的结点，就是要插入位置的前一个结点。还要注意的一个地方是在尾部插入结点后，一定要记得修改尾指针。

get

获取链表中第 index 个结点的值，直接遍历链表即可。由于保存了链表当前的结点总数，所以在查找前可以简单判断一下。

1
2
3
4
5
6
int get(int index) {
    if(index < 0 || index > size - 1) return -1;
    ListNode *cur = dummyhead->next;
    while(index--) cur = cur->next;
    return cur->val;
}

需要注意的是，这里要返回的是下标为 index 结点的值，所以循环开始时cur得指向第一个真实的结点。

deleteAtIndex

同样，删除之前也可以先对 index 进行判断。

1
2
3
4
5
6
7
8
9
10
void deleteAtIndex(int index) {
    if(index < 0 || index > size - 1) return;
    ListNode *cur = dummyhead;
    while(index--) cur = cur->next;
    ListNode *tmp = cur->next;
    if(tmp == tail) tail = cur;
    cur->next = cur->next->next;
    delete tmp;
    size--;
}

删除时，需要寻找的同样是被删除结点的前一个结点，所以循环开始时cur指向哑结点即可。同样，注意当删除的是最后一个结点时，尾指针要改成指向最后一个结点的前驱结点。

Summary

跟设计相关的题目的难点不在算法复杂度上，而是在理解题意和如何实现上。特别是第二个题目，有些地方其实交代的不是很清楚。特别是“第 index 个”这种说法，很容易让人产生误解。假如 index 是 3，到底是第 3 个结点呢，还是第 4（0，1，2，3） 个结点呢？当然，这个题目是第 4 个。
其实，不管是 3 还是 4，如果在这种问题上耗费太多时间，就没有意义了...尽管这个题把链表的大部分操作都考到了，但是还是觉得有不足的地方。

Buy me a coffee ? :)
0%