欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實(shí)現(xiàn)STL中的全排列函數(shù)next_permutation()

 更新時(shí)間:2024年09月25日 10:53:49   作者:mjh_yylx  
在算法競(jìng)賽中,全排列問(wèn)題是一個(gè)經(jīng)典且常見的題目,傳統(tǒng)的遞歸方法在處理較大的n時(shí)會(huì)遇到堆棧內(nèi)存限制的問(wèn)題,本文介紹了一種避免遞歸,使用next_permutation函數(shù)實(shí)現(xiàn)全排列的方法,感興趣的朋友跟隨小編一起看看吧

一、引言

相信很多小伙伴們都做過(guò)全排列的算法題,輸入一個(gè)n,輸出1~n的全排列。對(duì)于這個(gè)問(wèn)題,最經(jīng)典的是實(shí)現(xiàn)方法應(yīng)該是通過(guò)回溯實(shí)現(xiàn) 。

代碼如下

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    static int n;
    static List<Integer> list = new ArrayList<>();
    static boolean[] st = new boolean[20];
    public static void dfs(int u) {
        if (u == n) {
            for (int i = 0; i < list.size(); i++) {
                System.out.printf("%5d", list.get(i));
            }
            System.out.println();
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!st[i]) {
                st[i] = true;
                list.add(i);
                dfs(u + 1);
                st[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(0);
        sc.close();
    }
}

但是呢,這個(gè)算法存在一定的缺陷。我們以洛谷上的一道全排列的題為例。

我們?nèi)绻褂眠f歸去實(shí)現(xiàn)這個(gè)問(wèn)題的話,當(dāng)n較大時(shí),例如n==9,這時(shí)會(huì)因?yàn)檫f歸層數(shù)太多而出現(xiàn)堆棧內(nèi)存過(guò)大的情況,無(wú)法通過(guò)測(cè)試點(diǎn),這是我們用Java實(shí)現(xiàn),用c++則不會(huì)出現(xiàn)這個(gè)問(wèn)題。

那么我們想用Java解決這個(gè)問(wèn)題,該如何解決呢?

二、全排列函數(shù)next_permutation()

學(xué)習(xí)過(guò)STL的小伙伴肯定知道,在algorithm這個(gè)頭文件中有一個(gè)強(qiáng)大的函數(shù)next_permutation(),這個(gè)函數(shù)的作用是求某一個(gè)全排列的下一個(gè)全排列。

如圖,這個(gè)是3的全排列,并且是按照字典序排列起來(lái)的,假如現(xiàn)在一個(gè)序列是1 2 3,那么執(zhí)行next_permutation()之后,序列將會(huì)變成1 3 2,這就是這個(gè)函數(shù)的作用。

這個(gè)函數(shù)具體該如何使用呢?

三、next_permutation()的使用

這個(gè)函數(shù)和sort()函數(shù)類似,需要傳入起點(diǎn)迭代器和終點(diǎn)后一個(gè)迭代器(可以理解為是指針的一種),干說(shuō)比較抽象,我們看例子。

對(duì)于數(shù)組來(lái)講,第一個(gè)參數(shù)傳入數(shù)組的名字,第二個(gè)參數(shù)傳入數(shù)組的名字+數(shù)組的大小即可。字符數(shù)組和字符串同理

但是問(wèn)題又來(lái)了,Java中并沒有現(xiàn)成的這么強(qiáng)大的函數(shù),所以我參考next_permutation()的源碼,用java語(yǔ)言實(shí)現(xiàn)了一下。

四、Java實(shí)現(xiàn)next_permutation()

函數(shù)的功能是:如果當(dāng)前序列存在下一個(gè)序列,將序列原地變?yōu)橄乱粋€(gè)全排列,并且返回true,否則返回false;

代碼的思路就是

1. 檢查序列長(zhǎng)度,如果元素個(gè)數(shù)少于1,則沒有下一個(gè)全排列,return fasle
2. 找到第一組不滿足降序的連續(xù)兩個(gè)數(shù)
3. 如果找不到這樣的數(shù),說(shuō)明此時(shí)的全排列已經(jīng)是最后一個(gè),return false
4. 尋找i之后滿足大于arr[i]的最小的數(shù)
5. 找到后交換i和k-1 位置的數(shù)
6. 然后i后位置升序即可

