最近在刷算法題時(shí)我遇到了一個(gè)看似簡(jiǎn)單卻讓不少初學(xué)者“栽跟頭”的經(jīng)典問題——“與7無關(guān)的數(shù)”。很多同學(xué)一看題目覺得不就是判斷數(shù)字里有沒有7、能不能被7整除嗎結(jié)果一上手要么漏判要么性能拉胯要么邊界條件處理得一塌糊涂。這篇文章我們不只講這道題的標(biāo)準(zhǔn)解法。更重要的是我想和你探討一個(gè)更本質(zhì)的問題為什么一個(gè)簡(jiǎn)單的“過濾”邏輯會(huì)成為檢驗(yàn)程序員基本功的試金石這道題背后其實(shí)藏著對(duì)整數(shù)處理、循環(huán)優(yōu)化和邊界思維的全面考察。很多面試官喜歡用它來快速判斷候選人的代碼嚴(yán)謹(jǐn)性。如果你正在準(zhǔn)備編程入門考試、刷LeetCode基礎(chǔ)題或者想鞏固自己的循環(huán)與條件判斷能力那么這篇文章就是為你準(zhǔn)備的。我會(huì)從最暴力的解法開始一步步帶你分析性能瓶頸最終給出清晰、高效且健壯的代碼實(shí)現(xiàn)并解釋其中每一個(gè)容易踩坑的細(xì)節(jié)。1. 問題重述到底什么是“與7無關(guān)的數(shù)”題目通常這樣描述一個(gè)正整數(shù)如果它能被7整除或者它的十進(jìn)制表示法中某一位上的數(shù)字為7則稱這個(gè)數(shù)為“與7有關(guān)”。反之如果一個(gè)數(shù)既不能被7整除且它的每一位數(shù)字都不包含7則稱這個(gè)數(shù)為“與7無關(guān)的數(shù)”。現(xiàn)在給定一個(gè)正整數(shù)nn 100請(qǐng)計(jì)算1到n之間包含1和n所有“與7無關(guān)的數(shù)”的平方和。舉個(gè)例子如果 n 20。與7有關(guān)的數(shù)有7, 14, 17。與7無關(guān)的數(shù)則是1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 18, 19, 20。我們需要計(jì)算的是這些“無關(guān)數(shù)”的平方和12 22 32 42 52 62 82 ... 202。問題的核心判斷邏輯就兩點(diǎn)整除判斷i % 7 0數(shù)位判斷數(shù)字i的任意一位等于7很多新手會(huì)在這里犯第一個(gè)錯(cuò)誤只判斷了個(gè)位。比如數(shù)字17個(gè)位是7顯然有關(guān)但數(shù)字70呢個(gè)位是0但它能被7整除同樣有關(guān)。數(shù)字177呢十位和個(gè)位都是7。所以必須對(duì)整數(shù)的每一位進(jìn)行檢查。2. 基礎(chǔ)解法從“暴力拆解”開始理解我們先寫一個(gè)最直觀、最好理解的版本。這個(gè)版本可能效率不是最高但它能最清晰地展現(xiàn)整個(gè)邏輯流程適合初學(xué)者理解和調(diào)試。思路很簡(jiǎn)單遍歷1到n的每一個(gè)數(shù)i。如果i % 7 0跳過。否則將i逐位拆解檢查每一位是否為7。一旦發(fā)現(xiàn)某位是7就跳過。如果以上兩個(gè)條件都不滿足那么i就是“與7無關(guān)的數(shù)”將它的平方累加到結(jié)果中。如何拆解一個(gè)整數(shù)的每一位一個(gè)經(jīng)典的方法是使用while循環(huán)和取模運(yùn)算。#include stdio.h int main() { int n; int sum 0; // 用于累加平方和 scanf(%d, n); // 讀入n for (int i 1; i n; i) { // 條件1判斷是否能被7整除 if (i % 7 0) { continue; // 有關(guān)跳過當(dāng)前數(shù) } // 條件2判斷數(shù)位中是否包含7 int temp i; // 用一個(gè)臨時(shí)變量操作避免改變i int hasSeven 0; // 標(biāo)志位0表示不包含7 while (temp 0) { int digit temp % 10; // 取出當(dāng)前最低位 if (digit 7) { hasSeven 1; // 發(fā)現(xiàn)7設(shè)置標(biāo)志位 break; // 已經(jīng)確定有關(guān)可以提前結(jié)束循環(huán) } temp temp / 10; // 去掉最低位 } if (hasSeven 1) { continue; // 有關(guān)跳過當(dāng)前數(shù) } // 執(zhí)行到這里說明i是“與7無關(guān)的數(shù)” sum i * i; } printf(%d\n, sum); return 0; }代碼關(guān)鍵點(diǎn)解析int temp i;在數(shù)位拆解循環(huán)中我們修改了temp的值。如果直接用i會(huì)破壞外層for循環(huán)的計(jì)數(shù)器導(dǎo)致邏輯錯(cuò)誤。這是一個(gè)非常常見的初學(xué)者錯(cuò)誤。hasSeven標(biāo)志位用來記錄在拆解過程中是否遇到了數(shù)字7。使用標(biāo)志位比在循環(huán)內(nèi)部直接continue到外層更清晰避免了復(fù)雜的控制流。break;一旦發(fā)現(xiàn)某位是7立即跳出數(shù)位判斷循環(huán)因?yàn)橐呀?jīng)可以確定這個(gè)數(shù)“有關(guān)”無需檢查剩余位數(shù)。這是一個(gè)小的優(yōu)化。這個(gè)版本在 n100 時(shí)完全夠用但它揭示了我們第一個(gè)可以優(yōu)化的點(diǎn)對(duì)于每一個(gè)“可能有關(guān)”的數(shù)我們都進(jìn)行了一次完整的數(shù)位拆解循環(huán)。當(dāng)n很大時(shí)雖然本題限制n100這種開銷會(huì)累積。3. 性能優(yōu)化避免重復(fù)的數(shù)位拆解上面的基礎(chǔ)解法中while循環(huán)對(duì)于每個(gè)數(shù)i都會(huì)執(zhí)行。我們能否提前知道哪些數(shù)一定包含7對(duì)于本題n100的范圍優(yōu)化意義不大但作為一種思維訓(xùn)練我們可以考慮更高效的方法。思路預(yù)處理或更巧妙的判斷。對(duì)于兩位數(shù)我們可以直接判斷十位和個(gè)位避免循環(huán)。個(gè)位是7i % 10 7十位是7i / 10 7這樣對(duì)于n100的情況判斷數(shù)位包含7的代碼可以簡(jiǎn)化為// 條件2優(yōu)化版針對(duì)n100的情況 if (i % 10 7 || i / 10 7) { continue; }完整優(yōu)化后的代碼如下#include stdio.h int main() { int n; int sum 0; scanf(%d, n); for (int i 1; i n; i) { // 條件1整除判斷 if (i % 7 0) { continue; } // 條件2數(shù)位判斷 (優(yōu)化版僅適用于n100) if (i % 10 7 || i / 10 7) { continue; } // 與7無關(guān)的數(shù) sum i * i; } printf(%d\n, sum); return 0; }這個(gè)版本更加簡(jiǎn)潔高效。它提醒我們?cè)诿鞔_數(shù)據(jù)范圍的前提下可以用更直接的條件組合來代替通用的循環(huán)算法從而提升性能。4. 邊界情況與常見“坑點(diǎn)”即使邏輯清晰這道題仍有幾個(gè)地方容易出錯(cuò)。下面是一個(gè)“錯(cuò)誤示范”集合看看你中招了沒?？狱c(diǎn)1忽略數(shù)字0題目要求計(jì)算1到n之間的數(shù)。我們的循環(huán)從1開始這很好。但在數(shù)位拆解時(shí)如果使用while(temp 0)的循環(huán)條件對(duì)于temp0即原數(shù)i0的情況循環(huán)不會(huì)執(zhí)行。不過本題從1開始所以不會(huì)遇到0。但如果你習(xí)慣性地寫while(temp)或while(temp ! 0)并且循環(huán)從0開始就要注意0會(huì)被錯(cuò)誤地判斷為“不含7”而0能被任何非零數(shù)整除0%70所以它其實(shí)是“有關(guān)”的。好在本題規(guī)避了這個(gè)問題?？狱c(diǎn)2累加平方和時(shí)使用浮點(diǎn)數(shù)平方和可能很大嗎n最大為99所有“無關(guān)數(shù)”的平方和最大也不會(huì)超過100 * 1002 1,000,000實(shí)際上遠(yuǎn)小于此這在int類型通常32位最大值約21億的表示范圍內(nèi)綽綽有余。因此不需要使用long long或double。使用int足矣且更高效。但如果你在做類似題目時(shí)n的范圍很大比如n10000就需要考慮使用long long來防止溢出?？狱c(diǎn)3輸入格式與輸出格式這是一個(gè)OJOnline Judge題目的常見考點(diǎn)。題目通常要求嚴(yán)格遵循輸入輸出格式。比如輸入只有一行一個(gè)整數(shù)n。輸出只有一行一個(gè)整數(shù)表示平方和。 我們的代碼使用scanf(“%d”, n)和printf(“%d\n”, sum)是符合要求的。千萬不要畫蛇添足地打印提示語句如printf(“請(qǐng)輸入n:”)這會(huì)導(dǎo)致答案錯(cuò)誤?？狱c(diǎn)4循環(huán)條件錯(cuò)誤for (int i 1; i n; i)這里是i n包含了n本身。如果寫成i n就會(huì)漏掉最后一個(gè)數(shù)導(dǎo)致結(jié)果錯(cuò)誤。5. 通用解法的函數(shù)封裝為了代碼更清晰、可復(fù)用我們可以將核心判斷邏輯封裝成一個(gè)函數(shù)。這樣主程序邏輯會(huì)變得非常簡(jiǎn)潔。#include stdio.h #include stdbool.h // 使用bool類型需要此頭文件 // 函數(shù)功能判斷一個(gè)正整數(shù)是否“與7有關(guān)” // 返回值true表示有關(guān)false表示無關(guān) bool isRelatedToSeven(int num) { // 條件1能被7整除 if (num % 7 0) { return true; } // 條件2任何數(shù)位包含7 int temp num; while (temp 0) { if (temp % 10 7) { return true; } temp / 10; } // 兩個(gè)條件都不滿足則是無關(guān)數(shù) return false; } int main() { int n, sum 0; scanf(%d, n); for (int i 1; i n; i) { // 如果與7無關(guān)則累加其平方 if (!isRelatedToSeven(i)) { sum i * i; } } printf(%d\n, sum); return 0; }使用函數(shù)封裝的好處主邏輯清晰main函數(shù)一眼就能看懂遍歷判斷累加?？蓽y(cè)試性你可以單獨(dú)測(cè)試isRelatedToSeven函數(shù)輸入不同的值看返回結(jié)果是否正確。可維護(hù)性如果未來判斷規(guī)則變了比如變成“與3無關(guān)”你只需要修改這一個(gè)函數(shù)而不是在復(fù)雜的循環(huán)和條件嵌套里找代碼。6. 測(cè)試用例與結(jié)果驗(yàn)證寫完代碼必須用幾組測(cè)試數(shù)據(jù)來驗(yàn)證其正確性。這里提供幾個(gè)關(guān)鍵測(cè)試點(diǎn)測(cè)試用例1邊界最小值輸入n 1預(yù)期輸出1(因?yàn)?與7無關(guān)平方和為1) 驗(yàn)證程序應(yīng)輸出1。測(cè)試用例2包含明顯的有關(guān)數(shù)輸入n 10手動(dòng)計(jì)算有關(guān)數(shù)7無關(guān)數(shù)1,2,3,4,5,6,8,9,10平方和1491625366481100 336 預(yù)期輸出336測(cè)試用例3包含能被7整除和數(shù)位含7的數(shù)輸入n 20(我們最初的例子)有關(guān)數(shù)7,14,17無關(guān)數(shù)平方和1222324252628292102112122132152162182192202 計(jì)算過程1491625366481100121144169225256324361400 2336 預(yù)期輸出2336測(cè)試用例4最大值附近輸入n 99這個(gè)計(jì)算量稍大我們可以用程序?qū)Τ绦蚧蛘咝湃挝覀冞壿嫷恼_性。關(guān)鍵是確保程序能正常運(yùn)行并輸出一個(gè)整數(shù)。你可以將上述測(cè)試用例輸入你的程序核對(duì)輸出是否一致。這是調(diào)試和確保代碼正確性的必要步驟。7. 常見問題與排查指南在實(shí)現(xiàn)過程中你可能會(huì)遇到以下問題問題現(xiàn)象可能原因排查方式解決方案輸出結(jié)果總是0累加條件判斷邏輯反了檢查if條件是“有關(guān)”時(shí)累加還是“無關(guān)”時(shí)累加確保在“無關(guān)” (!isRelatedToSeven(i)) 時(shí)執(zhí)行sum i*i。結(jié)果比預(yù)期小漏掉了一些“無關(guān)數(shù)”1. 檢查循環(huán)條件是否為i n。2. 檢查數(shù)位判斷邏輯是否錯(cuò)誤地排除了如70、71等數(shù)(70能被7整除本應(yīng)排除)1. 確認(rèn)循環(huán)包含n。2. 用調(diào)試器或打印語句輸出每個(gè)被判斷為“有關(guān)”的數(shù)看是否正確。結(jié)果比預(yù)期大納入了一些“有關(guān)數(shù)”數(shù)位判斷可能只檢查了個(gè)位沒有檢查十位及以上。確保數(shù)位判斷循環(huán) (while) 能處理任意位數(shù)的數(shù)字在本題范圍內(nèi)。對(duì)于兩位數(shù)必須檢查十位和個(gè)位。程序運(yùn)行無輸出或異常結(jié)束輸入處理錯(cuò)誤或變量未初始化1. 檢查scanf是否正確讀取了n。2. 檢查sum變量是否初始化為0。1. 確保輸入格式匹配。2. 在聲明sum時(shí)立即初始化為0int sum 0;。對(duì)大一點(diǎn)的n如1000結(jié)果錯(cuò)誤平方和溢出計(jì)算i*i時(shí)如果i很大i*i可能超出int范圍導(dǎo)致溢出后累加出現(xiàn)負(fù)數(shù)或奇怪值。根據(jù)題目數(shù)據(jù)范圍選擇合適的數(shù)據(jù)類型。如果n可能很大將sum和i*i的計(jì)算改為long long類型。8. 最佳實(shí)踐與擴(kuò)展思考通過這道題我們可以總結(jié)出一些通用的編程最佳實(shí)踐先理清邏輯再寫代碼動(dòng)手前先用紙筆或注釋把“與7無關(guān)”的兩個(gè)條件及其關(guān)系“或”關(guān)系寫清楚。避免邊寫邊想邏輯混亂。注意數(shù)據(jù)范圍本題n100是一個(gè)很強(qiáng)的約束它允許我們使用簡(jiǎn)化的數(shù)位判斷。在更通用的場(chǎng)景下while循環(huán)拆解數(shù)位是更可靠的方法。善用函數(shù)分解即使題目簡(jiǎn)單將獨(dú)立的功能如判斷是否有關(guān)封裝成函數(shù)也能極大提高代碼的可讀性和可維護(hù)性。這是培養(yǎng)良好工程習(xí)慣的起點(diǎn)。重視測(cè)試用邊界值1 7 10 20 99、特殊值包含7的數(shù)、7的倍數(shù)來驗(yàn)證你的程序。自己算幾個(gè)小例子比盲目相信代碼更可靠。思考優(yōu)化在保證正確性的前提下思考是否有更高效的實(shí)現(xiàn)。例如本題中如果n非常大比如10^7我們還能怎么優(yōu)化也許可以提前計(jì)算出一個(gè)范圍內(nèi)所有7的倍數(shù)和包含7的數(shù)字用集合HashSet存儲(chǔ)然后遍歷時(shí)查表。這體現(xiàn)了從“模擬”到“算法”思維的跨越。擴(kuò)展思考如果題目變一下呢變體1求“與7無關(guān)的數(shù)”的個(gè)數(shù)而不是平方和。更簡(jiǎn)單累加器count即可變體2求“與7無關(guān)的數(shù)”的立方和。注意溢出風(fēng)險(xiǎn)可能要用long long變體3判斷條件改為“與數(shù)字k無關(guān)”。將代碼中的7改為變量k即可提升代碼通用性變體4n的范圍變得很大10^9求平方和對(duì)某個(gè)大數(shù)取模的結(jié)果。這需要數(shù)位DP等更高級(jí)的算法是這道題目的“進(jìn)階版”“與7無關(guān)的數(shù)”作為一個(gè)經(jīng)典的入門算法題其價(jià)值不在于題目本身有多難而在于它完整地串聯(lián)了循環(huán)、條件判斷、整數(shù)運(yùn)算、函數(shù)封裝和基礎(chǔ)測(cè)試這些編程核心要素。理解它并能有條理地實(shí)現(xiàn)和優(yōu)化它說明你已經(jīng)掌握了結(jié)構(gòu)化編程的基本功。下次再遇到類似的“過濾”或“篩選”類問題你就能從容地將這道題的解決思路遷移過去。