在当今的计算机科学和软件开发领域,学习数据结构与算法具有诸多重要意义:
数据结构:
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。它是组织和存储数据的方式,以便于对数据进行高效的访问、插入、删除、搜索和排序等操作。
常见的数据结构包括:
算法:
算法是解决特定问题的一系列清晰、准确的步骤。它描述了如何对给定的输入进行处理,以得到期望的输出。
算法具有以下特性:
例如,排序算法(如冒泡排序、快速排序)、搜索算法(如线性搜索、二分搜索)等都是常见的算法。
学习数据结构与算法是一个逐步深入且需要不断实践的过程,学习数据结构与算法需要耐心、实践和不断的总结,坚持下去就能取得良好的效果,以下是一些建议:
TO SUM,把基础语法学会,学透彻,然后就是多刷题。接下来我将详解讲解 数据结构与算法 中的 枚举和双指针算法 并对实例题目做出详解,请耐心看完。
枚举算法,也称为穷举算法,是一种简单直接的算法思想。它的基本思路是将问题的所有可能解一一列举出来,然后逐一检验每个可能解是否满足问题的条件,从而得到问题的解。
枚举算法的优点是思路简单,容易理解和实现。但它的缺点也很明显,如果可能解的数量非常大,那么枚举的效率会很低。
例如,要找出 1 到 100 之间所有的质数,我们可以逐个检查每个数是否能被 2 到它自身减 1 的数整除,如果都不能整除,那么这个数就是质数。
双指针算法是通过控制两个指针在数组或链表等数据结构上移动来解决问题的一种方法。
常见的双指针类型有:
给定字符串列表 strs ,返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在,返回 -1 。
特殊序列 定义如下:该序列为某字符串 独有的子序列(即不能是其他字符串的子序列)。
s 的 子序列可以通过删去字符串 s 中的某些字符实现。
例如,"abc" 是 "aebdc" 的子序列,因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)。
示例 1:
输入: strs = "aba","cdc","eae"
输出: 3
示例 2:
输入: strs = "aaa","aaa","aa"
输出: -1
提示:
这道题有个制约条件,他要求在数组里面的值都不能被含有子序列,那我们的初步思路就是先给这个数组按照元素的长度进行一个排序,然后从长到短的遍历,一旦枚举到符合要求的字符串,就立刻返回其长度。如果没有符合要求的字符串,返回 −1。
class Solution:
def findLUSlength(self, strs: List[str]) -> int:
# 判断 s 是否为 t 的子序列
def is_subseq(s: str, t: str) -> bool:
i = 0
for c in t:
if s[i] == c:
i += 1
if i == len(s): # 所有字符匹配完毕
return True # s 是 t 的子序列
return False
strs.sort(key=lambda s: -len(s))
for i, s in enumerate(strs):
if all(j == i or not is_subseq(s, t) for j, t in enumerate(strs)):
return len(s)
return -1
首先,定义了一个名为 Solution 的类,其中包含一个名为 findLUSlength 的方法,该方法接受一个字符串列表 strs 作为参数。在这个方法内部,又定义了一个名为 is_subseq 的函数,用于判断一个字符串 s 是否为另一个字符串 t 的子序列。
在 is_subseq 函数中,使用一个索引 i 来遍历字符串 s 。然后通过遍历字符串 t 中的每个字符。当 t 中的字符与 s 中当前索引 i 所指向的字符相同时,就将索引 i 向后移动一位。如果在遍历完 t 之后,索引 i 已经到达了 s 的末尾,那就说明 s 是 t 的子序列,此时函数返回 True ;否则返回 False 。
回到 findLUSlength 方法,首先使用 lambda 函数根据字符串的长度对 strs 列表进行降序排序。
然后通过一个循环遍历排序后的 strs 列表。对于每个字符串 s ,再通过一个内层的循环遍历整个 strs 列表。通过条件判断来检查当前的字符串 s 是否为其他字符串的子序列。如果对于所有的索引 j (除了当前索引 i ),s 都不是字符串 t 的子序列,那就说明 s 不是其他字符串的子序列,此时返回 s 的长度。
如果遍历完整个 strs 列表都没有找到这样的字符串,就返回 -1 。
栈(Stack)是一种特殊的线性表数据结构,它具有以下特点:
操作受限:栈的操作主要是在一端进行,这一端被称为栈顶。可以对栈进行入栈(Push)和出栈(Pop)操作。
先进后出(First In Last Out,FILO):就像往一个桶里放东西和取东西,先放进去的元素要等到后放进去的元素都取出后才能取出。
应用场景广泛:常用于函数调用、表达式求值、括号匹配、回溯算法等。
例如,想象一个叠盘子的场景,你把盘子一个个往上叠,取的时候总是从最上面开始取,这就是栈的工作方式。
在程序设计中,栈的实现可以通过数组或链表来完成。
栈结构的优点在于其操作简单、高效,并且能够很好地解决一些特定的问题,比如需要保存临时数据并且按照特定顺序处理的情况。
在使用数据结构和算法时,理解问题的本质、选择合适的数据结构以及设计正确的算法是关键。
以下是用python实现的一个简单的栈结构代码:
class Stack:
def __init__(self):
"""
初始化栈,使用一个列表来存储栈的元素
"""
self.items = []
def push(self, item):
"""
将元素压入栈顶
参数:
item -- 要压入栈的元素
"""
self.items.append(item)
def pop(self):
"""
弹出栈顶元素
返回:
弹出的元素,如果栈为空则返回 None
"""
if not self.is_empty():
return self.items.pop()
else:
return None
def peek(self):
"""
查看栈顶元素,但不弹出
返回:
栈顶元素,如果栈为空则返回 None
"""
if not self.is_empty():
return self.items[-1]
else:
return None
def is_empty(self):
"""
判断栈是否为空
返回:
如果栈为空返回 True,否则返回 False
"""
return len(self.items) == 0
def size(self):
"""
返回栈中元素的个数
返回:
栈中元素的个数
"""
return len(self.items)
给定一个包含括号的字符串,其中括号包括小括号 ()
、中括号 []
、大括号 {}
。判断该字符串中的括号是否匹配正确。
具体来说,匹配正确的条件是:对于每一个左括号,都能在后续找到对应的右括号,且它们的顺序正确,不存在交叉匹配的情况。例如,{[()]}
是匹配的,而 {[(])}
是不匹配的。
对于栈结构在括号匹配中的应用,以下是一般的步骤和思路:
步骤 1: 理解问题
括号匹配问题要求检查给定的表达式中括号是否正确匹配,即左括号和右括号数量相同且顺序正确。
步骤 2:选择栈数据结构
栈的特点是“先进后出”,非常适合处理需要回溯和匹配的情况。
步骤 3:算法设计
遍历表达式中的每个字符:
步骤 4:最终判断
遍历完表达式后,如果栈为空,说明括号匹配成功;否则,说明存在未匹配的左括号,匹配失败。
以下是一个使用 Python 实现的 栈结构括号匹配问题 示例代码:
class Stack:
def __init__(self):
self.items = [] # 初始化一个空列表用于存储栈的元素
def push(self, item):
self.items.append(item) # 将元素添加到栈顶
def pop(self):
if not self.is_empty(): # 如果栈不为空
return self.items.pop() # 弹出栈顶元素
else:
return None # 栈为空则返回 None
def peek(self):
if not self.is_empty(): # 如果栈不为空
return self.items[-1] # 返回栈顶元素
else:
return None # 栈为空则返回 None
def is_empty(self):
return len(self.items) == 0 # 判断栈是否为空
def size(self):
return len(self.items) # 返回栈的大小
def is_balanced(expression):
stack = Stack() # 创建一个栈对象
opening_brackets = "([{" # 定义左括号字符
closing_brackets = ")]}" # 定义右括号字符
bracket_pairs = {')': '(', ']': '[', '}': '{'} # 建立右括号与对应的左括号的映射
for char in expression: # 遍历表达式中的每个字符
if char in opening_brackets: # 如果是左括号
stack.push(char) # 将左括号压入栈
elif char in closing_brackets: # 如果是右括号
if stack.is_empty() or stack.pop()!= bracket_pairs[char]: # 如果栈为空或者弹出的左括号与当前右括号不匹配
return False # 则表达式括号不匹配
return stack.is_empty() # 遍历完后,如果栈为空,说明括号匹配,否则不匹配
# 测试用例
expression1 = "([{}])"
expression2 = "([)]"
print(is_balanced(expression1)) # 输出: True
print(is_balanced(expression2)) # 输出: False
数据结构:
算法:
学习要点:
学习价值:
TO SUM,学习数据结构与算法需要耐心和持续的练习,不断积累经验和提高解决问题的能力。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。