Xuan Luong
BAN USERdef count(s):
n_ways = [0 for _ in xrange(len(s) + 1)]
n_ways[len(s)] = n_ways[len(s) - 1] = 1
idx = len(s) - 2
while idx >= 0:
n_ways[idx] = n_ways[idx+1]
a, b = int(s[idx]), int(s[idx]+1)
number = a * 10 + b
if number <= 25:
n_ways[idx] += n_ways[idx+2]
idx -= 1
return n_ways[0]
Stack 1 for enqueuing.
Stack 2 for dequeing. If this stack is empty then keep popping stack 1 and pushing into stack 2 until stack 1 is empty.
O(1) amortized cost in time for each operation since each element is pushed twice and popped twice.
Nice question. My solution is to implment a subtract(a, b) function that actually does a-b without using the '-' operator. If the language is Java or C++, we can use bit manipulation based on the fact that negative number is the 2-complement of the positive counter part.
subtract(a, b) can be implemented as a + opposite(b).
If b is positive than opposite(b) is obtained by flipping b (xor with 1<<32 for int) and adding 1. If b is negative than opposite(b) is obtained by SUBTRACTING 1 and flipping it (xor with 1<<32).
Now for how to subtracting 1 from a number without using '-'. We keep iterating from the least significant bit to the most significant bit, invert the bit until the last inverted bit was 1.
Personally I think the dynamic programming solution is more intuitive and more language-agnostic.
- Xuan Luong October 27, 2017