(LeetCode)全排列

2023-11-06

目录

题目要求

题目理解以及思路分析

代码分部讲解

第一部分

第二部分


题目要求

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]


示例 3:

输入:nums = [1]
输出:[[1]]
 

提示:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

来源:力扣(LeetCode)
 

        上一篇讲的组合总数,运用的是回溯法。对于这道题相信很多人也会想到使用回溯法去解决,当然了回溯法之前说过了几乎是万能的解法,但是不合理的使用回溯法往往会使得程序变得冗长,运行超时等等。

题目理解以及思路分析

        1.首先先来理解题目,很简单对吧,其实就是数学上面的排列组合问题,数学上对于这种问题都有一个固定的公式去求解,但是很显然计算机上并没有这样的捷径。但~~~,不要担心,计算机有计算机的解法,熟悉了方法后你会发现 “人算不如天算”(嘿嘿)。

        2.明白了题目后就来说说思路,其实完全可以从不接触算法公式的小白去求解简单的数列的数学方法类似的思路。想想看,我们如果没有学数学上的公式的话,那对于这样的比较简单的题目该怎么去求解呢?怎么样?是不是明白了——对喽,就是用最最最最朴素的方法一个一个一个的列出来嘛。

        3.就算是一个一个的列出来,那我们也得有一个便捷的方法去排列啊,这样才能保证我们不漏不重。大多数人习惯的方法就是以第一个数字作为开头列举可能的结果,然后再以第二个数字为开头不动...........就这样以此类推。这样的方法是不是非常适合用我们计算机中的回溯法去求呢?

        既然理解了题目又搞懂了思路,那接下来我们就用 “事实说话”!!!

        GO!GO!GO!

代码分部讲解

第一部分

int count;   //定义全局变量

//回溯法
void backTrack(int* nums, int numsSize, int depth, int* path, bool* used, int** result)
{
  int i;   //定义变量
  if(depth == numsSize)   //判定条件
    {
      result[count] = (int*)malloc(sizeof(int)* numsSize);   //为返回数组分配空间
      memcpy(result[count++], path, sizeof(int)* numsSize);   //将此路径的值赋值给返回数组
      return;
    }
  for(i = 0; i < numsSize; i++)
    {
      if(used[i] == true)   //起到一个判定的作用
        continue;
      path[depth] = nums[i];   //将符合的值赋给该路径数组中
      used[i] = true;   //将该数据进行标记
      backTrack(nums, numsSize, depth + 1, path, used, result);   //回溯
      used[i] = false;   //清除
    }
}

        这一部分是整个程序的核心,也是上述思路的一个实体化表现。

        对一些地方着重讲解一下:

  for(i = 0; i < numsSize; i++)
    {
      if(used[i] == true)   //起到一个判定的作用
        continue;
      path[depth] = nums[i];   //将符合的值赋给该路径数组中
      used[i] = true;   //将该数据进行标记
      backTrack(nums, numsSize, depth + 1, path, used, result);   //回溯
      used[i] = false;   //清除
    }

很多读者可能不理解的一步是:

      if(used[i] == true)   //起到一个判定的作用
        continue;

        其实很好理解,但是首先必须清楚 bool函数 ,这个函数在这里不过多的讲解,仅仅粗略的讲解一下它的用法,这个函数其实是一种判定,它最后的结果仅仅只有 truefalse 两种,其中 0 为 false,0!为 true。

        明白这些后再来看这段代码——仅仅用作判断,那问题来了?它判断的到底是什么呢?  其实它判断的是这个数据之前有没有被使用过(也就是说再排列过程中有没有可能是它已经被使用过了?)这样就保证排列过程中数据被重复使用的情况。

当然,对于这一段:

used[i] = false;   //清除

        更简单了,认真看过上一篇文章的读者应该很快明白了。这一步就是回溯法模板中所提到的,用于对之前有影响的数据进行一个清除。仍不明白的读者可以去参考上一篇文章或者评论区留言都可。

第二部分

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    *returnSize = 1;   //初始化
    int i;
    for(i = 1; i <= numsSize; i++)   //计算返回数组行数为全排列的总数
      {
        (*returnSize) *= i;
      }
    *returnColumnSizes = (int*)malloc(sizeof(int)* (*returnSize));   
    for(i = 0; i < (*returnSize); i++)   //计算返回数组中每行的列数
      {
        (*returnColumnSizes)[i] = numsSize;
      }
    bool* used = (bool*)calloc(numsSize, sizeof(bool));  //分配空间
    int** result = (int**)malloc(sizeof(int*)* (*returnSize));   //分配空间
    int* path = (int*)malloc(sizeof(int)* (numsSize));   //分配空间
    count = 0;   //初始化
    backTrack(nums, numsSize, 0, path, used, result);   //调用函数

    return result;   //返回函数

}

         这一步就相对来说很简单了,主要就是对上一步的函数进行一些定义和配置。

    for(i = 1; i <= numsSize; i++)   //计算返回数组行数为全排列的总数
      {
        (*returnSize) *= i;
      }

        这个其实用的就是数学中的计算方法,我们仅仅只需要知道个数的总数即可,不必考虑它的每一种情况。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

(LeetCode)全排列 的相关文章

