Несколько интересных тем по алгоритмам

Эта статья впервые опубликованаsvtter.cn

ближайший номер

тема

K-битное число N

(К≤ 2000, N≤ 10 20)

Найдите ближайшее число больше N, сумма каждого бита этого числа такая же, как N, и реализуйте его в коде.

Например: 0050 требует, чтобы номер книги был 0104, 112 — 121;

Алгоритм анализа Алгоритм мышления

Невозможно напрямую перебрать это число, величина числа слишком велика, а число из K бит не может быть напрямую представлено int или float и сохранено в массиве. Это число следует проанализировать, шаг 1, начиная с наименьшей цифры справа, разложить последнюю цифру и разложить 1, чтобы получить предыдущую цифру. 9 и 0 специальные, поэтому с начала сканирования слева направо пропускаем при встрече с 0, а при встрече с первой не 0 цифрой ставим цифру -1, а потом передвигаем ее в конец, а потом, step2, Начните искать первое число, отличное от 9. Если вы встретите 9, поставьте 9 в конце. Если вы встретите не 9, добавьте 1, чтобы завершить операцию.

Общий пример:

1999000 -> 1990008-> 2000899

Одна проблема, на которую следует обратить внимание, заключается в том, что если это 999000, добавьте 1 в начале числа, и результат будет 1000899.

Несколько неуправляемых данных: 29399 -> 29489

Поддельный код

array = get_array() # number to char array
array.reverse()
step1 = true
step2 = false
zero = 0, cnt = 0;
for i : 1 - lengthof(array)
    if step1:
        if array[i] is 0:
            zero ++
        else:
            array[i] = array[i] - 1
            if zero > 0:
                array[0] = array[i]
                array[i] = 0
            step1 = false
            step2 = true
    else if step2:
        if array[i] is 9:
            if zero == 0:
                array[cnt+1] = array[cnt]
                array[cnt] = 9
                cnt++
                if (i != cnt):
                    array[i] = array[i-1]
            else:
                array[cnt + 1] = array[cnt]
                array[cnt] = 9
                cnt++
                array[i] = 0
        else:
            i = i+1
            step2 = false
            break
            
            
if not step2:
    array[lengthof(array)] = 1

array.reverse()
disp(array)

Сложность времени анализа O

Из-за обратной операции, 2К, плюс последняя сортировка минимального числа вперед, в худшем случае близко к К, 3К, работа в цикле зависит от удачи, но в худшем случае всего 5К, поэтому время сложность

О(3К)≈О(К)

исходный код

#include <stdio.h>
#include <string.h>

const int MAXN = 3000;
char array[MAXN];
int length_of_number;
void get_array()
{
    int i;
    char null;
    scanf("%d", &length_of_number);
    scanf("%c", &null);
    for (i = 0; i < length_of_number; i++)
    {
        scanf("%c", &array[i]);
    }
    scanf("%c", &null);
}

void reverse()
{
    int i ;
    char temp;
    for (i = 0; i < length_of_number/2; i++)
    {
        // _swap
        temp = array[i];
        array[i] = array[length_of_number - 1 - i];
        array[length_of_number-1-i] = temp;
    }
}

void run()
{
    reverse();
    int step1 = 1,
        step2 = 0,
        i = 0,
        zero = 0,
        cnt = 0;
    for (i = 0; i < length_of_number; i++)
    {
        if (step1)
        {
            if (array[i] == '0')
            {
                zero++;
            }
            else
            {
                array[i] = array[i] - 1;
                if (zero > 0)
                {
                    array[cnt] = array[i];
                    array[i] = '0';
                }
                step1 = 0, step2 = 1;
            }
        }
        else if (step2)
        {
            if (array[i] == '9')
            {
                if (zero == 0)
                {
                    array[cnt + 1] = array[cnt];
                    array[cnt] = '9';
                    cnt++;
                    if (i != cnt)
                    {
                        array[i] = array[i-1];
                    }
                }
                else
                {
                    array[cnt + 1] = array[cnt];
                    array[cnt] = '9';
                    cnt++;
                    array[i] = '0';
                }
            }
            else
            {
                array[i] ++;
                step2 = 0;
                break;
            }
        }
    }
    if (step2)
    {
        array[length_of_number] = '1';
        length_of_number ++;
    }
}

