LeetCode 670.最大交换 图解(附Java代码)

这篇具有很好参考价值的文章主要介绍了LeetCode 670.最大交换 图解(附Java代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode 670.最大交换 图解(附Java代码),leetcode,算法,贪心算法

  📝个人主页:哈__

期待您的关注 

LeetCode 670.最大交换 图解(附Java代码),leetcode,算法,贪心算法

今天给大家分享一道LeetCode的贪心类算法题目。

一、题目描述

给定一个非负整数,你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。

注意:

  1. 给定数字的范围是 [0, 108]

二、方法及思路

看题目中的描述,给出的一个数字只让我们交换一次,然后让这个数字的值达到最大?一开始想区确实没有思路,但抛开代码层面, 如同示例1给出的2736,你又能很轻松的得知交换后的数字为7236,不是7632,也不是7263。这是因为题目给出了我们限制,只让我们交换仅仅一次。

既然选择贪心,那么我就可能想要挑出这个数组中最大的值交换到这个数前边的一个位置。2736就是7最大,然后和2交换。9973就是9最大(可以把这个最大的值的下标索引当作是第二个9,因为我们是倒着来遍历数组的),但是这个9前边又没有可以交换的值,所以9973不交换。

如果这样的话问题就来了,如果题目给出的是9937呢?你是否还想要挑出一个最大的数交换?如果是这样的话你挑出最大的值为9,但9无法和前边的数进行交换了,这样就会导致结果出错。

所以仅仅记录数组中最大值的坐标是不行的。

在这里我进行了三个变量的初始化,一个是maxIndex(最大值的下标索引),index1,index2(需要交换的值的两个索引)

LeetCode 670.最大交换 图解(附Java代码),leetcode,算法,贪心算法

我们先将maxIndex初始化为最后一个索引,在我们从后往前找的时候不仅要记录这个maxIndex的变化,同时还要记录一下index1和index2,这两个变量就是用来记录我们最后要交换哪两个值的,初始化都为-1。那么到底什么情况需要交换呢?当我们开始逆序遍历,maxIndex指向的值大于当前遍历的值时,我们就应该将这两个值交换。我们希望的是最后的maxIndex的值能越靠前放越好,所以我们使用index1和index2记录下这两个需要交换的坐标而不实际交换。

下面是遍历的记录。

当j遍历到3的时候,maxIndex指向的6>3更新index1和index2索引。

LeetCode 670.最大交换 图解(附Java代码),leetcode,算法,贪心算法

当j遍历到7的时候,7>maxIndex指向的6,更新maxIndex索引

LeetCode 670.最大交换 图解(附Java代码),leetcode,算法,贪心算法 

当j遍历到2的时候, maxINdex指向的7>2,更新index1和index2

LeetCode 670.最大交换 图解(附Java代码),leetcode,算法,贪心算法 

至此,遍历结束,最后交换index1和index2指向的值。 

那么9937这样的值是否就可以正确的遍历了呢?

三、代码

class Solution {
    public int maximumSwap(int num) {
       String str = String.valueOf(num);
       char [] arr = str.toCharArray();
       int maxIndex = arr.length-1;
       int index1 = -1;
       int index2 = -1;
      for(int i = arr.length-1;i>=0;i--){
          if(arr[i]>arr[maxIndex]){
              maxIndex = i;
          }else if(arr[i]<arr[maxIndex]){
              index2 = i;
              index1 = maxIndex;
          } 
      }
      if(index1==-1) return num;
      char tmpVal = arr[index1];
      arr[index1] = arr[index2];
      arr[index2] = tmpVal;
      return Integer.parseInt(String.valueOf(arr));
    }
}

LeetCode 670.最大交换 图解(附Java代码),leetcode,算法,贪心算法文章来源地址https://www.toymoban.com/news/detail-853331.html

到了这里,关于LeetCode 670.最大交换 图解(附Java代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetCode 131.分割回文串 + 动态规划 + 回溯算法 + 优化 + 图解 + 笔记

    我的往期文章: leetCode 647.回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501 leetCode 131.分割回文串 + 回溯算法 + 图解 + 笔记-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/134700907?spm=1001.2014.3001

    2024年02月05日
    浏览(52)
  • 算法leetcode|85. 最大矩形(rust重拳出击)

    给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 rows == matrix.length cols == matrix[0].length 1 = row, cols = 200 matrix[i][j] 为 ‘0’ 或 ‘1’ 面对这道算法题目,二当家的再次陷入了沉思。 要不是刚做过 84. 柱状图中最大的矩形 这

    2024年02月08日
    浏览(51)
  • 算法leetcode|53. 最大子数组和(rust重拳出击)

    给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 1 = nums.length = 10 5 -10 4 = nums[i] = 10 4 面对这道算法题目,二当家的再次陷入了沉思。 刚开始以为要暴力破解,双循环什么的,但

    2024年02月08日
    浏览(41)
  • 【算法与数据结构】654、LeetCode最大二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似,相关代码可以互相参考,本题明示了要用递归来做,那么递归三要素不可缺少: 输入参数和返

    2024年02月09日
    浏览(44)
  • 算法leetcode|84. 柱状图中最大的矩形(rust重拳出击)

    给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 1 = heights.length =10 5 0 = heights[i] = 10 4 面对这道算法题目,二当家的再次陷入了沉思。 眼睛一看似乎有思路,但是一动手就容易不知

    2024年02月08日
    浏览(58)
  • 【算法|动态规划No.12】leetcode152. 乘积最大子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(43)
  • LeetCode算法递归类—二叉树中的最大路径和

    目录 124. 二叉树中的最大路径和 - 力扣(LeetCode) 题解: 代码: 运行结果: 二叉树中的  路径  被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中  至多出现一次  。该路径  至少包含一个  节点,且不一定经过根节点。 路径和

    2024年02月12日
    浏览(38)
  • 【贪心算法】【中位贪心】LeetCode:100123.执行操作使频率分数最大

    双指针 C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 贪心算法 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 你可以对数组执行 至多 k 次操作: 从数组中选择一个下标 i ,将 nums[i] 增加 或者 减少 1 。 最终数组的频率分数定义为数组

    2024年02月04日
    浏览(63)
  • leetcode410. 分割数组的最大值(java)

    难度 - 困难 410. 分割数组的最大值 给定一个非负整数数组 nums 和一个整数 m ,你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。 示例 1: 输入:nums = [7,2,5,10,8], m = 2 输出:18 解释: 一共有四种方法将 nums 分割为 2 个子数组

    2024年02月10日
    浏览(41)
  • LeetCode-1005-K次取反后最大化的数组和-贪心算法

    题目描述: 给你一个整数数组 nums 和一个整数 k ,按以下方法修改该数组: 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后,返回数组 可能的最大和 。 LeetCode-1005题目链接 思路见注释~ 代码实现

    2024年02月10日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包