Python数据结构:BF算法、匹配括号、回文链表、生成螺旋矩阵、移除列表元素、计算后缀表达式的值、顺时针旋转n维矩阵90度、折半查找

Python数据结构:BF算法、匹配括号、回文链表、生成螺旋矩阵、移除列表元素、计算后缀表达式的值、顺时针旋转n维矩阵90度、折半查找,第1张

Python数据结构:BF算法、匹配括号回文链表、生成螺旋矩阵、移除列表元素、计算后缀表达式的值、顺时针旋转n维矩阵90度、折半查找

目录

BF算法匹配字符串

匹配括号

回文链表

生成螺旋矩阵

移除列表元素

计算后缀表达式的值

顺时针旋转n维矩阵90度

折半查找


BF算法匹配字符串

BF算法:通过模式串T,与目标串S匹配,查找S中是否存在模式串T;

实现思路:通过目标串S的下标取出元素与模式串下标取出元素进行依次比较,如果发生不匹配,则模式串的下标归零,目标串S指向下一个索引。

要求:输出匹配目标串的第一个下标位,不匹配输出-1

代码:

def bf(st, tem):
    i = j = 0
    while i < len(st) and j < len(tem):
        if st[i] == tem[j]:
            j += 1
        else:
            j = 0
        i += 1
    if j == len(tem):
        return i - len(tem)
    else:
        return -1


if __name__ == '__main__':
    print(bf('asdfasdx', 'dx'))

 结果:

匹配括号

匹配括号:输入小括号,中括号,大括号,判断是否匹配