package algorithm.permutation;
import java.util.Arrays;
public class Permutation {
    public static void main(String[] args) {
        int[] arr = { 1, 4, 3, 2 };
        if(next_permutation(arr)){
            System.out.println(Arrays.toString(arr));
        }
        //System.out.println(Arrays.toString(arr));
    }
    public static boolean next_permutation(int[] arr) {
        //1. 元素個(gè)數(shù)少于1,沒有下一個(gè)全排列
        if(arr.length<=1){
            return false;
        }
        //2. 找到第一組不滿足降序的連續(xù)兩個(gè)數(shù)
        int i=arr.length-2;
        while(i>=0&&arr[i]>arr[i+1])i--;
        //如果找不到這樣的數(shù),說(shuō)明此時(shí)的全排列已經(jīng)是最后一個(gè)
        if(i==-1){
            return false;
        }
        //3. 尋找i之后 滿足大于arr[i]的最小的數(shù)
        int k=i+1;
        while(k<arr.length&&arr[k]>arr[i])k++;
        //4. 找到后交換i和k-1 位置的數(shù)
        swap(arr,i,k-1);
        //5. 然后i后位置升序即可
        Arrays.sort(arr,i+1,arr.length);
        return true;
    }
    static void swap( int[] arr,int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

寫出這個(gè)函數(shù)之后我們就可以在不使用遞歸的前提下,實(shí)現(xiàn)n的全排列啦!

五、使用next_permutation()實(shí)現(xiàn)全排列

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=i+1;
        }
        do{
            for(int i=0;i<n;i++){
                System.out.printf("%5d",arr[i]);
            }
            System.out.println();
        }
        while(next_permutation(arr));
    }
    static boolean next_permutation(int[] arr) {
        //元素個(gè)數(shù)少于1,沒有下一個(gè)全排列
        if(arr.length<=1){
            return false;
        }
        //找到第一組不滿足降序的連續(xù)兩個(gè)數(shù)
        int i=arr.length-2;
        while(i>=0&&arr[i]>arr[i+1])i--;
        //如果找不到這樣的數(shù),說(shuō)明此時(shí)的全排列已經(jīng)是最后一個(gè)
        if(i==-1){
            return false;
        }
        //尋找i之后 滿足大于arr[i]的最小的數(shù)
        int k=i+1;
        while(k<arr.length&&arr[k]>arr[i])k++;
        //找到后交換i和k-1 位置的數(shù)
        swap(arr,i,k-1);
        //然后i后位置升序即可
        Arrays.sort(arr,i+1,arr.length);
        return true;
    }
    static void swap( int[] arr,int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

我們提交后終于ac啦!??!

到此這篇關(guān)于Java實(shí)現(xiàn)STL中的全排列函數(shù)next_permutation()的文章就介紹到這了,更多相關(guān)Java STL全排列函數(shù)next_permutation()內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java面向?qū)ο蟮姆庋b特征深度解析

    Java面向?qū)ο蟮姆庋b特征深度解析

    在面向?qū)ο蟪淌皆O(shè)計(jì)方法中,封裝(英語(yǔ):Encapsulation)是指一種將抽象性函式接口的實(shí)現(xiàn)細(xì)節(jié)部分包裝、隱藏起來(lái)的方法。封裝可以被認(rèn)為是一個(gè)保護(hù)屏障,防止該類的代碼和數(shù)據(jù)被外部類定義的代碼隨機(jī)訪問(wèn)
    2021-10-10
  • SpringSecurit鹽值加密的密碼驗(yàn)證以及強(qiáng)密碼驗(yàn)證過(guò)程

    SpringSecurit鹽值加密的密碼驗(yàn)證以及強(qiáng)密碼驗(yàn)證過(guò)程

    在密碼加密過(guò)程中,鹽值的使用可以增強(qiáng)密碼的安全性,如果忘記存儲(chǔ)鹽值,將無(wú)法驗(yàn)證密碼,強(qiáng)密碼應(yīng)包含數(shù)字、字母和特殊字符,長(zhǎng)度應(yīng)在8到30位之間,以提高賬戶安全
    2023-03-03
  • Spring MVC 攔截器 interceptor 用法詳解

    Spring MVC 攔截器 interceptor 用法詳解

    這篇文章主要介紹了Spring MVC 攔截器 interceptor 用法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2020-07-07
  • java控制臺(tái)輸出圖書館管理系統(tǒng)

    java控制臺(tái)輸出圖書館管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了java控制臺(tái)輸出圖書館管理系統(tǒng),只用java代碼不用數(shù)據(jù)庫(kù)和GUI等,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-10-10
  • 詳細(xì)解讀java同步之synchronized解析

    詳細(xì)解讀java同步之synchronized解析

    synchronized關(guān)鍵字是Java里面最基本的同步手段,下面我們來(lái)一起學(xué)習(xí)一下
    2019-05-05
  • Java 中ConcurrentHashMap的實(shí)現(xiàn)

    Java 中ConcurrentHashMap的實(shí)現(xiàn)

    本文主要介紹Java 中ConcurrentHashMap的實(shí)現(xiàn),這里整理了詳細(xì)的資料,及簡(jiǎn)單實(shí)例代碼,有興趣的小伙伴可以參考下
    2016-09-09
  • java使用正則表達(dá)式查找包含的字符串示例

    java使用正則表達(dá)式查找包含的字符串示例

    這篇文章主要介紹了java使用正則表達(dá)式查找包含的字符串功能,結(jié)合具體實(shí)例形式分析了java針對(duì)字符串匹配查找的相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下
    2017-04-04
  • 舉例講解Java中的多線程編程

    舉例講解Java中的多線程編程

    這篇文章主要介紹了舉例講解Java中的多線程編程,線程是Java學(xué)習(xí)中的重要知識(shí),需要的朋友可以參考下
    2015-09-09
  • JVM之方法返回地址詳解

    JVM之方法返回地址詳解

    這篇文章主要介紹了JVM之方法返回地址詳解,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-02-02
  • 高吞吐、線程安全的LRU緩存詳解

    高吞吐、線程安全的LRU緩存詳解

    這篇文章主要介紹了高吞吐、線程安全的LRU緩存詳解,分享了相關(guān)代碼示例,小編覺得還是挺不錯(cuò)的,具有一定借鑒價(jià)值,需要的朋友可以參考下
    2018-02-02

最新評(píng)論