欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > 名人名企 > 算法每日一练 (11)

算法每日一练 (11)

2025/3/17 6:05:58 来源:https://blog.csdn.net/m0_46287918/article/details/146239558  浏览:    关键词:算法每日一练 (11)

💢欢迎来到张胤尘的技术站
💥技术如江河,汇聚众志成。代码似星辰,照亮行征程。开源精神长,传承永不忘。携手共前行,未来更辉煌💥

文章目录

  • 算法每日一练 (11)
    • 全排列
      • 题目描述
      • 解题思路
      • 解题代码
        • `c/c++`
        • `golang`
        • `lua`

官方站点: 力扣 Leetcode

算法每日一练 (11)

全排列

题目地址:全排列

题目描述

给定一个不含重复数字的数组 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 中的所有整数 互不相同

解题思路

  • 整体解题流程采用回溯的思路。
  • 首先递归终止条件,如果当前状态已经满足了子集的条件,则返回到上一层。在本题中,递归终止条件就是当前索引到达了数组末尾,则无需向下继续递归。
  • 紧接着就是在递归的过程中,枚举所有可能的选择,并针对每种情况都进行处理。
  • 从当前索引开始,尝试交换每个位置的元素,然后递归的调用 backtrack 方法处理每一种情况。
  • 紧接着回溯是关键步骤,在每次递归返回后,需要撤销当前的选择,恢复到上一步的状态,以便尝试其他可能性。
  • 最后当所有的排列全部列举完毕后,返回 result 结果集即可。

解题代码

c/c++
#include <vector>class Solution
{
public:std::vector<std::vector<int>> permute(std::vector<int> &nums){std::vector<std::vector<int>> result;std::vector<int> current = nums;backtrack(result, current, 0);return result;}private:void backtrack(std::vector<std::vector<int>> &result, std::vector<int> &current, int start){if (start == current.size()){result.push_back(current);return;}for (int i = start; i < current.size(); ++i){std::swap(current[start], current[i]);backtrack(result, current, start + 1);std::swap(current[start], current[i]);}}
};
golang
func permute(nums []int) [][]int {result := [][]int{}backtrack(&result, &nums, 0)return result
}func backtrack(result *[][]int, current *[]int, start int) {sz := len(*current)if start == sz {perm := make([]int, sz)copy(perm, *current)*result = append(*result, perm)return}for i := start; i < sz; i++ {(*current)[i], (*current)[start] = (*current)[start], (*current)[i]backtrack(result, current, start+1)(*current)[i], (*current)[start] = (*current)[start], (*current)[i]}return
}
lua
local function copyTable(t)local copy = {}for i = 1, #t docopy[i] = t[i]endreturn copy
endlocal function backtrack(result, current, start)local sz = #currentif sz == start thentable.insert(result, copyTable(current))returnendfor i = start, sz docurrent[i], current[start] = current[start], current[i]backtrack(result, current, start + 1)current[i], current[start] = current[start], current[i]end
endlocal function permute(nums)local result = {}backtrack(result, nums, 1)return result
end

🌺🌺🌺撒花!

如果本文对你有帮助,就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容,请随时向我提问。

在这里插入图片描述

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com