题解 | 交换到最大

这一题我被字符串与整型数之间的运算卡住了，花了好多时间

经过研究

假设 char temp='b'

(char)(temp-'1')得到的不是'a'而是temp的ASCII-1的ASCII后得到的ASCII对应的字符，一般是乱码或者不可见

要想得到'a'

我们应当进行的操作是

(char)(temp-1)得到的是'a'

=================================

接下来讲讲这道题的做法

这是一题贪心＋滑动窗口

我们要确定第i位的最优解，一般是从i开始，到Math.min(i+9,n-1)为止，因为有超出索引的可能，，所以要求最小值

首先在这个范围内，确定哪一个字符是最优解，并且记录它的位置

再进行移位操作，把这个最优解从它原本的位置移动到第i位，在这期间不断与前面的值进行交换

在最后把最优解赋值给s[i]，这样就可以避开移位过程中不停减一，不停减一是无效操作，因为后面会覆盖它

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int t=scanner.nextInt();
		while(t-->0) {
			String string=scanner.next();
			char s[]=string.toCharArray();
			for (int i = 0; i < s.length; i++) {
				int best_val=s[i]-'0';
				int best_pos=i;
				
				for (int j = i; j < Math.min(i+10, s.length); j++) {
					if(s[j]-'0'-(j-i)-best_val>0) {
						best_val=s[j]-'0'-(j-i);
						best_pos=j;
					}
				}
				for (int j = best_pos; j > i; j--) {
					char temp=s[j];
					s[j]=s[j-1];
//					temp-1得到的是ASCII-1，再强转以后就是对应字符。如果是temp-'1'，那么就是对应字符相减
					s[j-1]=temp;
				}
				s[i]=(char)('0'+best_val);
				
				}
			System.out.println(new String(s));
			}
			
			
		}
	}