这是悦乐书的第 302 次更新, 第 321 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 170 题 (顺位题号是 717). 有两个特殊字符, 第一个字符可以用一个比特 0 表示, 第二个字符可以用两个比特(10 或 11) 表示. 现在给出一个由比特位组成的数组, 判断其最后一个字符是否是一位字符. 数组的最后一位始终是比特 0. 例如:
输入: bits = [1,0,0]
输出: true
说明: 解码它的唯一方法是两位字符和一位字符, 所以最后一个字符是一位字符.
输入: bits = [1,1,1,0]
输出: false
说明: 解码它的唯一方法是两位字符和两位字符, 所以最后一个字符不是一位字符.
注意:
数组长度范围为[1,1000].
bits[i]始终为 0 或 1.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
为了满足最后一位是 0, 前面的 n-1 位必须完成匹配, 即前面的 n-1 位能够按照一位, 两位合理组成. 所以, 我们直接使用循环, 计算前面 n-1 位完成组合的长度, 判断其是否等于 n-1. 因为有两种情况, 遇到 0 的时候, 一位就行, 遇到 1 的时候, 只能是两位. 使用一个变量, 从 0 开始往后累加, 遇到 0 就加 1, 遇到 1 就加 2, 最后判断其是否等于 n-1.
- public boolean isOneBitharacter(int[] bits) {
- int len = bits.length, index = 0;
- while (index <len-1) {
- if (bits[index] == 0) {
- index++;
- } else {
- index += 2;
- }
- }
- return index == len-1;
- }
03 第二种解法
对于第一种解法, 我们还可以再优化下, 在循环中去掉 if 判断, 直接加上当前元素, 因为后面带了加 1, 遇到 0 还是加 1, 遇到 1, 就变成加 2 了, 和原来的思路一样.
- public boolean isOneBitharacter2(int[] bits) {
- int len = bits.length, index = 0;
- while (index < len-1) {
- index += bits[index] + 1;
- }
- return index == len-1;
- }
04 第三种解法
我们也可以从后往前推导. 因为数组最后一个数字始终是 0, 在遇到倒数第二个 0 时, 这中间 1 的个数只能是偶数个或者 0 个. 如果中间 1 的个数是 0 个, 即数组最后两个元素都是 0, 不管其前面是 1 还是 0, 都满足条件. 其二, 如果中间 1 的个数是奇数个, 并且是连着的, 就不满足题目的设定了.
- public boolean isOneBitharacter3(int[] bits) {
- int len = bits.length;
- int count = 0;
- for (int i = len - 2; i>= 0; i--) {
- if (bits[i] == 1) {
- count++;
- } else {
- break;
- }
- }
- return count%2 == 0;
- }
05 小结
算法专题目前已日更超过五个月, 算法题文章 170 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/c2b604732411