lintcode数字の削除
990 ワード
lintcode数字の削除
nビットの正の整数を表す文字列Aが与えられ、kビットの数字が削除され、残りの数字が元の順序で並べられて新しい正の整数が生成される.
k個の数値を削除した後の最小正の整数を見つけます.
N <= 240, k <= N
普通の貪欲な方法です.
前の対応するビット数の最小値を選択する、後のこの値の後ろに対応する最小値を選択する.
しかし、私は寝る前に普遍的な再帰式を考えて、動的な計画を利用して解答しました.再帰式は次のとおりです.
F(a,b)は配列Aの区間[[a,b]の最小値の位置である.
では、F(a,b)=min(F(i,b-1),A[b])があり、F(i,b-1)はaからb-1までの範囲内のすべてのF[i,b-1]の最小値を表し、これにより、埋め込み行列を用いて最小値の区間を求めることができる
しかし、この方法はここでは適用されません.この問題に比べて、この解答の時間の複雑さは大きすぎます.
nビットの正の整数を表す文字列Aが与えられ、kビットの数字が削除され、残りの数字が元の順序で並べられて新しい正の整数が生成される.
k個の数値を削除した後の最小正の整数を見つけます.
N <= 240, k <= N
普通の貪欲な方法です.
前の対応するビット数の最小値を選択する、後のこの値の後ろに対応する最小値を選択する.
class Solution {
public:
string DeleteDigits(string A, int k) {
int ResultSize = A.size() - k;
if(ResultSize == 1)
return A;
int last = 0;//
char NowMin = 0;
string Result;
for(int i = 0; i != ResultSize; i++)
{
NowMin = '9'+1;
for(int j = last; j != k+i+1; j++)
{
if(A[j] < NowMin)
{
NowMin = A[j];
last = j + 1;
}
}
if(NowMin != '0' || Result.size()==0)
Result += NowMin;;
}
return Result;
}
};
しかし、私は寝る前に普遍的な再帰式を考えて、動的な計画を利用して解答しました.再帰式は次のとおりです.
F(a,b)は配列Aの区間[[a,b]の最小値の位置である.
では、F(a,b)=min(F(i,b-1),A[b])があり、F(i,b-1)はaからb-1までの範囲内のすべてのF[i,b-1]の最小値を表し、これにより、埋め込み行列を用いて最小値の区間を求めることができる
しかし、この方法はここでは適用されません.この問題に比べて、この解答の時間の複雑さは大きすぎます.