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.