目录

题目

思路

Code

题目

题目内容：

小明设计了一条灯带，该灯带中共有 16 盏灯，编号 0 到 15。每盏灯有两种颜色，红色用字符 R 表示，绿色用字符 G 表示。每过一秒，灯带中的灯都会按照规则进行一次颜色变换。

如果上一秒 lights[i] 的两个相邻灯 lights[i-1] 和 lights[i+1] 颜色一致，则灯 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)。

Code

import 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 和第 i+1 位，得到当前灯左右邻居的颜色。 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)); List<String> 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)); } }

Go

package 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, 1<<16) 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机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。