实现思路:先定义一个字典存储括号,以后括号为键“),],}”,前括号为值“(,[,{”,再把键和值分别放入到新的列表中存储,使用栈的思想来匹配,通过下标取出的括号串的每一个元素,判断是键还是值,如果是值,也就是前括号,则进栈,如果是键则判断当前栈顶元素是否与之匹配,不匹配直接结束程序。

代码:

def match(s):
    assert len(s) > 0
    b = {')': '(', ']': '[', '}': '{'}
    k = b.keys()
    v = b.values()
    l = []
    for i in s:
        if i in v:
            l.append(i)
        elif i in k:
            if len(l) == 0 or l[-1] is not b.get(i):
                return False
            l.pop()
    return len(l) == 0


if __name__ == '__main__':
    print(match(input()))

结果:

回文链表

回文单链表:回文,12321则为回文,正读倒读都一样,判断链表是否是回文的,首先找到单链表的中点,获取中点采用快慢指针法,慢指针移动1格,快指针移动2格,当快指针到最大索引时,慢指针刚好到中点,把单链表的后半段逆置,再与前半段进行比较即可。

要求:输入字符串,中间使用一个空格间隔,转换为单链表,判断是否是回文链表

代码:

class linkNode:
    def __init__(self, d):
        self.data = d,
        self.next = None


def get_l(s):
    s = list(map(int, s.split(" ")))
    l = linkNode(0)
    p = l  # 引用传递
    for i in range(len(s)):
        p.next = linkNode(s[i])
        p = p.next
    return l.next


def palindrom(l):
    if l is None:
        return True;
    s = f = l
    while f.next is not None and f.next.next is not None:
        s = s.next
        f = f.next.next
    h = s.next
    q = reverser(h)
    s.next = None
    p = l
    while p is not None and q is not None:  # p和q都能为空,q为空循环完毕
        if p.data == q.data:
            p, q = p.next, q.next
        else:
            return False
    if q is None:  # q为空说明循环完毕了,说明匹配了
        return True
    return False


# 逆置链表
def reverser(h):
    l = linkNode(0)
    p = h
    while p is not None:
        x = p.next  # 保存当前项的指向
        p.next = l.next  # 当前项指向头结点的指向
        l.next = p  # 当前项指向头结点指向
        p = x
    return l.next


if __name__ == '__main__':
    l = get_l(input())
    print(palindrom(l))

结果:

生成螺旋矩阵

螺旋矩阵:[1,2,3],[8,9,4],[7,6,5]

代码

#生成螺旋矩阵,如下
# [1,2,3]
# [8,9,4]
# [7,6,5]
def spiral(n):
    matrix = [[0] * n for _ in range(n)]
    # 顺时针方向(右,下,左,上)
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    x = y = 0
    dn = 0  # 方向指针0;向右填充,1:向下填充,2:向上填充,3:向上填充

    for i in range(1, n * n + 1):  # 从1开始赋值,一直到n*n
        matrix[x][y] = i
        temp_x = x + dx[dn]
        temp_y = y + dy[dn]
        if 0 <= temp_x < n and 0 <= temp_y < n and matrix[temp_x][temp_y] == 0:
            x = temp_x
            y = temp_y
        else:
            dn = (dn + 1) % 4
            x += dx[dn]
            y += dy[dn]

    return matrix



if __name__ == '__main__':
    n = int(input("输入矩阵n值:"))
    matrix = spiral(n)
    for i in range(n):
        print(matrix[i])

结果

移除列表元素

代码:

# 输入一个列表lt,判断val是否在lt中,如果在,将其删除,最后输出删除后的lt和lt的长度

def remove_element(lt, val):
    k = 0
    for i in range(len(lt)):
        if lt[i] != val:
            lt[k] = lt[i]
            k += 1
    return k


if __name__ == '__main__':
    lt = list(map(int, input().split(' ')))
    val = int(input())
    k = remove_element(lt, val)
    print(k)  # 移除后的元素长度
    print(' '.join(map(str, lt[:k])))  # 输出移除后的新列表: lt[:k],从0开始截取,截取k位

结果:

计算后缀表达式的值

代码:

def get_value(lt):
    op = []
    i = 0
    while i < len(lt):
        opv = lt[i]
        if opv == "-":
            a, b = op.pop(), op.pop()
            op.append(b - a)
        elif opv == "+":
            a, b = op.pop(), op.pop()
            op.append(a + b)
        elif opv == "*":
            a, b = op.pop(), op.pop()
            op.append(a * b)
        elif opv == "/":
            a, b = op.pop(), op.pop()
            op.append(b / a)
        else:
            op.append(lt[i])
        i += 1
    else:
        return op[-1]


if __name__ == '__main__':
    lt = [56, 20, '-', 4, 2, '+', '/']
    print(get_value(lt))

结果:

顺时针旋转n维矩阵90度

把n维矩阵顺时针旋转90度

代码:

# 先对角线交换,再垂直交换
# [[2,3,4],
# [5,6,7],
# [8,9,1]]
# 翻转90度为
# [[8,5,2],
# [9,6,3],
# [1,7,4]]
# 1先对角线翻转为
# [[2,5,8],
# [3,6,9],
# [4,7,1]]
# 2再水平翻转
# [[8,5,2],
# [9,6,3],
# [1,7,4]]
# 4*4
# [[8,5,2,9],
#  [9,6,3,8],
#  [1,7,4,4],
#  [1,7,4,4]]

# 几层矩阵值,矩阵
def rotatin(n, matrix):
    mat = matrix
    # 对角线翻转
    # 0,0 0,1<=>1,0 0,2<=>2,0
    for i in range(n):
        for j in range(n - i):
            mat[i][j + i], mat[j + i][i] = mat[j + i][i], mat[i][j + i]
    # 水平翻转
    for x in range(n):
        for y in range(n // 2):  # 第一个与倒数第一个交换
            mat[x][y], mat[x][-y - 1] = mat[x][-y - 1], mat[x][y]
    return mat


if __name__ == '__main__':
    n = int(input("输入矩阵数:"))
    # matrix = [[2, 3, 4],
    #           [5, 6, 7],
    #           [8, 9, 1]]
    matrix = []
    for i in range(n):
        lt = list(map(int, input("第" + str(i + 1) + "行矩阵:").split(" ")))
        matrix.append(lt)
    matr = rotatin(n, matrix)
    for i in range(n):
        for j in range(n):
            if j == n - 1:
                print(matr[i][j], end="")
            else:
                print(matr[i][j], end="  ")
        print()

结果:

折半查找

折半查找:找出中点值(使用low=0和hight=n-1组成一个区间),判断查询值比中点索引值大还是小,如果小,则把高指针移动到low~mid这个区间里,再进行判断,重复进行即可。

要求:输出差查找到的位置,找不到输出-1

代码

# 折半查找
def BinSearch(R, k):
    n = len(R)
    low, high = 0, n - 1
    while low <= high:
        mid = (low + high) // 2
        if k == R[mid]:
            return mid
        if k < R[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1


if __name__ == '__main__':
    x = list(map(int, input().split(" ")))
    print(BinSearch(x, 3))

结果

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5689125.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存