主页 / 问题 / 1254655
Accepted
андрей марченков
Asked:2022-03-12 02:27:11 +0000 UTC2022-03-12 02:27:11 +0000 UTC

告诉我如何优化python代码以通过服务器上的随机测试

  • 772
Задача: Создайте функцию, которая принимает положительное целое  число
и возвращает  следующее за представленным большее число,  которое
можно сформировать, переставив его цифры.
Например:    
12 ==> 21   
513 ==> 531   
2017 ==> 2071
Если не получается сформировать число то вернуть -1
Это задание с сайта Codewars.com

https://www.codewars.com/kata/55983863da40caa2c900004e/train/python

这是我的解决方案

def next_bigger(n):
    # Условие для одинаковых цифр типа 1, 2,...111,333,...9999999 
    if str(n).count(str(n)[0]) == len(str(n)):
        return -1
    elif len(str(n)) == 2: # Условие для 2-х цифр
        if n > int(str(n)[::-1]): # для таких чисел 21, 53, 98 - большее число не получить
            return -1
        else:
            return int(str(n)[::-1])
    lst = []
    # Для других чисел производим комбинации и из комбинаций как только найдём
    # первое число больше заданного вставляем его в список и  break
    for el in permutations(str(n), len(str(n))):
        if int(''.join(el)) > n:
            lst.append(int(''.join(el)))
            break
    print(lst)
    if not lst:
        return -1
    return lst[0] 

Базовые тесты проходят все.
А вот случайные --- по времени не проходят
Подскажите пожалуйста!
python

5 个回答

  1. Best Answer

    改变算法：

    1. 对于非常特殊的情况，从中删除不必要的检查
    2. 不要使用permutations（这个枚举效率很低）

    该算法基于几个观察结果：

    1. 要获得一个新的更大的数字，您需要将数字条目中某个位置的一个数字替换为数字条目j中右侧（即较低的顺序）出现的一个大数字。
    2. 为了使这种替换过程中数字的变化最小，您需要选择一个j尽可能靠近数字右边缘的位置。
    3. 为了使数字的变化最小，您需要以最小的数字在前的方式排列剩余的数字。

    现在是程序本身。该算法不需要 2**n 的迭代（与 一样permutations，但在线性时间内工作（因为它对数字使用索引排序来找到最小数字，或者换句话说，只是计算它们）。

    import math

def generate_number_for_digit_counts(digit_counts):
    """ генерирует минимальное число, в котором есть заданное количество цифр
        digit_counts содержит для каждой цифры количество ее вхождений в число.
        см. тест test_order с примерами
    """
    val = 0
    for digit, count in enumerate(digit_counts):
        for _ in range(count):
            val = val * 10 + digit
    return val