void output()
{
    int i;
    reverse();
    for(i = 0; i < length_of_number; i++)
    {
        printf("%c", array[i]);
    }
    printf("\n");
}

int main()
{
    memset(array, 0, sizeof(array));
    freopen("input", "r", stdin);
    get_array();
    run();
    output();
    return 0;
}

Результаты теста

использоватьpythonСгенерируйте тестовые данные для тестирования:

"""
最接近的数字
"""
import random
import os

def test():
    """
    sample test
    """
    num = random.randint(0, 10000000)
    sum_of_num = 0
    for i in str(num):
        sum_of_num += int(i)

    length = len(str(num))
    temp_num = num + 1

    while(True):
        sum_temp = 0
        for i in str(temp_num):
            sum_temp += int(i)
        if sum_temp == sum_of_num:
            break
        temp_num += 1

    with open('input', 'w') as f:
        f.write(str(length) + '\n')
        f.write(str(num))

    res = os.popen('./ex2').read()
    if temp_num == int(res):
        return [True]
    else:
        return [False, num, temp_num, int(res)]


all = True
for i in range(1000):
    res = test()
    if res[0] is False:
        all = False
        print(res)

if all:
    print('Pass testing!')

Есть состояние ошибки:

пройти через:

Где улучшить и оптимизировать позже

1. реверс предназначен для удобства программирования, но если число слишком велико, это определенно повлияет на скорость, поэтому не используйте реверс в настоящее время.

2. Использование связанного списка может упростить код, сократить объем анализа и сэкономить время.

3. Рассмотрите несколько вопросов при работе со сменами

Найти сообщения

тема

Если нет "Водяного короля", но есть три ID, которые много постят, и количество постов превышает 1/4 от количества постов, как быстро узнать их ID.

Алгоритм анализа Алгоритм мышления

Сканируем массив ID от 0-n, записываем количество из 3-х цифр, если есть четвертая цифра, уменьшаем количество из трех цифр на 1, если есть цифра, которая уменьшается до 0, то уменьшаем количество новых цифр Число записывается как одно из исходных трех чисел.

Таким образом, после сканирования массива идентификаторов число оставшихся трех записанных чисел является тремя числами, которые необходимо запросить.

Поддельный код

array = get_array()
count = empty_set()
for i in array:
    if count.full:
        if i in count:
            count.i.num ++
        else:
            for j in count:
                count.j.num--
    else
        count.add(i)
disp(count)

Сложность времени анализа O

Размер последовательности равен N, а размер массива записанных чисел равен 3. Требуется 3 единицы времени, чтобы определить, есть ли 0 в счете массива записей, и найти существующее число ++, поэтому временная сложность

О(3n) ≈O(n)

исходный код

#include <stdio.h>
#include <string.h>

#define MAXN 5000
int idarray[MAXN];

int cur[3]; // 记录当前元素
int pos[3]; // 记录当前元素个数

// 检查是否在数组内，如果不在数组内，添加进入数组
void checkin(int no)
{
    int i;

    // 检查是否有空位置
    for (i = 0; i < 3; i++)
    {
        if (pos[i] == 0)
        {
            cur[i] = no;
            pos[i] ++;
            return;
        }
    }

    // 寻找指定数字++
    for (i = 0; i < 3; i++)
    {
        if (cur[i] == no)
        {
            pos[i] ++;
            return;
        }
    }

    // 没有找到重复数字，全部--
    for (i = 0; i < 3; i++)
        pos[i] --;
}

// 输出最后结果
void output()
{
    printf("%d %d %d\n", cur[0], cur[1], cur[2]);
}

// 主程序
int numberOfArray;
void run()
{
    int i;
    for (i = 0; i < numberOfArray; i++)
    {
        checkin(idarray[i]);
    }

    output();
}

