侯瑞哲的博客

Ruizhe's Blog

0%

发表于 更新于 Valine：

思路， 首先一个哨兵结点可以帮我们省去判断边界的代码，建立哨兵，并且令dummy.next = head

将pre指向开头

循环开始，只要head不为nil

令tail = pre

tail往下走k步，只要tail为nil，立即返回dummy.next

nxt记录下tail.next，head即将走向的下一个结点

反转head到tail中的节点，返回新的head和tail

def reverse(head, tail):

​ 反转代码，令pre指向tail.next，cur指向head

​ while prev != tail:

​ nxt = cur.next

​ cur.next = prev

​ prev = cur

​ cur = nxt

​ return tail, head

将pre的next指向新的head

pre.next = head

尾部已相连

更新pre指向tail

head指向nxt

最终head为nil时退出循环

返回dummy.next

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
27
28
29
30
31
32
33
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy

        while head:
            tail = pre
            # 查看剩余部分长度是否大于k
            for _ in range(k):
                tail = tail.next
                if not tail:
                    return dummy.next
            nxt = tail.next
            head, tail = self.reverse(head, tail)
            # 把子链表重新串联起来
            pre.next = head
            pre = tail
            head = nxt
        return dummy.next

    def reverse(self, head, tail):
        prev = tail.next
        cur = head
        while prev != tail:
            cur.next, cur, prev = prev, cur.next, cur
        return tail, head

发表于 Valine：

wiki 百科上的介绍：

Trie，字典树，也叫前缀树。是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，尔根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和比分内部节点所对应的键才有相关的值。

应用：

trie常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

要实现的方法

一般来讲trie要实现这么几个方法

  • 插入一个单词insert(word: str) -> None
  • 查找一个单词是否在trie中search(word:str) -> bool
  • 查找一个前缀是否在trie中startsWith(prefix:str) -> bool

leetcode上的208题实现trie

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
27
28
29
30
31
32
33
34
35
36
37
38
39
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.end_of_word = '#'

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end_of_word] = self.end_of_word

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.end_of_word in node

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

通常情况下没有必要使用一个trie node表示一个trie的节点，存入hash表和是否是结尾。结尾可以用一个特殊字符代替，判断这个字符是否在hash表中。这样每一个节点其实都是一个hash表。

发表于 Valine：

还记得刚拔完最后一颗智齿那天，去超市买了一个西瓜，虽然不能张口吃东西，甚至不能说话，但是买了西瓜，冰镇着，心里就很高兴。

发表于 更新于 Valine：

python实现并查集

并查集概念

并查集（UnionFind）也被称为不相交集数据结构。顾名思义，并查集主要操作是合并与查询，它是把初始不相交的集合经过多次合并操作后合并为一个大集合，然后可以通过查询判断两个元素是否已经在同一个集合中了。

并查集的应用场景一般就是动态连通性的判断，例如判断网络中的两台电脑是否连通，在程序中判断两个变量名是否指向同一内存地址等。

并查集的实现

并查集的存储结构

并查集逻辑上是森林，我们可以选出一个根结点作为代表，其他子结点指向根结点表示都在同一片森林中。在这里，并不关心结点的子结点是谁，只关心父结点是谁，所以物理上可以简单用python的列表来表示并查集，列表的下标表示结点，列表元素的值表示父结点。

并查集的API

根据并查集的特性，可以设计以下api

1
2
3
4
5
6
7
8
9
10
11
12
13
class UnionFind(object):
  """并查集"""
  def __init__(self, n):
    """长度为n的并查集"""
    
  def find(self, p):
    """查找p的根结点（祖先）"""
    
  def union(self, p, q):
    """连通p,q 让q指向p"""
    
  def is_connected(self, p, q):
    """判断pq是否已经连通"""

并查集的初始化

并查集的初始化有几种，无非就是用一种特殊的方式来表示初始的每一个元素都不相交，等待后续的合并操作。

第一种初始化的方式是用列表的下标初始化对应位置的值，当一个并查集S[i] == i时则判断它自己就是根结点。

1
2
3
4
def __init__(self, n):
  """长度为n的并查集"""
  self.uf = [i for i in range(n + 1)]      # 列表为0位置空出
  self.sets_count = n                                      # 判断并查集里共有几个集合，初始化默认互相独立

