leetcode-1247
本文最后更新于:2023年2月25日 晚上
题目描述
思路及实现
看完题目及示例,能够很快想到要使两个字符串相等,那么两个字符串中的'x'
和'y'
的数量应该相等,所以可以先统计一下两者的数量,如果不同可以直接返回-1
。
接下来从示例中寻找其他的情况,这边有两种思路:
- 从示例4着手,这是我一开始的思路。用暴力方法来解决示例4,会发现需要6次才能够解决;那么4次怎么来的呢?那肯定是有选择性的交换,即优先选择更优方案;仔细观察交换,就能够发现其实有两种交换方案:第一种,
s1 = 'x...x'
和's2 = 'y...y'
交换,这种情况下仅需一次交换;第二种,s1 = 'x...y'
和s2 = 'y...x'
交换,这种情况下需两次交换。那我们就更多地进行第一种交换就行了。 - 总结数学规律,统计
s1[i] = 'x', s2[i] = 'y'
和s1[i] = 'y', s2[i] = 'x'
的数量,计算结果。
这其中的思路2涉及到的详细数学规律,可以跳转至官解观看。
下面是思路1的代码:
1 |
|
写得非常复杂,但是不涉及复杂数学规律,简单易懂(自己认为的),可以在此之上总结出数学规律。
希望本文章能够帮到您~
leetcode-1247
https://map1e-g.github.io/2023/02/25/leetcode-1247/