Java?C++算法題解leetcode801使序列遞增的最小交換次數(shù)
更新時(shí)間：2022年10月10日 17:13:03 作者：AnjaVon
這篇文章主要為大家介紹了Java?C++題解leetcode801使序列遞增的最小交換次數(shù)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
題目要求
思路：狀態(tài)機(jī)DP
實(shí)現(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]);
}
}
- 時(shí)間復(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]);
}
};
- 時(shí)間復(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
}
}
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
實(shí)現(xiàn)二：滾動(dòng)數(shù)組
- 因?yàn)闋顟B(tài)變換僅依賴于前一項(xiàng)，所以可以改為使用滾動(dòng)數(shù)組優(yōu)化空間;
- 也就是把dp數(shù)組從n×2改為2×2大小，idx模1交替存儲(chǔ)。
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]);
}
}
- 時(shí)間復(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]);
}
};
- 時(shí)間復(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
}
}
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
總結(jié)
這個(gè)不用操作原數(shù)組直接改狀態(tài)的思路還有一點(diǎn)繞，看了好幾遍題解又推了幾個(gè)例子才理解過來(lái)。
以上就是Java C++題解leetcode801使序列遞增的最小交換次數(shù)的詳細(xì)內(nèi)容，更多關(guān)于Java C++ 序列遞增最小交換次數(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
您可能感興趣的文章:
相關(guān)文章
java開發(fā)主流定時(shí)任務(wù)解決方案全橫評(píng)詳解
這篇文章主要為大家介紹了java開發(fā)主流定時(shí)任務(wù)解決方案全橫評(píng)詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-09-09
springboot配置http跳轉(zhuǎn)https的過程
SSL是為網(wǎng)絡(luò)通信提供安全以及保證數(shù)據(jù)完整性的的一種安全協(xié)議，SSL在網(wǎng)絡(luò)傳輸層對(duì)網(wǎng)絡(luò)連接進(jìn)行加密，這篇文章主要介紹了springboot配置http跳轉(zhuǎn)https的過程,需要的朋友可以參考下2023-04-04
Spring?@Cacheable注解類內(nèi)部調(diào)用失效的解決方案
這篇文章主要介紹了Spring?@Cacheable注解類內(nèi)部調(diào)用失效的解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-01-01
springboot2自動(dòng)加載sql文件的實(shí)現(xiàn)
本文主要介紹了springboot2自動(dòng)加載sql文件的實(shí)現(xiàn),通過配置文件或注解的方式,我們可以輕松地將SQL語(yǔ)句映射到數(shù)據(jù)庫(kù)中,實(shí)現(xiàn)自動(dòng)加載,感興趣的可以了解一下2023-11-11
@DynamicUpdate //自動(dòng)更新updatetime的問題
這篇文章主要介紹了@DynamicUpdate //自動(dòng)更新updatetime的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07
基數(shù)排序簡(jiǎn)介及Java語(yǔ)言實(shí)現(xiàn)
這篇文章主要介紹了基數(shù)排序簡(jiǎn)介及Java語(yǔ)言實(shí)現(xiàn)，涉及基數(shù)排序的基本思想簡(jiǎn)單介紹和桶排序的分析，以及基數(shù)排序的Java實(shí)現(xiàn)，具有一定借鑒價(jià)值，需要的朋友可以參考下。2017-11-11
本篇文章小編為大家介紹，Java for循環(huán)的幾種用法分析。需要的朋友參考下2013-04-04
在開發(fā)中，都離不開攔截器的使用，比如說(shuō)在開發(fā)登錄功能時(shí)，實(shí)現(xiàn)權(quán)限管理功能時(shí)等，這篇文章主要帶大家使用SpringBoot梳理自定義攔截器的思路，需要的可以參考一下2023-08-08
Spring cloud stream是為構(gòu)建微服務(wù)消息驅(qū)動(dòng)而產(chǎn)生的一種框架。Spring Cloud Stream基于Spring boot的基礎(chǔ)上，可創(chuàng)建獨(dú)立的、生產(chǎn)級(jí)別的Spring應(yīng)用，并采用Spring Integration來(lái)連接消息中間件提供消息事件驅(qū)動(dòng)，一起看看吧2021-07-07
SpringCache是構(gòu)建在SpringContext基礎(chǔ)上的緩存實(shí)現(xiàn),提供了多種緩存注解,如@Cachable、@CacheEvict、@CachePut等,本文通過實(shí)例代碼介紹了Spring Cache的使用,感興趣的朋友一起看看吧2025-01-01