首页 > 编程语言 >(python)做题记录||2024.2.4||题目是codewars的【 All Balanced Parentheses】

(python)做题记录||2024.2.4||题目是codewars的【 All Balanced Parentheses】

时间:2024-02-05 14:33:51浏览次数:35  
标签:2024.2 Parentheses nums python 元素 used 排列组合 取出 permutations

题目链接:https://www.codewars.com/kata/5426d7a2c2c7784365000783/python
我的解决方案:

def balanced_parens(n):
    # Your code here!
    used_l=[False for i in range(n)]
    used_r=[False for i in range(n)]
    answers=[]
    def process(answer):
        if len(answer)==2*n:
            answers.append(answer)
            return
        for i in range(n):
            if used_l[i]:
                continue
            if i>0 and not used_l[i-1]:
                continue
            used_l[i]=True
            process(answer+'(')
            used_l[i]=False
        if used_r.count(False)>used_l.count(False):
            for i in range(n):
                if used_r[i]:
                    continue
                if i>0 and not used_r[i-1]:
                    continue
                used_r[i]=True
                process(answer+')')
                used_r[i]=False
    process('')
    return answers
print(balanced_parens(3))

这个解决方法借鉴了这篇文章里对itertools.permutations的优化。

itertools中的permutations的参数是一个可进行遍历操作的变量(比如列表,元组,字符串等),返回的是这个变量中所有元素的排列组合的所有可能。如:

from itertools import permutations
a=[1,2,3]
print(permutations(a))
for i in permutations(a):
    print(i,end=' ')
'''输出
<itertools.permutations object at 0x00000191DC5A3740>
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
'''

permutations函数还可以加入一个整数参数表示进行排列组合时取出的元素个数,没有该参数的话默认取出全部元素。permutation(a,2)返回的是从a中取出两个元素放在两个不同的位置上,所有的可能的结果

from itertools import permutations
a=[1,2,3]
print(permutations(a,2))
for i in permutations(a,2):
    print(i,end=' ')
'''输出
<itertools.permutations object at 0x000001DD1B9B3600>
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)
'''

如果传入的序列变量中有重复的元素,那函数返回的结果中也会有重复的元素(组合)

from itertools import permutations

a=[1,1,3]
print(permutations(a))
for i in permutations(a):
    print(i,end=' ')
'''输出
<itertools.permutations object at 0x000001D12F113600>
(1, 1, 3) (1, 3, 1) (1, 1, 3) (1, 3, 1) (3, 1, 1) (3, 1, 1)
'''

文章里写了一个新的permutations函数可以避免重复,如下:

class MyItertools:
    #排列组合时取出元素个数用默认参数L定义
    def permutations(self,nums,L=-1):
        #当传入了参数L且符合逻辑时,使用传入的参数作为返回长度
        #否则使用nums的长度,即取出所有元素进行排列组合
        L = len(nums) if L<=0 or L>len(nums) else L
        #对nums进行排序,使相同元素相邻
        nums.sort()
        #生成与nums等长的标记数组,用于标识nums中的元素是否已被取出
        used=[False for i in nums]
        
        #储存所有排列组合的结果
        results=[]
        
        def get_one(result):#每次调用函数,处理result剩余未放置元素的所有组合可能性
            if len(result)==L:
                #已经取出足够数量的元素,成功获得了一个排列组合结果
                results.append(result)
                return
                
            #i和value分别是下标和值
            #每次调用函数取出一个元素参与排列,而nums中所有尚未被取出的元素都有被取出的可能
            #遍历每种可能
            for i,value in enumerate(nums):
                #如果nums[i]已经被取出则跳过
                if used[i]:
                    continue
                #排列结果重复的根本原因是在一种排列组合中交换两个元素位置后结果不变
                #交换两个相同元素不会改变排列组合
                #为保证排列结果没有重复,要保证nums中相同的元素在排列时相对顺序不变
                #即不会只在相同元素直接互相交换去制造新的组合
                #要做到这一点,可保证相同元素只有前面的元素被取出参与排列后才会取出后面元素
                
                #如果nums[i]与它前面的元素的值相同,且前面的元素尚未被取出,则跳过该元素
                if i>0 and value==nums[i-1] and not used[i-1]:
                    continue
                
                #上面的条件都为满足,说明该元素(nums[i])可被取出
                used[i]=True#取出元素
                get_one(result+[value])#处理这个位置放置这个元素的所有可能性
                used[i]=False#处理之后取回该元素,继续循环,探索该位置放置其它元素的可能
        
        get_one([])
        return results

if __name__=='__main__':
    for i in MyItertools().permutations([1,2,3]):
        print(i,end=' ')

