Loading...
墨滴

Shinkai005

2021/12/19  阅读:31  主题:红绯

# 【leetcode】46.全排列

【leetcode】46.全排列

题目描述

image-20211214115931047
image-20211214115931047

题目思路

用回溯算法

  1. 所有排列情况
  2. 没有重复元素

个人题解

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

var permute = function (nums{
    /**
     用递归模拟出所有情况
     遇到包含重复元素的情况,就回溯
     收集所有到达递归重点的情况并返回
     */

    const res = [];
    const backtrack = (path) => {
      // 递归终点
        if (path.length === nums.length) {
            res.push(path);
            return;
        }
      //遍历
        nums.forEach(n => {
          //如果重复就返回
            if (path.includes(n)) {
                return;
            }
          // 为什么用concat 主要是因为不会改变path.
          // 递归.
            backtrack(path.concat(n));
        });
    };
    backtrack([]);
    return res;

};

递归的调用我一句一句说真说不清..... 得自己打开调试看...

说一点吧

  1. 第一个backtrack([])
    1. nums 1
  2. 第二个backtrack([1])
    1. nums 1 return
    2. nums 2
  3. 第三个backtrack([1,2])
    1. nums 1 return // forEach的return是类似continue的效果 进行下一个元素,如果想要跳出要使用trycatch,下面引用详解
    2. nums 2 return
    3. nums 3
  4. 第四个backtrack([1,2,3])
    1. 符合要求 res = [[1,2,3], ]
    2. return
  5. 回到第三个backtrack([1,2])
    1. 带入第四个 backtrack ([1,2]) 但是因为长度不满足不修改 return
  6. 回到第二个backtrack
    1. 接下来该nums 3
    2. backtrack([1,3])

....

  1. [1,3,2] 满足,然后回到第一个backtrack
    1. 接下来该nums 2
    2. 第二个backtrack([2])
  2. [2,1,3]满足...

为啥写这么详细!因为有人说我划水!

image-20211214133544133
image-20211214133544133

证明一下说的对着呢哦

if(newProducts.length===beforeProducts.length){
8             try{
9                 newProducts.forEach((data,index)=>{
10                     if(data.name!==beforeProducts[index].name){
11                         isRender = true;
12                         throw Error('need to render')
13                     }
14                 })
15             }catch(err){
16 
17             }

类似这样的代码,当符合条件时, throw一个错误.就可以跳出循环了

总结优化

这复杂度太高了

但是提交之后还行...

时间复杂度(time complexity)

其实是O(n!) 因此每次会把重复元素删除 每次减少1 也就是1 2 3 4 5 ...n-1 n 中间是✖️

空间复杂度(space complexity)

O(n)

Shinkai005

2021/12/19  阅读:31  主题:红绯

作者介绍

Shinkai005