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
0
投稿
猜你喜欢
- spring mvc @PathVariable / 带斜杠方式获取遇上这个问题,百度google了一下,抄袭里面的内容,可以实现,在此备忘
- spring容器是负责实例化、配置、组装组件的容器。容器的配置有很多,常用的是xml、Java注解和Java代码。在spring中Ioc容器
- 一、Spring Bean 集合注入在【Spring学习笔记(三)】已经讲了怎么注入基本数据类型和引用数据类型,接下来介绍如何注入比较特殊的
- 因为系统的菜单列表是不轻易改变的,所以不需要在每次请求的时候都去查询数据库,所以,在第一次根据用户id请求到菜单列表的时候,可以把菜单列表的
- 一、注解(annotations)列表 @SpringBootApplication:包含了@ComponentScan、@Configur
- 因为涉及到 io 流输入问题,如果不关闭会一直占用资源。所以使用过后要及时关闭,防止资源一直被占用。Scanner在使用前要导入 java.
- Java 使用IO流实现大文件的分割与合并文件分割应该算一个比较实用的功能,举例子说明吧比如说:你有一个3G的文件要从一台电脑Copy到另一
- 本文实例为大家分享了java实现鲜花销售系统的具体代码,供大家参考,具体内容如下一、练习目标1.体会数组的作用2.找到分层开发的感觉3.收获
- “Java is still not dead—and people are starting to figure that out.”本教
- 最近在研究springboot实现FastJson解析json数据的方法,那么今天也算个学习笔记吧!添加jar包:<dependenc
- SQLite是Android自带的关系型数据库,是一个基于文件的轻量级数据库。Android提供了3种操作数据的方式,SharedPrefe
- 如下所示:package com.lcn.day05;import java.util.Scanner;public class Array
- 简介本文主要讲解如何用java Selenium 控制鼠标在浏览器上的操作方法。主要列举的代码示例,无图显示。可以自己上代码执行操作看效果。
- 一、简介Spring Cache是一个框架,实现了基于注解的缓存功能,只需要简单地加一个注解,就能实现缓存功能。Spring Cache提供
- 在开发Android应用程序中,经常会自定义View来实现各种各样炫酷的效果,在实现这吊炸天效果的同时,我们往往会定义很多attr属性,这样
- 一、简单介绍翻看Spring的源码时,发现@Bean注解的源码上标注了Since: 3.0,也就是说,@Bean注解是Spring从3.0版
- android线程消息机制主要由Handler,Looper,Message和MessageQuene四个部分组成。平常在开发中,我们常用来
- 二叉搜索树的定义它是一颗二叉树任一节点的左子树上的所有节点的值一定小于该节点的值任一节点的右子树上的所有节点的值一定大于该节点的值特点: 二
- 项目中用到用户定义运算公式进行就算的需求,这样需要进行字符串四则运算解析,下面提供字符串公式四则运算解析与计算工具类,需要的同学可参考。工具
- 提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档前言这两天在项目中使用到Java的导入导出功能,以前对这块有一定了解,但是没