随机推荐

  • Jenkins 联动 飞书 以签名校验方式 推送测试报告通知消息

    1 获取 飞书 Bot webhook 和 secret 2 python脚本 参考 Song Estelle 的文章 这里重写了部分代码 以签名校验方式发送通知 记得安装相关依赖 usr bin python3 encoding utf
  • Java 中的阻塞队列

    Java 中的阻塞队列 1 ArrayBlockingQueue 由数组结构组成的有界阻塞队列 2 LinkedBlockingQueue 由链表结构组成的有界阻塞队列 3 PriorityBlockingQueue 支持优先级排序的无界阻
  • Python 日期字符串和时间戳解析方法详解

    原文链接 https dreamhomes top posts 202103091919 html 由于从事智能运维AIOps相关的算法研究 因此日常接触的最多就是时间序列相关的数据 在不同场景下时间字符串表示的格式可能都不相同 因此本文记
  • 解决git pull 报错insufficient permission for adding an object to repository database .git/objects

    这个报错是没有 git objects文件的写入权限 可能是 git objects被root角色创建 等到别的角色去操作时就产生了权限问题 所以解决这个问题就要改 git objects的权限 chown R username group
  • Java学习之:异常及其处理方式

    文章目录 1 所有异常都继承 Throwable 类 2 分类 3 为什么要处理异常 4 异常处理格式 5 完整异常信息的取得 5 1 常见的异常 6 throws throw 关键字 6 1 throws 用在定义方法上 6 1 1 用在
  • R中重命名数据框列名小技巧

    R中重命名数据框列名 文章目录 前言 一 基础包names函数和索引 二 使用dplyr rename函数 前言 R语言中两种修改数据框列名的小方法 创建名为df的数据框 一 基础包names函数和索引 将第二列名score修改为popul
  • 深入理解Android之Gradle

    转自 http blog csdn net innost article details 48228651 深入理解Android之Gradle 格式更加精美的PDF版请到 https pan baidu com s 1boG2cLD下载
  • SQL语句中的循环

    SQL语句中的循环 SQL语句中的循环类似于foreach循环 可以循环遍历某个表并进行新增 修改和删除的操作 SQL语句中的循环 使用SQL的游标来实现 上示例 declare ID int 声明变量 名称 类型 begin 开始 pri
  • setFocus不能生效的问题

    focusInEvent只有在对象显示出来的情况下设定setFocus才可以触发 这一点help手册里有说明 转一篇文章如下 http blog csdn net alex201030273437 article details 81937
  • CSV简单了解

    1 CSV介绍 CSV全称是Comma Separate Values 这种文件格式可以作为不同程序之间的数据交互的格式 csv就是一种纯文本文件 如 txt doc等 即是一组字符序列 字符之间已英文字符的逗号或制表符 Tab 分隔 语法
  • Python数据结构-----leetcode232.用栈实现队列

    目录 前言 方法讲解 示例 代码实现 232 用栈实现队列 前言 我们都知道队列的特征是先进先出 就跟排队一样先到先得 而栈的特征是后进后出 那这里我们怎么去通过两个栈来实现一个队列的功能呢 这一期我们一起来学习吧 方法讲解 这里需要准备好
  • 订单业务中的重要问题:超卖问题的解决方案

    订单业务中的重要问题 超卖问题的解决方案 我在做过的一些项目中都涉及到了订单的业务 如果你的项目中有关于订单的业务模块 那肯定说明你的项目中有卖商品的功能 所以有买卖场景就面临一个很常见的一个问题 那就是超卖问题 下面我就整理一下我在做项目
  • MyBatis与JDBC连接数据库所使用的url之间的差异

    1 在JDBC连接里是这样的 连接无误 2 在Mybatis里配置要这样 3 主要区别 说明 JDBC 方式连接 MySQL 不需要对 进行转义 而在Mybatis里要求一定要对 转义 4 如果是在properties文件里 不用转义的 在
  • IP静态路由实验报告

    一 将192 168 1 0 24划分为4个网段 192 168 1 0 26 192 168 1 64 26 192 168 1 128 26 192 168 1 192 26 1 取192 168 1 0 26继续划分 为主干道添加IP
  • Spring 加载、解析applicationContext.xml 流程

    概要 Spring 框架使用了BeanFactory 进行加载 xml 和生成 bean 实例 下面我们分析下Spring加载xml文件的过程 spring 版本是最新的 4 3 9 release 版本 示例 XmlBeanFactory
  • java 转换tif图片为jpg,解决转换后颜色异常问题

    java 转换tif图片为jpg 解决转换后颜色异常问题 说明 正常情况下 tif转换jpg图片会出现颜色失真 丢失部分颜色 原因是两种图片的色彩模式不同 jpg默认使用的是RGB色彩模式 TIF默认使用的是CMYK色彩模式 RGB的色域比
  • 有关“ModuleNotFoundError: No module named ‘flask._compat’”错误的解决过程

    在进行flask安装后 运行程序的过程中出现了 ModuleNotFoundError No module named flask compat 的错误 在查询了多个网站后给出了不同的答案 其报错原因是flask版本过高导致无法识别该语法
  • 仿京东 项目笔记2(注册登录)

    这里写目录标题 1 注册页面 1 1 注册 登录页面 接口请求 1 2 Vue开发中Element UI的样式穿透 1 2 1 v deep的使用 1 2 2 elementUI Dialog内容区域显示滚动条 1 3 注册页面 步骤条和表
  • 服务器i5 和e系列,e5和i5有什么区别

    两个系列的处理器主要在设计规格和面向范围方面存在区别 设计规格上 前者核心数更多 多线程能力更强 但睿频能力相对较弱 后者核心数较少 多线程能力不如前者 但睿频能力更强 面向范围上 前者主要面向服务器 嵌入式等企业设备 后者主要面向消费级硬
  • (LeetCode)全排列

    目录 题目要求 题目理解以及思路分析 代码分部讲解 第一部分 第二部分 题目要求 给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 你可以 按任意顺序 返回答案 示例 1 输入 nums 1 2 3 输出 1 2 3 1 3