題目描述

數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。例如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過(guò)數(shù)組長(zhǎng)度的一半，因此輸出2。

解析：保存數(shù)組首個(gè)數(shù)字，計(jì)數(shù)值置一，然后遍歷整個(gè)數(shù)組。遇到相同的數(shù)組，計(jì)數(shù)值加一，遇到不同的數(shù)字，計(jì)數(shù)值減一，當(dāng)計(jì)數(shù)值減到零時(shí)，用當(dāng)前數(shù)組數(shù)字替換保存的數(shù)字，再繼續(xù)進(jìn)行比較，以此類推，比較直到數(shù)組尾。因?yàn)橹貜?fù)出現(xiàn)的數(shù)字次數(shù)超過(guò)數(shù)組長(zhǎng)度一半，因此結(jié)果保存的數(shù)字即為所求數(shù)組數(shù)字

class Solution { public:int MoreThanHalfNum_Solution(vector<int> numbers) {if(isValidArray(numbers))return 0;int num;//保存數(shù)int cnt;//計(jì)次數(shù)int length=numbers.size();num=numbers[0];cnt=1;for(int i=1;i<length;i++){if(num==numbers[i])cnt++;else{cnt--;if(cnt==0){num=numbers[i];cnt=1;}}}if(isHalfArray(numbers,num))return num;elsereturn 0;}bool isValidArray(vector<int> numbers){if(numbers.size()==0)return true;elsereturn false;}bool isHalfArray(vector<int> numbers,int num){int length=numbers.size();int cnt=0;for(int i=0;i<length;i++){if(num==numbers[i])cnt++;}if(cnt >= length/2)return true;elsereturn false;} };
題目描述

輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4,。

解析：以最小堆的方式調(diào)整數(shù)組排序，此時(shí)，樹(shù)根節(jié)點(diǎn)即為最小值，每求出一個(gè)最小值，下次進(jìn)行排序時(shí)去掉樹(shù)根節(jié)點(diǎn)進(jìn)行排序，以此類推，依次求出每一次的最小值

class Solution { public:vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {vector<int> res;if(k > input.size()) return res;for(int i = 0; i < k; i++){heapSort(input,i,input.size());res.push_back(input[i]);}return res;}void heapSort(vector<int> &input, int root, int end){//堆排序 for(int j = end - 1; j > root; j--){int parent = (j - 1 - root) / 2 + root;//parent=（j-1）/2if(input[parent] > input[j]){//交換input[parent] += input[j];input[j] = input[parent] - input[j];input[parent] -= input[j];}}} };題目描述

HZ偶爾會(huì)拿些專業(yè)問(wèn)題來(lái)忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)。今天測(cè)試組開(kāi)完會(huì)后,他又發(fā)話了:在古老的一維模式識(shí)別中,常常需要計(jì)算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時(shí)候,問(wèn)題很好解決。但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個(gè)負(fù)數(shù),并期望旁邊的正數(shù)會(huì)彌補(bǔ)它呢？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個(gè)開(kāi)始,到第3個(gè)為止)。你會(huì)不會(huì)被他忽悠住？
解析：累加：若累加和小于當(dāng)前值，說(shuō)明應(yīng)從當(dāng)前值開(kāi)始累加；每次累加時(shí)比較替換最大累加值 class Solution { public:int FindGreatestSumOfSubArray(vector<int> array) {int length=array.size();if(length > 0){int sum=array[0];int max=array[0];for(int i=1;i<length;i++){sum+=array[i];if(sum<array[i])sum=array[i];if(max<sum)max=sum;}return max;}return 0;} };
題目描述

求出1~13的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6次,但是對(duì)于后面問(wèn)題他就沒(méi)轍了。ACMer希望你們幫幫他,并把問(wèn)題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)。

解析：

方法一：末尾為1時(shí)對(duì)10取余等于1，因此，對(duì)每個(gè)數(shù)依次取余并除十再取余，直到為零。累加得結(jié)果

方法二：

同理分析4位數(shù)，5位數(shù)。。。。。
設(shè)N = abcde ,其中abcde分別為十進(jìn)制中各位上的數(shù)字。
如果要計(jì)算百位上1出現(xiàn)的次數(shù)，它要受到3方面的影響：百位上的數(shù)字，百位一下（低位）上的數(shù)字，百位一上（高位）上的數(shù)字。
如果百位上數(shù)字為0，百位上可能出現(xiàn)1的次數(shù)由更高位決定。比如：12013，則可以知道百位出現(xiàn)1的情況可能是：100~199，1100~1199,2100~2199，，.........，11100~11199，一共1200個(gè)。可以看出是由更高位數(shù)字（12）決定，并且等于更高位數(shù)字（12）乘以 當(dāng)前位數(shù)（100）。
如果百位上數(shù)字為1，百位上可能出現(xiàn)1的次數(shù)不僅受更高位影響還受低位影響。比如：12113，則可以知道百位受高位影響出現(xiàn)的情況是：100~199，1100~1199,2100~2199，，.........，11100~11199，一共1200個(gè)。和上面情況一樣，并且等于更高位數(shù)字（12）乘以 當(dāng)前位數(shù)（100）。但同時(shí)它還受低位影響，百位出現(xiàn)1的情況是：12100~12113,一共114個(gè)，等于低位數(shù)字（113）+1。
如果百位上數(shù)字大于1（2~9），則百位上出現(xiàn)1的情況僅由更高位決定，比如12213，則百位出現(xiàn)1的情況是：100~199,1100~1199，2100~2199，...........，11100~11199,12100~12199,一共有1300個(gè)，并且等于更高位數(shù)字+1（12+1）乘以當(dāng)前位數(shù)（100）。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??綜合以上三種情況，當(dāng)百位對(duì)應(yīng)0或>=2時(shí)，有(a+8)/10次包含所有100個(gè)點(diǎn)，還有當(dāng)百位為1(a%10==1)，需要增加局部點(diǎn)b+1
?之所以補(bǔ)8，是因?yàn)楫?dāng)百位為0，則a/10==(a+8)/10，當(dāng)百位>=2，補(bǔ)8會(huì)產(chǎn)生進(jìn)位位，效果等同于(a/10+1)

class Solution { public:int NumberOf1Between1AndN_Solution(int n){int sum=0;for(int i=1;i<=n;i++)sum+=count(i);return sum;}int count(int n){int cnt=0;while(n){if(n%10==1)cnt++;n=n/10;}return cnt;} };
class Solution { public:int NumberOf1Between1AndN_Solution(int n){int cnt = 0;int i = 1;for(i = 1;i <= n;i = i*10){int a = n / i , b = n % i ;cnt = cnt + ( a + 8 ) / 10 * i + ( a % 10 == 1 ) * ( b + 1 ) ;}return cnt;} };
題目描述

輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3，32，321}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為321323。

解析：把數(shù)組每個(gè)數(shù)字轉(zhuǎn)換為字符串，比較后重新排序

class Solution { public:static bool compare( const string &st1,const string &st2){string s1 = st1+st2;string s2 = st2+st1;return s1<s2;}string PrintMinNumber(vector<int> numbers) {string result;if(numbers.size()<=0){return result;}vector<string> strNum;for(int i=0;i<numbers.size();i++ ){stringstream ss;ss<<numbers[i];string s = ss.str();strNum.push_back(s);}sort(strNum.begin(),strNum.end(),compare);for(int i=0;i<strNum.size();i++){result.append(strNum[i]);}return result;} };

總結(jié)

以上是生活随笔為你收集整理的剑指offer 算法 （时间效率）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。