【剑指Offer】俯视50题之31 - 40题
面試題31連續(xù)子數(shù)組的最大和?
面試題32從1到n整數(shù)中1出現(xiàn)的次數(shù)?
面試題33把數(shù)組排成最小的數(shù)?
面試題34丑數(shù)?
面試題35第一個(gè)僅僅出現(xiàn)一次的字符?
面試題36數(shù)組中的逆序?qū)?/span>
面試題37兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)?
面試題38數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)?
面試題39二叉樹的深度?面試題40數(shù)組中僅僅出現(xiàn)一次的數(shù)字?
/*******************************************************/
面試題31連續(xù)子數(shù)組的最大和?，輸入一個(gè)數(shù)組。數(shù)組里面有正數(shù)，也有負(fù)數(shù)。
求連續(xù)數(shù)的最大值
實(shí)現(xiàn)例如以下：
int MaxSum(int num[], int length) {int CurrentSum = 0;int iResult = 0x80000000;if (num == NULL || length < 0){return 0;/* invalid */}for (int i = 0; i < length; i++){if (CurrentSum <= 0){CurrentSum = num[i];}else{CurrentSum += num[i];}if (CurrentSum > iResult)iResult = CurrentSum;}return iResult; }面試題32從1到n整數(shù)中1出現(xiàn)的次數(shù)?，輸入一個(gè)N，求1到N全部的整數(shù)中1出現(xiàn)的次數(shù)
實(shí)現(xiàn)例如以下：
#include <iostream>int CountNum(int n) {int iCurrentNum = 0;/* 當(dāng)前位的數(shù) */int iNTemp = n;int iResult = 0;int iBase = 1; /* 個(gè)位 */int iRemain = 0;if (n <= 0){return 0;}while (iNTemp > 0){iCurrentNum = iNTemp % 10;iNTemp = iNTemp/10;if (iCurrentNum > 1){iResult+= (iNTemp + 1)*iBase;}else if (iCurrentNum == 1){iResult+= (iNTemp)*iBase + iRemain + 1;}else if (iCurrentNum == 0){iResult+= (iNTemp)*iBase;}iRemain += iCurrentNum*iBase; /* 先計(jì)算剩余數(shù)大小*/iBase = iBase*10; /**然后計(jì)算下次base位*/ }return iResult; }int main() {printf("%d\n",CountNum(11)); }
面試題33把數(shù)組排成最小的數(shù)?
實(shí)現(xiàn)例如以下：
#include <iostream> #define MAX_NUM_LENGTH 10int compare(const void *str1, const void *str2) {char str1Temp[MAX_NUM_LENGTH*2 +1];char str2Temp[MAX_NUM_LENGTH*2 +1];strcpy(str1Temp, (const char*)str1);strcat(str1Temp, (const char*)str2);strcpy(str2Temp, (const char*)str2);strcat(str2Temp, (const char*)str1);return strcmp(str1Temp,str2Temp);} void GetMinNum(int num[], int length) {char **numStr = (char **)malloc(length + 1);for (int i = 0; i < length; i++){numStr[i] = (char *)malloc(MAX_NUM_LENGTH +1);sprintf(numStr[i],"%d",num[i]);}qsort(numStr,length,sizeof(char *),compare);for (int i = 0; i < length; i++){printf("%s",numStr[i]);}/* 釋放內(nèi)存 */for (int i = 0; i < length; i++){free(numStr[i]);}free(numStr);}int main() {int num[] = {1,234,341};GetMinNum(num, 3); }
面試題34丑數(shù)?
實(shí)現(xiàn)例如以下：
#include <iostream> #define MAX_NUM_LENGTH 10int min(int a, int b, int c) {int min = (a>b)?b:a;min = (min > c)?
c:min; return min; } /* 僅僅能被2、3、5整除的 */ int GetUglyNum(int n) { /* 創(chuàng)建一個(gè)n個(gè)元素的數(shù)組 */ int UglyNum[n]; int p2 = 0; int p3 = 0; int p5 = 0; int NextIndex = 1; UglyNum[0] = 1; while(NextIndex < n) { UglyNum[NextIndex] = min(UglyNum[p2]*2, UglyNum[p3]*3 ,UglyNum[p5]*5); while(UglyNum[p2]*2 <= UglyNum[NextIndex]) { p2++; } while(UglyNum[p3]*3 <= UglyNum[NextIndex]) { p3++; } while(UglyNum[p5]*5 <= UglyNum[NextIndex]) { p5++; } NextIndex++; } return UglyNum[NextIndex - 1]; } int main() { printf("%d\n",GetUglyNum(3)); }
面試題35第一個(gè)僅僅出現(xiàn)一次的字符?
實(shí)現(xiàn)例如以下：
#include <iostream> #define VOS_OK 0 #define VOS_ERR 1/* 僅僅能被2、3、5整除的 */ int GetFirstChar(char *str, char *result) {unsigned int hashNum[256] = {0};char *p;if (str == NULL){return VOS_ERR;}p = str;while(*p != '\0'){hashNum[*p]++;p++;}p = str;while(*p!= '\0'){if (hashNum[*p] == 1){*result = *p;return VOS_OK;}p++;}return VOS_ERR;}int main() {char iChar;if (VOS_OK == GetFirstChar("aabcddb", &iChar)){printf("%c\n",iChar);}else{printf("Error!"); } }
面試題36數(shù)組中的逆序?qū)?/span>
實(shí)現(xiàn)例如以下：
/* 求數(shù)組中的逆序?qū)?*/ #include <iostream> #define VOS_OK 0 #define VOS_ERR 1 int Merge(int *numA, int begin,int mid, int end) {int startA = begin;int startB = mid + 1;int *numB = (int *)malloc(sizeof(int)*(end + 1));int currentIndex = 0;long long result = 0;if (numA == NULL || begin > mid || mid > end)/* 其余異常函數(shù)調(diào)用處保證 */{return 0;}while (startA <=mid && startB <= end){if (numA[startA] <= numA[startB]){numB[currentIndex] = numA[startA++];}else{numB[currentIndex] = numA[startB++];/* 前面的大于后面的，則前數(shù)組之后的元素也大于該元素 */result += mid - startA + 1;}currentIndex++;}while (startA <= mid){numB[currentIndex++] = numA[startA++];}while (startB <= end){numB[currentIndex++] = numA[startB++];}for (int i = begin; i <= end; i++){numA[i] = numB[i];}free(numB);return result;}int MergeSort(int *num, int start, int end) {int result = 0;int mid;if (num == NULL || start >= end) /* 注意start == end 的時(shí)候*/{return 0; }mid = (start + end)>>1;result = MergeSort(num, start, mid) + MergeSort(num, mid +1, end);result += Merge(num,start,mid,end);return result;}int main() {int num[]={2,1,3,5,6};printf("%d\n",MergeSort(num, 0, 4)); }
面試題37兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)?
實(shí)現(xiàn)例如以下：
? 1）暴力法
? ? ? ? ?每次遍歷鏈表A,然后將鏈表A中當(dāng)前結(jié)點(diǎn)在鏈表B中查找。假設(shè)找到則停止查找，返回。
? 2）空間換取時(shí)間
? ? ? ?將兩個(gè)鏈表都入棧，然后從最后一個(gè)結(jié)點(diǎn)開始比較。直到不相等為止。
? 3）同一時(shí)候向后查找
?? 先遍歷鏈表A得長(zhǎng)度lengthA。再遍歷鏈表B得長(zhǎng)度lengthB
?? 假如A比B長(zhǎng)n。則A先走n步，假如B比A長(zhǎng)n，則B先走n步。
?? 然后同一時(shí)候向后走，直到第一個(gè)相等的結(jié)點(diǎn)
面試題38數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)?
有兩種思路：利用二分查找法，找到該數(shù)中間出現(xiàn)的位置，然后分別向前后遍歷同樣數(shù)，可得到該數(shù)出現(xiàn)的次數(shù)
? ? ?利用二分查找法，找打該數(shù)最左邊及最右邊出現(xiàn)的位置。然后就能夠求得該數(shù)出現(xiàn)的次數(shù)
左右查詢實(shí)現(xiàn)例如以下：
#include <iostream> int MaxSum(int num[], int length, int value) {int iResult = 0;int i = 0;int j = length - 1;int mid;int k;while(i <= j ){mid = (i + j)>>1;if (num[mid] > value){j= mid - 1;}else if (num[mid] < value){i = mid + 1;}else{/* 向左查詢*/k = mid-1;while (k >= i &&(num[k] == value)){k--;iResult++;}/* 向右查詢*/k = mid+1;while (k <= j &&(num[k] == value)){ k++;iResult++;}printf("================");return iResult + 1;}}return iResult; }int main() {int num[]={2,2,2,2,5,5,6,6};printf("%d\n",MaxSum(num, 8, 2) );getchar(); }
第二種實(shí)現(xiàn)方法：
#include <iostream> int GetFirstK(int num[], int length, int value) {int mid;int i = 0;int j = length - 1;if (num == NULL){return 0;}while (i <= j){mid = (i + j)>>1;if (num[mid] > value){j = mid - 1;}else if (num[mid] < value){i = mid + 1;}else{if (mid -1 >= 0 && (num[mid - 1] == value)){j = mid - 1;}else{return mid;}}}return 0; }int GetLastK(int num[], int length, int value) {int mid;int i = 0;int j = length - 1;if (num == NULL){return 0;}while (i <= j){mid = (i + j)>>1;if (num[mid] > value){j = mid - 1;}else if (num[mid] < value){i = mid + 1;}else{if (mid + 1 <= j && (num[mid + 1] == value)){i = mid + 1;}else{return mid;}}}return 0; }int main() {int num[]={2,2,2,2,5,5,6,6};printf("%d\n",GetLastK(num, 8, 2) - GetFirstK(num, 8, 2) + 1);getchar(); }
面試題39二叉樹的深度?
實(shí)現(xiàn)例如以下：
int DepthTree(BinaryNode *root) {int leftDepth = 0;int rightDepth = 0;if (root == NULL){return 0;}leftDepth = DepthTree(root->lchild);rightDepth = DepthTree(root->rchild);retrun (leftDepth > rightDepth)? (leftDepth + 1):(rightDepth + 1); }
擴(kuò)展題目：推斷一個(gè)樹是否是平衡二叉樹
實(shí)現(xiàn)例如以下：
bool IsBlanceTree(BinaryNode *root, int *depth) {int leftDepth = 0;int rightDepth = 0;int diff;if (root == NULL){return true;}leftDepth = DepthTree(root->lchild);rightDepth = DepthTree(root->rchild);if (IsBlanceTree(root->lchild, &leftDepth)&&IsBlanceTree(root->rchild, &rightDepth)){diff = leftDepth - rightDepth;if (diff < 1 && diff > -1){*depth = (leftDepth > rightDepth)? (leftDepth + 1):(rightDepth + 1);return true;}}retrun false; }
面試題40數(shù)組中僅僅出現(xiàn)一次的數(shù)字?：給一個(gè)數(shù)組，數(shù)組中有兩個(gè)數(shù)僅僅出現(xiàn)一次。其余數(shù)出現(xiàn)兩次，求這兩個(gè)數(shù)
思路：將數(shù)組分成兩組，分別異或去重。怎樣分組呢？分組依據(jù)異或之后。最后一位二進(jìn)制值為1的位分組。對(duì)數(shù)組一進(jìn)行異或最后得一個(gè)數(shù)。對(duì)數(shù)組二異或。最后得還有一個(gè)數(shù)。
則最后得到的兩個(gè)數(shù)是所求的數(shù)。
實(shí)現(xiàn)例如以下：
int FindFirstBitIsOne(int resultOR) {for (int i = 0; i < 32; i++){if (resultOR & (1 << i)){return i;}}return 0;}int IsBitOne(int data, int indexOfOne) {return data & (1<<indexOfOne);} void FindNumsAppearOnce(int data[],int length,int *num1,int num2) {if (data == NULL || length < 2){return;}int resultOR = 0;for (int i = 0; i < length; i++){resultOR ^=data[i];}int indexOfOne = FindFirstBitIsOne(resultOR);for (int j = 0; j < length; j++){if (IsBitOne(data[j], indexOfOne)){*num1 ^=data[j];}else{*num2^=data[j];}}}
posted on 2017-05-24 10:29 mthoutai 閱讀(...) 評(píng)論(...) 編輯 收藏
轉(zhuǎn)載于:https://www.cnblogs.com/mthoutai/p/6897666.html
總結(jié)
以上是生活随笔為你收集整理的【剑指Offer】俯视50题之31 - 40题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： bootstrap table教程--使
- 下一篇： js模块化历程