当前位置: 首页 > news >正文

高唐网站开发广东seo网站设计

高唐网站开发,广东seo网站设计,开发一套软件app,给企业做网站 内容需要对方提供题目描述 全排列 给定一个不含重复数字的数组 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 ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 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 中的所有整数 互不相同

解法

回溯法

这个问题可以看作有 n 个排列成一行的空格,我们需要从左往右依此填入题目给定的 n 个数,每个数只能使用一次。那么很直接的可以想到一种穷举的算法,即从左往右每一个位置都依此尝试填入一个数,看能不能填完这 n 个空格,在程序中我们可以用「回溯法」来模拟这个过程。

定义回溯函数:

private void backtrack(int n, List<Integer> output, ArrayList<List<Integer>> res, int first) {
}

first为当前要填的位置,n位需要填的总位置数。

  • 如果 first=n,说明已经填完了 n 个位置(注意下标从 0 开始),找到了一个可行的解,将 output 放入答案数组中,递归结束。
  • 如果first < n,填第 first 个数的时候遍历题目给定的 n 个数,如果这个数没有被标记过,就尝试填入,并将其标记,继续尝试填下一个位置。
  • 假设我们已经填到第 first 个位置,那么 nums 数组中 [0,first−1]是已填过的数的集合,[first,n−1] 是待填的数的集合。

java代码:

class Solution {/*** 回溯** @param nums* @return*/public List<List<Integer>> permute(int[] nums) {ArrayList<List<Integer>> res = new ArrayList<>();// nums不好交换位置,使用ListList<Integer> output = new ArrayList<Integer>();for (int num : nums) {output.add(num);}int n = nums.length;// 使用回溯backtrack(n, output, res, 0);return res;}/*** 回溯算法:*  如果 first=n,说明已经填完了 n 个位置(注意下标从 0 开始),找到了一个可行的解,将 output 放入答案数组中,递归结束。*  如果first < n,填第 first 个数的时候遍历题目给定的 n 个数,如果这个数没有被标记过,就尝试填入,并将其标记,继续尝试填下一个位置*  假设我们已经填到第 first 个位置,那么 nums 数组中 [0,first−1]是已填过的数的集合,[first,n−1] 是待填的数的集合*** @param n  原数组长度,也是结果数组最后的总长度* @param output  当前的数组* @param res  结果数组* @param first  当前位置*/private void backtrack(int n, List<Integer> output, ArrayList<List<Integer>> res, int first) {// 已经填完了 n 个位置,将 output 放入答案数组中,递归结束if (first == n) {// 注意这里的output,每次递归是公用的,所以需要把它放入新列表再放到结果列表res.add(new ArrayList<>(output));}// 开始填第first个数for (int i = first; i < n; i++) {// 动态维护数组,交换位置Collections.swap(output, first, i);// 继续递归填下一个数backtrack(n, output, res, first + 1);// 回退,需要吧位置交换回来Collections.swap(output, first, i);}}
}

复杂度

  • 时间复杂度:O(n*n!),其中 n 为数组的长度
  • 空间复杂度:O(n)
http://www.tj-hxxt.cn/news/39402.html

相关文章:

  • 如何做一款服装网站合肥seo招聘
  • 做网站需要什么特色浙江seo技术培训
  • 义乌市网站制作搜索引擎营销的原理是什么
  • 建站运营新闻广告策划案优秀案例
  • wordpress中文语言包下载优化网站排名如何
  • 做外贸网站需要注意些什么问题合肥网络推广营销
  • 通栏网站今日热点新闻10条
  • 厦门市app开发网站建设公司营销网络的建设
  • 学校网站 建设措施关键词搜索工具
  • 王烨萌 俄罗斯seo入门基础教程
  • 网站秒杀小程序怎么做目前搜索引擎排名
  • 安卓游戏模板下载网站百度网盘客服人工电话95188
  • 南昌网站建设价格网络营销的优势是什么
  • 电影资源分享网站怎么做的软文推广500字
  • wordpress去除顶部厦门谷歌seo公司有哪些
  • 余姚做轴承网站龙华网站建设
  • win 搭建wordpress黑帽seo优化推广
  • html5搭建手机网站杭州网站优化培训
  • 网站制作过程中常见的问题微信小程序开发教程
  • 网站中的文字滑动怎么做的百度联盟点击广告赚钱
  • 政府机关单位网站建设方案网站生成
  • 做策划的网站推广网络培训平台有哪些
  • html网站设计实例代码原版百度
  • 网络营销工具的使用关键词优化外包服务
  • 跨境独立网站北京企业推广
  • 东莞常平镇邮政编码效果好的关键词如何优化
  • 淘宝网站建设单子好接吗竞价托管是啥意思
  • 刚开始做网站布局很吃力 怎么办站长网站查询
  • 智联招聘网站可以做两份简历吗下载百度免费
  • 上海网站设计成功柚v米科技百度网站推广申请