本文主要是介绍2023 E3 算法题第一题 （Difference Letter Count），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题的内容
Task 1
You are given a string letters made of N English letters. Count the number of different letters that appear in both uppercase and lowercase where all lowercase occurrences of the given letter appear before any uppercase occurrence.
For example, for letters = “aaAbcCABBc” the answer is 2. The condition is met for letters ‘a’ and ‘b’, but not for ‘c’.
Write a function:
class Solution { public int solution(String letters); }
1
that, given a string letters, returns the number of different letters fulfilling the conditions above.
Examples:Given letters = ''aaAbcCABBc", the function should return 2, as explained above.
Given letters = “xyzXYZabcABC”, the function should return 6.
Given letters = “ABCabcAefG”, the function should return 0.
Write an efficient algorithm for the following assumptions:N is an integer within the range [1…100,000];
string letters is made only of letters (a-z and/or A-Z).
解法 1
思路 1
构建一个Map，Map的key是小写字母，Map的Value有三个值分别为0，1，2.
0 : 代表只有一个小写字母。
1: 代表所有这个小写字母在大写字母之前。也就是正确的字母
2: 至少一个大写字母在这个小写字母前面。也就是不正确的字母。
写一个for 循环构建这个Map就可以了。
代码 1
class DifferenceLetterCount2 {public boolean isLowerCase(String letter){if (letter.equals(letter.toLowerCase())){return true;}else{return false;}}public int solution(String letters) {// 0 : initial , 1 : true, 2 : falseMap<String, Integer> letterMap = new HashMap<String, Integer>();Integer correctOrder = 0;char[] letterArray = letters.toCharArray();for (int i =0 ; i< letters.length(); i++ ){String letter = Character.toString(letterArray[i]);Integer flag = letterMap.get(letter.toLowerCase());if (flag== null){if (isLowerCase(letter)){letterMap.put(letter, 0);}else{letterMap.put(letter.toLowerCase(), 2);}}else{if (flag==0 ){if (!isLowerCase(letter)){correctOrder++;letterMap.put(letter.toLowerCase(), 1);}}else if(flag==1){if (!isLowerCase(letter)){letterMap.put(letter.toLowerCase(), 2);}}}}return correctOrder;}public static void main(String[] args) {DifferenceLetterCount2 solution = new DifferenceLetterCount2();// Test casesSystem.out.println(solution.solution("aaAbcCABBc")); // Output: 2System.out.println(solution.solution("xyzXYZabcABC")); // Output: 6System.out.println(solution.solution("ABCabcAefG")); // Output: 0}
}
解法 2
思路
构建一个长度为26的整数数组。26代表26各字母，数组里面整数有三个值0， 1， -1， 2.
0 ： 初始值。代表没有相应的字母。
1：只有一个小写字母。
2： 所有小写在大写之前，代表正确顺序。
-1 ： 不正确顺序，至少一个大写字母在小写之前。
写个for 循环构建这个整数数组。
代码
class DifferenceLetterCount {public int solution(String letters) {int count = 0;int[] array = new int[26];for (int i = 0; i < letters.length(); i++) {if (Character.isLowerCase(letters.charAt(i))) { // lowerint index = letters.charAt(i) - 'a';// -1, 1 do nothingif (array[index] == 0)array[index] = 1; // only have lowercase letterif (array[index] == 2)array[index] = -1; //incorrect order} else { // upperint index = Character.toLowerCase(letters.charAt(i)) - 'a';// -1, 2 do nothingif (array[index] == 0)array[index] = -1; // incorrect orderelse if (array[index] == 1)array[index] = 2; // correct order}}for (int e : array) {if (e == 2)count++; // count the number of correct order.}return count;}public static void main(String[] args) {DifferenceLetterCount solution = new DifferenceLetterCount();// Test casesSystem.out.println(solution.solution("aaAbcCABBc")); // Output: 2System.out.println(solution.solution("xyzXYZabcABC")); // Output: 6System.out.println(solution.solution("ABCabcAefG")); // Output: 0}
}这篇关于2023 E3 算法题第一题 （Difference Letter Count）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
