华为OD机考算法题：字符串比较

目录

题目部分

解读与分析

代码实现

---

题目部分

---

解读与分析

题目解读：

两个字符串A、B的长度相等，设下标为 i 的字符 A[i] 与 B[i] 对应的 ASCII 码的绝对值为 diffAbs[i]。diffAbs 中连续的 n 个元素之和小于或等于 V，求 n 的最大值。

分析与思路：

此题虽然难度虽然是“难”，实际很简单。

先遍历字符串A、B，依次计算每一个字符 A[i]、B[i] 的 ASCII 码的绝对值之差，存放到整型数组 diffAbs 中。

接着遍历 diffAbs，从第一个元素 diffAbs[0] 开始寻找连续元素之和小于或等于 V 的区块，设区块的左下标为 leftIndex，右下标为 rightIndex。初始值 leftIndex、rightIndex 均为 0，当区块中元素之和大于 V 时，leftIndex 向右移动（注意要保证 rightIndex >= leftIndex）；当和小于 rightIndex 时，rightIndex 往右移动。直到 rightIndex 到达最后一个元素。在滑动过程中，( rightIndex - leftIndex + 1 ) 的最大值即为最大的连续个数。

需要遍历两次，其中第一次为遍历字符串A、B，第二次遍历数组 diffAbs。时间复杂度和空间复杂度均为 O(n)。

此题和往期的题《华为OD机考算法题：补种未成活胡杨》《华为OD机考算法题：根据某条件聚类最少交换次数》《华为OD机考算法题：区块链文件转储系统》比较类似。

---

代码实现

Java代码

import java.util.Scanner;
 
/**
 * 字符串比较
 * @since 2023.10.09
 * @version 0.1
 * @author Frank
 *
 */
public class StringComparation {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String strA = sc.nextLine();
			String strB = sc.nextLine();
			String strV = sc.nextLine();
			int v = Integer.parseInt( strV );
			processStringComparation( strA, strB, v );
		}
	}
	
	private static void processStringComparation( String strA, String strB, int v )
	{
		int[] diffAbs = new int[ strA.length() ];
		for( int i = 0; i < diffAbs.length; i ++ )
		{
			int eachDiffAbs = Math.abs( strA.charAt( i ) - strB.charAt( i ) );
			diffAbs[i] = eachDiffAbs;
		}
		
		int leftIndex = 0;
		int rightIndex = 0;
		int maxCount = 0;
		int curSum = diffAbs[0];
		while( rightIndex <= diffAbs.length - 1 )
		{
			if( curSum > v )
			{
				if( leftIndex >= diffAbs.length - 1 )
				{
					break;
				}
				curSum -= diffAbs[ leftIndex ];
				leftIndex ++;				
				if( rightIndex < leftIndex )
				{					
					rightIndex = leftIndex;
					curSum += diffAbs[ rightIndex ];
				}
				continue;
			}
			
			// curSum <= v
			if( rightIndex - leftIndex + 1 >= maxCount )
			{
				maxCount = rightIndex - leftIndex + 1;
			}
			
			if( rightIndex >= diffAbs.length - 1 )
			{
				break;
			}
			rightIndex ++;
			curSum += diffAbs[ rightIndex ];
		}
		
		System.out.println( maxCount );
	}
}

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 strA = line;
        var strB = await readline();
        var strV = await readline();
        var v = parseInt(strV);
        processStringComparation(strA, strB, v);
    }
}();
 
function processStringComparation(strA, strB, v) {
 
    var diffAbs = new Array();
    for (var i = 0; i < strA.length; i++) {
        var eachDiffAbs = Math.abs(strA.charCodeAt(i) - strB.charCodeAt(i));
        diffAbs[i] = eachDiffAbs;
    }
 
    var leftIndex = 0;
    var rightIndex = 0;
    var maxCount = 0;
    var curSum = diffAbs[0];
    while (rightIndex <= diffAbs.length - 1) {
        if (curSum > v) {
            if (leftIndex >= diffAbs.length - 1) {
                break;
            }
            curSum -= diffAbs[leftIndex];
            leftIndex++;
            if (rightIndex < leftIndex) {
                rightIndex = leftIndex;
                curSum += diffAbs[rightIndex];
            }
            continue;
        }
 
        // curSum <= v
        if (rightIndex - leftIndex + 1 >= maxCount) {
            maxCount = rightIndex - leftIndex + 1;
        }
 
        if (rightIndex >= diffAbs.length - 1) {
            break;
        }
        rightIndex++;
        curSum += diffAbs[rightIndex];
    }
 
    console.log(maxCount);
}

(完)