Codility代写 Python笔试OA真题讲解

一道Codility平台基础算法题讲解.

原题如下:

Two non-negative integers are called siblings if they can be obtained from each other by rearranging the digits of their decimal representations. For example, 123 and 213 are siblings. 535 and 355 are also siblings.

A set consisting of a non-negative integer N and all of its siblings is called the family of N. For example, the family of 553 comprises three numbers: 355, 535 and 553

Write a function:

def solution (N)

that, given a non-negative integer N, returns the largest number in the family of N. The function should return – 1 if the result exceeds 100.000.000.

For example, given N = 213 the function should return 321. Given N = 553 the function should return

553.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..2,147,483,647].

题目大意为给定一个整数N, 自由排列N组成的数字的顺序, 返回最大的那个数.

解题思路:

要想得到最大数, 我们需要尽可能把大的数字放到最高位. 比如对 N=123, 最大数是321, 3放到最高位, 2放到第2高位, 最后放1.

所以求解的步骤是:

1. 得到构成N的数字
2. 按从大到小排列这些数字
3. 求按这些数字组合得到的整数

比如对N=132, 第1步得到 [2, 3, 1], 第2步得到[3, 2, 1], 第3步得到 321.

Python代码如下:

def solution(N):
    # get digits
    digits = []
    while N > 0:
        digit = N % 10
        digits.append(digit)
        N //= 10
    
    digits.sort(reverse=True)
    ret = 0
    for d in digits:
        ret = ret * 10 + d
        if ret > 100000000:
            return -1
    return ret

这题考察了2个基础算法, 1个是由整数得到组成整数的数字, 另一个是由数字得到整数.