本系列博客習(xí)題來自《算法(第四版)》倘是，算是本人的讀書筆記停团，如果有人在讀這本書的旷坦，歡迎大家多多交流。為了方便討論佑稠，本人新建了一個(gè)微信群(算法交流)秒梅，想要加入的，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝舌胶。另外捆蜀，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論
知識(shí)點(diǎn)
- 前移編碼
題目
1.3.40 前移編碼幔嫂。從標(biāo)準(zhǔn)輸入讀取一串字符辆它，使用鏈表保存這些字符并刪除重復(fù)字符。當(dāng)你讀取了一個(gè)從未見過的字符時(shí)履恩，將它插入表頭锰茉。當(dāng)你讀取了一個(gè)重復(fù)的字符時(shí)，將它從鏈表中刪去并再次插入表頭切心。將你的程序命名為 MoveToFront：它實(shí)現(xiàn)了著名的前移編碼策略飒筑，這種策略假設(shè)最近訪問過的元素很可能會(huì)再次訪問片吊，因此可以用于緩存、數(shù)據(jù)壓縮等許多場(chǎng)景协屡。
1.3.40 Move-to-front. Read in a sequence of characters from standard input and maintain the characters in a linked list with no duplicates. When you read in a previ- ously unseen character, insert it at the front of the list. When you read in a duplicate character, delete it from the list and reinsert it at the beginning. Name your program MoveToFront: it implements the well-known move-to-front strategy, which is useful for caching, data compression, and many other applications where items that have been recently accessed are more likely to be reaccessed.
分析
本人所有簡(jiǎn)書的算法文章詳細(xì)分析已經(jīng)移入小專欄：算法四習(xí)題詳解俏脊，歡迎大家訂閱
答案
private static class Node {
char item;
Node next;
}
public static class MoveToFront {
private Node first;
private int N=0;
public void Judge(char c)
{
Node current = first;
for(int i=0;i < N;i++)
{
if(current.item == c)
{
current = current.next;
return ;
}
current=current.next;
}
this.push(c);
}
public void push(char item)
{
Node oldfirst= first;
first = new Node();
first.item=item;
first.next=oldfirst;
N++;
}
public void print()
{
for(Node current=first;current!=null;current=current.next) {
System.out.print(current.item+" ");
}
}
}
public static void main(String[] args){
MoveToFront mtf = new MoveToFront();
while(!StdIn.isEmpty())
{
mtf.Judge(StdIn.readChar());
}
mtf.print();
}
廣告
我的首款個(gè)人開發(fā)的APP壁紙寶貝上線了，歡迎大家下載肤晓。
