2022.01.2-redis为什么这么快

今天打了周赛，第四道hard周赛结束才过，菜鸡如我

参加会议的最多员工数

class Solution:
    def maximumInvitations(self, fa: List[int]) -> int:
        n = len(fa)
        pre = defaultdict(list)
        cnt =[0] * n
        for i in range(n):
            pre[fa[i]].append(i)
            cnt[fa[i]] += 1
        
        # 求最大的环
        vis = [False] * n
        q = deque()
        for i in range(n):
            if cnt[i] == 0:
                q.append(i)
        while q:
            cur = q.popleft()
            vis[cur] = True
            cnt[fa[cur]] -= 1
            if cnt[fa[cur]] == 0:
                q.append(fa[cur])
        
        res = 0
        def dfs(x, cnt):
            if not vis[x]:
                vis[x] = True
                dfs(fa[x], cnt + 1)
            else: 
                nonlocal res
                res = max(res, cnt)
        for i in range(n):
            if not vis[i]:
                dfs(i, 0)
                

        # 求互相喜欢的人连带着喜欢他们的人        
        res2 = 0
        def dfs2(x, y):
            res = 0
            for i in pre[x]:
                if i != y:
                    res = max(res, dfs2(i, y))
            return res + 1
        for i in range(n):
            if fa[fa[i]] == i and fa[i] > i:
                res2 += dfs2(i, fa[i]) + dfs2(fa[i], i)
    
        print(res, res2)
        return max(res, res2)

每日一题，挺有意思的数学题

390. 消除游戏

class Solution:
    def lastRemaining(self, n: int) -> int:
        # 1 2 3 4 5 6 
        #   3   2   1  => f(2k) = 2k + 2 - 2f(k)
        # 1 2 3 4 5 6 7
        #   3   2   1  => f(2k + 1) = 2k + 2 - 2f(k)
        return 1 if n == 1 else 2 * (n // 2 + 1- self.lastRemaining(n // 2)) 

三道剑指

剑指 Offer 06. 从尾到头打印链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if not head: return []
        return self.reversePrint(head.next) + [head.val]

剑指 Offer 24. 反转链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head
        pre = None
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

剑指 Offer 35. 复杂链表的复制

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        cur = head
        # 插入新节点
        while cur:
            nxt = cur.next
            cur.next = Node(cur.val, nxt, cur.random)
            cur = nxt
        cur = head.next            
        # 更新新节点的random
        while cur:
            cur.random = cur.random.next if cur.random else None
            cur = cur.next.next if cur.next else None
        cur = head
        # 拆分链表
        res = head.next
        while cur:
            nxt = cur.next.next
            cur.next.next = nxt.next if nxt else None
            cur.next = nxt
            cur = nxt
        return res

面试题：为什么redis这么快？

1、完全基于内存，绝大部分请求是纯粹的内存操作，非常快速。数据存在内存中，类似于HashMap，HashMap的优势就是查找和操作的时间复杂度都是O(1)；

2、数据结构简单，对数据操作也简单，Redis中的数据结构是专门进行设计的；

3、采用单线程，避免了不必要的上下文切换和竞争条件，也不存在多进程或者多线程导致的切换而消耗 CPU，不用去考虑各种锁的问题，不存在加锁释放锁操作，没有因为可能出现死锁而导致的性能消耗；

4、使用多路I/O复用模型，非阻塞IO；

5、使用底层模型不同，它们之间底层实现方式以及与客户端之间通信的应用协议不一样，Redis直接自己构建了VM 机制 ，因为一般的系统调用系统函数的话，会浪费一定的时间去移动和请求；
链接：https://juejin.cn/post/6844903663224225806