Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >数据结构学习-python实现01--0401

数据结构学习-python实现01--0401

原创
作者头像
到不了的都叫做远方
修改于 2020-04-02 02:16:58
修改于 2020-04-02 02:16:58
50100
代码可运行
举报
运行总次数:0
代码可运行

经过近两年多的转行自学,乱七八糟的学了不少的东西,依然没有走到自己想要去的方向,继续学习,努力吧!

本来学习机器学习,学了一遍sklearn,然后想从头学些常用算法,发现写代码的时候,还是需要数据结构方面的知识,于是暂缓继续机器学习的学习,把数据结构与算法过一遍,一点一点进步。

算法问题分类:

  • 1.what:判断与分类
  • 2.why:求因与证明
  • 3.how:过程与构建

我非常喜欢今天看的MOOC当中的老师讲解的这一段,虽然很基础,但是感觉他不单对我的算法学习进行了开导,而且对我现实生活的思考方式,有了一定的影响。

一、今天学习编写了三段小程序,是检查“变位词”的三种python算法:

代码语言:python
代码运行次数:0
运行
AI代码解释
复制
第一种:逐字检查法:
def anagramSolution(s1, s2):
    if len(s1) == len(s2):  # 先查长短,快速判断
        alist = list(s2)  # 字符串可以索引,但不可变,将其变为列表
        pos1 = 0  # 位置参数
        stillOK = True  # 判别条件,由于需要跳出条件控制,及最终返回值
        while pos1<len(s1) and stillOK:
            pos2 = 0
            found = False  # 查找到具体值时使用的标记
            while pos2<len(alist) and not found:
                if s1[pos1] == alist[pos2]:
                    found = True
                else:
                    pos2 += 1
            if found:
                alist[pos2] = None
            else:
                stillOK = False
            pos1 += 1
        return stillOK
    else:
        return False
# 遇到的坑:
# 1、我在 if found 处缩进出了问题,当有重复字母时,不能识别,注意缩进,保证一次循环,只更改一个位置的值
# 2、忘记pos1 += 1,导致死循环,由于之前总是用for循环,导致使用while时忘记停止条件。

代码语言:python
代码运行次数:0
运行
AI代码解释
复制
第二种算法:排序比较,老师说时间复杂度较高,sort()排序会比较耗时。
def sortword(s1, s2):
    alist = list(s1)
    blist = list(s2)
    
    alist.sort()
    blist.sort()
    pos = 0
    matches = True
    while pos<len(s1) and matches:
        if alist[pos] == blist[pos]:
            pos +=1
        else:
            matches = False
    return maches

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
第三种:计数比较法,相对最快。
def numcount(s1, s2):
    c1 = [0] * 26
    c2 = [0] * 26
    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')  # 用ASCII码值标记位置
        c1[pos] += 1
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] += 1
    j = 0
    stillok = True
    while j < 26 and stillok:  # 判断每个字母出现的次数是否相同
        if c1[j] == c2[j]:
            j += 1
        else:
            stillok = False
    return stillok

其实有第四种,暴力法,没有试,需要学习。

二、今天学习了第一种线性结构--栈(一种有序的数据项的集合,遵循后进先出的原则LIFO)

栈可以用在很多地方,今天学习到的应用方面是:

  • 1.判断括号是否正确的闭合、推广可以判断前段页面的代码闭合情况。
  • 2.可以用于中缀、前缀、后缀表达式的计算问题。
代码语言:python
代码运行次数:0
运行
AI代码解释
复制
# 一个基本的栈结构:用列表来实现栈,列表前段为栈底,后端为栈顶,这样使用append、pop会更快O(1)的复杂度
class Stack:
    def __init__(self):  # 创建栈,首先为空栈
        self.items = []
        
    def isEmpty(self):  # 判断栈是否为空,需要返回值,True/False
        return self.items == []
    
    def push(self, item):  # 入栈操作,不需要返回值,加入栈顶
        self.items.append(item)
        
    def pop(self):  # 出栈操作,有返回值,移除栈顶元素
        return self.items.pop()
    
    def peek(self): # 查看栈顶元素, 有返回值
        return self.items[len(self.items)-1]
    
    def size(self):  # 查看站内元素数,有返回值
        return len(self.items)

