本站首页 收藏本站
广告位联系

APP正在开发中...
返回顶部
您的位置： 主页 > 软件编程 > java >

收藏
分享到

Java C++算法题解leetcode801使序列递增的最小交换次数

java 来源：互联网 作者：秩名 发布时间：2022-10-11 20:54:00 人浏览
摘要

题目要求 思路：状态机DP 实现一：状态机 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int minSwap(int[] nums1, int[] nums2) { int n = nums1.length; int[][] f = new int[n][2]; for (int i = 1;

题目要求

思路：状态机DP

实现一：状态机

Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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]);

    }

}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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]);

    }

};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

Rust

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

    }

}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

实现二：滚动数组

  • 因为状态变换仅依赖于前一项，所以可以改为使用滚动数组优化空间;
    • 也就是把dp数组从n×2改为2×2大小，idx模1交替存储。

Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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]);

    }

}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

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]);

    }

};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

Rust

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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

    }

}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

总结

这个不用操作原数组直接改状态的思路还有一点绕，看了好几遍题解又推了几个例子才理解过来。
版权声明 : 本文内容来源于互联网或用户自行发布贡献，该文观点仅代表原作者本人。本站仅提供信息存储空间服务和不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权， 违法违规的内容， 请发送邮件至2530232025#qq.cn(#换@)举报，一经查实，本站将立刻删除。

您可能感兴趣的文章 :

原文链接 : https://juejin.cn/post/7152778131969933348
相关文章

  • SpringBoot自定义错误处理逻辑介绍

    SpringBoot自定义错误处理逻辑介绍
    1. 自定义错误页面 将自定义错误页面放在 templates 的 error 文件夹下，SpringBoot 精确匹配错误信息，使用 4xx.html 或者 5xx.html 页面可以打印错误

  • Java实现手写一个线程池的代码

    Java实现手写一个线程池的代码
    线程池技术想必大家都不陌生把，相信在平时的工作中没有少用，而且这也是面试频率非常高的一个知识点，那么大家知道它的实现原理和

  • Java实现断点续传功能的代码

    Java实现断点续传功能的代码
    题目实现：网络资源的断点续传功能。 二、解题思路 获取要下载的资源网址 显示网络资源的大小 上次读取到的字节位置以及未读取的字节
  • 你可知HashMap为什么是线程不安全的
    HashMap 的线程不安全 HashMap 的线程不安全主要体现在下面两个方面 在 jdk 1.7 中，当并发执行扩容操作时会造成环形链和数据丢失的情况 在

  • ArrayList的动态扩容机制的介绍

    ArrayList的动态扩容机制的介绍
    对于 ArrayList 的动态扩容机制想必大家都听说过，之前的文章中也谈到过，不过由于时间久远，早已忘却。 所以利用这篇文章做做笔记，加

  • JVM基础之字节码的增强技术介绍

    JVM基础之字节码的增强技术介绍
    字节码增强技术 在上文中，着重介绍了字节码的结构，这为我们了解字节码增强技术的实现打下了基础。字节码增强技术就是一类对现有字

  • Java中的字节码增强技术

    Java中的字节码增强技术
    1.字节码增强技术 字节码增强技术就是一类对现有字节码进行修改或者动态生成全新字节码文件的技术。 参考地址 2.常见技术 技术分类 类

  • Redis BloomFilter布隆过滤器原理与实现

    Redis BloomFilter布隆过滤器原理与实现
    Bloom Filter 概念 布隆过滤器（英语：Bloom Filter）是1970年由一个叫布隆的小伙子提出的。它实际上是一个很长的二进制向量和一系列随机映射

  • Java C++算法题解leetcode801使序列递增的最小交换次

    Java C++算法题解leetcode801使序列递增的最小交换次
    题目要求 思路：状态机DP 实现一：状态机 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int minSwap(int[] nums1, int[] nums2) { int n

  • Mybatis结果集映射与生命周期介绍

    Mybatis结果集映射与生命周期介绍
    一、ResultMap结果集映射 1、设计思想 对简单的语句做到零配置，对于复杂一点的语句，只需要描述语句之间的关系就行了 2、resultMap的应用场
推荐阅读
最新更新
友情链接
  • 本站所有内容来源于互联网或用户自行发布，本站仅提供信息存储空间服务，不拥有版权，不承担法律责任。如有侵犯您的权益，请您联系站长处理！
  • Copyright © 2017-2022 F11.CN All Rights Reserved. F11站长开发者网 版权所有 | 苏ICP备2022031554号-1 | 51LA统计