void input()
{
    int i;
    scanf("%d", &numberOfArray);
    for(i = 0; i < numberOfArray; i++)
    {
        scanf("%d", &idarray[i]);
    }

}

int main()
{
    freopen("input", "r", stdin);
    int groupOfTest;
    scanf("%d", &groupOfTest);
    while(groupOfTest--)
    {
        memset(cur, 0, sizeof(cur));
        memset(pos, 0, sizeof(pos));
        memset(idarray, 0, sizeof(idarray));
        input();
        puts("Test running...");
        run();
    }
    return 0;
}

Результаты теста

Эти тестовые данные используютPythonГенерируется автоматически.

"""
寻找发帖水王
"""

import random

N = 4000
a, b = (int(N/4), int(N/3))
three_id = random.sample(range(1, 100), 3)
three_id_num = {}
sum_rand = 0
for i in three_id:
    temp = random.randint(a, b)
    sum_rand += temp
    three_id_num[i] = three_id_num.get(i, 0) + temp

id_array = [random.randint(1, 100) for i in range(N-sum_rand)]
for i in three_id:
    id_array = id_array + [i for j in range(three_id_num[i])]

random.shuffle(id_array)

print('Most three id:', three_id)
print('Three id num: ', three_id_num)
print('Sum of three_id num: ', sum_rand)
print('---------------')
# print(id_array)

with open('input', 'w') as f:
    f.write('1\n')
    f.write(str(N) + '\n')
    for i in id_array:
        f.write(str(i) + ' ')

Где улучшить и оптимизировать позже

1. Для случая, когда N относительно мало, его можно искать в памяти, но когда речь идет о больших данных, этот метод может быть не таким простым, и массив не может быть построен внутри, и его нужно считывать с диска по частям. ;

2. Если количество искомых идентификаторов увеличивается, временно сохраняемый массив может быть больше;

3. Эта реализация не использует карту в STL. Если используется карта, это может еще больше упростить понимание кода. Карта использует хэш для внутренней реализации, что может ускорить поиск данных при столкновении с данными с большим объемом данных.

Угольный босс Шаньси

тема

Вы - угольный босс в Шаньси. Вы добыли 3000 тонн угля в районе добычи и должны перевезти его на рынок. От вашего района добычи до рынка 1000 километров. У вас в руках поезд, сжигающий уголь. Этот поезд может вместить только 1000 тонн угля, а потребление энергии относительно велико - одна тонна угля расходуется на километр. Простите, как угольщик, знающий программирование, как бы вы возили на рынок больше всего угля?

Алгоритм анализа Алгоритм мышления

Найдите оптимальное решение с точки зрения динамического программирования:
Предполагая, что начальный объем груза равен t, расстояние до пункта назначения равно s, а вместимость поезда равна c, максимальное количество груза, которое можно перевезти до пункта назначения, представляет собой функцию F(t, s).
3 основные ситуации:
(1) t (2) s 3) 2s

F (t, s)=(t/ c−1)∗ (c−2s)+(c−s)

Рекурсию можно получить:

