学习日记-2019527

发表于 |

AcWing 137雪花雪花雪花，Python逆序循环，Python List删除元素，Python re模块解析，Python KMP算法实现字符串匹配

剑指刷题：2019/5/27

AcWing 137雪花雪花雪花

【转】https://blog.csdn.net/qq_30277239/article/details/90273218

字符串的最小表示法：

求一个字符串的循环同构体中最小字典序的那个。比如bcda的循环同构体有bcda，cdab，dabc，abcd，其中最小表示法是abcd。

暴力求解O(n$^2$)：

定义双指针i = 0，j = 1，首先a < b所以字符串的第二个位置不会作为最优解字符串的开头，同理，后面的cd也都不会作为字符串的开头，直到j = 4匹配到了另一个a，于是i，j均右移，发现后面的bc也都相等，继续右移，直至遇见了d < e,所以abce不可能是最小表示法的前缀，然后j又回到下标为5的位置，i也回到开头，a < b，继续比较。

优化：

j指针不再跳回原位置进行下一次匹配，直接从字典序大的那个开始

例如：

abcdabcebdd

adcebddabcd

两个循环同构体在d和e的位置失配时，第一个指针重新回到下标为0的位置，而第二个指针不需要在从下标为0的位置的后一个位置再进行比较，既然abce都失去了前缀的资格，那么第二个指针从第五个字符b再次开始比较即可

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
# -*- coding: utf-8 -*-
# @Time    : 2019/5/27 14:46
# @Author  : zhengjiani
# @Software: PyCharm
# @Blog    ：https://zhengjiani.github.io/
"""
题目描述：
有N片雪花，每片雪花由六个角组成，每个角都有长度。第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1,ai,2,…,ai,6。
因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。
例如ai,1,ai,2,…,ai,6和ai,2,ai,3,…,ai,6，ai,1就是形状相同的雪花。ai,1,ai,2,…,ai,6和ai,6,ai,5,…,ai,1也是形状相同的雪花。
我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。求这N片雪花中是否存在两片形状相同的雪花。
"""
import sys
#字符串的最小表示法
def find_min(s):
    i = 0 #起始指针
    j = 1 #指向第一位
    k = 0 #匹配长度
    size = len(s)
    while i<size and j<size and k<size:
        a = (i+k) % size
        b = (j+k) % size
        if s[a] == s[b]:
            k += 1
        elif s[a]>s[b]:
            i += k+1
            k = 0 #已匹配长度置0
        else:
            j += k+1
            k = 0
        if i==j:
            j += 1
    return min(i,j)#返回最小表示的位置

def main():
    s = 'bcdabcebdd'
    print(find_min(s)+1)#4,也就是a所在字符串的位置

if __name__ == '__main__':
    main()

本题需要判断雪花是否相同，只要两片雪花的六个角的最小表示法相同，我们就可以断定这两片雪花完全相同，所不同的是：上面介绍的最小表示法只能自左往右循环，而本题可以自右向左循环，只需读入时备份一下逆置的数组，然后仅保留两个数组的最小表示即可。

本题的主要思路就是，先对所有雪花都哈希映射到某个值，只有两片雪花散列后的值相等时他们才可能相等，再比较他们的最小表示法即可验证。

Python逆序循环

1
2
3
4
5
6
7
8
#逆序循环
def removeElement2(nums,val):
    """原地删除指定元素"""
    j = len(nums)
    for i in range(j-1,-1,-1):
        if nums[i] == val:
            nums.pop(i)
    return len(nums)

Python List删除元素

1.使用del删除元素

根据索引删除，删除索引范围内的元素，删除整个列表，del操作没有返回值

1
2
3
l = [1,2,3,4]
del l[3]
#[1,2,3]

2.使用list方法pop删除元素

根据索引删除，返回索引位置的元素

1
2
3
l = [1,2,3,4]
l.pop(2)
#[1,2,4]

3.使用切片删除元素

