Re: [問題]n位整數拿掉m數字得到最大數值
※ 引述《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)
討論串 (同標題文章)