刷爆力扣之1 比特与 2 比特字符

刷爆力扣之1 比特与 2 比特字符

HELLO，各位看官大大好，我是阿呆 🙈🙈🙈

今天阿呆继续记录下力扣刷题过程，收录在专栏算法中 😜😜😜

该专栏按照不同类别标签进行刷题，每个标签又分为 Easy、Medium、Hard 三个等级 👊👊👊

本部分所有题目均来自于LeetCode 网，并于每道题目下标明具体力扣网原题链接 🏃🏃🏃

OK，兄弟们，废话不多直接上题，冲冲冲 🌞🌞🌞

一 🏠 题目描述

717. 1 比特与 2 比特字符

有两种特殊字符：

• 第一种字符可以用一比特 0 表示
• 第二种字符可以用两比特（10 或 11）表示

给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一个一比特字符，则返回 true

示例 1:

输入: bits = [1, 0, 0]
输出: true
解释: 唯一的解码方式是将其解析为一个两比特字符和一个一比特字符
所以最后一个字符是一比特字符
1
2
3
4

示例 2:

输入：bits = [1,1,1,0]
输出：false
解释：唯一的解码方式是将其解析为两比特字符和两比特字符
所以最后一个字符不是一比特字符
1
2
3
4

提示:

• 1 <= bits.length <= 1000
• bits[i] 为 0 或 1

二 🏠破题思路

2.1 🚀 关键信息

解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎

一个以 0 结尾的二进制数组 bits ，若最后一个字符必须是一个一比特字符，则返回 true

第一种字符可以用一比特 0 表示 = 第一种字符一定以 0 开头

第二种字符可以用两比特（10 或 11）表示 = 第二种字符一定以 1 开头

提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃

2.2 🚀 思路整理

对数组正序遍历

① 当 bits[i] = 0 时，说明当前是第一种字符，将 i 加一

② 当 bits[i] = 1 时，说明当前是第二种字符，将 i 加二

如果遍历至 i = len - 1，那么说明最后一个字符一定是第一种字符 🌷🌷🌷

注：因若数组以第二种字符结尾，则 i = len

整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃

三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路，直接代码走起来 👇👇👇👇

bool isOneBitCharacter(std::vector &bits) {
    int len = bits.size(), i = 0; //获取数组长度, 初始化索引
    while (i < len - 1) { //遍历数组
        i += bits[i] + 1; //移动对应距离
    }
    return i == len - 1;  //判断最后一个字符是否为第一种字符
}
1
2
3
4
5
6
7

3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃

那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇

i += bits[i] + 1; //移动对应距离
1

① 当 bits[i] = 0 时，说明当前是第一种字符，将 i 加一

② 当 bits[i] = 1 时，说明当前是第二种字符，将 i 加二

这里 bits[i] 数值 0，1 也正好对应了移动的距离，一种巧妙的写法 🐳🐳🐳

四 🏠 心路历程

为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈

博主在第一阶段提取 🚀 关键信息没有问题，在第二阶段 🚀 思路整理没有问题

代码实现时未联想到使用 bits[i] 简化代码 😶😶😶 ，代码如下 👇👇👇👇

bool isOneBitCharacter(vector& bits) {
    int offsets = 0, len = bits.size();
    std::vector::const_iterator iter = bits.cbegin(); //使用了迭代器(冗余)

    while (true) {
        if (offsets == len) return false; //判断应丢到循环外, 效率差
        else if (offsets == len - 1) return true;

        if (*iter == 0) iter += 1, offsets += 1;
        else iter += 2, offsets += 2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

五 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

如果各位看官大大觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