4: Maximize Number with Swap

uuuouou

虽然没有难度还是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. };

复制代码

张正

不需要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. }

复制代码