1
2
3
l = [1,2,3,4]
l = l[:2]+l[3:]
#[1,2,4]

4.使用list方法remove删除指定值的元素

删除第一个符合条件的元素

1
2
3
l = [1,2,3,4]
l.remove(3)
#[1,2,4]

Python re模块解析

提前编译正则表达式

http://www.codebelief.com/article/2017/01/python-standard-library-re-module-functions/

1
2
3
4
5
6
7
8
import re
re.compile(pattern,flags=0)
#等价写法
prog = re.compile(pattern)
result = prog.match(string)
#等价于
result = re.match(pattern,string)
#提前编译可以提高速度

仅匹配第一个满足条件的字符串

1
2
3
4
re.search(pattern, string, flags=0)
#eg1
re.search('ll', 'helloll', flags=0)
#output:<re.Match object; span=(2, 4), match='ll'>

仅匹配字符串的起始位置子串

1
2
3
4
re.match(pattern, string, flags=0)
#eg1
re.match('ll', 'helloll', flags=0)
#output:None

通过匹配表达式来切割字符串

如果指定了 maxsplit 的值，且不为0，那么最多进行 maxsplit 次的字符串切割操作。最后剩下的未被切割的字符串，将作为一个整体添加到结果列表中。这种情况下，结果列表最多会有 maxsplit + 1 项。

1
2
3
4
5
6
re.split(pattern, string, maxsplit=0, flags=0)
#eg1
re.split('ll', 'helloll', flags=0)
#output:['he', 'o', '']
re.split('ll', 'helloll', maxsplit=1,flags=0)
#output:['he', 'oll']

以列表的形式返回所有不重叠的匹配结果,空匹配结果同样会被添加到列表中。

如果表达式中含有捕获分组，那么表达式匹配到的结果中，只有捕获分组里的内容会被添加到结果列表中

1
2
3
4
5
re.findall(r'(\w)\d', 'a1 b2 c3 d4')
#output:['a', 'b', 'c', 'd']
#捕获分组
re.findall(r'(\w)(\d)', 'a1 b2 c3 d4')
[('a', '1'), ('b', '2'), ('c', '3'), ('d', '4')]

返回一个迭代器，包含所有不重叠的匹配结果，空匹配结果同样会被添加到列表中。

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
f = re.finditer(pattern, string, flags=0)
for i in f:
    print(i)
    print(i.span())#元组形式
#eg:
"""
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
输入: haystack = "hello", needle = "ll"
输出: 2
"""
import re
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if needle not in haystack:
            return -1
        if needle == '':
            return 0
        n1 = len(haystack)
        n2 = len(needle)
        f = re.finditer(needle,haystack)
        for i in f:
            return i.span()[0]

返回一个被替换后的字符串

1
2
3
4
5
6
7
8
9
10
11
re.sub(pattern, repl, string, count=0, flags=0)
#count指定匹配次数
text = 'a1 b2 c3'
re.sub(r'(\w)(\d)', r'\2\1', text)
#output:'1a 2b 3c'
#repl是函数，每一次匹配成功时被调用，返回值是替换后的字符串
def foo(matchobj):
...     if matchobj.group(0) == '-': return '+'
...     else: return '*'
re.sub(r'\D', foo, '1-2/4')
#output:'1+2*4'

Python KMP算法实现字符串匹配

KMP算法：

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

部分匹配值表：前缀和后缀的最长的共有元素长度

移动位数 = 已匹配的字符数 - 对应的部分匹配值

nexts数组即为部分匹配值表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
部分匹配表
获取“模式串”的部分匹配值
"""
def pmt(s):
    prefix = set()
    postfix = set()
    ret = [0]
    for i in range(1, len(s)):
        prefix.add(s[:i])
        postfix = {s[j:i + 1] for j in range(1, i + 1)}
        ret.append(len(prefix & postfix))
    return ret
if __name__ == '__main__':
    _next = [0]*len("ABCDA")
    getNext("ABCDA",_next)
    print(_next)