Java C++ 算法题解拓展leetcode670最大交换示例
作者:AnjaVon 发布时间:2022-05-18 23:31:51
标签:Java,C++,算法,题解,最大交换
题目要求
思路:模拟
Java
class Solution {
public int maximumSwap(int num) {
List<Integer> list = new ArrayList<>();
while (num != 0) {
list.add(num % 10);
num /= 10;
}
int n = list.size(), res = 0;
int[] idx = new int[n];
for (int i = 0, j = 0; i < n; i++) {
if (list.get(i) > list.get(j)) // 严格大于
j = i;
idx[i] = j;
}
for (int i = n - 1; i >= 0; i--) { // 高位开始
if (list.get(idx[i]) != list.get(i)) {
int tmp = list.get(idx[i]);
list.set(idx[i], list.get(i));
list.set(i, tmp);
break;
}
}
for (int i = n - 1; i >= 0; i--)
res = res * 10 + list.get(i);
return res;
}
}
时间复杂度:O(log num)
空间复杂度:O(log num)
C++
class Solution {
public:
int maximumSwap(int num) {
vector<int> list;
while (num != 0) {
list.emplace_back(num % 10);
num /= 10;
}
int n = list.size(), res = 0;
int idx[n];
for (int i = 0, j = 0; i < n; i++) {
if (list[i] > list[j]) // 严格大于
j = i;
idx[i] = j;
}
for (int i = n - 1; i >= 0; i--) { // 高位开始
if (list[idx[i]] != list[i]) {
int tmp = list[idx[i]];
list[idx[i]] =list[i];
list[i] = tmp;
break;
}
}
for (int i = n - 1; i>= 0; i--)
res = res * 10 + list[i];
return res;
}
};
时间复杂度:O(log num)
空间复杂度:O(log num)
Rust
这个部分代码似乎有一点小问题【不用似乎就是有】……有就先有着吧……搞了半个小时也没解决【摆烂】
impl Solution {
pub fn maximum_swap(num: i32) -> i32 {
let mut list = vec![];
let mut res = num;
while (res != 0) {
list.push(res % 10);
res /= 10;
}
let n = list.len();
let mut idx = vec![0; n];
let mut j = 0;
for i in 0..n {
if list[i] > list[j] {
j = i;
}
idx[i] = j;
}
for k in n-1..0 {
if list[idx[k]] != list[k] {
list.swap(idx[k], k);
break;
}
}
for l in n-1..0 {
res = res * 10 + list[l];
}
res
}
}
时间复杂度:O(log num)
空间复杂度:O(log num)
来源:https://juejin.cn/post/7142875009252818975


猜你喜欢
- classProgram{ staticvoid Main() {&
- 每一个应用程序,其实都会有分享的需求,比如一键分享一篇文章或者一些活动到微博或者微信亦或者是twitter等社交平台,因为人类是社交动物,而
- 本文实例讲述了Android操作SQLite数据库(增、删、改、查、分页等)及ListView显示数据的方法。分享给大家供大家参考,具体如下
- 在分布式系统架构中,如果一个应用不能对来自依赖的故障进行隔离,那该应用本身就处在被拖垮的风险中。 因此,为了构建稳定、可靠的分布式系统,我们
- System.getProperty(user.dir)定位问题前言随着学习java web 的深入学习,为了巩固自己的学习成果,练习了一个
- 作为.NET进阶内容的一部分,垃圾回收器(简称GC)是必须了解的内容。本着“通俗易懂”的原则,本文将解释CLR中垃圾回收器的工作原理。基础知
- 标准c++中string类函数介绍注意不是CString之所以抛弃char*的字符串而选用C++标准程序库中的string类,是因为他和前者
- 本文实例为大家分享了ActionBar下拉式导航的实现代码,供大家参考,具体内容如下利用Actionbar同样可以很轻松的实现下拉式的导航方
- 实践过程效果代码public partial class Form1 : Form{ public Form1()
- 一.什么是maven?Maven是一个项目管理工具,它包含了一个项目对象模型 (Project Object Model),一组标准集合,一
- 本文实例讲述了Android编程使WebView支持HTML5 Video全屏播放的解决方法。分享给大家供大家参考,具体如下:1)需要在An
- java7增强的try语句关闭资源传统的关闭资源方式import java.io.FileInputStream;import java.i
- 之前文章中我们讲到,java中实现同步的方式是使用synchronized block。在java 5中,Locks被引入了,来提供更加灵活
- 一、错误处理原理分析使用SpringBoot创建的web项目中,当我们请求的页面不存在(http状态码为404),或者器发生异常(http状
- 这篇文章主要介绍了springboot跨域CORS处理代码解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,
- 1、题目描述找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知
- 概览阿里巴巴在2018年7月份发布Nacos, Nacos是一个更易于构建云原生应用的动态服务发现、配置管理和服务管理平台。并表示在6-8个
- 我们知道,(1)如果是整百的年份,能被400整除的,是闰年;(2)如果不是整百的年份,能被4整除的,也是闰年。每400年,有97个闰年。鉴于
- 前言quarkus号称超音速亚原子JAVA为Graalvm量身定制的java堆栈,是否名副其实呢?下面就来看看真实情况如何。动手前先简单介绍
- 1.实现方式说明本文在---- 手写redis @ Cacheable注解支持过期时间设置 的基础之上进行扩展。1.1问题说明