有没有程序高手。。。求救

风之咩~

呵呵小帅哥 发表于 2015-4-5 14:27
就怕思路有了。。然后我语句写不出

没事 有好的思路就是有了方向 遇到不会的就多查查语句嘛
总比你现在连动手都不知道往那边好

呵呵小帅哥

风之咩~ 发表于 2015-4-5 14:29
没事 有好的思路就是有了方向 遇到不会的就多查查语句嘛
总比你现在连动手都不知道往那边好

也是。。。。

thelord

1. 暴力法
穷举所有的数，然后找最小
2. 反向扫描
2.1 当成字符数组，从尾部向前扫描。寻找比当前字符小的，有则交换，得到新数。答案就出自这些数
如字符串 s="2336574"，序号为 0～6
s[6] = 4，第一个比4小的是3，交换s[2]和s[6]，得到 2346573，高位序号 2
s[5] = 7，交换s[5]，s[4]，得 2336754，高位序号 4
同理 ....
2.2 比较所有新数的高位序号，选择序号最大的那个
2.3 将高位序号后的数从小到大排序
所以，最终结果为 2336745

======= 补充 =======
经过和 @lbj888 童鞋的探讨，方法 2 确实冗余了些。下面的做法应当更有效（可以递归实现？) @呵呵小帅哥
3. 逆向遍历，向后扫描，找到比自己大的所有数，选择其中最小的交换，然后排序，done
如字符串 s="263861"，序号为 0～5
s[4] = 6，后面没有比自己大的
s[3] = 8，同上
s[2] = 3，后面比自己大但最小的数是 6，交换 s[2]和s[4]
从小到大排序 s[3]~s[5]
所以，最终结果为 266138
已由python实现（见23楼）

呵呵小帅哥

thelord 发表于 2015-4-5 15:01
1. 暴力法
穷举所有的数，然后找最小
2. 反向扫描

好像看明白了。。俺去试试看

lbj888

thelord 发表于 2015-4-5 15:01
1. 暴力法
穷举所有的数，然后找最小
2. 反向扫描

方法2结果只动了后三位，过程需要动倒数第五位，没觉得不对劲么

netghf

嗯，就这样吧。我不知道什么情况

lbj888

此回复非本人，本人刚注册，无权回复
从后往前扫描的那哥们把3和4换了可最终结果不用动3发现没。
我提供个思路，虽然也是从后开始扫描。
倒第二位向后看，如果倒第一比他小，看倒第三；
倒第三位向后看，倒第二位比他小，看倒第四；
。。。
倒第n位向后看，倒第n-1位比他大，两数对调；
后n-1位从小到大排列；
结束

thelord

lbj888 发表于 2015-4-5 15:28
此回复非本人，本人刚注册，无权回复
从后往前扫描的那哥们把3和4换了可最终结果不用动3发现没。
我提供 ...

没太明白，最好用个例子讲解
我给的只是个例子，算法不止考虑这种情况

lbj888

thelord 发表于 2015-4-5 15:50
没太明白，最好用个例子讲解
我给的只是个例子，算法不止考虑这种情况

就拿你的例子，2336574
int l=s.length()-1;
s[l-1]>s[l]，看倒第三位
s[l-2]<s[l-1]，两数对换，2336754
s[l-1]~s[l]从小到大排，2336745
我的思路是从倒第二开始让自己与后一位相比，自己较大则继续（如果一直比下去还不能换就会发现是降序排列的），直到后一位比自己大，和他对调，对调后，因为当前位数字更大了，满足条件1，所以包括自己及左边的数字都不用动了，只需右边的数从小到大排列实现条件2即可。

thelord

lbj888 发表于 2015-4-5 16:05
就拿你的例子，2336574
int l=s.length()-1;
s[l-1]>s[l]，看倒第三位

你的方法里只有相邻交换，某些情况下可能不对，比如 2363861
不过确实还有种做法，有点递归的味道
逆向遍历，向后扫描，找到比自己大的所有数，选择其中最小的交换，然后排序，done