Permutations פתרון Leetcode  


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ Atlassian בלומברג Byte eBay פייסבוק garena קדימה אבא גולדמן זאקס Google לינקדין מיקרוסופט אורקל Salesforce SAP סופר VMware מעבדות וולמארט יאהו
אלגוריתמים חזרה לאחור קידוד ראיון אישי הוכחת ראיונות 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.

גישת מעקב אחר פתרונות קוד קידוד  

Permutations פתרון Leetcodeאורן

הבעיה Permutations Leetcode Solution ביקש מאיתנו ליצור את כל התמורות של הרצף הנתון. באופן כללי, אנו נדרשים ליצור תמורה או שרקורסיות רצף כלשהי היא המפתח. אבל כאן רקורסיה או מעקב אחורה קצת מסובך. דרך אחת הייתה יכולה לבחור אלמנט מאלמנטים שלא נבחרו ולהציב אותו בסוף התשובה. בדרך זו יוצרים תמורה ואיכשהו הקפידו לזכור כי תמורה זו נוצרה ואין לחזור עליה. אך במקום לעשות זאת, אנו מנסים למצוא דרך פשוטה לבצע את המשימה. מה אם נבחר אלמנט ונחליף אותו עם האלמנט הנוכחי. ואז בצע שיחה רקורסיבית כדי ליצור את כל התמורות עבור הרצף אינדקס אחד אחרי האינדקס הנוכחי.

ראה גם
מיזוג שתי רשימות מקושרות ממוינות

ברגע שסיימנו לייצר את התמורות אינדקס אחד קדימה. אנו מסירים את האלמנט שנבחר ואז בוחרים אלמנט אחר וחוזרים על הנוהל. בדרך זו אנו מוודאים שהצבנו כל אלמנט שאינו בשימוש לפחות פעם אחת במיקום הנוכחי. ומכיוון שביצענו שיחה רקורסיבית לבעיית משנה קטנה יותר. בעיית המשנה הקטנה יותר היא יצירת תמורה לרצף שמתחיל ממש אחרי האינדקס הנוכחי. הוספת התמורות לתמורה הנוכחית משלימה סט של תמורות עם אלמנט שנקבע באינדקס הנוכחי. בדרך זו אנו ממשיכים לחצות את המערך משמאל לימין ומחלקים את הבעיה לבעיות משנה קטנות יותר. ברגע שנגיע לצורך יצרנו תמורה אפשרית ונוסיף אותה לתשובה.

קוד מעקב חוזר  

קוד C ++ לפתרון Permetations 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]]

ניתוח מורכבות  

מורכבות זמן

O (Sigma (P (N, K)), כאשר P הוא התמורה k של n או תמורה חלקית. באופן רשמי יותר, P (N, k) = (N!) / ((Nk)!).

ראה גם
הפוך שני מערכים שווים על ידי היפוך פתרון ה- Leetcode של מערכי המשנה

מורכבות בחלל

עַל!), מכיוון שעלינו לאחסן את כל הפתרונות האפשריים שהם N! בגודל שבו N הוא גודל המערך.