データ構造とアルゴリズム: 単調に増加する数値

[[439817]]

単調に増加する数字

LeetCode の問題へのリンク: https://leetcode-cn.com/problems/monotone-increasing-digits

負でない整数 N が与えられた場合、N 以下の最大の整数を見つけます。この整数は、各桁の数字が単調に増加するという事実を満たす必要があります。

(すべての隣接する数字 x と y が x <= y を満たす場合にのみ、整数は単調に増加すると言います。)

例1:

入力: N = 10
出力: 9

例2:

入力: N = 1234
出力: 1234

例3:

入力: N = 332
出力: 299

注: N は [0, 10^9] の範囲の整数です。

力ずくの解決法

質問は非常に単純なので、最初に思いつくのは力ずくの解決法です。私が代わりにやってみますが、結果は当然タイムアウトです!

コードは次のとおりです。

クラスソリューション{
プライベート：
    ブールチェック番号( int数値){
整数 最大= 10;
        while (数値) {
 int t = 数値 % 10;
            （最大値＞＝t）の場合、最大値＝t;
それ以外 戻る 間違い;
            数値 = 数値 / 10;
        }
戻る 真実;
    }
公共：
 int monotoneIncreasingDigits( int N) {
 ( int i = N; i > 0; i --)の場合{  
            checkNum(i) の場合、 iを返します。
        }
 0を返します。
    }
 };

時間計算量: O(n * m) mはnの長さ
空間計算量: O(1)

貪欲アルゴリズム

この問題では、N 以下の最大の単調増加する整数が求められるため、2 桁の数字を例に挙げます。

たとえば、98 の場合です。strNum[i - 1] > strNum[i] (非単調増加) になると、まず strNum[i - 1] -- にして、次に strNum[i] を 9 にして、整数が 89 になるようにします。これは、98 未満の最大の単調増加整数です。

この点をしっかり考えれば、この問題は簡単に解決できるでしょう。

局所最適: strNum[i - 1] > strNum[i] の場合、strNum[i - 1] -- とし、strNum[i] を 9 に設定します。これにより、これらの 2 つの数字が最大の単調増加する整数になることが保証されます。

グローバル最適値: N 以下の単調に増加する最大の整数を取得します。

ただし、局所最適値から大域最適値を導き出すには、トラバース順序とマークの開始点（一律 9 に変更）など、他の条件も必要です。

前から後ろへ移動しますか、それとも後ろから前へ移動しますか?

前から後ろへトラバースする場合、strNum[i - 1] > strNum[i] であれば、strNum[i - 1] を 1 減らします。ただし、このとき strNum[i - 1] を 1 減らすと、strNum[i - 2] より小さくなる可能性があります。

少し抽象的ですが、例えば332という数字を前から後ろへたどっていくと329になります。このとき、2は最初の数字の3より小さいので、実際の結果は299になるはずです。

したがって、前から後ろへトラバースすると、すでにトラバースされた結果が変わります。

次に、後ろから前へ走査することで、最後の比較の結果を再利用できます。332の値は後ろから前へ変化します: 332 -> 329 -> 299

トラバーサル順序が決定された後、局所最適解から大域最適解を推測できます。反例が見つからない場合は、貪欲法を試してください。

C++ コードは次のとおりです。

クラスソリューション{
公共：
 int monotoneIncreasingDigits( int N) {
        文字列 strNum = to_string(N);
        // フラグは割り当て9の開始位置を示すために使用されます
        //フラグに値が割り当てられていない場合に2 番目のforループが実行されないようにするには、このデフォルト値を設定します。
 intフラグ = strNum.size ( );
 ( int i = strNum.size () - 1; i > 0; i -- ) {  
            strNum[i - 1] > strNum[i] の場合 {
                フラグ = i;
                strNum[i - 1] --;  
            }
        }
 ( int i = flag; i < strNum.size ( ) ); i++) {
            strNum[i] = '9' ;
        }
 stoi(strNum)を返します。
    }
 };

時間計算量: O(n) nは数の長さ
空間計算量: O(n) は文字列を必要とするため、文字列に変換する方が便利である

要約する

