首页 > 试题广场 >

红绿灯智能识别

[编程题]红绿灯智能识别
  • 热度指数:50 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
vivo某项目组正在优化智能驾驶中红绿灯识别相关的难题,需根据红绿灯的变化来推测出当前剩余秒数。本题以红灯的识别为例。

城市红绿灯的信号显示由两块LED屏幕表示,左屏显示十位数,右屏显示个位数。
个位数字包含0-9,十位数除了包含0-9外,还有A,b,C,d,E,F这些字样,分别对应数字10到数字15。例如 b3 表示 113 秒。
实地调研发现,红绿灯存在一定的坏灯率。表现为LED屏中的某些子区域(子区域分布参照图1中最左侧的0-6标识)为常亮或者常熄状态。
这里我们不考虑左右两个LED灯总损坏区域数超过3的场景。

现给定你一个长度为2*N的数组,表示连续N秒内智能设备接收到的红灯信号值,数组每两个下标为一组,分别表示LED灯左屏和右屏的信号值。

请计算最后一次信号值所表示的剩余秒数。若无法根据输入确定结果,请返回-1。

LED灯的信号转换成输入数值的逻辑如下:
    1、每个灯由7个子区域组成,参照下图1中最左侧的0到6。
    2、亮色区域表示为1,暗色区域表示为0,按序合并后组成一个长度为7的二进制序列。例如:8表示为 1111111, 6表示为1101111。
    3、将上述二进制序列对应数字即为信号值。
    4、0-F的二进制对应关系按顺序如下:
         1110111, 0010010, 1011101, 1011011,0111010, 1101011, 1101111, 1010010,1111111, 1111011, 1111110, 0101111,1100101, 0011111, 1101101, 1101100
         可参考图2进行对照。

图1:


图2:

示例1

输入

[82,119,111,123,111,127]

输出

68

说明

82的二进制为[1010010],对应数字7。119的二进制为[1110111],对应数字0。 故第一组信号值为70。
依次类推:接收到的信号分别为70,69,68。故当前红灯还剩余68秒。   

示例2

输入

[82,107,82,58,82,91]

输出

-1

说明

若没有任何LED区域损坏,那么82的二进制为[1010010],对应数字7,107对应的二进制为1101011,对应数字5。故第一组对应信号值75。
以此类推,接收到的信号分别为75、74、73。所以当没有任何LED区域损坏时,答案为73。
但是同时要考虑到可能LED存在三个及以下区域损坏的场景,故还存在其他可能情况。
比如当左侧LED灯0号区域为常亮方式的损坏时,实际红灯剩余秒数序列可能为 15、14、13时,依然符合题意。
故当前智能系统无法唯一确定当前剩余时间,所以返回-1。

示例3

输入

[109,119,31,127,31,127,31,86,31,111]

输出

136

说明

我们观察左侧LED的变化,109的二进制为1101101,对应E(14),31的二进制为0011111,对应d(13)。故我们知道十位数从E变成了d。
再观察个位数,119对应1110111,127(连续两次)对应1111111,86对应1010110,111对应的二进制为1101111。
通过观察图形我们发现,右侧LED灯的4号区域损坏,属于常亮状态。秒数分别为140,139,138,137,136。
不存在其他任何在LED总损坏区域小于等于三的场景,能符合用例中信号值的变化。

备注:
1、不考虑LED总损坏区域数超过3的场景。
2、2 < N <= 50
3、0 <= arr[i] < 128

这道题你会答吗?花几分钟告诉大家答案吧!