第十屆藍橋杯省賽題：把 2019 分解成 3 個各不相同的正整數之和，并且要求每個正整數都不包含數字 2 和 4，一共有多少種不同的分解方法？
- 題目
- 我的思路
- 上代碼
- 心得體會
- 這次的糾錯程序整個就倆字兒
題目
【問題描述】
把 2019 分解成 3 個各不相同的正整數之和，并且要求每個正整數都不包含數字 2 和 4，一共有多少種不同的分解方法？注意交換 3 個整數的順序被視為同一種方法，例如 1000+1001+18 和1001+1000+18 被視為同一種，
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
我的思路
本人初步接觸藍橋杯的演算法題，也沒系統研究過同類題型，只是簡單分享下自己的做題感悟，第一次發布博文，歡迎大家批評指正！
- 初步想法還是選擇直接暴力拆分 ，于是考慮最大限度減少回圈次數；
- 原理是以第一個數為三個數中最小的數依次向后遍歷，遍歷次數需要總數2019的三分之一即可，這里設第一個數為 i；
- 確定完第一個數之后，再以第二個數為剩下兩個數中最小的數依次向后遍歷，遍歷次數需要 2019 - i 的二分之一即可，這里設第二個數為 j，第三個數為 k；
- 題目要求交換順序的三個正整數不算數，于是考慮將這三個數直接從小到大排列之后再存盤到結果集；
- 受上一個題計算子字串個數的啟發，我選用了HashMap存盤結果集，存盤思想就是把這三個數排序之后用+號連接轉為字串存入Map，這樣可以直接避免重復值；
- 最后，列印出Map的size即可；
上代碼
public void testInt(){
int int0 = 2019;
HashMap map = new HashMap();
for(int i = 1;i<=(int0/3);i++){//其實第一個數遍歷到2019的三分之一即可
if( Integer.toString(i).contains("2") || Integer.toString(i).contains("4") ){
continue; //如果第一個數包含2或4則直接不考慮
}
for(int j = 1;j<=((int0-i)/2);j++){//其實第二個數遍歷到2019-i的二分之一即可
if( Integer.toString(j).contains("2") || Integer.toString(j).contains("4") ){
continue; //如果第二個數包含2或4則直接不考慮
}
int k = int0-i-j;
if( Integer.toString(k).contains("2") || Integer.toString(k).contains("4") ){
continue; //如果第三個數包含2或4則直接不考慮
}
//將三個數值按從小到大排列
//sortThree方法就是把三個數從小到大排一下然后中間用+號連接成字串
map.put(sortThree(i,j,k),0);
}
}
System.out.println(map.size());
}
于是乎，程式的輸出是
我還挺高興，但是查閱了好幾個網上的大佬給出的結果都是40785…
草率了，把41087個結果列印出來挨個檢查！
添加代碼段輸出Map中的值：
Set<Map.Entry<String,Integer>>set = map.entrySet();
for(Map.Entry<String ,Integer>entry : set){
System.out.println(entry.getKey());
}
System.out.println(map.size());
輸出如下：
為了驗證每條結果是否重復或結果不為2019的情況，我把所有資料放到了Excel里（亂入）：
首先編輯公式
選擇填充范圍
向下填充公式
A列添加條件格式：重復值標紅—>>添加篩選條件：按顏色篩選 ，B列按升序排序
得到如下結果：
結果為A列無重復值且結果均為2019…
這波大意了？！
于是乎又審了遍題目，淦！三個不同正整數的和？？
改代碼！
public void testInt(){
int int0 = 2019;
HashMap map = new HashMap();
for(int i = 1;i<=(int0/3);i++){//其實第一個數遍歷到2019的三分之一即可
if( Integer.toString(i).contains("2") || Integer.toString(i).contains("4") ){
continue; //如果第一個數包含2或4則直接不考慮
}
for(int j = 1;j<=((int0-i)/2);j++){//其實第二個數遍歷到2019-i的二分之一即可
if( Integer.toString(j).contains("2") || Integer.toString(j).contains("4") || i==j){
continue; //如果第二個數包含2或4，或者前兩個數相同，則直接不考慮
}
int k = int0-i-j;
if( Integer.toString(k).contains("2") || Integer.toString(k).contains("4") || i==k || j==k){
continue; //如果第三個數包含2或4,或者一三數相同或二三數相同，則直接不考慮
}
//將三個數值按從小到大排列
//sortThree方法就是把三個數從小到大排一下然后中間用+號連接成字串
map.put(sortThree(i,j,k),0);
}
}
System.out.println(map.size());
}
此處添加了判斷三個數中是否含相等值的條件
結果如下：
好的，這波可以安心的繼續脫發了，
心得體會
現在還在考慮要不要參加藍橋杯比賽，編了幾道題也大概了解了些比賽時候的一點注意事項，那就是一定要冷靜，然后認真審題！
這次的糾錯程序整個就倆字兒
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/264456.html
標籤：其他
下一篇：大資料平臺搭建 | Hive