この問題では、98 などの 1 つの例についてのみ明確に考える必要があります。strNum[i - 1] > strNum[i] (非単調増加) になると、まず strNum[i - 1] を 1 減らし、strNum[i] に 9 を割り当てて、整数が 89 になるようにします。対応する貪欲な解決策を自然に考えることができます。

貪欲さについて考えるときは、トラバースの順序も考慮する必要があります。後ろから前へトラバースすることによってのみ、最後の比較の結果を再利用できます。

最終的なコードを実装するときには、値 9 の割り当てを開始する場所をマークするためのフラグを使用するなどのいくつかのテクニックも必要です。

その他の言語

ジャワ:

バージョン 1
クラスソリューション{
公共  int monotoneIncreasingDigits( int N) {
        String[] 文字列 = (N + "" ).split( "" );
 int開始 = 文字列.長さ;
 ( int i = strings.length - 1; i > 0; i --) {  
            整数.parseInt(文字列[i]) <整数.parseInt(文字列[i - 1]) の場合
                文字列[i - 1] = ( Integer .parseInt(文字列[i - 1]) - 1) + "" ;
                開始 = i;
            }
        }
 ( int i = start; i < strings.length; i++) {
            文字列[i] = "9" ;
        }
戻る 整数.parseInt(String . join ( "" , strings));
    }
 }

Java バージョン 1 では、String 配列が作成され、Integer.parseInt メソッドが複数回使用されるため、時間とスペースの使用量が膨大になり、12 ミリ秒かかります。次のバージョンでは、char 配列をその場で変更するため、1 ミリ秒かかります。

バージョン2
クラスソリューション{
公共  int monotoneIncreasingDigits( int n) {
        (n==0)の場合は0を返します。
 char [] chars = Integer .toString(n).toCharArray();
 int start = Integer .MAX_VALUE; //startの初期値は最大値に設定されます。これは、数値自体が単調増加しているときに、どの桁も9に変更する必要がない状況を防ぐためです。
 ( int i=chars.length-1;i>0;i --) {  
            （文字[i]<文字[i-1]）の場合{
                文字[i-1] --;  
                開始=i;
            }
        }
        StringBuilder res=新しいStringBuilder();
 ( int i=0;i<chars.length;i++) {
            if (chars[i]== '0' &&i==0) continue ;//09のような状況を防ぐ
            (i>=開始)の場合{
                res.append( '9' );
            }そうでない場合はres.append(chars[i]);
        }
戻る 整数.parseInt(res.toString());
    }
 }

パイソン:

クラスソリューション:
    def monotoneIncreasingDigits(self, n: int ) -> int :
        a = リスト(str(n))
 iが範囲(len(a)-1,0,-1)内にある場合:
            int (a[i]) < int (a[i-1])の場合:
                a[i-1] = str( int (a[i-1]) - 1) です。
                a[i:] = '9' * (len(a) - i) #pythonはフラグ値を設定する必要はなく、長さに応じて9を与えるだけです
戻る  int ( "" . join (a))

行く

func monotoneIncreasingDigits(N int ) int {
    s := strconv.Itoa(N) //添え字を使いやすくするために数値を文字列に変換する
    ss := []byte(s) //簡単に変更できるように文字列をバイト配列に変換します。
    n := 長さ(ss)
    n <= 1の場合{
 Nを返す
    }
 i:=n-1; i>0; i -- {  
        if ss[i-1] > ss[i]{//前の桁が次の桁より大きいので、前の桁を1減らし、次の桁をすべて9に設定します。
            ss[i-1] -= 1
 j := i ; j < n; j++の場合、後続の数字はすべて 9 に設定されます。
                ss[j] = '9'  
            }
        }
    }
    res, _ := strconv.Atoi(文字列(ss))
戻り値
}

ジャバスクリプト

var monotoneIncreasingDigits =関数(n) {
    n = n.toString()
    n = n.split( '' ).map(item => {
戻る+アイテム
    })
    フラグ = 無限大
(i = n.length - 1; i > 0; i --)の場合{  
        n[i - 1] > n[i]の場合{
            フラグ = i
            ｎ[i - 1] = ｎ[i - 1] - 1
            9 は
        }
    } 
 
 (i = flag; i < n.length; i++)の場合{
        9 は
    } 
 
    n = n.join ( '' )
戻る+n
 };