代码语言:python
代码运行次数:0
运行
AI代码解释
复制
# 利用栈判断括号闭合情况
def symbolChecker(symbolString):
    s = Stack()  # 首先建立一个空栈
    balanced = True  # 假设栈括号是对应的。
    index = 0  # 利用索引
    
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in '({[':  # 入栈判断
            s.push(symbol)
        else:
            if s.isEmpty():  # 判断栈是否为空,在此处的括号,让我纠结了一小时,为什么没判断正确。
                balanced = False
            else:
                top = s.pop()
                if not matches(top, symbol):
                    balanced = False
        index += 1
                
    if balanced and s.isEmpty():
        return True
    else:
        return False
    
def matches(open, close):  # 栈顶的括号,需要和新出现的括号配对,才能证明其正确性。此处利用位置匹配
    opens = '([{'  # 位置对应
    closers = ')]}'  # 位置对应
    return opens.index(open) == closers.index(close)
    
    
print(symbolChecker('({{}})'))

# 查错办法:1.在有输出结果处打印变量,检查哪里的分支没有进入。检查未进入原因,修改代码!

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
数据结构学习-python实现-树--0414
树的实战应用:解析树。 import stack # 之前写好的栈 import binarytree # 之前写好的二叉树 import operator # 处理运算符 def buildparsetree(fpexp): print(fpexp) # 打印输入,避免出问题,例如不符合解析形式,这段代码必须是全括号。 fplist = list(fpexp) pstack = stack.Stack() etree = binarytree.BinaryTre
到不了的都叫做远方
2020/04/14
5330
数据结构与算法基础-(2)
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
ImAileen
2024/01/18
1550
数据结构与算法基础-(2)
数据结构与算法基础-(5)---栈的应用-(1)括号匹配
我们都写过这样的表达式: ( 5 + 6 ) * ( 7 + 8 ) / ( 4 + 3 )
ImAileen
2024/01/18
2450
数据结构与算法基础-(5)---栈的应用-(1)括号匹配
python数据结构之堆栈
堆栈又称为栈或堆叠,是计算机科学中一种特殊的串列形式的抽象数据类型,其特殊之处在于只能允许在链表或数组的一端进行加入数据(push)和输出数据(pop)的运算。由于堆栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。
python与大数据分析
2022/03/11
3410
python数据结构之堆栈
学点算法之字符串的乱序检查
问题 字符串的乱序检查。 一个字符串是另一个字符串的乱序。如果第二个字符串只是第一个的重新排列,例如,’heart’ 和 ‘earth’ 就是乱序字符串。’python’ 和 ‘typhon’ 也是。为了简单起见,我们假设所讨论的两个字符串具有相等的长度,并且他们由 26 个小写字母集合组成。我们的目标是写一个布尔函数,它将两个字符串做参数并返回它们是不是回文。 解法1:检查 我们对乱序问题的第一个解法是检查第一个字符串是不是出现在第二个字符串中。如果可以检验到每一个字符,那两个字符串一定是回文。可以通过用
小歪
2018/04/04
1.4K0
学点算法之字符串的乱序检查
学点算法之栈的学习与应用
在学习栈前,脑海中对这个词只有一个印象:客栈 栈是什么 栈(有时称为“后进先出栈”)是一个项的有序集合,其中添加移除新项总发生在同一端。 这段话初学者是懵逼的,别急,往下看。 对栈的一般操作: Stack() 创建一个空的新栈。 它不需要参数,并返回一个空栈。 push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。 pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。 peek() 从栈返回顶部项,但不会删除它。不需要参数。 不修改栈。 isEmpty
小歪
2018/04/04
7590
学点算法之栈的学习与应用
【Python数据结构与算法】线性结构小结
栈Stack维持了数据项后进先出LIFO的次序 stack的基本操作包括push,pop,isEmpty
ImAileen
2024/01/18
1810
【Python数据结构与算法】线性结构小结
使用栈解决实际面试问题
数据结构这门学了很多遍,基本概念都知道,而且还很熟。可就是在实际工作中找不到应用的地方。这个问题,应该是大部分人都遇到的问题。今天我们使用栈来解决一个实际问题。
TalkPython
2020/05/27
5090
数据结构学习-python实现-数据查找--0410
数据查找算法的实质是数据的比对。 1.确定基本步骤 2.步骤足够简单,并反复执行。 3.查找次数介于1和n之间,平均为n/2,算法复杂度为O(n) # 无序表的顺序查找 def sequentialsearch(alist, item): pos = 0 found = False while pos < len(alist) and not found: # 退出while循环的两种方式 if alist[pos] == item: fo
到不了的都叫做远方
2020/04/10
3610
数据结构学习-python实现-数据排序--0411
数据为何要排序?首先想到的是排序的数据能够更加便于观察,并更好的使用查找算法,降低复杂度。
到不了的都叫做远方
2020/04/11
3800
线性结构 队列与栈
栈(Stack)是一种遵循先进后出(LIFO)原则的有序列表,新添加或待删除的元素都保存在栈的一端,这一端被称作为栈顶,另一端被称作为栈底。在栈里,新元素都靠近栈顶,旧元素都靠近栈底。
py3study
2020/01/02
4250
数据结构学习-python实现02--0402
今日继续进行了队列及单链表的学习。 一、队列,先进先出的有序结构。基础代码如下: # 基本队列的代码 class Queue: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def enqueue(self, item): self.items.insert(0, item)
到不了的都叫做远方
2020/04/02
4050
数据结构与算法基础-(4)
抽象数据类型(ADT - Abstract Data Types) ------------> " 栈 " 是一个有次序的数据集,每个数据仅从" 栈顶 " 一端加入到数据集中,从数据集中移除,栈具有后进先出LIFO的特性.
ImAileen
2024/01/18
1340
数据结构与算法基础-(4)
数据结构与算法——打开编程世界的大门
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。它是组织和存储数据的方式,以便于对数据进行高效的访问、插入、删除、搜索和排序等操作。
Xxy_1008
2024/08/12
2200
数据结构与算法——打开编程世界的大门
python使用list实现栈
# -*- coding: utf-8 -*- """ @author: sato @file: stack.py @time: 2019-08-22 00:06 """ class Stack(object): def __init__(self): self.items = [] def is_empty(self): return len(self.items) == 0 def push(self, item): s
用户2458545
2022/09/07
4190
数据结构[Python--Stack]
难得有些许空闲,看一下Python的数据结构--Stack,现将几个典型示例进行总结!
py3study
2020/01/07
4540
数据结构小记【Python/C++版】——栈篇
元素在栈中的移动顺序依照后进先出(LIFO)原则,较早入栈的元素,更接近栈底,更晚被弹出。
Coder-ZZ
2023/02/23
3000
数据结构小记【Python/C++版】——栈篇
【苏州程序大白用2万字】解析数据结构和八大排序算法☀️《❤️记得收藏❤️》
我们的计算机实验室有 30 台计算机与一台打印机联网。当学生想要打印时,他们的打印任务与正在等待的所有其他打印任务“一致”。第一个进入的任务是先完成。如果你是最后一个,你必须等待你前面的所有其他任务打印。
苏州程序大白
2021/09/14
4780
【苏州程序大白用2万字】解析数据结构和八大排序算法☀️《❤️记得收藏❤️》
数据结构与算法-(7)---栈的应用-(3)表达式转换
像 * 这种操作符( operator ) 介于操作数 ( operand )中间的表示法,称为 "中缀" 表示法.
ImAileen
2024/01/18
2300
数据结构与算法-(7)---栈的应用-(3)表达式转换
用js来实现那些数据结构05(栈02-栈的应用)
  上一篇文章我们一起实现了栈,那么这一篇文章我们一起来用栈解决问题。看看如何用栈来解决进制转换,平衡圆括号以及汉诺塔问题,使我们对栈有更为深入的理解。 1、进制转换 我们先来看看十进制如何转换成二进制,十进制整数转换为二进制整数采用"除2取余,逆序排列"法。具体做法是:用2整除十进制整数,可以得到一个商和余数;再用2去除商,又会得到一个商和余数,如此进行,直到商为0时为止,然后把先得到的余数作为二进制数的低位有效位,后得到的余数作为二进制数的高位有效位,依次排列起来。简单来说就是拿十进制数去除以二,如果
zaking
2018/05/02
8690
用js来实现那些数据结构05(栈02-栈的应用)
相关推荐
数据结构学习-python实现-树--0414
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验