专栏首页Petrichor的专栏leetcode: 46. Permutations

leetcode: 46. Permutations

Problem

# Given a collection of distinct numbers, return all possible permutations.
#
# For example,
# [1,2,3] have the following permutations:
# [
#     [1,2,3],
#     [1,3,2],
#     [2,1,3],
#     [2,3,1],
#     [3,1,2],
#     [3,2,1]
# ]

Idea

当只有1时候:[1]
当加入2以后:[2, 1], [1, 2]
当加入3以后:[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]
前3个permutation分别对应将3插入[2, 1]的0, 1, 2的位置。
同理后3个为插入[1, 2]的。因此可以用逐个插入数字来构造所有permutations。

AC

DFS:

class Solution():
    def permute(self, x):
        return self.dfs(x)
    def dfs(self, x):
        if len(x) == 0:
            return []
        if len(x) == 1:
            return [x]
        pre, cur = self.dfs(x[:-1]), []
        for p in pre:
            for i in range(len(x)):
                cur.append(p[:i] + [x[-1]] + p[i:])
        return cur


if __name__ == "__main__":
    assert Solution().permute([1, 2, 3]) == [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode: 47. Permutations II

    JNingWei
  • leetcode: 70. Climbing Stairs

    JNingWei
  • leetcode: 80. Remove Duplicates from Sorted Array II

    leetcode: 26. Remove Duplicates from Sorted Array

    JNingWei
  • 深度优先遍历--最大的岛屿

    问题描述:给定一个二维矩阵,0表示水,1表示陆地,一个岛屿是指相邻的上下左右的陆地面积,求最大的岛屿

    绝命生
  • 通过IP获取地理位置信息的几种方式

    1、QQWry IP纯真数据库 纯真版IP地址数据库是当前网络上最权威、地址最精确、IP记录以及网吧数据最多的IP地址数据库。收集了包括中国电信、中国移动、中...

    小小科
  • 你不知道的 HTTPS中间人攻击

    研究生毕业了,好好给自己放了个假期,休息了两周,文章博客都没有更新。从大学开始基本上没过暑假,匆匆忙忙的。再过两天,就要去腾讯工作了,做了自己喜欢的网络安全,重...

    七夜安全博客
  • 如何避免问渣问题?

    大宽宽
  • 你不知道的 HTTPS中间人攻击

    研究生毕业了,好好给自己放了个假期,休息了两周,文章博客都没有更新。从大学开始基本上没过暑假,匆匆忙忙的。再过两天,就要去腾讯工作了,做了自己喜欢的网络安全,重...

    七夜安全博客
  • 039android初级篇之获取已安装应用的图标签名等信息并保存

    对于已安装的应用我们可以使用PackageManager获取其图标 程序版本 版本名称 应用名 程序的权限 程序的签名等等。

    上善若水.夏
  • engineercms小程序注册方式

    那么小程序端,如何匹配这个用户呢,需要有个登录(感觉又像注册,往下看),用网页版的用户名和密码——服务端收到后进行验证,如果密码对上了,则服务端记录这个用户的小...

    hotqin888

扫码关注云+社区

领取腾讯云代金券