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);
		}
	}
}



郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。