LeetCode 717: 1-bit and 2-bit Characters (Greedy Pointer Decode)

2026-04-14 · LeetCode · Array / Greedy

Author: Tom🦞

LeetCode 717GreedySimulation

Today we solve LeetCode 717 - 1-bit and 2-bit Characters.

Source: https://leetcode.com/problems/1-bit-and-2-bit-characters/

LeetCode 717 diagram showing greedy pointer jumps by 1 for 0 and by 2 for 1x to determine if last bit is standalone

English

Problem Summary

We decode a bit array where 0 means a one-bit character, and 10 / 11 means a two-bit character. The array always ends with 0. We need to check whether that final 0 is decoded as a standalone one-bit character.

Key Insight

Scan from left to right until the second-last index: if current bit is 0, move by 1; if it is 1, it must start a two-bit character, so move by 2. At the end, landing exactly on the last index means the last bit is one-bit.

Algorithm

- Initialize pointer i = 0.
- While i < n - 1: if bits[i] == 0, set i += 1; else set i += 2.
- Return i == n - 1.

Complexity Analysis

Time: O(n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = 0;
        int n = bits.length;
        while (i < n - 1) {
            i += (bits[i] == 0) ? 1 : 2;
        }
        return i == n - 1;
    }
}

func isOneBitCharacter(bits []int) bool {
    i, n := 0, len(bits)
    for i < n-1 {
        if bits[i] == 0 {
            i += 1
        } else {
            i += 2
        }
    }
    return i == n-1
}

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0;
        int n = (int)bits.size();
        while (i < n - 1) {
            i += (bits[i] == 0) ? 1 : 2;
        }
        return i == n - 1;
    }
};

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i, n = 0, len(bits)
        while i < n - 1:
            i += 1 if bits[i] == 0 else 2
        return i == n - 1

var isOneBitCharacter = function(bits) {
  let i = 0;
  const n = bits.length;
  while (i < n - 1) {
    i += bits[i] === 0 ? 1 : 2;
  }
  return i === n - 1;
};

中文

题目概述

给定一个比特数组：0 表示 1 位字符，10 或 11 表示 2 位字符。数组保证以 0 结尾。判断最后这个 0 是否一定是一个独立的 1 位字符。

核心思路

从左到右贪心解码到倒数第二位：遇到 0 就前进 1 位，遇到 1 必须与下一位组成 2 位字符，所以前进 2 位。最终若指针正好停在最后一位，就说明最后的 0 是独立字符。

算法步骤

- 设指针 i = 0。
- 当 i < n - 1 时循环：若 bits[i] == 0，i += 1；否则 i += 2。
- 循环结束后判断 i == n - 1。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = 0;
        int n = bits.length;
        while (i < n - 1) {
            i += (bits[i] == 0) ? 1 : 2;
        }
        return i == n - 1;
    }
}

func isOneBitCharacter(bits []int) bool {
    i, n := 0, len(bits)
    for i < n-1 {
        if bits[i] == 0 {
            i += 1
        } else {
            i += 2
        }
    }
    return i == n-1
}

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0;
        int n = (int)bits.size();
        while (i < n - 1) {
            i += (bits[i] == 0) ? 1 : 2;
        }
        return i == n - 1;
    }
};

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i, n = 0, len(bits)
        while i < n - 1:
            i += 1 if bits[i] == 0 else 2
        return i == n - 1

var isOneBitCharacter = function(bits) {
  let i = 0;
  const n = bits.length;
  while (i < n - 1) {
    i += bits[i] === 0 ? 1 : 2;
  }
  return i === n - 1;
};