牛客网前端全国模考编程题解答

刚刚结束了前端的模考，一共三道编程题，谈一谈我的想法：

1. 最长 DNA 序列。

题目要求：已知合法的 DNA 字母为 "A"、"C"、"T"、"G"，有一个字符串，求在这个字符串中最长的连续 DNA 序列的长度。

例如：输入 "ATBCDEG"，因为最长连续序列为 "AT"，输出2。

解析：我是这样想的，无论是 "A"、"C"、"T"、"G"，中的哪一个，只要包含在其中，就是合法的，那么我们就不需要知道究竟是哪个 DNA 字母。我们新建一个长度为 N 的数组 isDNA，遍历字符串 str， 如果当前满足 DNA 字母，就令 isDNA[i] = 1，否则令 isDNA[i] = 0。一轮下来我们得到了一个由 0 和 1 组成的数组，这时我们将这个数组连续相加为一个字符串 rstr，通过 rstr.split("0") 方法获取切除 0 过后的字符串数组，找出这个数组中字符串的最大长度，就是本题的答案。

例：给出字符串 ""ATBCDEG"，则转换成字符串 "1100001"，则切割后得到 ["11", "", "1"]，最大长度为 2。

时间复杂度：O（N）

空间复杂度：O（N）

public static void main(String[] args){
	Scanner in = new Scanner(System.in);
	String str = in.nextLine();
	List<Character> set = new ArrayList<>();
	set.add('A');
	set.add('T');
	set.add('C');
	set.add('G');
	String[] isDNA = new String[str.length()];
	char[] chars = str.toCharArray();
	for (int i = 0; i < chars.length; i++) {
		if(set.contains(chars[i])){
			isDNA[i] = "1";
		}else{
			isDNA[i] = "0";
		}
	}
	String res = "";
	for (int i = 0; i < isDNA.length; i++) {
		res = res + isDNA[i];
	}
	String[] rstr = res.split("0");
	int max = 0;
	for (int i = 0; i < rstr.length; i++) {
		if(rstr[i].length() > max){
			max = rstr[i].length();
		}
	}
	System.out.println(max);
	in.close();
}

2. 最长偶串

题目要求：设由两个相同的字符串组成的字符串为偶串，例如 "xyzxyz" 是偶串，而 "ababa" 不是偶串，给出一个字符串，可以从字符串的末尾删除一个或者多个字符，要求删除后的子串为偶串。求最大子串的长度。

例如：输入 "xyzxyzab"，输出 6。

解析：既然是从字符串的末尾开始删除，那么我们每删除一个字符 str[i]，就假设该子串是偶串，如果是，就返回 i ，如果不是，就继续删除。

时间复杂度：O（N）

空间复杂度：O（1）

public static void main(String[] args){
	Scanner in = new Scanner(System.in);
	String str = in.nextLine();
	int cut = 0;
	String left = null;
	String right = null;
	int size = 0;
	for(int i = str.length() - 1; i >= 0; i--){
		cut = i/2;
		left = str.substring(0, cut);
		right = str.substring(cut, i);
		if(left.equals(right)){
			size = i;
			break;
		}
	}
	System.out.println(size);
	in.close();
}

3. 最少回文数量

题目要求：给出 N 个字符，每个字符只能用一次，求出这 N 个字符能拼凑出的最少回文串的数量。

例如：给出 "ababa"，则输出 1，因为这 5 个字符串可以拼凑出一个回文串；若给出 "abacd"，则输出 3，因为能拼凑出的最少回文串是 "aba"、"c"、"d"（注：第一个子串也可以是 "aca"、"ada"）。

解析：其实这道题我们并不用纠结回文串本身，因为第一题目没有求回文串，第二给出的字符是任意拼凑的，所以我们只需要把思维集中在回文串的性质上即可。思考在所有字符当中，如果一个字符出现的次数为偶数，那么任意一个回文串与该字符组合都可以拼凑出一个更大的回文串。如果一个字符出现的次数为奇数，那么任意一个奇数长度的回文串与其组合只能拼凑出两个回文串，任意一个偶数长度的回文串与其组合则可以拼凑出一个更大的回文串。现在，我们考虑一个问题，一个奇数长度的回文串与一个偶数长度的回文串拼凑结果是一个更大的奇数长度回文串，而一个一个奇数长度的回文串与一个奇数长度回文串拼凑结果是一个更大的奇数长度回文串和一个单一的字符。那么，本题就迎刃而解了，如果一个字符的出现次数为奇数，则回文串个数增加，如果一个字符的出现次数为偶数，则个数不变，且允许第一个奇数出现时个数不增加，因为第一个奇数本身是一个回文串。所以这里我们需要用到哈希表来存储字符出现的次数。

时间复杂度：O（N）

空间复杂度：O（N）

public static void main(String[] args){
	Scanner in = new Scanner(System.in);
	String str = in.nextLine();
	char[] chars = str.toCharArray();
	HashMap<Character, Integer> map = new HashMap<>();
	for (int i = 0; i < chars.length; i++) {
		Integer num = map.get(chars[i]);
		if(num == null){
			map.put(chars[i], 1);
		}else{
			map.put(chars[i], num + 1);
		}
	}
	Iterator<Integer> it = map.values().iterator();
        //初始为 0，允许第一个奇数不增加
	int number = 0;
	while(it.hasNext()){
		int count = it.next();
		if(count%2 != 0){
			number++;
		}
	}
	System.out.println(number);
}