Leetcode PHP题解--D126 717. 1-bit and 2-bit Characters


题目链接

717. 1-bit and 2-bit Characters

题目分析

这道题目的描述很难懂,我看了Discussion区别人解释才看懂了。

现在采用2位的霍夫曼编码,即:只有0、10和11三种。

给定一个数组,每一个值为1位。现在固定最后一位为0,判断这最后一位是1位的还是2位的。即:是10的0,还是0的0。

解题思路

考虑使用栈来实现,遇到1则入栈,0则把“最后一位为1位编码”标记置1。如果栈里已经有值了,说明当前是2位编码。把标记置0。

最终代码

<?php
class Solution {

    /**
     * @param Integer[] $bits
     * @return Boolean
     */
    function isOneBitCharacter($bits) {
        $stack = [];
        $isOneBit = false;
        foreach($bits as $bit){
            if(isset($stack[0])){
                array_pop($stack);
                $isOneBit = false;
            }
            else{
                if($bit == 1){
                    $stack[] = $bit;
                }
                else{
                    $isOneBit = true;
                }
            }
        }
        
        return $isOneBit;
    }
}

若觉得本文章对你有用,欢迎用爱发电资助。


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D125 107. Binary Tree Level Order Traversal II

>> 下一篇: Leetcode PHP题解--D127 455. Assign Cookies