算法合集之《數(shù)位計數(shù)問題解法研究》(文件)
【正文】 數(shù)字和為 S的數(shù)中，有多少個比 K小。 ? 那么，不妨轉化思路，首先固定數(shù)字和，進而簡化并解決問題。 ? 對于原問題的兩問，事實上似乎求 K在 1~N中的位置較為容易求出，因為它比較符合我們的解題思路。 例題 1： The Sum ? 數(shù)字個數(shù)為奇數(shù)的情況： (這里以[10000,56789]為例進行研究 ) ? +10+00+0 ? 1+00+01 ? +10+00+2 ? 1+00+03 ? …………… ? 5+67+89 可以看到，相鄰兩項基本都互相抵消了，只有個位相差 1 例題 1： The Sum ? 數(shù)字個數(shù)為偶數(shù)的情況： (這里以[100000,456789]為例進行研究 ) ? +10+00+00 ? +10+00+01 ? +10+00+02 ? +10+00+03 ? …………… ? +45+67+89 可以看到，每一列的符號都是固定的，因此只需要對每一列分別進行求和即可 例題 1總結 原區(qū)間詢問 同位數(shù)區(qū)間詢問 奇數(shù)位數(shù)區(qū)間詢問 偶數(shù)位
教學課件相關推薦
鄂ICP備17016276號-1