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

Java?C++算法題解leetcode801使序列遞增的最小交換次數(shù)

 更新時間:2022年10月10日 17:13:03   作者:AnjaVon  
這篇文章主要為大家介紹了Java?C++題解leetcode801使序列遞增的最小交換次數(shù)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

題目要求

思路:狀態(tài)機(jī)DP

實現(xiàn)一:狀態(tài)機(jī)

Java

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[][] f = new int[n][2];
        for (int i = 1; i < n; i++)
            f[i][0] = f[i][1] = n + 10; // 初始化
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                f[i][0] = Math.min(f[i][0], f[i - 1][1]);
                f[i][1] = Math.min(f[i][1], f[i - 1][0] + 1); 
            }
        }
        return Math.min(f[n - 1][0], f[n - 1][1]);
    }
}
  • 時間復(fù)雜度:O(n)
  • 空間復(fù)雜度:O(n)

C++

class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int f[n][2];
        for (int i = 1; i < n; i++)
            f[i][0] = f[i][1] = n + 10; // 初始化
        f[0][0] = 0;
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                f[i][0] = min(f[i][0], f[i - 1][1]);
                f[i][1] = min(f[i][1], f[i - 1][0] + 1); 
            }
        }
        return min(f[n - 1][0], f[n - 1][1]);
    }
};
  • 時間復(fù)雜度:O(n)
  • 空間復(fù)雜度:O(n)

Rust

impl Solution {
    pub fn min_swap(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n = nums1.len();
        let mut f = vec![vec![n + 10; 2 as usize]; n as usize];
        f[0][0] = 0;
        f[0][1] = 1;
        for i in 1..n {
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                f[i][0] = f[i][0].min(f[i - 1][1]);
                f[i][1] = f[i][1].min(f[i - 1][0] + 1); 
            }
        }
        f[n - 1][0].min(f[n - 1][1]) as i32
    }
}
  • 時間復(fù)雜度:O(n)
  • 空間復(fù)雜度:O(n)

實現(xiàn)二:滾動數(shù)組

  • 因為狀態(tài)變換僅依賴于前一項,所以可以改為使用滾動數(shù)組優(yōu)化空間;
    • 也就是把dp數(shù)組從n×2改為2×2大小,idx模1交替存儲。

Java

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[][] f = new int[2][2];
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            int tru = n + 10, fal = n + 10; // 暫存
            int pre = (i - 1) & 1, cur = i & 1;
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                tru = f[pre][0];
                fal = f[pre][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                tru = Math.min(tru, f[pre][1]);
                fal = Math.min(fal, f[pre][0] + 1); 
            }
            // 更新
            f[cur][0] = tru;
            f[cur][1] = fal;
        }
        return Math.min(f[(n - 1) & 1][0], f[(n - 1) & 1][1]);
    }
}
  • 時間復(fù)雜度:O(n)
  • 空間復(fù)雜度:O(1)

C++

class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int f[2][2];
        f[0][0] = 0;
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            int tru = n + 10, fal = n + 10; // 暫存
            int pre = (i - 1) & 1, cur = i & 1;
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                tru = f[pre][0];
                fal = f[pre][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                tru = min(tru, f[pre][1]);
                fal = min(fal, f[pre][0] + 1); 
            }
            // 更新
            f[cur][0] = tru;
            f[cur][1] = fal;
        }
        return min(f[(n - 1) & 1][0], f[(n - 1) & 1][1]);
    }
};
  • 時間復(fù)雜度:O(n)
  • 空間復(fù)雜度:O(1)

Rust

impl Solution {
    pub fn min_swap(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n = nums1.len();
        let mut f = vec![vec![n + 10; 2 as usize]; 2 as usize];
        f[0][0] = 0;
        f[0][1] = 1;
        for i in 1..n {
            let (mut tru, mut fal) = (n + 10, n + 10);
            let (pre, cur) = ((i - 1) & 1, i & 1);
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                tru = f[pre][0];
                fal = f[pre][1] + 1;
            }
            if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
                tru = tru.min(f[pre][1]);
                fal = fal.min(f[pre][0] + 1); 
            }
            f[cur][0] = tru;
            f[cur][1] = fal;
        }
        f[(n - 1) & 1][0].min(f[(n - 1) & 1][1]) as i32
    }
}
  • 時間復(fù)雜度:O(n)
  • 空間復(fù)雜度:O(1)

