題目描述

小明最近在研究壓縮算法。 他知道，壓縮的時候如果能夠使得數(shù)值很小，就能通過熵編碼得到較高的壓縮比。 然而，要使數(shù)值很小是一個挑戰(zhàn)。 最近，小明需要壓縮一些正整數(shù)的序列，這些序列的特點(diǎn)是，后面出現(xiàn)的數(shù)字很大可能是剛出現(xiàn)過不久的數(shù)字。對于這種特殊的序列，小明準(zhǔn)備對序列做一個變換來減小數(shù)字的值。 變換的過程如下： 從左到右枚舉序列，每枚舉到一個數(shù)字，如果這個數(shù)字沒有出現(xiàn)過，則將數(shù)字變換成它的相反數(shù)，如果數(shù)字出現(xiàn)過，則看它在原序列中最后的一次出現(xiàn)后面（且在當(dāng)前數(shù)前面）出現(xiàn)了幾種數(shù)字，用這個種類數(shù)替換原來的數(shù)字。 比如，序列(a1, a2, a3, a4, a5)=(1, 2, 2, 1, 2)在變換過程為： a1: 1未出現(xiàn)過，所以a1變?yōu)?span id="ze8trgl8bvbq" class="token operator">-1； a2: 2未出現(xiàn)過，所以a2變?yōu)?span id="ze8trgl8bvbq" class="token operator">-2； a3: 2出現(xiàn)過，最后一次為原序列的a2，在a2后、a3前有0種數(shù)字，所以a3變?yōu)?span id="ze8trgl8bvbq" class="token number">0； a4: 1出現(xiàn)過，最后一次為原序列的a1，在a1后、a4前有1種數(shù)字，所以a4變?yōu)?span id="ze8trgl8bvbq" class="token number">1； a5: 2出現(xiàn)過，最后一次為原序列的a3，在a3后、a5前有1種數(shù)字，所以a5變?yōu)?span id="ze8trgl8bvbq" class="token number">1。 現(xiàn)在，給出原序列，請問，按這種變換規(guī)則變換后的序列是什么。 輸入格式： 輸入第一行包含一個整數(shù)n，表示序列的長度。 第二行包含n個正整數(shù)，表示輸入序列。 輸出格式： 輸出一行，包含n個數(shù)，表示變換后的序列。 例如，輸入： 5 1 2 2 1 2 程序應(yīng)該輸出： -1 -2 0 1 1 再例如，輸入： 12 1 1 2 3 2 3 1 2 2 2 3 1 程序應(yīng)該輸出： -1 0 -2 -3 1 1 2 2 0 0 2 2 數(shù)據(jù)規(guī)模與約定 對于30%的數(shù)據(jù)，n<=1000； 對于50%的數(shù)據(jù)，n<=30000； 對于100%的數(shù)據(jù)，1 <=n<=100000，1<=ai<=10^9 資源約定： 峰值內(nèi)存消耗（含虛擬機(jī)） < 256M CPU消耗 < 3000ms 請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。 所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。 注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。 注意：主類的名字必須是：Main，否則按無效代碼處理。

思路分析

通過30%

代碼實(shí)現(xiàn)

package lanqiao;import java.util.*;public class Main {public static Map<Integer,Integer> lastIndex=new HashMap<Integer, Integer>();//數(shù)字與下標(biāo)的映射public static int[] data;//存儲輸入到每個字符public static int[] ans;//存儲每個的結(jié)果public static int n;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n=scanner.nextInt();//輸入序列的長度data=new int[n];ans=new int[n];for (int i = 0; i < n; i++) {int num= scanner.nextInt();data[i]=num;if(lastIndex.get(num)==null){//沒有出現(xiàn)過ans[i]=-num;}else {//出現(xiàn)過//統(tǒng)計(jì)p_num和i之間有多少不同的數(shù)字Set<Integer> set = new HashSet<>();for(int j=lastIndex.get(num)+1;j<i;j++){set.add(data[j]);}ans[i]=set.size();}lastIndex.put(num,i);//更新}for (int i = 0; i < n; i++) {System.out.print(ans[i]+" ");}} }

總結(jié)

以上是生活随笔為你收集整理的2016蓝桥杯省赛---java---A---10(压缩转换)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。