外贸功能网站建设,站长seo推广,怎么阻止网站,渭城区住房和城乡建设局网站交换字符使得字符串相同【LC1247】 有两个长度相同的字符串 s1 和 s2#xff0c;且它们其中 只含有 字符 x 和 y#xff0c;你需要通过「交换字符」的方式使这两个字符串相同。 每次「交换字符」的时候#xff0c;你都可以在两个字符串中各选一个字…交换字符使得字符串相同【LC1247】 有两个长度相同的字符串 s1 和 s2且它们其中 只含有 字符 x 和 y你需要通过「交换字符」的方式使这两个字符串相同。 每次「交换字符」的时候你都可以在两个字符串中各选一个字符进行交换。 交换只能发生在两个不同的字符串之间绝对不能发生在同一个字符串内部。也就是说我们可以交换 s1[i] 和 s2[j]但不能交换 s1[i] 和 s1[j]。 最后请你返回使 s1 和 s2 相同的最小交换次数如果没有方法能够使得这两个字符串相同则返回 -1 。 考完一门 下周还有一门 加油哇 思路 当两种字符串某个位置字符不同时有两种情况: 第一种情况为s1[i]为xs2[i]为y记该种情况次数为nXy第二种情况为s1[i]为ys2[i]为X记该种情况次数为nYx 交换的方法有两种 通过一次交换x-y 或者y-x 使nXy或者nYx减少2通过两次交换x-x x-y 或者y-y y-x使nXy和nYx各减少1 如果nXy和nYx有一个为奇数那么无法使字符串相等。否则优先采取第一种交换方式【局部最优】然后当都只剩下一个时通过两次交换使字符串相等交换次数为nXy/2nYx/2nXy%2nYx%2nXy/2 nYx/2nXy\%2 nYx\%2nXy/2nYx/2nXy%2nYx%2 实现 class Solution {public int minimumSwap(String s1, String s2) {int nX 0, nY 0;int n s1.length();for (int i 0; i n; i){if (s1.charAt(i) ! s2.charAt(i)){if (s1.charAt(i) x){nX;}else{nY;}}}int res 0;res nX / 2;if (nX % 2 1){res 1;nY;}if (nY % 2 1){return -1;}res nY / 2;return res;}
}复杂度 时间复杂度O(n)O(n)O(n)空间复杂度O(1)O(1)O(1)
