Baidu笔试-01序列排序的交换次数
问题描述:
问题分析:
解法一:设置双指针,start,end;当data[start]=‘1’,data[end]=’0’时,表示需要进行交换,次数加1;否则data[end]=’1’则前移end指针;data[start]=‘0’则后移start指针;
该算法仅需遍历一次
解法二:先遍历一次计算字符数组中0的个数zero,再计算前zero个字符中1的个数,即是要交换到后面的字符(仅需遍历到zero个字符即可);
代码:
解法一:
import java.util.Scanner; public class Main1 { public static void main(String[] args) { Scanner in = new Scanner(System.in); //记录有多少组数据 int data_length = in.nextInt(); //第一层循环 for (int i = 0; i < data_length; i++) { String str = in.next(); char[] chars = str.toCharArray(); int start = 0; int end = chars.length - 1; int result = 0; while(start < end) { if (chars[start] == '1' && chars[end] == '0') { ++result; start ++; end --; } else { if(chars[end] == '1') { end --; } if(chars[start] == '0') { start ++; } } } System.out.println(result); } } }
解法二: import java.util.Scanner; public class Main1 { public static void main(String args[]) { Scanner in = new Scanner(System.in); int n = in.nextInt(); while (n-- != 0) { int zero = 0, swap = 0; String str = in.next(); for (int i = 0; i < str.length(); i++) if (str.charAt(i) == '0') zero++; for (int i = 0; i < zero; i++) if (str.charAt(i) == '1') swap++; System.out.println(swap); } } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。