✅创作者：陈书予
🎉个人主页：陈书予的个人主页
🍁陈书予的个人社区，欢迎你的加入: 陈书予的社区
🌟专栏地址: Java华为OD机试真题（2022&2023)
文章目录
- 1. 题目描述
- 2. 输入描述
- 3. 输出描述
- 4. Java算法源码
- 5. 测试
- 6.解题思路
1. 题目描述
给你一个字符串数组 words ，每一个字符串长度都相同，令所有字符串的长度都为 n 。
每个字符串 words[i] 可以被转化为一个长度为n - 1的 差值整数数组 difference[i] ，其中对于 0 <= j <= n - 2 有difference[i][j] = words[i][j+1] - words[i][j]。注意两个字母的差值定义为它们在字母表中 位置 之差，也就是说'a' 的位置是 0 ，‘b’ 的位置是 1 ，‘z’ 的位置是 25 。
比方说，字符串 “acb” 的差值整数数组是 [2 - 0, 1 - 2] = [2, -1] 。
words 中所有字符串 除了一个字符串以外 ，其他字符串的差值整数数组都相同。你需要找到那个不同的字符串。
请你返回 words中 差值整数数组 不同的字符串。
2. 输入描述
words = ["adc","wzy","abc"]
3. 输出描述
"abc"
解释：
- “adc” 的差值整数数组是 [3 - 0, 2 - 3] = [3, -1] 。
- “wzy” 的差值整数数组是 [25 - 22, 24 - 25]= [3, -1] 。
- “abc” 的差值整数数组是 [1 - 0, 2 - 1] = [1, 1] 。
不同的数组是 [1, 1]，所以返回对应的字符串，“abc”。
4. Java算法源码
public String oddString(String[] words) {
int n = words[0].length();
int[] difference = new int[n - 1];
// 计算第一个字符串的差值整数数组
for (int j = 0; j < n - 1; j++) {
difference[j] = words[0].charAt(j + 1) - words[0].charAt(j);
}
// 遍历其他字符串，找到差值整数数组不同的字符串
for (int i = 1; i < words.length; i++) {
for (int j = 0; j < n - 1; j++) {
if (words[i].charAt(j + 1) - words[i].charAt(j) != difference[j]) {
return words[i];
}
}
}
return ""; // 如果所有字符串的差值整数数组都相同，则返回空字符串
}
5. 测试
| 示例输入 | 示例输出 |
|---|---|
| words = [“aaa”,“bob”,“ccc”,“ddd”] | “bob” |
| words = [“adc”,“wzy”,“abc”] | “abc” |
6.解题思路
- 找到一个字符串的差值整数数组作为基准数组，可以选择第一个字符串的差值整数数组作为基准。
- 遍历剩余的字符串，逐个比较它们的差值整数数组与基准数组是否相同。
- 如果找到差值整数数组不同的字符串，则返回该字符串。
- 如果所有字符串的差值整数数组都相同，则返回空字符串。
使用一个示例来说明解题思路：
假设输入的字符串数组为 words = ["adc","wzy","abc"]，每个字符串的长度都为 3。
首先，计算第一个字符串 "adc" 的差值整数数组：[3 - 0, 2 - 3] = [3, -1]。
然后，遍历剩余的字符串 "wzy" 和 "abc"：
"wzy"的差值整数数组为[25 - 22, 24 - 25] = [3, -1]，与基准数组[3, -1]相同。"abc"的差值整数数组为[1 - 0, 2 - 1] = [1, 1]，与基准数组[3, -1]不同。
因此，差值整数数组不同的字符串是 "abc"。
综上所述，解题思路如上所示。
下面是思路的流程图表示：
