650. 2 Keys Keyboard

LeetCode medium original: C# #array #csharp #dynamic-programming #leetcode #math #matrix #medium #sliding-window

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

LeetCode Static

На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. given Ganzzahl n, return минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.

Beispiel:

Input: n = 3

Output: 3

C# Lösung

zugeordnet/original

public class Solution {
    public int MinSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (i % j == 0) {
                    dp[i] = Math.Min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

C++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinSteps(int n) {
        if (n == 1) return 0;
        vector<int>& dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (i % j == 0) {
                    dp[i] = min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

Java Lösung

zugeordnet/original

public class Solution {
    public int minSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (i % j == 0) {
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

JavaScript Lösung

zugeordnet/original

var minSteps = function(n) {
    if (n === 1) return 0;
    const dp = new Array(n + 1).fill(0);
    for (let i = 2; i <= n; i++) {
        dp[i] = i;
        for (let j = 1; j <= i / 2; j++) {
            if (i % j === 0) {
                dp[i] = Math.min(dp[i], dp[j] + i / j);
            }
        }
    }
    return dp[n];
};

Python Lösung

zugeordnet/original

def minSteps(n):
    if n == 1:
        return 0
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = i
        for j in range(1, i // 2 + 1):
            if i % j == 0:
                dp[i] = min(dp[i], dp[j] + i // j)
    return dp[n]

Go Lösung

zugeordnet/original

package main

import (
    "fmt"
    "math"
)

func minSteps(n int) int {
    if n == 1 {
        return 0
    }
    dp := make([]int, n+1)
    for i := 2; i <= n; i++ {
        dp[i] = i
        for j := 1; j <= i/2; j++ {
            if i%j == 0 {
                dp[i] = int(math.Min(float64(dp[i]), float64(dp[j]+i/j)))
            }
        }
    }
    return dp[n]
}

Algorithm

Используйте dynamic programming для отслеживания минимального количества операций, необходимых для достижения определенного количества 'A' на экране.

Итерируйтесь от 1 до n, проверяя все возможные делители текущего числа и обновляя минимальное количество операций для каждого числа.

Возвращайте значение из таблицы динамического программирования для n.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.