資訊專欄INFORMATION COLUMN
摘要：示例輸入輸出解釋答案應(yīng)為除去外，在區(qū)間內(nèi)的所有數(shù)字。即這個(gè)數(shù)最多位。解答這一題就是利用回溯法求組合數(shù)，從這個(gè)集合中求。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定一個(gè)非負(fù)整數(shù) n，計(jì)算各位數(shù)字都不同的數(shù)字 x 的個(gè)數(shù)，其中 0 ≤ x < 10的n次方 。
示例:
輸入: 2
輸出: 91
解釋: 答案應(yīng)為除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 區(qū)間內(nèi)的所有數(shù)字。即這個(gè)數(shù)最多n位。
解答：
這一題就是利用回溯法求組合數(shù)，從(0,1,2,3,4,5,6,7,8,9)這個(gè)集合中求c(k,1)+...+c(k,k),k>=1,k<=n。求組合的代碼很好寫，需要注意的是第1為不能為0,所以不能從第1位開始調(diào)用，而是要從第2位開始（下面的backtrack(1,k,flag);這里的1就是第二位，因?yàn)閺?開始算位數(shù)）。
java ac代碼:
class Solution {
int ans;
public int countNumbersWithUniqueDigits(int n) {
boolean[]flag = new boolean[10];
for(int k = 1;k <= n;k++)
for(int j = 1; j <= 9;j++){
flag[j] = true;
backtrack(1,k,flag);
flag[j] = false;
}
return ans+1;
}
void backtrack(int i,int n,boolean[]flag)
{
if(i == n)
{
ans++;
return;
}
for(int j = 0;j <= 9;j++)
if(!flag[j])
{
flag[j] = true;
backtrack(i+1,n,flag);
flag[j] = false;
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/73393.html
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個(gè)圖，寫出一個(gè)函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對于一個(gè)具有樹特征的無向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
摘要：此模型的特殊性相鄰的三個(gè)值可以得到一個(gè)爆破值，相鄰的兩個(gè)值相當(dāng)于沒有值，賦予類比二分法求極值。通過二分確定具體的位置。此處二分法到極值是三個(gè)連續(xù)的數(shù)，從相鄰三個(gè)數(shù)的固定值，逐次放寬范圍，確定越來越寬的爆破值。 此題的總結(jié)： 求解 最大爆破值， 是一個(gè) 倒序 二分法問題，最終的原子結(jié)構(gòu)是連續(xù)的三個(gè)數(shù)。連續(xù)的三個(gè)數(shù)，可以 往上遞推 間隔一個(gè)數(shù)的三個(gè)數(shù)，間隔n個(gè)數(shù)的三個(gè)數(shù)特點(diǎn)在于：每一...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個(gè)人主頁：應(yīng)無所住而生...
摘要：對于每個(gè)氣球，提供的輸入是水平方向上，氣球直徑的開始和結(jié)束坐標(biāo)?？梢陨涑龅墓臄?shù)量沒有限制。弓箭一旦被射出之后，可以無限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。解答這是一道區(qū)間覆蓋問題，不太好說清楚，利用模板即可。 題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對于每個(gè)氣球，提供的輸入是水平方...
閱讀 969·2021-10-13 09:39
閱讀 3641·2021-09-26 10:16
閱讀 2968·2019-08-30 15:54
閱讀 1116·2019-08-30 14:22
閱讀 2953·2019-08-29 15:39
閱讀 3357·2019-08-27 10:52
閱讀 865·2019-08-26 13:59
閱讀 1842·2019-08-26 12:20
