Writing in the front

Here’s a real interview question.

The topic is encoding the decimal to binary conversion:

Such as:

2, 3 NovemberCopy the code

coded

Python3 implementation

def translate(num: int) :
    result = []
    whilenum ! =0:
        result.append(str(num % 2))
        num = num // 2

    return "".join(result[::-1])
 
print(translate(3)) # 11
Copy the code

Think one step up

The above code is very simple to implement the decimal to binary logic, now need to implement the decimal to octal conversion, decimal to hexadecimal conversion, binary to decimal, and so on.

For example, convert hexadecimal to decimal

15 15
a 16
13 19
Copy the code

It’s actually pretty easy to do just by replacing the divisor, which is python3

# hex number mapping
temp = {
    '10': 'a'.'11': 'b'.'12': 'c'.'13': 'd'.'14': 'd'.'15': 'f'
}

# flip the dictionary
temp_reverse = {v: k for k, v in temp.items()}


def translate1(num: int, extra: int) - >str:
    result = []
    whilenum ! =0:
        result.append(str(num % extra))
        num = num // extra
    return "".join([temp.get(i, i) for i in result[::-1]])


def translate2(b: str, extra: int) - >int:
    result = 0
    for index, value in enumerate(b[::-1]):
        result += int(temp_reverse.get(value, value)) * extra ** index
    return result
    
The hex() function is used to verify the result
for i in range(14.20):
    b = translate1(i, 16)
    o = translate2(b, 16)
    print(hex(i)[2:]."".join(b), i, o)
    
# the results
"""
e d 14 14
f f 15 15
10 10 16 16
11 11 17 17
12 12 18 18
13 13 19 19
"""
Copy the code

Graphic process

The corresponding process of converting decimal to binary is actually the process of taking the remainder by division (the divisor is the corresponding base). As shown in the figure, the remainder is recorded by backward division, and the result is obtained by reversing the remainder. On the contrary, the process of converting binary to decimal is the process of corresponding remainder multiplication.

Think step two

Requirement: Orderly generate Excel columns like A, B, C… Z AA AB; That is, passing in a number to generate the corresponding sequence representation for example: 26 -> Z, 27 -> AA;

Answer:

  • The problem is similar to base conversion 27 base data.
  • It’s not going to be the case that the range of values for each digit might be different.
  • By obtaining the quotient and the value corresponding to the remainder conversion.
def num2xls_col(idx) :
    if idx < 1:
        raise ValueError("Index is too small")
    result = ""
    whileidx ! =0:
        idx, r = divmod(idx - 1.26)
        result = chr(r + ord('A')) + result
    return result

# verify results
for num in range(1.26 * 8) :if num % 26 in [0.1.2.25.24] :print(num2xls_col(num), end=",")
    elif num % 26= =3:
        print("...", end="")
# A,B,... X,Y,Z,AA,AB,... AX,AY,AZ,BA,BB,... BX,BY,BZ,CA,CB,... CX,CY,CZ,DA,DB,... DX,DY,DZ,EA,EB,... EX,EY,EZ,FA,FB,... FX,FY,FZ,GA,GB,... GX,GY,
Copy the code

It looks like a base conversion problem, but in practice it’s a little bit different, but essentially it’s all division and remainder. The version that starts with the dictionary stores the mapping between numbers and letters, and it’s probably easier to use ASCII code.

conclusion

  • For this seemingly simple problem, it is important to consider the boundary, for example, the first example did not consider the number less than zero.
  • ASCII can effectively result in sequential relationships between letters and numbers.
  • I hope you can follow my order step by step to understand my way of thinking.
  • Similar algorithm problems must be considered step by step from simple problems, step by step summary.