【Acwing算法題】|動態(tài)規(guī)劃-數(shù)位統(tǒng)計dp-計數(shù)問題-創(chuàng)新互聯(lián)

題目:

338. 計數(shù)問題 - AcWing題庫https://www.acwing.com/problem/content/340/

創(chuàng)新互聯(lián)建站2013年至今，先為新密等服務(wù)建站，新密等地企業(yè)，進行企業(yè)商務(wù)咨詢服務(wù)。為新密企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。思路分析:

思路是來自acwing y總和Alicia編程果果的代碼:

AcWing 338. 計數(shù)問題---超短寫法 - AcWinghttps://www.acwing.com/solution/content/7128/

根據(jù)他們的代碼思路我整理了以下的內(nèi)容:

題目要求求數(shù)字i在[1,n]之間的整數(shù)中出現(xiàn)的次數(shù).

可以枚舉數(shù)字 n 的每一位, 當(dāng)數(shù)字i確定在這一位出現(xiàn)的時候, 計算在 [1,n] 之間的所有整數(shù)中有多少種可能性并累加.

因此當(dāng)數(shù)字 n 的每一位都枚舉過后, 代表數(shù)字 i 出現(xiàn)在數(shù)字n的每一位時, 在 [1,n] 范圍內(nèi)的整數(shù)的所有可能性都累加上了.

比如數(shù)字 n 是 abcdefg, 固定數(shù)字 i 出現(xiàn)在 d 的位置, 那么所有可能性就是左側(cè)可能性 * 右側(cè)可能性:?

1<= xxx i?yyy<= abc d?efg

由題意可知, xxx<= abc, 所以分成以下兩個情況討論:?

(1) xxx = 0 ~ abc -1, yyy = 0 ~ 999 隨便取, 可能性 res = abc * 1000, 即左邊* 10的(d的位數(shù))次冪

(2) xxx = abc, 此時 d >= i, 分情況討論:

??? ?如果d >i, yyy = 0 ~ 999, 隨便取, 可能性 res = 1000, 即 10的(d的位數(shù))次冪

??? ?如果d = i, yyy = 0 ~ efg, ?可能性 res = efg + 1, 即右邊的數(shù)字 + 1

代碼:

代碼也是根據(jù)果果的代碼, 添加了注釋來幫助復(fù)習(xí):

# include# includeusing namespace std;

int dgt(int n) // 計算整數(shù)n有多少位
{
    int res = 0;//存儲位數(shù)
    while (n) ++ res, n /= 10;//只要不為0 就除10,結(jié)果保留的是整數(shù). 最后一次/10是0,跳出循環(huán)
    return res;//返回整數(shù)n的位數(shù)
}



int cnt(int n, int i) // 計算從1到n的整數(shù)中數(shù)字i出現(xiàn)多少次
{
    int res = 0, d = dgt(n);//res 存儲數(shù)字i出現(xiàn)的次數(shù), d是整數(shù)n的位數(shù)
    for (int j = 1; j<= d; ++ j) // 枚舉數(shù)字n的每一位, 從右到左, 計算數(shù)字i出現(xiàn)多少次
    {
        // l和r是數(shù)字n第j位左邊和右邊的整數(shù) (abc和efg); dj是整數(shù)n第j位的數(shù)字
        int p = pow(10, j - 1), //pow求x的y次冪 用來計算l和r 或者自己寫一個power10函數(shù)
        l = n / p / 10, r = n % p,
        dj = n / p % 10;//取余數(shù) 就是j位的數(shù)字
        // 當(dāng)?shù)趈位左邊的整數(shù)小于l (xxx = 000 ~ abc - 1), 此時 res = 左側(cè)可能性 * 右側(cè)隨便取
        if (i) res += l * p;//如果i不為0,左邊的可能數(shù)量(l)*右邊可能性數(shù)量(全部), 如果j是4 p就是1000, l*1000
        if (!i && l) res += (l - 1) * p; //如果i = 0, 左邊高位不能全為0, (視頻中xxx = 001 ~ abc - 1)
        // 當(dāng)?shù)趈位左邊的整數(shù)等于l (xxx = abc)的情況, 此時 要看第j位數(shù)字的大小來計算
        if ( (dj >i) && (i || l) ) res += p;//如果第j位數(shù)字dj >i, i和l都不是0, 那么右側(cè)隨便取, 可能性就是p
        if ( (dj == i) && (i || l) ) res += r + 1;//如果dj == i, i和l都不是0, 那么能取到j(luò)位右側(cè)[0,r]之間所有整數(shù)

    }
    return res;
}

int main()
{
    int a, b;//兩個整數(shù)a 和 b
    while (cin >>a >>b , a) //不斷讀取輸入, 直到輸入的a,b是0,0就結(jié)束輸入
    {
        if (a >b) swap(a, b);//保證a

如果pow() 函數(shù)不熟悉的話, 可以按照y總解法, 自己寫一個power函數(shù), 求10 的 x次方, 調(diào)用的時候可以寫 int p = power10(j - 1):

int power10(int x) //返回10的x次方
{
    int res = 1;
    while (x--) res *= 10;
    return res;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁名稱：【Acwing算法題】|動態(tài)規(guī)劃-數(shù)位統(tǒng)計dp-計數(shù)問題-創(chuàng)新互聯(lián)
標題路徑：http://www.muchs.cn/article8/hgcop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計、手機網(wǎng)站建設(shè)、商城網(wǎng)站、云服務(wù)器、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)