【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成

简介: 【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成

递归

字母大小写全排列

class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        def DFS(s_list, index):
            if index == len(s_list):
                res.append(''.join(s_list))
                return 
            # 未修改当前字符(字母或者数字)的一条分支  
            DFS(s_list, index + 1)
            # 修改当前字母的的另一条分支
            if s_list[index].isalpha():
                s_list[index] = chr(ord(s_list[index]) ^ 32)
                DFS(s_list, index + 1)
        res = []
        S = list(S)
        DFS(S, 0)
        return res
# 回溯
class Solution:
    def permutation(self, s: str) -> List[str]:
        def backtrack(s, cur_s):
            if len(cur_s) == len(s):
                res.append(cur_s)
                return
            for i in range(len(s)):
                if i > 0 and s[i] == s[i-1] and visited[i-1] == False:
                    continue
                if visited[i] == False:
                    visited[i] = True
                    backtrack(s, cur_s + s[i])
                    visited[i] = False
        res = []
        visited = [False for _ in range(len(s))]
        s = ''.join(sorted(list(s)))
        backtrack(s,'')
        return res

22.括号生成

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def generator(left, right, s):
            if left == n and right == n:
                res.append(s)
                return
            if left < n:
                generator(left+1, right, s + '(')
            if left > right:
                generator(left, right+1, s + ')')
        generator(0,0,'')
        return res


相关文章
|
14小时前
|
算法 Python
python中算法递归错误(Recursion Errors)
【7月更文挑战第18天】
8 1
|
14天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
12 3
|
24天前
|
算法 C语言 计算机视觉
【数据结构与算法 经典例题】括号匹配问题
【数据结构与算法 经典例题】括号匹配问题
|
29天前
|
存储 算法 程序员
数据结构与算法===递归
数据结构与算法===递归
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
24 2
|
1月前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
19 2
|
1月前
|
机器学习/深度学习 存储 算法
算法学习:递归
算法学习:递归
20 0
|
1月前
|
算法
二叉树删除节点算法---递归
二叉树删除节点算法---递归
|
1月前
|
算法
|
1天前
|
传感器 算法
基于无线传感器网络的MCKP-MMF算法matlab仿真
MCKP-MMF算法是一种启发式流量估计方法,用于寻找无线传感器网络的局部最优解。它从最小配置开始,逐步优化部分解,调整访问点的状态。算法处理访问点的动态影响半径,根据带宽需求调整,以避免拥塞。在MATLAB 2022a中进行了仿真,显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段:慢启动阶段识别瓶颈并重设半径,随后进入周期性调整阶段,追求最大最小公平性。
基于无线传感器网络的MCKP-MMF算法matlab仿真