def next_bigger(n):
    # количество разрядов в числе
    digits = int(math.log10(n)) + 1
    # k-й элемент содержит количество цифр k, которые встретились при просмотре числа
    digit_counts = 10 * [0]
    # вспомогательное значение, которое используется для выделения разряда
    curr_base = 1
    for j in range(digits, 0, -1): # просматриваем разряды начиная справа
        curr_digit = (n // curr_base) % 10 # выделяем цифру в текущем разряде
        digit_counts[curr_digit] += 1      # увеличиваем счетчик просмотреных 
                                           # для текущей цифры
        # следующий цикл ищет есть ли справа от текущей цифры
        # большая цифра. Ищем такую минимальную
        # начиная от curr_digit + 1 и до 9
        for i in range(curr_digit + 1, 10):
            if (digit_counts[i] == 0): # если цифра і нам не встречалась
                continue               # то переходим к следующей т.е. i+1

            # тут мы оказываемся если цифра i встречалась нам правее от текущей
            # позиции j
            digit_counts[i] -= 1  # цифру i будем ставить в позицию j
                                  # для этого исключaeм ее из тех, которые будем
                                  # размещать справа от позиции j

            # тут составляем новое число
            # у него начало (до позиции j-1) от числа n:
            #      n // curr_base - это цифры от начала до j включительно, т.е.
            #      с curr_digit в самой правой позиции
            # далее идет цифра i:        
            #      - curr_digit + i это замена curr_digit на i в позиции j
            # далее идут остальные цифры числа отсортированные по возрастанию
            return curr_base * (n // curr_base - curr_digit + i) \
                + generate_number_for_digit_counts(digit_counts)

        curr_base *= 10

    return -1

import pytest
@pytest.mark.parametrize("test_input,expected", [
    ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0),
    ([1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0),
    ([1, 0, 0, 0, 1, 0, 0, 0, 0, 0], 4),
    ([1, 0, 4, 0, 1, 0, 0, 0, 0, 0], 22224),
])
def test_generate_number_for_digit_counts(test_input, expected):
    assert generate_number_for_digit_counts(test_input) == expected


@pytest.mark.parametrize("test_input,expected", [
    (2017, 2071),
    (2071, 2107),
    (2107, 2170),
    (2701, 2710),
    (2170, 2701),
    (2710, 7012),
    (82734210, 82740123),
    (8273421110, 8274011123),
    (8974421110, 9011124478),
    (91684, 91846)
])
def test_next_bigger(test_input, expected):
    assert next_bigger(test_input) == expected
    • 4

  2. 总的来说，我没有看个别情况的支票，也许支票中数字很长的情况下需要它们，以免白白驱动期权。算法本身似乎像这样工作正常：

    from itertools import permutations

def next_bigger(n):
    zu = None
    for el in permutations(str(n), len(str(n))):
        q = int(''.join(el))
        if q > n:
            if not zu or q < zu:
                zu = q
    if not zu:
        return -1
    return zu 

next_bigger(127643)

    底线是我查看所有组合，但同时我正在寻找大于 的最小数字n。

    如果您拒绝转换int并使用字符串，您可以稍微缩短时间：

    def next_bigger(n):
    zu = None
    n = str(n)
    for el in permutations(n, len(n)):
        q = ''.join(el)
        if q > n:
            if not zu or q < zu:
                zu = q
    return int(zu) or -1
    • 2

  3. 初步考虑。

    让一些数字，例如，123456789我们修改如下：

    1. 第 - 位的数字i减少1,
    2. 左边的所有数字都保持不变，
    3. 右边的所有数字都设置为9：
    Исходное:            123 4 56789
Модифицированное:    123 3 99999

    修改后的数量严格小于原始数量。而如果右边的九换成其他数字，那么修改后的数字会变得更小。这意味着对于修改后的数字要大于原始数字，最左边的修改数字不能减少。

    现在我们像这样修改数字：

    1. i将-th 位置的数字增加1,
    2. 左边的所有数字都将保持不变，
    3. 右侧的所有数字都将设置为0：
    Исходное:            123 4 56789
Модифицированное:    123 5 00000

Исходное:            123456 7 89
Модифицированное:    123456 8 00

    现在修改后的数字严格大于原始数字。而如果右边的零被其他数字代替，那么修改后的数字会变得更大。因此，要增加数字，必须增加最左边的修改数字。

    另外，根据上面的例子可以看出，“最左修改位”越靠右，修改后的数字与原来的差异就越小。

    算法

    让一个数字由一个数字数组表示arr，其中arr[0] 是数字的最高位，是数字arr[arr.length - 1] 的最低位。

    1. arr.length - 2在从到的循环中0，我们遍历数字，直到找到一个小于右侧数字的数字，即 arr[i] < arr[i+1]. 我们称之为“基地”。
    2. 如果数组中没有这样的数字，则该数组表示一个非递增的数字序列。因此，通过排列数字，不可能使数字更大。我们会回来-1的。
    3. 在这一步，数组由三部分组成。枢轴左侧的数字、枢轴数字和枢轴右侧的数字。

    例子：

         5432   1   987654321

    这里是左边5432。基数 - 1。右侧 - 987654321。

    笔记：

    • 左边可以是空集。
    • 右侧至少包含一位数字。
    • 右侧至少有一个数字大于枢轴数字。
    • 仅在右侧通过排列增加总数是不可能的，因为 右侧的数字按非递增顺序排列。

    所以，现在我们可以通过交换参考数字和右边的数字来增加数字。因此，增加左侧的数字是没有意义的：结果数字将大于我们用 9 替换枢轴和整个右侧的数字。

    我想保持参考数字不变，并在右侧增加一些东西。但这也是做不到的。右侧的数字按非递增顺序排列。仅在右侧没有数字排列，不要增加右侧。

    所以你需要增加基数。并尽可能少地增加。让我们在所有大的数字中找到比参考数字小的右边的数字并将它们交换。现在，即使右边的所有数字都重置为零，结果数字也将严格大于原始数字。

    但是，我们不能简单地将右侧重置为零 - 只有排列。因此，我们以非递减的数字对右侧进行排序。

    我们继续算法：

    1. 让我们记住辅助变量中的参考图pivot。
    2. 让我们在右侧找到大于参考数字的最小数字。让我们从右侧删除它（现在右侧可以是一个空集）并写它来代替参考数字。
    3. 让我们将右侧尽可能小。以非递减数字对右侧进行排序。（不必直接应用排序算法。由于右侧的数字是非递增顺序的，因此将它们反转即可。）
    4. 让我们将参考元素pivot插入右侧，以便保留右侧数字的顺序。
    5. 结果数组包含问题的解决方案。

    所有阶段 - 搜索参考数字，在右侧搜索，从右侧移除，右侧反转，右侧添加 - 具有线性复杂度O(N)，其中N 是数组中的位数arr。算法的最终复杂度为O(N)。

    代码草图（唉，但我不能用 python 编写代码......让它成为 JavaScript）：

    function nextBigger(n) {
    let arr = Number(n).toFixed().split("");
    
    //Ищем индекс опорного элемента
    let pivotIndex = arr.length - 2;
    for ( ; pivotIndex >= 0; --pivotIndex)
        if (arr[pivotIndex] < arr[pivotIndex + 1])
            break;
    if (pivotIndex < 0)
        return -1;
    
    //Извлекаем из массива правую часть и опорный элемент
    //Сразу сделаем реверс правой части
    let right = arr.splice(pivotIndex + 1, arr.length - pivotIndex - 1).reverse();
    let pivot = arr.pop();
    
    //Ищем индекс заменителя опорного элемента
    let pivotRepIndex = right.findIndex(elem => elem > pivot);
    //Извлекаем из правой части заменитель опорного элемента
    let pivotRep = right.splice(pivotRepIndex, 1);
    
    //Ищем позицию в правой части для вставки опорного элемента
    let j = 0;
    for ( ; j < right.length; ++j)
        if (pivot <= right[j])
            break;
    
    //Вставляем опорный элемент в правую часть
    right.splice(j, 0, pivot);
    
    //Объединяем левую часть, заменитель опорного и правую часть.
    arr = arr.concat(pivotRep, right);
    
    return Number(arr.join(""));
}

console.log(nextBigger(12));
console.log(nextBigger(513));
console.log(nextBigger(2017));
console.log(nextBigger(54321987654321));

    • 2

  4. next_permutation使用类似于 C++ STL 中使用的算法。据我记得，itertools与重复项类似的方法不能正常工作，但它的实现（线性时间）非常简单，将花费更多时间来解析数字并收集回来。

    def nextperm(seq):
    i = len(seq) - 2
    while i >= 0 and seq[i] >= seq[i+1]:
        i -= 1
    if i < 0:
        return None
    j = len(seq) - 1
    while seq[j] <= seq[i]:
        j -= 1
    seq[i], seq[j] = seq[j], seq[i]
    seq[i+1:] = reversed(seq[i+1:])
    return seq

s = list(str(534))
n = nextperm(s)
if n:
    print("".join(n))
else:
    print(-1)
    • 2

    1. 并非总是找到的第一个数字将是之后的下一个数字

    2. 第一次检查变得容易得多len(set(str(n))) == 1。

    3. 在检查中，您经常执行相同的转换，例如str(n), len(str(n)))，最好将它们移动到变量中。

    试试这样：

    def next_bigger(n):
    n_s = str(n)
    n_len = len(n_s)
    if len(set(n_s)) == 1:
        return -1
    if n_len == 2:
        k = int(n_s[::-1])
        return k if k>n else -1

    lst = []
    for el in permutations(n_s):
        k = int(''.join(el))
        if k > n:
            lst.append(k)
    return min(lst) if lst else -1

    UPD1：

    def next_bigger(n):
    n_lst = list(str(n))
    n_len = len(n_lst)
    new = -1
    if len(set(n_lst)) == 1:
        return -1
    for i in range(n_len-1, 0, -1):
        for j in range(i, -1, -1):
            if n_lst[i] > n_lst[j]:
                n_lst[i], n_lst[j] = n_lst[j], n_lst[i]
                k = int(''.join(n_lst))
                if new == -1 or new > k:
                    new = k
                n_lst[i], n_lst[j] = n_lst[j], n_lst[i]
    return new
    • 1

相关问题