华为OD机考算法题：字符串解密_od字符串解析

目录

题目部分

解读与分析

代码实现

---

题目部分

---

解读与分析

题目解读：

本题有 2 行输入，第一行输入字符串的字符中字符的范围是 'a'~'z' 和 '0' ~ '9'，在输入字符串中，如果字符范围在 'a'~'f' 或 '0' ~ '9' 中，那么这些字符是干扰字符，可以理解为间隔符。这些间隔符把源字符串分割成了多个字符串。

第二行输入一个字符串，统计出这个字符串中出现的唯一字符串个数，设为 max，即当同一个字母出现多次时只计算一次。

从第一行分隔出的多个字符串中，过滤掉不同字母数大于 max 的字符串。在剩下的字符串中，找出不同字母数最大的字符串，如果字符串是唯一的，输出它；如果不同字母数最大的字符串存在多个，输出字典序最大的那个；如果不存在符合条件的字符串，则输出 "Not Found"。

分析与思路：

先设置 3 个变量：
1. max，整形变量。用于统计第二行输入字符串的唯一字符个数。
2. currentMax，整形变量，初始值为 0。在遍历过程中，用于统计在分隔字符串时，记录不同字母数不大于 max 的最大个数。
3. output，字符串长度，初始值为 "Not Found"。

算法如下：
1. 遍历第二行字符串中的字母，把所有字符放到一个 set 中，最后统计 set 中元素的个数，赋值给 max。
为什么要先计算 max 值呢？因为这样做可以减少统计的工作量。
先遍历第二行字符串，在计算出 max 值之后，再遍历第一行字符串时，可以直接忽略掉分隔后长度大于 max 的字符串。否则，需要先统计分隔后的所有字符串（无论长度是多少），最后还是要过滤掉长度大于 max 的字符串，多了些不必要的工作量。
2. 遍历第一行字符串中的字母，根据干扰字母（分隔符），把它分隔成若干字符串。对于遍历过程中的每个字符串，进行如下操作：
① 如果此字符串的不同字母数大于 max，则舍弃它。
② 如果此字符串的不同字母数小于 currentMax，舍弃它。
③ 如果此字符串的不同字母数大于 currentMax，把此字符串不同字母数赋值给 currentMax，并把此字符串赋值给 output。
④ 如果此字符串的不同字母数等于 currentMax，比较此字符串与 output 的字典序大小，如果此字符串的字典序较大，则更新 output 的值为此字符串。
3. 遍历完字第一行字符串后，输出 output。

此算法只需要遍历一次字符串，时间复杂度为 O(n)。在遍历过程中，仅需要 3 个临时变量，空间复杂度为 O(1)。 

---

代码实现

Java代码

import java.util.Scanner;
import java.util.Set;
import java.util.Arrays;
import java.util.HashSet;
 
/**
 * 字符串解密
 * 
 * @since 2023.09.07
 * @version 0.1
 * @author Frank
 *
 */
public class StringDecrypt {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String firstLine = sc.nextLine();
			String secondLine = sc.nextLine();
			processStringDecrypt(firstLine, secondLine);
		}
 
	}
 
	private static void processStringDecrypt(String firstLine, String secondLine) {
		int max = getUniqueCount(secondLine);
		int currentMax = 0;
		String output = "Not Found";
		Character[] fiterChars = { 'a', 'b', 'c', 'd', 'e', 'f', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
		Set<Character> filterSet = new HashSet<Character>(Arrays.asList(fiterChars));
		
		int i = 0;
		while (i < firstLine.length()) {
			Character first = firstLine.charAt( i );
			if( filterSet.contains( first ) )
			{
				i ++;
				continue;
			}
			int leftIndex = i;
			int rightIndex = i; // 不包含
			Character iterChar = firstLine.charAt( i );
			while( !filterSet.contains( iterChar ))
			{
				i ++;
				if( i >= firstLine.length() )
				{
					rightIndex = i;
					break;
				}
				iterChar = firstLine.charAt( i );
			}
			rightIndex = i;
			
			String subStr = firstLine.substring( leftIndex, rightIndex );
			int subStrUniCnt = getUniqueCount( subStr );
			if( subStrUniCnt == 0 || subStrUniCnt < currentMax || subStrUniCnt > max  )
			{
				continue;
			}
			
			if( subStrUniCnt > currentMax )
			{
				currentMax = subStrUniCnt;
				output = subStr;
				continue;
			}
			
			// subStrLength == currentMax
			if( output.compareTo( subStr ) < 0 )
			{
				output = subStr;
				continue;
			}
		}
 
		System.out.println(output);
	}
 
	private static int getUniqueCount(String secondLine) {
		Set<Character> charSet = new HashSet<Character>();
		for (int i = 0; i < secondLine.length(); i++) {
			charSet.add(secondLine.charAt(i));
		}
 
		return charSet.size();
	}
 
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {
    while (line = await readline()) {
        var firstLine = line;
        var secondLine = await readline();
        processStringDecrypt(firstLine, secondLine);
    }
 
}();
 
function processStringDecrypt(firstLine, secondLine) {
    var max = getUniqueCount(secondLine);
    var currentMax = 0;
    var output = "Not Found";
 
    var filterSet = new Set(['a', 'b', 'c', 'd', 'e', 'f', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9']);
 
    var i = 0;
    while (i < firstLine.length) {
        var first = firstLine.charAt(i);
        if (filterSet.has(first)) {
            i++;
            continue;
        }
        var leftIndex = i;
        var rightIndex = i; // 不包含
        var iterChar = firstLine.charAt(i);
        while (!filterSet.has(iterChar)) {
            i++;
            if (i >= firstLine.length) {
                rightIndex = i;
                break;
            }
            iterChar = firstLine.charAt(i);
        }
        rightIndex = i;
 
        var subStr = firstLine.substring(leftIndex, rightIndex);
        var subStrUniCnt = getUniqueCount(subStr);
        if (subStrUniCnt == 0 || subStrUniCnt < currentMax || subStrUniCnt > max) {
            continue;
        }
 
        if (subStrUniCnt > currentMax) {
            currentMax = subStrUniCnt;
            output = subStr;
            continue;
        }
 
        // subStrLength == currentMax
        if (output < subStr) {
            output = subStr;
            continue;
        }
    }
 
    console.log(output);
}
 
function getUniqueCount(secondLine) {
    var charSet = new Set();
    for (var i = 0; i < secondLine.length; i++) {
        charSet.add(secondLine.charAt(i));
    }
    return charSet.size;
}

(完)