题解

LeetCode： 链表K组翻转 | Collection函数

K个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明 :
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路：

  • 采用递归的方法。按K个节点一组向后推进，直到剩下的节点少于K；
  • 从链表后端往前，把每组节点传入reverse进行翻转；
  • reverse将第一个节点指向末尾 tail，然后第二个节点指向第一个节点，第三个节点指向第二个节点…此时得到该组反转后的链表。reverse返回反转后链表的链表头；
  • 该链表头回到reverseKGroup后，被作为下一次reverse的tail，这样一组接一组就可以连成一整个链表了。
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
class Solution:
    def reverse(self,head,q,tail):
        if head==q:#防止K==1的情况
            return head
        now,pre,nxt=head,head.next,tail#这里将nxt设为tail，让当前组和之前的结果连接在一起
        while pre!=q:#逆转链表
            now.next=nxt
            nxt=now
            now=pre
            pre=pre.next
        pre.next=now
        now.next=nxt
        return pre#返回重置后链表的头（即初始链表的尾
        
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        q,num,tail=head,k,None
        if not head :
            return None
        while q.next!=None and num>1:
            q=q.next
            num-=1
        if num==1 and q.next:
            tail=self.reverseKGroup(q.next,k)#从后往前得到每组运算后的结果
        elif num!=1:#如果当前剩余节点小于K，不用逆转
            return head 
        pre=self.reverse(head,q,tail)#这里tail被传入了
        return pre#返回重置后链表的头

串联所有单词的字符

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = “barfoothefoobarman”,
words = [“foo”,”bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：
输入：
s = “wordgoodgoodgoodbestword”,
words = [“word”,”good”,”best”,”word”]
输出：[]

思路：

  • 一开始我想的是对words全排列，然后在s上滑动窗口。提交之后超时了，确实还是复杂度太高了。看了其他的题解发现可以用colletions库中的Count快速实现。collections库我不太清楚，所以后面还会跟一个collection库的学习笔记。
  • 首先先从collection import Count，将words列表变成一个Count字典，此时words里只有” 单词 : 它在words中的个数”
  • i=0 开始向后遍历，得到每组子串为 s[i:i+words的长度]
  • 由于words中每个单词的长度都一样，所以把当前子串按照单词长度拆开，变成Count字典，即可得到当前子串的” 单词:数量 “
  • 将子串和words的Count字典比较，如果两个一致则当前子串是个“串联所有单词的字符”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        from collections import Counter
        if not words or not s:
            return []
        lens,lenw,lenws,res=len(s),len(words[0]),len(words),[]
        words=Counter(words)
        for i in range(lens-lenw*lenws+1):
            cur_s=s[i:i+lenw*lenws]
            tep_s=[]
            for j in range(0,len(cur_s),lenw):
                tep_s.append(cur_s[j:j+lenw])
            if words==Counter(tep_s):
                res.append(i)
        return res

Collection库

namedtuple()

命名元组赋予每个位置一个含义，提供可读性和自文档性。它们可以用于任何普通元组，并添加了通过名字获取值的能力，通过索引值也是可以的。

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
Point=nametuple("Point",['x','y'])
p=Point(11,y=12)

p[0]+p[1]
>>>23
p.x+p.y
>>>23
x,y
>>>11,12
p
>>>Point(x=11,y=12)

##### deque
优化过的双向队列，两端的开销都是O(1) 。
常用的方法有：
```py
s='ijk'
dq=deque(s)
dq.append('x')#在右边加入x
dq.leftappend('y')#在左边加入y
dq.pop()#弹出右边
dq.leftpop()#弹出左边

dq.extend('shzuecs')#右边加入这一堆东西
dq.leftextend('uuxhuf')#左边加入这一堆
dq.clear()#消除全部

dq.pop()#报错，弹出IndexError
ChainMap
1
2
3
4
5
6
7
8
baseline = {'music': 'bach', 'art': 'rembrandt'}
adjustments = {'art': 'van gogh', 'opera': 'carmen'}

ChainMap(adjustments, baseline)
>>>ChainMap({'music': 'bach', 'art': 'rembrandt'}, {'art': 'van gogh', 'opera': 'carmen'})

list( ChainMap(baseline,adjustments))
>>>['art', 'opera', 'music']

ChainMap 的作用是将多个字典组合在一起，虽然创建一个新字典或者原字典update也可以实现这个功能，但比起通过ChainMap实现还是慢了很多。
可以通过key输出值，不过若被连接的两个字典有同样的key，仅输出前一个字典的value

Counter
1
2
3
4
5
6
cnt = Counter()
for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
    cnt[word] += 1

print(cnt)
>>>Counter({'blue': 3, 'red': 2, 'green': 1})

Counter用于将输入列表的单词和单词频率以字典形式返回。Counter操作的对象必须是可哈希的，元组、字符串、number类都是可哈希的对象，而列表、字典是不可哈希的。

之前做过一道单词统计题，show-me-the-code(python)第 0004 题：任一个英文的纯文本文件，统计其中的单词出现的个数。就可以使用Counter来做。

1
2
3
4
5
with open(filepath, 'r', encoding='utf-8') as f:
    s=f.read()
pattern = "\w+"
lst = re.findall(pattern, s)#原文提取单词加入列表
res = Counter(lst)#输出单词: 频率 字典
defaultdict

是一个可以指定默认值的字典类型，和传统dic相比就多了这个功能，其他的都一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
d = defaultdict(list)#默认值是list，首次遇到key时，字典中没有这个键值对，创建键值对，值为list
for k, v in s:
    d[k].append(v)#可以在创建的list上append了

print(d)
>>>[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

s='dihcuahif'
d=defaultdict(int)
for i in s:
    d[i]+=1
>>> sorted(d.items())
[('i', 4), ('m', 1), ('p', 2), ('s', 4)]

defaultdict通过重写missing实现这个功能，创建defaultdict对象时，括号中参数为default_factory，若missing函数找不到当前键值，将该键的值设为default_factory，随后返回。