大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

有两种字符，一种是 0，一种是10或者11。

给出了一个由这两种字符组成的数组，判断最后一位的数字是否一定是单个的 0．

解题方法

遍历

有两种字符串，一种是 0，一种是 10 或 11。即一种长度是1，一种长度是2.

所以找个指针然后遍历一遍，看看当前值是 0 还是1，是 0 走一步，是1走两步。

题目告诉了数组的最后一个元素一定是 0，所以最后如果恰好到达len-1，说明最后一个数字的长度为 1 ，也就是 0，就满足题意了。

717. 1比特与2比特字符.001.png

代码如下：

  1. class Solution(object):
  2.     def isOneBitCharacter(self, bits):
  3.         """
  4.         :type bits: List[int]
  5.         :rtype: bool
  6.         """
  7.         pos = 0
  8.         while pos < len(bits) - 1:
  9.             pos += 2 if bits[pos] == 1 else 1
  10.         return pos == len(bits) - 1
  1. class Solution {
  2. public:
  3.     bool isOneBitCharacter(vector<int>& bits) {
  4.         const int N = bits.size();
  5.         int pos = 0;
  6.         while (pos < N - 1) {
  7.             pos += bits[pos] == 1 ? 2 : 1;
  8.         }
  9.         return pos == N - 1;
  10.     }
  11. };
  1. class Solution {
  2.     public boolean isOneBitCharacter(int[] bits) {
  3.         int N = bits.length;
  4.         int pos = 0;
  5.         while (pos < N - 1) {
  6.             pos += bits[pos] == 1 ? 2 : 1;
  7.         }
  8.         return pos == N - 1;
  9.     }
  10. }

日期

  • 时间复杂度：$O(N)$，其中 $N$ 是数组长度；
  • 空间复杂度：$O(1)$。

总结

image.png

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。