Динамическое программирование - Ugly Numbers II｜Go Theme Month

Go

[Месяц изучения темы Golang] На выходных я попробовал ответить на несколько вопросов по динамическому программированию и отправил очень деликатную учебную версию. Ответ был очень хорошим. Далее я буду использовать два языка для вопросов по кодированию и чистке, а именно GO и JAVA , ребята, продолжайте писать вопросы.

Если вы не знакомы с динамическим программированием, перейдите к этой статье.\color{red}{Если вы не знакомы с динамическим программированием, перейдите к этой статье~}

Живите много дней - десять последовательных динамических программ - сверхтонкий анализ |

Это относительно простой вопрос 😄😄😄 \color{green}{Это относительно простой вопрос 😄 😄 😄 ~}

Какие вопросы вы можете решить с помощью динамического программирования?

1. Считать

  • Сколько способов попасть в правый нижний угол
  • Сколькими способами можно выбрать k чисел да и сложить

2. Найдите максимальное и минимальное значения

  • Максимальная сумма чисел пути из левого верхнего угла в правый нижний угол
  • самая длинная восходящая длина подпоследовательности

3. Ищите существования

  • В игре со сбором камней обязательно ли выиграет тот, кто сделает первый ход?
  • Можно ли выбрать k чисел так, чтобы сумма была суммой

4. Комплексное применение

  • динамическое программирование + хэш
  • динамическое программирование + рекурсия
  • ...

буквенный код 264. Уродливые числа II

Учитывая целое число n, пожалуйста, найдите и верните n-е уродливое число.

Уродливые числа — это положительные целые числа, которые содержат только простые делители 2, 3 и/или 5.

 

Пример 1:

Вход: n = 10

Выход: 12

Объяснение: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] — это последовательность первых 10 некрасивых чисел.

Пример 2:

Вход: n = 1

выход: 1

Объяснение: 1 часто считают некрасивым числом.  

намекать:

1 <= n <= 1690

--

Здорово! 😄😄😄 \color{green}{Отлично! 😄 😄 😄 ~}

Код ссылки

языковая версия ГО

func nthUglyNumber(n int) int {
    dp := make([]int, n+1)
    dp[1] = 1
    p2, p3, p5 := 1, 1, 1
    for i := 2; i <= n; i++ {
        x2, x3, x5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
        dp[i] = min(min(x2, x3), x5)
        if dp[i] == x2 { 
            p2++   // 出现次数
        }
        if dp[i] == x3 {
            p3++
        }
        if dp[i] == x5 {
            p5++
        }
    }
    return dp[n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

NICEЭто слишком просто 😄😄😄 \color{red}{NICE слишком просто 😄 😄 😄 ~}

Java-версия

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
                p2++;
            }
            if (dp[i] == num3) {
                p3++;
            }
            if (dp[i] == num5) {
                p5++;
            }
        }
        return dp[n];
    }
}

❤️❤️❤️❤️

Большое спасибо, что смогли увидеть эту статью.Если эта статья хорошо написана и вы думаете, что есть что-то, пожалуйста, ставьте лайк👍 Следуйте ❤️ Пожалуйста, поделитесь 👥 Это действительно полезно для меня, красавчик Оппа! ! !

Если в этом блоге есть какие-либо ошибки, пожалуйста, критикуйте и советуйте, это очень ценится!

В конце статьи мы недавно составили материал для интервью «Руководство по прохождению интервью по Java», в котором рассматриваются основные технологии Java, JVM, параллелизм Java, SSM, микросервисы, базы данных, структуры данных и многое другое. Как получить: GitHub github.com/Tingyu-Note…, следуйте официальной учетной записи для получения большего контента: Tingyu Notes, которые будут предоставляться один за другим.

Категории