總結(jié)

這個不用操作原數(shù)組直接改狀態(tài)的思路還有一點繞,看了好幾遍題解又推了幾個例子才理解過來。

以上就是Java C++題解leetcode801使序列遞增的最小交換次數(shù)的詳細(xì)內(nèi)容,更多關(guān)于Java C++ 序列遞增最小交換次數(shù)的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • Python文件高級操作函數(shù)之文件信息獲取與目錄操作

    Python文件高級操作函數(shù)之文件信息獲取與目錄操作

    這篇文章主要介紹了Python文件高級操作函數(shù)之文件信息獲取與目錄操作,在Python中,內(nèi)置了文件(File)對象。在使用文件對象時,首先需要通過內(nèi)置的open()方法創(chuàng)建一個文件對象,然后通過該對象提供的方法進(jìn)行一些基本文件操作,需要的朋友可以參考下
    2023-05-05
  • 基于log4j2.properties踩坑與填坑

    基于log4j2.properties踩坑與填坑

    這篇文章主要介紹了log4j2.properties踩坑與填坑方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-12-12
  • 利用Spring Data MongoDB持久化文檔數(shù)據(jù)的方法教程

    利用Spring Data MongoDB持久化文檔數(shù)據(jù)的方法教程

    這篇文章主要給大家介紹了關(guān)于利用Spring Data MongoDB持久化文檔數(shù)據(jù)的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考借鑒,下面來一起看看吧。
    2017-08-08
  • Java數(shù)據(jù)結(jié)構(gòu)之隊列(動力節(jié)點Java學(xué)院整理)

    Java數(shù)據(jù)結(jié)構(gòu)之隊列(動力節(jié)點Java學(xué)院整理)

    隊列(Queue)是只允許在一端進(jìn)行插入,而在另一端進(jìn)行刪除的運算受限的線性表。 這篇文章詳細(xì)給大家介紹了java數(shù)據(jù)結(jié)構(gòu)之隊列,感興趣的朋友跟隨小編一起學(xué)習(xí)吧
    2017-04-04
  • Java并發(fā)編程中的ReentrantLock詳解

    Java并發(fā)編程中的ReentrantLock詳解

    這篇文章主要介紹了Java并發(fā)編程中的ReentrantLock詳解,從Java 5 開始,引入了一個高級的處理并發(fā)的java.util.concurrent包,它提供了大量更高級的并發(fā)功能,能大大簡化多線程程序的編寫,需要的朋友可以參考下
    2023-11-11
  • 基于spring+quartz的分布式定時任務(wù)框架實現(xiàn)

    基于spring+quartz的分布式定時任務(wù)框架實現(xiàn)

    在Spring中的定時任務(wù)功能,最好的辦法當(dāng)然是使用Quartz來實現(xiàn)。這篇文章主要介紹了基于spring+quartz的分布式定時任務(wù)框架實現(xiàn),有興趣的可以了解一下。
    2017-01-01
  • SpringBoot個性化啟動Banner設(shè)置方法解析

    SpringBoot個性化啟動Banner設(shè)置方法解析

    這篇文章主要介紹了SpringBoot個性化啟動Banner設(shè)置方法解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-03-03
  • Java實現(xiàn)權(quán)重隨機(jī)算法詳解

    Java實現(xiàn)權(quán)重隨機(jī)算法詳解

    平時,經(jīng)常會遇到權(quán)重隨機(jī)算法,從不同權(quán)重的N個元素中隨機(jī)選擇一個,并使得總體選擇結(jié)果是按照權(quán)重分布的。本文就詳細(xì)來介紹如何實現(xiàn),感興趣的可以了解一下
    2021-07-07
  • Java-lambda表達(dá)式入門看這一篇就夠了

    Java-lambda表達(dá)式入門看這一篇就夠了

    lambda表達(dá)式最簡單的作用就是用于簡化創(chuàng)建匿名內(nèi)部類對象,Lambda表達(dá)式是一個可傳遞的代碼塊,可以在以后執(zhí)行一次或多次,下面通過本文給大家介紹Java-lambda表達(dá)式入門教程,感興趣的朋友一起看看吧
    2021-05-05
  • java集合類源碼分析之Set詳解

    java集合類源碼分析之Set詳解

    下面小編就為大家?guī)硪黄猨ava集合類源碼分析之Set詳解。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-10-10

最新評論