整數(shù)中1出現(xiàn)的次數(shù)
第一個(gè)只出現(xiàn)一次的字符
把數(shù)組排成最小的數(shù)
整數(shù)中1出現(xiàn)的次數(shù)
題目描述：求出113的整數(shù)中1出現(xiàn)的次數(shù),并算出1001300的整數(shù)中1出現(xiàn)的次數(shù)？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6次,但是對(duì)于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)（從1 到 n 中1出現(xiàn)的次數(shù)）。
我的做法：
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
//我的會(huì)被鄙視的暴力破解法
int count=0;
for(int i=1;i<=n;i++)
{
int temp=i;
while(temp>0)
{
if(temp%10==1)
count++;
temp=temp/10;
}
}
return count;
}
};
smart方法：
個(gè)位
我們知道在個(gè)位數(shù)上，1會(huì)每隔10出現(xiàn)一次，例如1、11、21等等，我們發(fā)現(xiàn)以10為一個(gè)階梯的話，每一個(gè)完整的階梯里面都有一個(gè)1，例如數(shù)字22，按照10為間隔來分三個(gè)階梯，在完整階梯0-9，10-19之中都有一個(gè)1，但是19之后有一個(gè)不完整的階梯，我們需要去判斷這個(gè)階梯中會(huì)不會(huì)出現(xiàn)1，易推斷知，如果最后這個(gè)露出來的部分小于1，則不可能出現(xiàn)1（這個(gè)歸納換做其它數(shù)字也成立）。
我們可以歸納個(gè)位上1出現(xiàn)的個(gè)數(shù)為：
n/10 * 1+(n%10!=0 ? 1 : 0)
十位
現(xiàn)在說十位數(shù)，十位數(shù)上出現(xiàn)1的情況應(yīng)該是10-19，依然沿用分析個(gè)位數(shù)時(shí)候的階梯理論，我們知道10-19這組數(shù)，每隔100出現(xiàn)一次，這次我們的階梯是100，例如數(shù)字317，分析有階梯0-99，100-199，200-299三段完整階梯，每一段階梯里面都會(huì)出現(xiàn)10次1（從10-19），最后分析露出來的那段不完整的階梯。我們考慮如果露出來的數(shù)大于19，那么直接算10個(gè)1就行了，因?yàn)?0-19肯定會(huì)出現(xiàn)；如果小于10，那么肯定不會(huì)出現(xiàn)十位數(shù)的1；如果在10-19之間的，我們計(jì)算結(jié)果應(yīng)該是k - 10 + 1。例如我們分析300-317，17個(gè)數(shù)字，1出現(xiàn)的個(gè)數(shù)應(yīng)該是17-10+1=8個(gè)。
那么現(xiàn)在可以歸納：十位上1出現(xiàn)的個(gè)數(shù)為：
- 設(shè)k = n % 100，即為不完整階梯段的數(shù)字
- 歸納式為：(n / 100) * 10 + (if(k > 19) 10 else if(k < 10) 0 else k - 10 + 1)
百位
現(xiàn)在說百位1，我們知道在百位，100-199都會(huì)出現(xiàn)百位1，一共出現(xiàn)100次，階梯間隔為1000，100-199這組數(shù)，每隔1000就會(huì)出現(xiàn)一次。這次假設(shè)我們的數(shù)為2139。跟上述思想一致，先算階梯數(shù) * 完整階梯中1在百位出現(xiàn)的個(gè)數(shù)，即n/1000 * 100得到前兩個(gè)階梯中1的個(gè)數(shù)，那么再算漏出來的部分139，沿用上述思想，不完整階梯數(shù)k199，得到100個(gè)百位1，100<=k<=199則得到k - 100 + 1個(gè)百位1。
那么繼續(xù)歸納百位上出現(xiàn)1的個(gè)數(shù)：
- 設(shè)k = n % 1000
- 歸納式為：(n / 1000) * 100 + (if(k >199) 100 else if(k < 100) 0 else k - 100 + 1)
后面的依次類推....
再次回顧個(gè)位
我們把個(gè)位數(shù)上算1的個(gè)數(shù)的式子也納入歸納式中
- k = n % 10
- 個(gè)位數(shù)上1的個(gè)數(shù)為：n / 10 * 1 + (if(k > 1) 1 else if(k < 1) 0 else k - 1 + 1)
完美！歸納式看起來已經(jīng)很規(guī)整了。 來一個(gè)更抽象的歸納，設(shè)i為計(jì)算1所在的位數(shù)，i=1表示計(jì)算個(gè)位數(shù)的1的個(gè)數(shù)，10表示計(jì)算十位數(shù)的1的個(gè)數(shù)等等。
- k = n % (i * 10)
- count(i) = (n / (i * 10)) * i + (if(k > i * 2 - 1) i else if(k < i) 0 else k - i + 1)
好了，這樣從10到10的n次方的歸納就完成了。
?sum1 = sum(count(i))，i = Math.pow(10, j), 0<=j<=log10(n)
但是有一個(gè)地方值得我們注意的，就是代碼的簡(jiǎn)潔性來看，有多個(gè)ifelse不太好，能不能進(jìn)一步簡(jiǎn)化呢？ 我們可以把后半段簡(jiǎn)化成這樣，我們不去計(jì)算i * 2 - 1了，我們只需保證k - i + 1在[0, i]區(qū)間內(nèi)就行了，最后后半段可以寫成這樣：min(max((n mod (i*10))?i+1,0),i)
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if(n <= 0)
return 0;
int count = 0;
for(long i = 1; i <= n; i *= 10){
long diviver = i * 10;
count += (n / diviver) * i + Math.min(Math.max(n % diviver - i + 1, 0), i);
}
return count;
}
}
第一個(gè)只出現(xiàn)一次的字符
題目描述：在一個(gè)字符串(0<=字符串長(zhǎng)度<=10000，全部由字母組成)中找到第一個(gè)只出現(xiàn)一次的字符,并返回它的位置, 如果沒有則返回 -1（需要區(qū)分大小寫）
利用map：
class Solution {
public:
int FirstNotRepeatingChar(string str) {
map<char,int> mp;
for(int i=0;i<str.length();i++)
{
mp[str[i]]++;
}
for(int i=0;i<str.length();i++)
{
if(mp[str[i]]==1)
return i;
}
return -1;
}
};
把數(shù)組排成最小的數(shù)
題目描述：輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3，32，321}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為321323。
class Solution {
public:
static bool Compare(int a,int b) //靜態(tài)成員函數(shù)sort可以直接調(diào)用
{
if(to_string(a)+to_string(b)<to_string(b)+to_string(a))
return true;
else
return false;
}
string PrintMinNumber(vector<int> numbers) {
sort(numbers.begin(),numbers.end(),Compare);
string res;
for(int i=0;i<numbers.size();i++)
{
res+=to_string(numbers[i]);
}
return res;
}
};