F (t, s)=m ax {F( F (t,i), s−i)}(1Анализ этого уравнения проблематичен, например, F(1750, 250) вычислит 1125;

Таким образом, правильный результат должен относиться к t/c, то есть оставшегося топлива в начальной точке недостаточно для транспортировки в конечную точку, и оно сразу выбрасывается. Уравнение третьего этапа должно быть

F (t, s)=( t/ / c−1)∗ (c−2 s)+( c−s )+( t%c−2 s), если (t% c>2 s)

Поддельный код

begin:
    if t < s:
        f[t][s] = 0
    elif s < t < c:
        f[t][s] = t - s
    elif 2*s < c:
        f[t][s] = int((t//c-1)*(c-2*s) + (c-s))
        if t % c > 2*s:
            f[t][s] += int(t % c-2*s)
    else:
        pre = -2
        for i in range(1, s):
            pre = int(max(F(F(t, i), s-i), pre))
        f[t][s] = pre
end
disp(f[3000][1000])

Сложность времени анализа O

Временная сложность

О (3000∗3000)

Потому что каждое число нужно вычислять заново.

исходный код

"""
山西煤老板
"""
c = 1000
f = [[-1 for k in range(4000)] for j in range(4000)]
for j in range(4000):
    for k in range(4000):
        if j < k:
            f[j][k] = 0
count = 1000
cnt = 0


def F(t, s):
    """
    dp
    """
    global count
    global c
    global f
    # count -= 1
    # if count == 0:
        # count = int(input())

    t = int(t)
    s = int(s)
    if f[t][s] != -1:
        return f[t][s]
    if t < s:
        f[t][s] = 0
    elif s < t < c:
        f[t][s] = t - s
    elif 2*s < c:
        f[t][s] = int((t//c-1)*(c-2*s) + (c-s))
        if t % c > 2*s:
            f[t][s] += int(t % c-2*s)
    else:
        pre = -2
        for i in range(1, s):
            pre = int(max(F(F(t, i), s-i), pre))
        f[t][s] = pre
    print(t, s, f[t][s])
    return f[t][s]


print(F(3000, 500))

Результаты теста

Где улучшить и оптимизировать позже

1. Удалить немного данных для ускорения

2. Сохраните значение f, чтобы уменьшить значения повторяющихся операций.

3. Должен быть более простой способ, что-то вроде этого, но это трудно объяснить.

   

4. 3 y=1000 5 x= 1000 решает для x+ y= 200+333 = 533, таким образом экономя 533 тонны угля к прибытию последнего поезда

Facebook

тема

Given a list of words, L, that are all the same length, and a string, S, find the starting position of the substring of S that is concatenation of each word in L exactly once and without intervening characters. This substring will occur exactly once in S.

Алгоритм анализа Алгоритм мышления

Используйте хэш-карту, чтобы сохранить хэш-значение слова, чтобы ускорить поиск. (Старый)

Используйте хеш-функцию напрямую, чтобы найти хеш-значение строки и, наконец, получить результат.

По формуле

h ash (w 1 )+has h(w 2 )=has h( w 2 )+hash( w 1 )

Поддельный код

hash_word_list = list(map(hash, words))
hash_sum = reduce(lambda x, y: x + y, hash_word_list)

for i in range(len(sentence)):
    wl = word_len
    wlist = [sentence[i+j*wl:i+j*wl+wl] for j in range(words_len)]
    temp_sum = 0
    for k in wlist:
        temp_sum += hash(k)
    if temp_sum == hash_sum:
        print(i)
        break

Сложность времени анализа O

длина строки

O (le ng thO fS )

исходный код

#!/usr/bin/env python3
"""
facebook

"""
from functools import reduce

while True:
    words = input()
    # words = "fooo barr wing ding wing"
    words = words.split(' ')
    word_len = len(words[0])
    words_len = len(words)

    hash_word_list = list(map(hash, words))
    hash_sum = reduce(lambda x, y: x + y, hash_word_list)

    sentence = input()
    # sentence = """lingmindraboofooowingdin\
    # gbarrwingfooomonkeypoundcakewingdingbarrwingfooowing"""

    # print(words, words_len, word_len, sentence)

    for i in range(len(sentence)):
        wl = word_len
        wlist = [sentence[i+j*wl:i+j*wl+wl] for j in range(words_len)]
        # print(wlist)
        temp_sum = 0
        for k in wlist:
            temp_sum += hash(k)
        if temp_sum == hash_sum:
            print(i)
            break

Результаты теста

Смысл генерации тестовых данных не очень большой, т.к.

Где улучшить и оптимизировать позже

1. Хотя хэш превосходен по скорости, с точки зрения точности, в случае коллизии хэша значение может быть неточным. В настоящее время для решения этой проблемы можно использовать хэш-карту, но для сброса хэш-карты потребуется больше времени.

For n -m - problems

Problemset

Assume we have a sequence that contains N numbers of type long. And we know for sure that among this sequence each number does occur exactly n times except for the one number that occurs exactly m times (0 < m < n). How do we find that number with O(N) operations and O(1) additional memory?

Algorithm

^ is the add operation without carry.
По умолчанию один и два равны 0, то есть числа не существует.
Когда число а встречается впервые, единица отмечает существование а, а двойка не изменяется.
Когда число а приходит во второй раз, одной фишки а не существует, а две фишки а существуют.
Когда число а встречается в третий раз, единица остается неизменной, а двойка знака а не существует.

Создайте операцию, которая сохраняет данные в один и два с помощью XOR.

Pseudocode

def solve2(array):
    one = 0, two = 0
  for i in range(array):
      one = (one ^ array[i]) & ~two
    two = (two ^ array[i]) & ~one
  return one, two

array = input()
_, res = solve2(array)

### Source code

#!/usr/bin/env python

def solve(array):
   one, two = 0, 0
   for i in array:
       one = (one ^ i) & ~two
       two = (two ^ i) & ~one
   return one, two


if __name__ == '__main__':
   array = input()
   array = array.split(' ')
   array = list(map(lambda x: int(x), array))
   # print(array)
   _, res = solve(array)
   print(res)

Test

#!/usr/bin/env python3
import random

def test():
    """
    测试
    """
    array = []
    n, m = 3, 2
    numberofNum = random.randint(100, 1000)

    record = {}
    for _ in range(numberofNum):
        temp = random.randint(10, 10000)
        while temp in record:
            temp = random.randint(10, 10000)
        record[temp] = 1
        for _ in range(3):
            array.append(temp)

    temp = random.randint(10, 1000)
    while temp in record:
        temp = random.randint(10, 1000)

    array.append(temp)
    array.append(temp)

    from run import solve
    _, res = solve(array)
    if res != temp:
        print('ERROR')
        print(array, temp)
        input()
    else:
        print('Pass: res: ', res, 'temp:', temp)

for i in range(50):
    test()

Use python generate data to test.

Discussion and improve

Если n не равно 3, необходимо построить больше временных переменных.

очень длинный массив

тема

Очень длинный и длинный короткий массив A, разобьем его на m подмассивов B1, B2,..., Bm длины L, каждый из которых после сортировки является возрастающей арифметической последовательностью, и найдем наибольшее значение L.

Например, A={−1,3,6,1,8,10} можно разделить на B1={−1,1,3},B2={6,8,10}, L=3 требуемый .

Анализ алгоритмов

Сначала отсортируйте, затем начните идти в три шага.

1. Подсчет количества элементов O (n)

2. Сортировать O (nlog (n))

   ​

Первым шагом является перечисление размера L и м. Судя по заголовку, L * m = длина массива. Перечисление начинается с m, равного 1, и полученное L гарантированно будет максимальным значением.

Второй шаг — это глубокий поиск, который определяет начальную точку и размер начального шага текущего подмассива и использует pos для записи выбранного элемента текущего массива.

Третий шаг перечисления, в соответствии с начальным размером шага, заданным начальной точкой, начинает размер шага перечисления, если размер шага перечисления может найти достаточно элементов в массиве, то есть число равно L, затем запишите метод деления и начать перечисление со следующей начальной точки. Если размер шага и начальная точка перечисления не могут соответствовать условиям, вернитесь к предыдущему узлу и повторите поиск, добавив размер шага, записанный предыдущим узлом, + 1. Когда количество начальных точек перебора достигает m, требуемый результат удовлетворяется.

На простом языке это означает разделить исходный массив на m массивов с начала, После сортировки нераспределенные элементы каждого предыдущего узла являются отправной точкой подмассива. Если использовать поиск в ширину, то есть каждый раз присваивать подмассиву число, удовлетворяющее требованию к размеру шага подмассива, то в конце будет обнаружено, что количество выделенных элементов не соответствует требованиям, что приводит к потере много времени.

Среди них есть несколько методов обрезки для поиска в глубину:

1. Если текущий размер шага*(L-1) превышает максимальный элемент массива, поиск можно остановить

2. Если при заданном размере шага размер следующего числа превышает предыдущее число + размер шага, то поиск можно не продолжать.

   Потому что массив уже отсортирован.

3. Существуют и другие приемы обрезки, которые отражены в коде.

временная сложность

n — длина массива, время сортировки — O(nlogn), время перечисления m — n, время шага перечисления — 65536 [короткий интервал], время перечисления всех элементов — n, поэтому время верхняя граница алгоритма

O (65536n 2 )

На практике из-за наличия таких операций, как обрезка, должно быть лучше, чем в этот раз.

Поддельный код

leng = len(Array)
for m=1 to n:
    if n % m != 0:
        continue
    L = n // m
    # deep search
    res, record = findArray(L, m)

def findArray(L, m):
    group = 0
    pos = np.ones(leng)
    record = []
    record_start = []
    while group != m:
        step = 0
        start = getStart(pos)
        res, step = 寻找合适的步长(start, step, pos, record, L)
        if res:
            找到了计数
        while res is False:
            没找到弹出栈，往回找
        if 弹出栈为空:
            不用找了找不到了
   return False, None

исходный код

#!/usr/bin/env python3
# coding: utf-8
"""
arrays
"""

from __future__ import print_function
import numpy as np

array = [-1, 3, 6, 1, 8, 10]
# array = [1, 5, 9, 2, 6, 10]
# array = [1, 2, 4, 5, 8, 9, 13, 14]
# array = [1, 2, 4, 7, 11]
array = sorted(array)
print(array)
leng = len(array)
maxn = array[leng-1]
enable = 1
disable = 0


def findJ(j, step, pos, record, L):
    """
    寻找以J为开始，以步长step为开始的数列
    """
    class StepError(Exception):
        pass

    class MaxException(Exception):
        pass

    if pos[j] == disable:
        return False
    start = array[j]
    pre = start
    record_temp = []

    # remember zero
    try:
        for step in range(step, 40000):
            # 把第一个数字记录
            record_temp.append(j)
            pos[j] = disable
            pre = start

            if start + step * (L - 1) > maxn:
                raise MaxException

            try:
                cnt = 1
                if cnt == L:
                    record.append(record_temp)
                    return True, step

                for k in range(j, leng):

                    if pos[k] == disable:
                        continue
                    elif pos[k] == enable and array[k] == pre + step:
                        record_temp.append(k)
                        pre = array[k]
                        cnt += 1
                        pos[k] = disable
                    elif pos[k] == enable and array[k] > pre + step:
                        raise StepError

                    if cnt == L:
                        record.append(record_temp)
                        return True, step

            except StepError:
                # 重置标记
                for r in record_temp:
                    pos[r] = enable
                record_temp = []

    except MaxException:
        # 没有合适的step
        return False, None


def findArray(L, m):
    """
    寻找数组
    """

    pos = np.ones(leng)
    record = []
    record_start = []
    group = 0

    while group != m:
        start = 0
        while pos[start] == disable:
            start += 1

        step = 0
        res, step = findJ(start, step, pos, record, L)
        if res:
            group += 1
            record_start.append((start, step))
        while res is False:
            try:
                start, step = record_start.pop()
                for r in record.pop():
                    pos[r] = enable
                group -= 1
                res, step = findJ(start, step+1, pos, record, L)
            except IndexError:
                return False, None
    return True, record


def divideArray():
    """
    分离数组
    m 是分离的数组的个数
    L 是分离的数组的长度
    """
    for m in range(1, leng+1):
        if leng % m != 0:
            continue

        L = leng // m
        res, record = findArray(L, m)

        def trans(x):
            return array[x]

        if res:
            print('lenth: ', L)
            for r in record:
                temp = map(trans, r)
                print(list(temp))
            return

    print('No result.')


if __name__ == '__main__':
    divideArray()

контрольная работа

Результаты генерации тестовой выборки могут быть неточными, если вы найдете какие-то тестовые выборки, вы можете их отозвать, модифицировав массив в коде.

обсуждать

1. После записи начальной точки и размера шага вы должны быть в состоянии использовать эти две точки, чтобы определить, какие элементы используются в настоящее время.Если места недостаточно, вы не можете применить запись записи.Если следующий слой не соответствует условиям для возврата можно использовать начальную точку и размер шага.Отодвиньте элемент, который был использован.