Решение Leetcode с перестановками  


Сложный уровень средний
Часто спрашивают в саман Амазонка Apple Atlassian Bloomberg ByteDance eBay Facebook Garena GoDaddy Goldman Sachs Google LinkedIn Microsoft Oracle Salesforce SAP Uber VMware Walmart Labs Yahoo
алгоритмы Откат кодирование Интервью подготовка к собеседованию LeetCode LeetCodeSolutions

Решение задачи Permutations Leetcode Solution предоставляет простую последовательность целых чисел и просит нас вернуть полный вектор или массив всех перестановок данной последовательности. Итак, прежде чем приступить к решению проблемы. Мы должны быть знакомы с перестановками. Итак, перестановка - это не что иное, как набор заданных целых чисел. Итак, когда мы говорим, что нам нужны все перестановки последовательности. Мы имеем в виду, что мы должны распечатать или вернуть все возможные варианты заданной последовательности. Давайте рассмотрим несколько примеров для лучшего понимания.

Given sequence: [1,2,3]
Permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Объяснение: Все способы, которыми вы можете записать 1, 2, 3 в последовательности, были даны как выходные данные. Всего существует 6 способов написать 1, 2, 3 в перестановке.

[0,1]
[[0,1],[1,0]]

Объяснение: Есть только 2 способа записать 0, 1.

Подход с возвратом для решения Leetcode перестановок  

Решение Leetcode с перестановкамишпилька

Задача Permutations Leetcode Solution попросила нас сгенерировать все перестановки данной последовательности. Как правило, нам необходимо сгенерировать перестановку или некоторая рекурсия последовательности - ключ к успеху. Но здесь рекурсия или возврат с возвратом немного сложны. Одним из способов было выбрать элемент из неотобранных элементов и поместить его в конец ответа. Таким образом сгенерируйте перестановку и каким-то образом убедитесь, что помните, что эта перестановка сгенерирована и не должна повторяться. Но вместо этого мы пытаемся найти простой способ выполнить задачу. Что, если мы выберем элемент и поменяем его местами с текущим элементом. Затем сделайте рекурсивный вызов, чтобы сгенерировать все перестановки для последовательности с одним индексом после текущего индекса.

Смотрите также
Объединить два отсортированных связанных списка

Как только мы закончим с генерацией перестановок, на один индекс впереди. Мы удаляем выбранный элемент, а затем выбираем другой элемент и повторяем процедуру. Таким образом мы гарантируем, что каждый неиспользуемый элемент хотя бы раз был помещен в текущую позицию. И поскольку мы сделали рекурсивный вызов меньшей подзадачи. Меньшая подзадача - создание перестановки для последовательности, начинающейся сразу после текущего индекса. Добавление этих перестановок к текущей перестановке завершает набор перестановок с элементом, установленным в текущем индексе. Таким образом, мы продолжаем обходить массив слева направо и разделяем проблему на более мелкие подзадачи. Когда мы достигаем потребности, мы генерируем возможную перестановку и добавляем ее к ответу.

Код возврата  

Код C ++ для решения Leetcode с перестановками

#include <bits/stdc++.h>
using namespace std;

void permutationUtil(vector<int> &nums, int i, int &numsSize, vector<vector<int>> &answer){
    if(i == numsSize){
        answer.push_back(nums);
    }
    for(int j = i; j < numsSize; j++){
        swap(nums[i], nums[j]);
        permutationUtil(nums, i+1, numsSize, answer);
        swap(nums[i], nums[j]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> answer;
    int numsSize = nums.size();
    permutationUtil(nums, 0, numsSize, answer);
    return answer;
}

int main(){
    vector<int> nums({1, 2, 3});
    vector<vector<int>> answer = permute(nums);
    for(auto i: answer){
        for(auto j: i)
            cout<<j<<" ";
        cout<<"\t";
    }
}
1 2 3   1 3 2   2 1 3   2 3 1   3 2 1   3 1 2

Код Java для перестановок Решение Leetcode

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
    public static void permutationUtil(List<Integer> nums, int i, int numsSize, List<List<Integer>> answer){
        if(i == numsSize){
            answer.add(new ArrayList<Integer>(nums));
        }
        for(int j = i; j < numsSize; j++){
            Collections.swap(nums, i, j);
            permutationUtil(nums, i+1, numsSize, answer);
            Collections.swap(nums, i, j);
        }
    }
 
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new LinkedList();
        int numsSize = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<numsSize;i++)
            list.add(nums[i]);
        permutationUtil(list, 0, numsSize, answer);
        return answer;
    }
 
    public static void main(String[] args){
    	int nums[] = {1, 2, 3};
    	List<List<Integer>> answer = permute(nums);
    	System.out.println(answer.toString());
    }
}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

Анализ сложности  

Сложность времени

О (Сигма (P (N, K)), где P - k перестановка n или частичная перестановка. Более формально P (N, k) = (N!) / ((Nk)!).

Смотрите также
Сделайте два массива равными, переставив подмассивы в решении Leetcode

Космическая сложность

НА!), поскольку мы должны хранить все возможные решения, которые равны N! по размеру, где N - размер массива.