找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 761|回复: 1
收起左侧

[资源分享] 4: Maximize Number with Swap

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-3-2015 12:44 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
虽然没有难度还是WA了2次,需要注意:(1)swap之后别忘了swap back,要细心呐
(2)结果要初始化为原值,表示swap the ith digit with the ith dight,由于题目说是by swapping any two digits,two还加粗强调,就以为必须交换一次,就初始化为了INT_MIN,然后又WA了

  1. class Solution {
  2. public:
  3.         int maximizeResult(int n) {
  4.                 auto s = to_string(n);
  5.                 int res = n;
  6.                 for(int i = 0; i < s.size(); ++i){
  7.                         for(int j = i+1; j < s.size(); ++j){
  8.                                 swap(s【i】, s[j]);
  9.                                 res = max(res, stoi(s));
  10.                                 swap(s【i】, s[j]);
  11.                         }
  12.                 }
  13.                 return res;
  14.         }
  15. };
复制代码



4

主题

0

精华

54

积分

资深会员

Rank: 2

积分
54
发表于 2-25-2016 02:53 PM | 显示全部楼层
不需要Brute-force也可以,时间复杂度O(n)。

  1. class Solution {
  2.         public int maximizeResult(int n) {
  3.                 char [] input = String.valueOf(n).toCharArray();
  4.                 int left = 0;
  5.                 int right = 0;
  6.                 for (int i = 1; i < input.length; i++) {
  7.                         if(input【i】 >= input[right])
  8.                                 right = i;
  9.                 }
  10.                 while(input[left] >= input[right] && left < right) {
  11.                         left++;
  12.                 }
  13.                 char tmp = input[left];
  14.                 input[left] = input[right];
  15.                 input[right] = tmp;
  16.                
  17.                 return Integer.parseInt(String.valueOf(input));
  18.         }
  19. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表