Java?C++算法題解leetcode801使序列遞增的最小交換次數(shù)
題目要求
思路:狀態(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中,內(nèi)置了文件(File)對象。在使用文件對象時,首先需要通過內(nèi)置的open()方法創(chuàng)建一個文件對象,然后通過該對象提供的方法進(jìn)行一些基本文件操作,需要的朋友可以參考下2023-05-05利用Spring Data MongoDB持久化文檔數(shù)據(jù)的方法教程
這篇文章主要給大家介紹了關(guān)于利用Spring Data MongoDB持久化文檔數(shù)據(jù)的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考借鑒,下面來一起看看吧。2017-08-08Java數(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基于spring+quartz的分布式定時任務(wù)框架實現(xiàn)
在Spring中的定時任務(wù)功能,最好的辦法當(dāng)然是使用Quartz來實現(xiàn)。這篇文章主要介紹了基于spring+quartz的分布式定時任務(wù)框架實現(xiàn),有興趣的可以了解一下。2017-01-01SpringBoot個性化啟動Banner設(shè)置方法解析
這篇文章主要介紹了SpringBoot個性化啟動Banner設(shè)置方法解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-03-03Java實現(xiàn)權(quán)重隨機(jī)算法詳解
平時,經(jīng)常會遇到權(quán)重隨機(jī)算法,從不同權(quán)重的N個元素中隨機(jī)選擇一個,并使得總體選擇結(jié)果是按照權(quán)重分布的。本文就詳細(xì)來介紹如何實現(xiàn),感興趣的可以了解一下2021-07-07