作者nilson847552 (lalala)
看板Prob_Solve
标题Re: [问题]n位整数拿掉m数字得到最大数值
时间Fri Nov 22 02:27:32 2013
※ 引述《PATRICKSTARS (PatrickStar)》之铭言：
: Given an integer (not necessary a decimal number) with n digits, we want to
: remove m (<=n) digits from this number such that the resulting number is as
: large as possible. Design an O(n) time algorithm to solve it.
: 可以提示如何下手吗?
从最高位往个位扫
当目前数字 < 下一个
则舍弃目前数字
若下一个没有数字了
也舍弃目前数字
虚拟码
int f (int input, int m){
LinkedList l;
//双向linked list l
//从头到尾是高位到低位digit
if(m >= l.size)
return 0;
p = l.head ;
while (m > 0){
if (p.next== null || p.value < p.next.value ){
if (p.next==null){
p = p.last;
p.next = null;
}
else{
temp = p.last;
temp.next=p.next;
p=temp;
}
m--;
}
else
p=p.next;
}
//把list l转回数字
temp = l.tail;
int ret=0;
int s=0;
while(temp!=null){
ret+=temp.value * 10^s;
s++;
temp = temp.last;
}
return ret;
}
--
Sent from my Android
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 36.237.37.2
※ 编辑: nilson847552 来自: 36.237.37.2 (11/22 11:12)