数字能排序字符串不能排序_算法题——[leetcode1585]判断字符串s能否通过排序操作变为t...

Hard级别的新题&＃xff1a;给定数字串s和t&＃xff0c;它们只由&＃39;0&＃39;到&＃39;9&＃39;这10个数字组成。问你可以不断选择s的任意子串&＃xff0c;对其进行排序&＃xff0c;问最后能不能把它变为t?

数据范围: s和t只由数字组成&＃xff0c;并且长度相同&＃xff0c;长度不超过100000。

例如s &＃61; "84532" t &＃61; "34852"&＃xff0c; 返回true。

我们可以选择先对s的前4个字符排序&＃xff0c;变为"34582"

再对s的下标为2和3的两个字符排序&＃xff0c;变为"34852"得到t。

分析&＃xff1a;有点意思的题。问题的关键是&＃xff0c;对任意子串排序和对任意长度为2的子串排序——对相邻两个字符排序&＃xff0c;没有任何区别。看起来对相邻两个字符排序的操作要弱于对任意子串排序&＃xff0c;但其实它们是等效的。因为如果我们要对某个子串排序&＃xff0c;我们可以选择这个子串里的最小的&＃xff0c;通过对相邻两个字符排序的操作&＃xff0c;将其换到子串的开头&＃xff0c;再找到次小的&＃xff0c;把它换到第2个位置——就像冒泡排序一样。因此&＃xff0c;我们可以简单地考虑是否能通过对相邻两个字符排序&＃xff0c;把s变为t。

方法1 由小到大处理字符c。我们看字符c在s和t出现的位置。这里必须满足s和t中该字符出现的次数一样多&＃xff0c;并且t中该字符出现的每个位置一定要不大于s中该字符出现的每个位置——这样该字符可以不断左移动到指定位置&＃xff0c;然后我们再把所有的c从s和t中删掉&＃xff0c;继续统计下一个字符。

这里多说两句&＃xff0c;真正的操作过程是反过来的&＃xff0c;先处理9&＃xff0c;这时0-8都删光了&＃xff0c;所以只要个数相等&＃xff0c;就一定没问题。然后处理8&＃xff0c;这时实际上字符串只有8和9&＃xff0c;然后按照我们的判断方法&＃xff0c;只要t中每个8的位置比s中8的位置更靠前&＃xff0c;则就可以。因为8在只有8和9的世界里&＃xff0c;8可以自由地往前换……如此类推。

可是在实现时&＃xff0c;我们c是从0-9循环的&＃xff0c;每次判断位置时&＃xff0c;忽略掉小于它的字符即可&＃xff0c;而没有必要真正地删除。

代码&＃xff1a;

class Solution {public: bool isTransformable(string s, string t) { for (char c &＃61; &＃39;0&＃39;; c <&＃61; &＃39;9&＃39;; &＃43;&＃43;c) { vector v; for (int i &＃61; 0, p &＃61; 0; i &＃61; c) { &＃43;&＃43;p; } } int num &＃61; 0; for (int i &＃61; 0, p &＃61; 0; i &＃61; v.size() || v[num] &＃61; c) { &＃43;&＃43;p; } } if (num !&＃61; v.size()) { return false;            }             } return true; }};

方法2 按照t中的顺序处理。思路类似。我们统计s中每个字符出现的位置。然后对t中的每个字符&＃xff0c;我们知道该字符是该数字的第几次出现。设这个字符是x, 若其可以移动到指定位置(无论前移还是后移)&＃xff0c;只要保证s中比x小的还没处理的字符不在x之前(左)出现就好。因为如果这样一个字符y存在&＃xff0c;y在s中比 x更靠前(左)&＃xff0c;而在t中比x更靠后(右)&＃xff0c;而y

代码&＃xff1a;

class Solution {public: bool isTransformable(string s, string t) { vector> p(10); vector ind(10); for (int i &＃61; 0; i &＃61; p[c].size()) { return false; } for (int j &＃61; 0; j