【 All Balanced Parentheses】这个题目也相当于对n个'('和n个')'进行排列组合,每次组合时,对所有可放置元素进行遍历。这个题对可放置元素有限制,因为要符合括号闭合的规则,只有已放置多余的'('时才能放置')'。因为'('')'都相当于相同元素,于是我就用了上面的方法避免重复

标签:2024.2,Parentheses,nums,python,元素,used,排列组合,取出,permutations
From: https://www.cnblogs.com/l25428455/p/18007019

相关文章

  • python时实检测数据库表的数据变化
     在实际的数据处理和监控应用中,有时我们需要实时监测数据库表的数据变化,以便及时发现和处理数据更新、插入或删除操作。本文将介绍如何使用Python和数据库连接库来实现对数据库表的实时监测,帮助读者了解如何利用Python编写监控程序,实时捕获数据库表的数据变化。 第一步:连接数据......
  • Python正则表达式实战:提取字符串中的数字
    在文本处理中,有时我们需要从字符串中提取数字,并去除其他非数字字符。Python中的re模块提供了强大的正则表达式功能,可以帮助我们实现这一目标。本文将介绍如何使用Python的re模块来提取字符串中的数字,以及如何应用正则表达式进行文本处理。第一步:导入所需库和模块在开始之前,我们首先......
  • python保存图片的白色区域为透明怎么设置
    在图像处理中,有时我们需要将图片中的白色区域设置为透明,以便在后续操作中能够更好地与其他图像或背景融合。Python提供了丰富的图像处理库,如PIL(Pillow)和OpenCV,可以帮助我们实现这一目标。本文将介绍如何使用Python进行图像处理,将图片中的白色区域设置为透明。第一步:导入所需库和模......
  • python对矩阵中每个元素求绝对值的方法
    在Python中,对矩阵中每个元素求绝对值是一种常见的操作,特别在数值计算和数据处理中经常会用到。本文将介绍如何使用Python中的NumPy库来对矩阵中每个元素求绝对值,帮助读者更好地理解和应用这一操作。第一步:导入NumPy库NumPy是Python中用于科学计算的一个重要库,提供了大量用于数组操......
  • Python Fire:更加灵活的命令行参数
    之前介绍过Python的Fire库,一个用来生成命令行工具的的库。请参考:PythonFire:自动生成命令行接口今天,针对命令行参数,补充两种更加灵活的设置方式。1.*args型参数*args型的参数可以接受任意长度的参数。比如,模拟一个学校发送通知的功能:importfiredefnotions(school,*name......
  • 再测python3.13 —— python3.13是否移除了GIL的限制(续)
    前文:python3.13是否移除了GIL的限制x86_64ubuntu22.04环境下编译版本python3.13.0alpha0源码——python3.13.0alpha0的源码编译相关资料:PEP703–MakingtheGlobalInterpreterLockOptionalinCPythonhttps://github.com/python/cpython/issues/108223......
  • 如何在Python中保留异常装饰器的堆栈跟踪
    异常装饰器是一种通过装饰器(Decorator)机制来捕获和处理函数中异常的技术。当函数中发生异常时,装饰器可以捕获异常并进行处理,也可以记录异常信息或进行其他操作。堆栈跟踪(StackTrace)是指在发生异常时,系统会输出一个包含异常信息和函数调用链的信息。对于经常使用python做爬虫来说,这......
  • 理解日志基础:使用Python进行有效的日志记录
    源码分享https://docs.qq.com/sheet/DUHNQdlRUVUp5Vll2?tab=BB08J2日志记录是任何软件开发过程中的一个基本组成部分,尤其是在爬虫开发中。有效的日志记录策略可以帮助开发者监控爬虫的行为,诊断问题,以及追踪爬虫的性能。Python的logging模块提供了一套强大的日志记录工具,它可以帮助......
  • 【教程】Python代码混淆工具,Python源代码保密、加密、混淆
    引言Python作为一种高级脚本语言,便捷的语法和丰富的库使它成为众多开发者的首选。然而,有时候我们希望保护我们的Python源代码,避免被他人轻易获取和篡改。为了实现这一目标,我们可以采取代码混淆的技术手段。本文将介绍Python代码混淆的现状、优化方法和常用工具。正文1.使用pyc......
  • list assign in python
    ListAssignwithdifferentstrategiesinPythonHereisacodeblockdefrun_infer(self,g_blocks:List[TraceBlock],max_o_num:int=THREADS_NUM)->Iterable[B_PAIRS]:self.model.eval()_g_blocks=[*g_blocks]_default_inst=ArmInst(opcod......