华为OD机试真题 新系统 2026-08-09 Java、Go、C【灯带颜色变换】

目录题目思路Code题目题目内容小明设计了一条灯带该灯带中共有 16 盏灯编号 0 到 15。每盏灯有两种颜色红色用字符 R 表示绿色用字符 G 表示。每过一秒灯带中的灯都会按照规则进行一次颜色变换。如果上一秒 lights[i] 的两个相邻灯 lights[i-1] 和 lights[i1] 颜色一致则灯 lights[i] 在当前秒需要设置为绿色。其他场景包括相邻灯颜色不一致或者灯只有单一邻居则该灯在当前秒需要设置为红色。编号 0 的灯和编号 15 的灯不相邻编号 0 的灯只有右邻居编号 15 的灯只有左邻居。给定灯带初始状态请输出 t 秒后灯带中各灯颜色。输入描述输入包含灯带初始状态 lights 和整数 t。lights 是长度固定为 16 的字符串只包含 R 或 G。t 表示经过的秒数范围为 1 到 10000000。样例中也可能按两行输入第一行为 lights第二行为 t。输出描述样例中也可能按两行输入第一行为 lights第二行为 t。输出描述输出长度为 16 的字符串表示 t 秒后灯带中各灯的颜色。样例 1输入RRRRRRRRRRRRRRRR 1输出RGGGGGGGGGGGGGGR说明初始状态全红位置 1 到 14 的灯左右邻居都是红色因此变为绿色。两端灯只有单一邻居因此为红色。样例 2输入RRRRRRRRRRRRRRRR 2输出RRGGGGGGGGGGGGRR说明第 1 秒变换后状态为 RGGGGGGGGGGGGGGR第 2 秒中央绿色区域继续收缩。样例 3输入RGGGRGGGRGGGRGGG 1输出RRGRGRGRGRGRGRGR说明对每个位置应用一次规则即可得到输出。思路整体思路灯带只有 16 盏灯每盏灯只有 R 和 G 两种颜色因此所有可能状态最多为 2 的 16 次方个。每个状态的下一秒状态由规则唯一决定长时间模拟一定会进入循环。第一步把字符串编码成整数状态其中某一位为 1 表示该位置为绿色。这样可以快速读取左右邻居颜色也可以把状态作为数组或哈希表下标记录出现时间。第二步从第 0 秒开始模拟每次在生成下一状态前检查当前状态是否已经出现。如果已经出现就能得到循环起点和循环长度剩余秒数只需要对循环长度取模。第三步对取模后的少量剩余秒数继续模拟最后把整数状态解码成长度为 16 的字符串。两端位置没有两个邻居下一秒一定按规则落为红色。复杂度分析状态数量最多 65536 个单次转移只检查 16 个位置时间复杂度为 O(65536 * 16) 的上界空间复杂度为 O(65536)。Codeimport java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Main { static final int LIGHT_COUNT 16; static int encode(String lights) { int state 0; // 用整数的 16 个二进制位表示 16 盏灯第 i 位固定对应第 i 盏灯。 // 1 i 只把第 i 位变成 1绿色灯执行按位或后被记录为 1红色灯保持默认的 0。 for (int i 0; i LIGHT_COUNT; i) { if (lights.charAt(i) G) { state | 1 i; } } return state; } static String decode(int state) { StringBuilder result new StringBuilder(); // state i 把第 i 盏灯对应的位移到最右边再与 1 运算即可单独取出该位。 // 取到 1 还原成 G取到 0 还原成 R最终顺序与原灯带完全一致。 for (int i 0; i LIGHT_COUNT; i) { result.append(((state i) 1) 1 ? G : R); } return result.toString(); } static int nextState(int state) { // next 初始为 0表示下一轮所有灯默认都是红色满足变绿规则时再把对应位置设为 1。 int next 0; // 首尾灯没有完整的左右邻居题意只让中间 14 盏灯根据邻居变色。 for (int i 1; i LIGHT_COUNT - 1; i) { // 分别取出第 i-1 和第 i1 位得到当前灯左右邻居的颜色。 int left (state (i - 1)) 1; int right (state (i 1)) 1; // 左右邻居同为红色或同为绿色时当前灯下一轮变绿。 // 邻居不同则不设置这一位当前灯自然保持默认的红色。 if (left right) { next | 1 i; } } return next; } static String solve(String lights, int rounds) { int[] firstSeen new int[1 LIGHT_COUNT]; Arrays.fill(firstSeen, -1); // firstSeen[state] 保存这条完整灯带第一次出现在第几轮-1 表示还没出现过。 // state 表示当前灯带颜色分布time 表示已经完成了多少轮变换。 int state encode(lights); int time 0; while (time rounds) { if (firstSeen[state] ! -1) { // 同一状态再次出现后后续变化顺序也会重复。 // 当前轮数减首次出现轮数就是循环长度完整循环可以直接跳过。 int cycleLength time - firstSeen[state]; // 对循环长度取余只留下最后不足一个完整循环的轮数。 int remaining (rounds - time) % cycleLength; while (remaining 0) { state nextState(state); remaining--; } return decode(state); } firstSeen[state] time; state nextState(state); time; } return decode(state); } static String cleanLights(String text) { // 兼容截图里的带引号写法也兼容普通 OJ 的纯灯带字符串输入。 return text.replace(\, ).trim(); } public static void main(String[] args) throws Exception { BufferedReader reader new BufferedReader(new InputStreamReader(System.in)); ListString lines new ArrayList(); String line; // 先丢弃空行剩余内容可能是“灯带,轮数”单行格式也可能分别占两行。 while ((line reader.readLine()) ! null) { if (!line.trim().isEmpty()) { lines.add(line.trim()); } } String lights; int rounds; if (lines.size() 1 lines.get(0).contains(,)) { // 单行输入形如 RGRG...,10 时逗号左边是灯带右边是变换轮数。 String[] parts lines.get(0).split(,, 2); lights cleanLights(parts[0]); rounds Integer.parseInt(parts[1].trim()); } else { // 多行输入时第一行是灯带第二行是轮数这是普通判题最常见的格式。 lights cleanLights(lines.get(0)); rounds Integer.parseInt(lines.get(1).trim()); } // 只输出最终灯带颜色不附加说明文本保持判题输出干净。 System.out.print(solve(lights, rounds)); } }Gopackage main import ( fmt io os regexp strconv strings ) func parseInput(text string) (string, int) { var builder strings.Builder cursor : 0 // 题目固定有 16 盏灯每盏灯只用 R 或 G 表示。 // 输入可能包含引号、逗号或换行因此逐字符收集前 16 个颜色不依赖某一种分隔格式。 for index, ch : range text { if ch R || ch G { builder.WriteRune(ch) if builder.Len() 16 { // cursor 移到灯带之后后面只需要从剩余文本中寻找变换轮数。 cursor index 1 break } } } // 灯带后面的第一个整数就是需要执行的变换轮数。 numberText : regexp.MustCompile(\d).FindString(text[cursor:]) turns, _ : strconv.Atoi(numberText) return builder.String(), turns } func encode(lights string) int { state : 0 // 整数的第 i 个二进制位固定代表第 i 盏灯。 // 1 i 只在第 i 位产生 1绿色灯与 state 做按位或后记为 1红色灯保留 0。 for i : 0; i 16; i { if lights[i] G { state | 1 i } } return state } func decode(state int) string { result : make([]byte, 16) // state i 把第 i 位移到最右边再与 1 运算就只剩第 i 盏灯的颜色位。 // 位值 1 还原成 G位值 0 还原成 R。 for i : 0; i 16; i { bit : (state i) 1 if bit 1 { result[i] G } else { result[i] R } } // 内部用整数压缩状态输出时必须恢复成题目要求的 16 位灯带字符串。 return string(result) } func nextState(state int) int { // result 初始所有位都是 0表示下一轮所有灯先默认成红色。 result : 0 // 下标 0 和 15 是首尾灯缺少一侧邻居所以只处理下标 1~14。 for i : 1; i 15; i { // 分别读取左右邻居的颜色位0 表示红色1 表示绿色。 left : (state (i - 1)) 1 right : (state (i 1)) 1 if left right { // 两个邻居同为红色或同为绿色时当前灯下一轮变绿。 // 邻居不同则不设置该位当前灯保持默认红色。 result | 1 i } } return result } func solve(lights string, turns int) string { seen : make([]int, 116) for i : range seen { seen[i] -1 } state : encode(lights) time : 0 // seen[state] 保存完整灯带第一次出现的轮数-1 表示之前没有出现。 for time turns { if seen[state] ! -1 { // 相同灯带再次出现后后续变化顺序也会重复两次轮数之差就是循环长度。 cycle : time - seen[state] // 完整循环可以直接跳过只模拟剩余轮数除以循环长度后的余数。 remain : (turns - time) % cycle for remain 0 { state nextState(state) remain-- } return decode(state) } // 第一次看到当前状态时记录轮数然后正常计算下一轮。 seen[state] time state nextState(state) time } return decode(state) } func main() { data, _ : io.ReadAll(os.Stdin) lights, turns : parseInput(string(data)) fmt.Print(solve(lights, turns)) }C#include stdio.h #include string.h int encode_state(const char lights[]) { int state 0; // 用整数的 16 个二进制位保存灯带第 i 位固定对应第 i 盏灯。 // 1 i 只把第 i 位变成 1绿色灯执行按位或后记为 1红色灯保留默认的 0。 for (int i 0; i 16; i) { if (lights[i] G) { state | 1 i; } } return state; } void decode_state(int state, char answer[]) { // state i 把第 i 盏灯对应的位移到最右边与 1 运算后只剩这一位。 // 结果为 1 还原成绿色 G为 0 还原成红色 R。 for (int i 0; i 16; i) { answer[i] ((state i) 1) ? G : R; } answer[16] \0; } int next_state(int state) { // result 初始为 0表示下一轮所有灯默认红色满足变绿规则时再设置对应位。 int result 0; // 首尾灯缺少一侧邻居不参与变色所以只遍历下标 1 到 14。 for (int i 1; i 15; i) { // 分别读取当前灯左右邻居对应的二进制位0 是红色1 是绿色。 int left (state (i - 1)) 1; int right (state (i 1)) 1; if (left right) { // 两个邻居同色时当前灯下一轮变绿不同色则保持 result 中默认的红色。 result | 1 i; } } return result; } void solve(const char lights[], int turns, char answer[]) { static int seen[1 16]; for (int i 0; i (1 16); i) { seen[i] -1; } int state encode_state(lights); int time 0; // seen[state] 保存完整灯带第一次出现的轮数-1 表示此前没有出现。 while (time turns) { if (seen[state] ! -1) { // 同一状态再次出现说明后续变化会重复两次出现轮数之差就是循环长度。 int cycle time - seen[state]; // 完整循环可以直接跳过只模拟剩余轮数除以循环长度后的余数。 int remain (turns - time) % cycle; while (remain 0) { state next_state(state); remain--; } decode_state(state, answer); return; } // 第一次看到当前状态时记录轮数然后正常计算下一轮。 seen[state] time; state next_state(state); time; } decode_state(state, answer); } int main(void) { char buffer[256]; size_t length fread(buffer, 1, sizeof(buffer) - 1, stdin); buffer[length] \0; char lights[17]; int index 0; char *cursor buffer; // 输入可能带引号、逗号或空格逐字符收集前 16 个 R/G就能得到固定长度灯带。 while (*cursor ! \0 index 16) { if (*cursor R || *cursor G) { lights[index] *cursor; } cursor; } lights[16] \0; // 收集完灯带后继续向后寻找第一个整数它就是要执行的变换轮数。 while (*cursor ! \0 (*cursor 0 || *cursor 9)) { cursor; } int turns 0; sscanf(cursor, %d, turns); char answer[17]; solve(lights, turns, answer); printf(%s, answer); return 0; }【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。