第二种初始化方式将列表每一个结点初始化为-1，列表的节点值为负数表示它自己就是根结点，这样做还有一个好处可以用-n表示自己的子结点数量，下面的按规模优化中可以让结点数量小的树并到结点多的树上，提高find操作的效率。我们就选用这种方式来初始化。

1
2
3
4
def __init__(self, n):
  """长度为n的并查集"""
  self.uf = [-1 for i in range(n + 1)] # 列表0位置空出
  self.sets_count = n                                       # 判断并查集里共有几个集合，初始化默认互相独立

并查集的查询

查询操作是查找某个结点所在的集合，返回该集合的根结点，即返回列表的下标。下面是一种简单的查询，代码如下。

1
2
3
4
def find(self, p):
  while self.uf[p] >= 0:
    p = self.yf[p]
  return p

可以很清楚的看出上面的方法很简单，找到结点元素值为负的表示找到了根结点并返回，但是该种方法在极端情况下（由树退化为链表）效率不高，查找的效率为O(n)，如左下图所示

查询是并查集的核心操作之一，它的效率也决定了整个算法的效率，所以在规模很大的情况下，O(n)的时间的复杂度是不被接受的，那就需要改进，改进的方法就是路径压缩。路径压缩的思想也很简单，就是在查找根结点的过程中，顺便把子结点的父结点改成根结点，这样下次查询的效率只需要O(1)的时间复杂度就可以完成，大大提高了效率。改进后效果图如右上图所示。

路径压缩的find操作可以通过递归来实现

1
2
3
4
5
6
def find(self, p):
  """尾递归"""
  if self.uf[p] < 0:
    return p
  self.uf[p] = self.find(self.uf[p])
  return self.uf[p]

可以发现这个递归是尾递归，可以改进成循环的方式

1
2
3
4
5
6
7
8
def find(self, p):
  """查找p的根节点（祖先）"""
  r = p                                                           # 初始p
  while self.uf[p] > 0:
    p = self.uf[p]
  while r != p:                                           # 路径压缩，把压缩下来的结点祖先全指向根结点
    self.uf[r], r = p, self.uf[r]
  return p

并查集的合并

合并两棵树的操作可以简单的规定让右边的树的根结点指向左边树的根结点，示意图如左下图所示。

直接右往左合并的缺点就是当右边的规模大于左边的规模时，在查找时，做路径压缩需要把右边所有的根结点更改为左边的根结点，如右上图所示，这明显有些划不来，所以合并的一种优化方式就是按规模合并，即吧规模小的树往规模大的树上合并。其实还有一种按秩合并（树高度小的往高度大的合并而不改变树的整体高度）。但是这种方法不与路径压缩兼容，因为路径压缩直接改变了数的高度，所以本人选择按规模合并和路径压缩结合的方式优化并查集。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
def union(self, p, q):
  """连通p, q 让q指向p"""
  proot = self.find(p)
  qroot = self.find(q)
  if proot == qroot:
    return
  if self.uf[proot] > self.uf[qroot]:     # 负数比较，左边的规模更小
    self.uf[qroot] += self.uf[proot]
    self.uf[proot] = qroot
  else:
    self.uf[proot] += self.uf[qroot]       # 规模相加
    self.uf[qroot] = proot
  self.sets_count -= 1                  # 连通后集合总数减一

连通性的判断

有了查找操作，判断两个结点是否连通就显得容易多了，一行代码就可以搞定，就是判断他们的根结点是否相同。

1
2
3
def is_connected(self, p, q):
  """判断pq是否已经连通"""
  return self.find(p) == self.find(q)   # 即判断两个结点是否是属于同一个祖先

