leetcode 10.25-11.01

2020-10-30

717 1比特字符与2比特字符
LCP 06 拿硬币

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

有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。

现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

示例 1:

输入:
bits = [1, 0, 0]
输出: True
解释:
唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
示例 2:

输入:
bits = [1, 1, 1, 0]
输出: False
解释:
唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/1-bit-and-2-bit-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：从前往后扫描数组，判断最后一位是不是1比特字符。由于开头是1的一定是2比特字符，扫描中遇到1可以直接向后跳两位继续扫描。

方法二：从后往前扫描，数最后一段连续的1的个数，如果是偶数个1，那么最后一个0就是1比特字符；否则为2比特字符

class Solution(object):
    def isOneBitCharacter(self, bits):
        """
        :type bits: List[int]
        :rtype: bool
        """
        if len(bits) is 1 or bits[-2] is 0: return True
        # 方法一：
        # index = 0
        # while index < (len(bits) - 1):
        #     if bits[index] == 1: index += 2
        #     else: index += 1
        # if index == (len(bits) - 1): return True
        # else: return False
        
        # 方法二：
        one_count = 0
        for i in range(1, len(bits)):
            if bits[len(bits)-1-i] == 1: one_count += 1
            else: break
        if one_count % 2 == 0: return True
        else: return False

LCP 06. 拿硬币

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

示例 1：

输入：[4,2,1]

输出：4

解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。

示例 2：

输入：[2,3,10]

输出：8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/na-ying-bi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：疯狂拿两个，奇数再多拿一个。凑数的题，赶紧的，不想思考了。

class Solution(object):
    def minCount(self, coins):
        """
        :type coins: List[int]
        :rtype: int
        """
        ret = 0
        for coin in coins:
            ret = ret + (coin / 2) + (coin % 2)
        return ret