携程9月7日笔试（第四题）

第四题解法：考试时没做出来。复杂度大约是NlogN（猜的，但肯定比N^2小得多）.

s = "10000000"
n = len(s)
length = [0] * (len(s))

for i in range(n - 1, -1, -1):
    if s[i] == "1":
        length[i] = 0
    else:
        length[i] = 1
        begin = i + 1
        while begin < n and s[begin] == "0":
            if begin + length[begin] < n - 1:
                length[i] += length[begin] + 1
                begin += length[begin] + 1
            else:
                length[i] += length[begin]
                break
# print(s)
# print(length)
print(sum(length))