完整代码附录

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class UnionFind(object):
    """并查集类"""
    def __init__(self, n):
        """长度为n的并查集"""
        self.uf = [-1 for i in range(n + 1)]    # 列表0位置空出
        self.sets_count = n                     # 判断并查集里共有几个集合, 初始化默认互相独立

    # def find(self, p):
    #     """查找p的根结点(祖先)"""
    #     r = p                                   # 初始p
    #     while self.uf[p] > 0:
    #         p = self.uf[p]
    #     while r != p:                           # 路径压缩, 把搜索下来的结点祖先全指向根结点
    #         self.uf[r], r = p, self.uf[r]
    #     return p

    # def find(self, p):
    #     while self.uf[p] >= 0:
    #         p = self.uf[p]
    #     return p

    def find(self, p):
        """尾递归"""
        if self.uf[p] < 0:
            return p
        self.uf[p] = self.find(self.uf[p])
        return self.uf[p]

    def union(self, p, q):
        """连通p,q 让q指向p"""
        proot = self.find(p)
        qroot = self.find(q)
        if proot == qroot:
            return
        elif self.uf[proot] > self.uf[qroot]:   # 负数比较, 左边规模更小
            self.uf[qroot] += self.uf[proot]
            self.uf[proot] = qroot
        else:
            self.uf[proot] += self.uf[qroot]  # 规模相加
            self.uf[qroot] = proot
        self.sets_count -= 1                    # 连通后集合总数减一

    def is_connected(self, p, q):
        """判断pq是否已经连通"""
        return self.find(p) == self.find(q)     # 即判断两个结点是否是属于同一个祖先

转载

出处：https://www.cnblogs.com/yscl/p/10185293.html

作者：yscl

参考

  • 数据结构--并查集的原理及实现
  • 并查集(Union-Find)算法介绍

其他并查集

普通的并查集只是简单的记录了和集合的关系，即判断是否属于该集合，而带权并查集则是不仅记录了和集合的关系，还记录了集合内元素的关系，一般就是指代集合内元素和根结点的关系，实现起来也很简单，就是额外利用一个列表value[]，来记录每个节点与根结点的关系。然后在每次合并和路径压缩中更新权值。更新的规则遵循向量法则，处理环类关系的问题中，还可以取模更新。具体可以参考一下文章。

  • https://blog.csdn.net/yjr3426619/article/details/82315133
  • https://blog.csdn.net/u013075699/article/details/80379263
  • https://blog.csdn.net/sunmaoxiang/article/details/80959300

发表于 更新于 Valine：

现在这个社会，不光现在这个社会，实际上从有史以来，这个人，为了养家糊口，要学一门手艺。你包括你读书，你读到硕士，读到博士，你无非就是，学什么，都是为了找一份好工作。对吧，到最后。手艺人，是最吃香的。文凭，是个敲门砖，之后的一切素质，包括你工作上，用的一些东西，都是之后，进入社会，以后的再教育。

发表于 更新于 Valine：

上午11：30

大约10点开始拔的智齿，医生很温柔。用针都是很慢的，一针麻醉之后，渐渐的从舌根麻到舌尖。我这时心里挺安定的，既来之则安之。医生大概就用了20分钟。左下这颗智齿就拔完了。缝合的医生来缝了两针，就咬上了棉花止血。我出去坐在了椅子上，使劲咬着，没什么痛感，就是麻。这时大概10点40。坐了好一会，大概11点20，我打开手机，买了医生叮嘱昨天去药店还没买到的替硝唑，加上昨天买的罗红霉素，两种消炎药已经备齐了。拔牙的时候，听见医生说，现在手段都高级了，以前他拔牙的时候，北大医学院的医生，也要上锤子去拔，他疼了半个月。今天他给我做的是最微创的一种。两三天就好了，一天就能吃东西了。大概到了11点半，棉花咬得差不多了，医生叫进屋里要看一看血止的情况。我吐掉棉花球，医生看了看，血已经不流了。挺好，就可以走了。在11点半左右，我感谢了医生，走出了医院。伴随我的四颗智齿至此都已拔除。人的牙一共有32颗，我完成了很多人都会做的拔智齿，也和很多人一样还剩下28颗。

现在敷着冰袋。没什么痛感。挺好的。

发表于 Valine：

我一共有四颗智齿，上面两颗长的过程中有坏的现象，去年已经一并拔去。

因为这个手术不大，所以两颗智齿可以一起拔。晚上疼了一会，就过去了。

下面的两颗智齿，在长的过程中是横着长的，其实这是很常见的现象，如果不管，会挤坏掉好牙。

上周已经拔掉了一颗，医生在伤口上缝了针，也是疼了一晚上，没吃止痛药，甚至没吃消炎药，也好了。

今天，要拔最后一颗智齿了，至此困扰我的四颗智齿都将拔除。

按医生的话，我满口的牙也将从左右上下32颗变成28颗，不会再忍受因为智齿而难以刷干净的牙缝。

一切都是好兆头。