劍指Offer66題C++面試題+答案總結(jié)

1、二維數(shù)組中的查找
在一個二維數(shù)組中(每個一維數(shù)組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數(shù),輸入這樣的一個二維數(shù)組和一個整數(shù),判斷數(shù)組中是否含有該整數(shù)。
/* 3 4 5 4 5 6 6 7 8 從左下角開始查找,當target比左下角數(shù)字大時,右移;小時,上移 */ class Solution { public: bool Find(int target, vector<vector<int> > array) { int rows = array.size(), cols = array[0].size(); int i = rows - 1, j = 0; while(i>=0&&j<cols){ if(array[i][j] == target) return true; else if(array[i][j] > target) i--; else j++; } return false; } };
2、替換空格
請實現(xiàn)一個函數(shù),將一個字符串中的每個空格替換成“%20”。例如,當字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
/* 從前往后替換,后面的字符要多次移動,效率低下 從后往前,先計算需要多少空間,每個字符只移動一次,效率更高 例如:a b c 從后往前,當前第i位為'c'(非空格),前有n個空格,則i+2*n位為c 當前第i位為' '(空格),前有n個空格,則i+2*n位為%,i+2*n+1位為2,i+2*n+2位為0 */ class Solution { public: void replaceSpace(char *str,int length) { int sum = 0; for(int i=0;i<length;i++){ if(str[i] == ' ') sum++; } for(int i=length-1;i>=0;i--){ if(str[i] != ' ') str[i + 2*sum] = str[i]; else{ sum--; str[i + 2*sum] = '%'; str[i + 2*sum + 1] = '2'; str[i + 2*sum + 2] = '0'; } } } };
3、從尾到頭打印鏈表
輸入一個鏈表,按鏈表值從尾到頭的順序返回一個ArrayList。
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> res; stack<int> stack; while(head){ stack.push(head->val); head = head->next; } while(!stack.empty()){ res.push_back(stack.top()); stack.pop(); } return res; } };
4、重建二叉樹
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果,請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6},則重建二叉樹并返回。
/* 前序遍歷序列{1,2,4,7,3,5,6,8} 1是根元素 中序遍歷序列{4,7,2,1,5,3,8,6} 1之前4,7,2是左子樹中序,之后5,3,8,6是右子樹中序 前序中1后的3個是左子樹前序,之后是右子樹前序 問題轉(zhuǎn)換為根元素已知,求左子樹和右子樹的重建二叉樹,進行遞歸 */ /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { return buildtree(pre,vin,0,pre.size()-1,0,vin.size()-1); } TreeNode* buildtree(vector<int> pre,vector<int> vin,int pl,int pr,int vl,int vr) { if(pl > pr || vl > vr) return NULL; TreeNode* root = new TreeNode(pre[pl]); int i; for(i=vl;i<=vr;i++){ if(vin[i] == pre[pl]) break; } int num = i - vl; //左子樹個數(shù) root->left = buildtree(pre,vin,pl+1,pl+num,vl,vl+num-1); root->right = buildtree(pre,vin,pl+num+1,pr,vl+num+1,vr); return root; } };
5、用兩個棧實現(xiàn)隊列
用兩個棧來實現(xiàn)一個隊列,完成隊列的Push和Pop操作。 隊列中的元素為int類型。
/* 用兩個棧實現(xiàn)一個隊列的功能 入隊:將元素進棧A 出隊:判斷棧B是否為空,如果為空,則將棧A中所有元素pop,并push進棧B,棧B出棧; 如果不為空,棧B直接出棧。 用兩個隊列實現(xiàn)一個棧的功能 入棧:將元素進隊列A 出棧:判斷隊列A中元素的個數(shù)是否為1,如果等于1,則出隊列,否則將隊列A中的元素依次出隊列并放入隊列B,直到隊列A中的元素留下一個,然后隊列A出隊列,再把隊列B中的元素出隊列以此放入隊列A中。 */ class Solution { public: void push(int node) { stack1.push(node); } int pop() { while(!stack1.empty()){ stack2.push(stack1.top()); stack1.pop(); } int res = stack2.top(); stack2.pop(); while(!stack2.empty()){ stack1.push(stack2.top()); stack2.pop(); } return res; } private: stack<int> stack1; stack<int> stack2; };
6、旋轉(zhuǎn)數(shù)組的最小數(shù)字
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾,我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個非減排序的數(shù)組的一個旋轉(zhuǎn),輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn),該數(shù)組的最小值為1。 NOTE:給出的所有元素都大于0,若數(shù)組大小為0,請返回0。
class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { if(rotateArray.size() == 0) return 0; int i = 0, j = rotateArray.size()-1; while(i < j){ int mid = (i + j)/2; if(rotateArray[mid] > rotateArray[j]){ i = mid + 1; //3 4 7 8 1 2 旋轉(zhuǎn)點在右,左順序 } else if(rotateArray[mid] < rotateArray[j]){ j = mid; //7 8 1 2 3 4 旋轉(zhuǎn)點在左,右順序 } else{ //1 0 1 1 1 或 1 1 1 0 1 順序部分為常數(shù) i ++; //或 j --; } } return rotateArray[i]; } };
7、斐波那契數(shù)列
大家都知道斐波那契數(shù)列,現(xiàn)在要求輸入一個整數(shù)n,請你輸出斐波那契數(shù)列的第n項(從0開始,第0項為0)。
n<=39
class Solution { public: int Fibonacci(int n) { //0 1 1 2 3 5 …,使用動態(tài)規(guī)劃 int i = 0, j = 1; while(n>0){ int tmp = j; j = i+j; i = tmp; n--; } return i; } };
8、跳臺階
一只青蛙一次可以跳上1級臺階,也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法(先后次序不同算不同的結(jié)果)。
/* 最后一步跳1,有f(n-1)種情況 最后一步跳2,有f(n-2)種情況 共f(n)=f(n-1)+f(n-2),1 1 2 3 5(斐波那契數(shù)列)使用動態(tài)規(guī)劃 */ class Solution { public: int jumpFloor(int number) { int i = 1, j = 1; while(number>0){ int tmp = j; j = i + j; i = tmp; number--; } return i; } };
9、變態(tài)跳臺階
一只青蛙一次可以跳上1級臺階,也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
//f(n) = f(1) + f(2) + f(3) +...+ f(n-1) + 1 //1 2 4 8 ... class Solution { public: int jumpFloorII(int number) { vector<int> step; while(number>0){ int sum = 0; for(int i=0;i<step.size();i++){ sum += step[i]; } step.push_back(sum+1); number--; } return step.back(); } }; /* class Solution { public: int jumpFloorII(int number) { int res = 1; for(int i=1;i<number;i++){ res += jumpFloorII(i); } return res; } }; */
10、矩形覆蓋
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形,總共有多少種方法?
/* | | | | f(n-1) | | | | — — | | f(n-2) — — | | f(n) = f(n-1) + f(n-2),1 2 3 5 8…,動態(tài)規(guī)劃 */ class Solution { public: int rectCover(int number) { if(number == 0) return 0; int i = 1, j = 1; while(number>0){ int tmp = j; j = i + j; i = tmp; number--; } return i; } };
11、二進制中1的個數(shù)
輸入一個整數(shù),輸出該數(shù)二進制表示中1的個數(shù)。其中負數(shù)用補碼表示。
/* 將n與n-1相與會把n的最右邊的1變?yōu)?,比如 1100&1011 = 1000 */ class Solution { public: int NumberOf1(int n) { int res=0; while(n!=0){ res++; n = n&(n-1); } return res; } }; /* #include <bitset> */ class Solution { public: int NumberOf1(int n) { bitset<32>a(n); //32位的2進制 return a.count(); //返回1的個數(shù) } };
12、數(shù)值的整數(shù)次方
給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。
/* 10^1101 = 10^0001*10^0100*10^1000,即base*1 * base^2 * base^4 * … 通過&1和>>1來逐位讀取1101 */ class Solution { public: double Power(double base, int exponent) { double res = 1; int e = abs(exponent); while(e!=0){ if(e&1 == 1){ res *= base; } base *= base; e = e>>1; } return exponent>0?res:1/res; } };
13、調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
輸入一個整數(shù)數(shù)組,實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序,使得所有的奇數(shù)位于數(shù)組的前半部分,所有的偶數(shù)位于數(shù)組的后半部分,并保證奇數(shù)和奇數(shù),偶數(shù)和偶數(shù)之間的相對位置不變。
/* 要想保證原有次序,則只能順次移動或相鄰交換。 1.i從左向右遍歷,找到第一個偶數(shù)。 2.j從i+1開始向后找,找到第一個奇數(shù)。 3.將[i,...,j-1]的元素整體后移一位,將找到的奇數(shù)放入i位置 */ class Solution { public: void reOrderArray(vector<int> &array) { for(int i=0;i<array.size();i++){ if(array[i]%2 == 0){ for(int j=i+1;j<array.size();j++){ if(array[j]%2 == 1){ int tmp = array[j]; for(int k=j-1;k>=i;k--){ array[k+1] = array[k]; } array[i] = tmp; break; } } } } } };
14、鏈表中倒數(shù)第k個結(jié)點
輸入一個鏈表,輸出該鏈表中倒數(shù)第k個結(jié)點。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ /* 兩指針指向頭結(jié)點, 第一個指針走(k-1)步,到k節(jié)點 兩個指針同時往后移動,當?shù)谝粋€結(jié)點到達末尾的時候,第二個結(jié)點所在位置就是倒數(shù)第k個節(jié)點 */ class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if(!pListHead || k==0) return NULL; ListNode* node1 = pListHead; ListNode* node2 = pListHead; int i = 0; while(node1){ if(i>=k){ node2 = node2 -> next; } node1 = node1 -> next; i++; } return i<k ? NULL : node2; } };
15、反轉(zhuǎn)鏈表
輸入一個鏈表,反轉(zhuǎn)鏈表后,輸出新鏈表的表頭。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ /* 1 2 3 4 5 遍歷鏈表,當前值為4時,相當于新建值為4的鏈表node,node->next = 前面鏈表反轉(zhuǎn),node即為所求 當前值為5時,相當于新建值為5的鏈表node,node->next = 上一步的值 */ class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode* res = NULL; while(pHead){ ListNode* tmp = new ListNode(pHead->val); tmp -> next = res; res = tmp; pHead = pHead -> next; } return res; } };
16、合并兩個排序的鏈表
輸入兩個單調(diào)遞增的鏈表,輸出兩個鏈表合成后的鏈表,當然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* res = new ListNode(0);//初始化,取幾不重要 ListNode* here = res; //標記位置 while(pHead1 && pHead2){ if(pHead1->val < pHead2->val){ res -> next = pHead1; pHead1 = pHead1 -> next; } else{ res -> next = pHead2; pHead2 = pHead2 -> next; } res = res -> next; } res -> next = pHead1 ? pHead1:pHead2; return here->next; } };
17、樹的子結(jié)構(gòu)
輸入兩棵二叉樹A,B,判斷B是不是A的子結(jié)構(gòu)。(ps:我們約定空樹不是任意一個樹的子結(jié)構(gòu))
/* /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if(pRoot1 && pRoot2){ return issub(pRoot1,pRoot2)|| HasSubtree(pRoot1->left,pRoot2)|| HasSubtree(pRoot1->right,pRoot2); } return false; } bool issub(TreeNode* l1, TreeNode* l2) { if(l2){ return l1&& l1->val==l2->val&& issub(l1->left,l2->left)&& issub(l1->right,l2->right); } return true; } };
18、二叉樹的鏡像
操作給定的二叉樹,將其變換為源二叉樹的鏡像。
二叉樹的鏡像定義: 源二叉樹 8 / \ 6 10 / \ / \ 5 7 9 11 鏡像二叉樹 8 / \ 10 6 / \ / \ 11 9 7 5
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: void Mirror(TreeNode *pRoot) { if(!pRoot) return; TreeNode *tmp = pRoot->left; pRoot->left = pRoot->right; pRoot->right = tmp; Mirror(pRoot->left); Mirror(pRoot->right); } };
19、順時針打印矩陣
輸入一個矩陣,按照從外向里以順時針的順序依次打印出每一個數(shù)字,例如,如果輸入如下4 X 4矩陣: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
/* m n i 1 2 3 4 5 6 j 7 8 9 */ class Solution { public: vector<int> printMatrix(vector<vector<int> > matrix) { vector<int> res; int i = 0,j = matrix.size()-1,m = 0,n = matrix[0].size()-1; while(i<=j && m<=n){ for(int k=m;k<=n;k++) res.push_back(matrix[i][k]); i++;//削首行 if(i>j) break; for(int k=i;k<=j;k++) res.push_back(matrix[k][n]); n--;//削尾列 if(m>n) break; for(int k=n;k>=m;k--) res.push_back(matrix[j][k]); j--;//削尾行 if(i>j) break; for(int k=j;k>=i;k--){ res.push_back(matrix[k][m]); } m++;//削首列 } return res; } };
20、包含min函數(shù)的棧
定義棧的數(shù)據(jù)結(jié)構(gòu),請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)(時間復雜度應為O(1))。
/* 用stack1保存數(shù)據(jù),用stack2做輔助棧保存依次入棧最小的數(shù) stack1:5, 4, 3, 8, 10, 11, 12, 1 stack2:5, 4, 3,no, no, no, no, 1 no代表此次不入棧 入棧,如果stack1的壓入比stack2壓入大,stack2不壓;小于等于,兩棧同時壓入 出棧,如果兩棧頂元素不等,stack1出,stack2不出;相等,都出 */ class Solution { public: stack<int> stack1,stack2; void push(int value) { stack1.push(value); if(stack2.empty()) stack2.push(value); else{ if(value <= stack2.top()) stack2.push(value); } } void pop() { if(stack1.top() == stack2.top()) stack2.pop(); stack1.pop(); } int top() { return stack1.top(); } int min() { return stack2.top(); } };
21、棧的壓入、彈出序列
輸入兩個整數(shù)序列,第一個序列表示棧的壓入順序,請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序,序列4,5,3,2,1是該壓棧序列對應的一個彈出序列,但4,3,5,1,2就不可能是該壓棧序列的彈出序列。(注意:這兩個序列的長度是相等的)
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> s; int k = 0,len = pushV.size(); for(int i=0;i<len;i++){ s.push(pushV[i]); while(k<len && popV[k] == s.top()){ s.pop(); k++; } } return s.empty(); } };
22、從上往下打印二叉樹
從上往下打印出二叉樹的每個節(jié)點,同層節(jié)點從左至右打印。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int> res; queue<TreeNode* > q; if(root) q.push(root); while(!q.empty()){ if(q.front()->left) q.push(q.front()->left); if(q.front()->right) q.push(q.front()->right); res.push_back(q.front()->val); q.pop(); } return res; } };
23、二叉搜索樹的后序遍歷序列
輸入一個整數(shù)數(shù)組,判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設輸入的數(shù)組的任意兩個數(shù)字都互不相同。
/* 二叉搜索樹BST 左子樹值都比root小,右子樹值都比root大。 去掉最后一個元素root,其他分成兩段: 前一段(左子樹)小于x,后一段(右子樹)大于x,且這兩段(子樹)都是BST的后序遍歷 */ class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if(sequence.size()==0) return false; return isok(sequence,0,sequence.size()-1); } bool isok(vector<int> arr,int l,int r) { if(l >= r) return true; int i=l; while(i<r && arr[i]<arr[r]) i++; //找到滿足BST的右子樹開頭 for(int j=i;j<r;j++) if(arr[j] < arr[r]) return false; //判斷剩下是否為右子樹 return isok(arr,l,i-1)&& isok(arr,i,r-1); } };
24、二叉樹中和為某一值的路徑
輸入一顆二叉樹的根節(jié)點和一個整數(shù),打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。(注意: 在返回值的list中,數(shù)組長度大的數(shù)組靠前)
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<vector<int> > res; vector<int> tmp; vector<vector<int> > FindPath(TreeNode* root,int expectNumber) { if(root) helper(root,expectNumber); return res; } void helper(TreeNode* root,int n) { tmp.push_back(root->val); if(root->val == n && !root->left && !root->right) res.push_back(tmp); else{ if(root->left) helper(root->left,n-root->val); if(root->right) helper(root->right,n-root->val); } tmp.pop_back(); } };
25、復雜鏈表的復制
輸入一個復雜鏈表(每個節(jié)點中有節(jié)點值,以及兩個指針,一個指向下一個節(jié)點,另一個特殊指針指向任意一個節(jié)點),返回結(jié)果為復制后復雜鏈表的head。(注意,輸出結(jié)果中請不要返回參數(shù)中的節(jié)點引用,否則判題程序會直接返回空)
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ /* 復制節(jié)點,如:復制節(jié)點A得到A1,將A1插入節(jié)點A后面 復制random,遍歷鏈表,A1->random = A->random->next; 將鏈表拆分成原鏈表和復制后的鏈表 */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(!pHead) return NULL; RandomListNode* cur = pHead;//從頭復制節(jié)點 A->B->C 變成A->A'->B->B'->C->C' while(cur){ RandomListNode* copynode = new RandomListNode(cur->label); copynode -> next = cur -> next; cur->next = copynode; cur = cur -> next -> next; } cur = pHead;//從頭復制random,A1->random = A->random->next; while(cur){ if(cur -> random) cur -> next -> random = cur -> random -> next; cur = cur -> next -> next; } cur = pHead;//從頭將鏈表拆分成原鏈表和復制后的鏈表 RandomListNode* res = cur -> next; //復制后的鏈表,標記位置 RandomListNode* tmp; while(cur -> next){ tmp = cur -> next; cur -> next = tmp -> next; cur = tmp; } return res; } };
26、二叉搜索樹與雙向鏈表
輸入一棵二叉搜索樹,將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點,只能調(diào)整樹中結(jié)點指針的指向。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: //樹的線索化,利用了二叉樹結(jié)點中的空指針,讓它們分別指向本結(jié)點的前驅(qū)或者后繼 TreeNode* head = NULL; TreeNode* res = NULL; TreeNode* Convert(TreeNode* pRootOfTree) { if(!pRootOfTree) return NULL; helper(pRootOfTree); return res; } void helper(TreeNode* root) { if(!root) return; helper(root->left); if(!head){ //中序遍歷第一個,即樹的左下角 head = root; res = root; } else{ head -> right = root; root -> left = head; head = root; } helper(root->right); } };
27、字符串的排列
輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
輸入一個字符串,長度不超過9(可能有字符重復),字符只包括大小寫字母。
/* 問題轉(zhuǎn)換為先固定第一個字符,求剩余字符的排列 再把第一個字符與后面每一個字符交換,并同樣遞歸獲得首位后面的字符串組合 a b b c: a+f(bbc),b+f(abc),c+f(cbba); 遍歷出所有可能出現(xiàn)在第一個位置的字符 f(bbc)=b+f(bc),c+f(bb); f(bc)=b+f(c),c+f(b); f(c)=c; */ class Solution { public: vector<string> res; vector<string> Permutation(string str) { helper(str,0); sort(res.begin(),res.end()); return res; } void helper(string s,int n) { if(n == s.size()-1){ //終止條件 if(find(res.begin(),res.end(),s) == res.end()) res.push_back(s); } else{ for(int i=n;i<s.size();i++){ swap(s,i,n); helper(s,n+1); swap(s,i,n); } } } void swap(string &str,int i,int j) { char tmp = str[i]; str[i] = str[j]; str[j] = tmp; } };
28、數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半,請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次,超過數(shù)組長度的一半,因此輸出2。如果不存在則輸出0。
/* 如果重復的次數(shù)超過一半的話,一定有相鄰的數(shù)字相同這種情況的 對數(shù)組同時去掉兩個不同的數(shù)字,到最后剩下的一個數(shù)就是該數(shù)字 */ class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { if(numbers.empty()) return 0; int res = numbers[0]; int times = 0; for(int i=0;i<numbers.size();i++){ if(numbers[i] == res) times++; else{ times--; if(times == 0){ res = numbers[i]; times = 1; } } } //check times = 0; for(int i=0;i<numbers.size();i++){ if(numbers[i] == res) times++; } return times>numbers.size()/2?res:0; } }; /* 涉及到快排sort,其時間復雜度為O(NlogN)并非最優(yōu) class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { // 因為用到了sort,時間復雜度O(NlogN),并非最優(yōu) if(numbers.empty()) return 0; sort(numbers.begin(),numbers.end()); int middle = numbers[numbers.size()/2];//假設存在眾數(shù)may //check int count=0; // 出現(xiàn)次數(shù) for(int i=0;i<numbers.size();++i) { if(numbers[i]==middle) ++count; } return (count>numbers.size()/2) ? middle : 0; } }; */
29、最小的k個數(shù)
輸入n個整數(shù),找出其中最小的K個數(shù)。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字,則最小的4個數(shù)字是1,2,3,4,。
/* 基于堆排序算法,構(gòu)建最大堆。時間復雜度為O(nlogk) 用最大堆保存這k個數(shù),每次只和堆頂比,如果比堆頂小,刪除堆頂,新數(shù)入堆 如果用快速排序,時間復雜度為O(nlogn); */ class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> res; priority_queue<int> q; //priority_queue<int,vector<int>,greater<int>> q;最小堆 if(input.empty() || k>input.size() || k==0) return res; for(int i=0;i<input.size();i++){ if(i<k) q.push(input[i]); else{ if(input[i] < q.top()){ q.pop(); q.push(input[i]); } } } while(!q.empty()){ res.push_back(q.top()); q.pop(); } return res; } };
30、連續(xù)子數(shù)組的最大和
HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當向量全為正數(shù)的時候,問題很好解決。但是,如果向量中包含負數(shù),是否應該包含某個負數(shù),并期望旁邊的正數(shù)會彌補它呢?例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)。給一個數(shù)組,返回它的最大連續(xù)子序列的和,你會不會被他忽悠???(子向量的長度至少是1)
class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { int res = array[0]; int max = 0; for(int i=0;i<array.size();i++){ max += array[i]; if(max > res) res = max; if(max < 0) max = 0; } return res; } };
31、整數(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次,但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數(shù)區(qū)間中1出現(xiàn)的次數(shù)(從1 到 n 中1出現(xiàn)的次數(shù))。
/* n=10917 1~10917 所有數(shù)里在個位的1的數(shù)量: 前面為0~1090,個位后無,排列組合共1*1091種情況;前面為1091時,個位后為1。總共:1*1091+1(m=1,情況3) 所有數(shù)里在十位的1的數(shù)量: 前面為0~108,十位后為0~9,排列組合共10*109種情況;前面為109時,十位后為0~7??偣玻?0*109+8(m=8,情況2) 所有數(shù)里在百位的1的數(shù)量: 前面為0~9,百位后為0~99,排列組合共100*10種情況;前面為10時,百位后為0~99??偣玻?00*10+100(m=100,情況3) 所有數(shù)里在千位的1的數(shù)量: 前面為0~0,千位后為0~999,排列組合共1000*1種情況;前面為1時,千位后沒有滿足的??偣玻?000*1+0(m=0,情況1) 所有數(shù)里在萬位的1的數(shù)量: 前面為無,萬位后為0~917??偣玻?000*0+918(m=918,情況2) 精髓在于后面部分m值分三種情況: ①當前位為0時,m=0;②當前位為1時,m=后面值+1;③當前位為2~9時,m=10^(后面的位數(shù)) */ class Solution { public: int NumberOf1Between1AndN_Solution(int n) { if(n == 0) return 0; int res = 0; int base = 1,t = n,m; while(t!=0){ if(t%10 == 0) m = 0; else if(t%10 == 1) m = n-t*base+1; else m = base; t/=10; res+=base*t+m; base*=10; } return res; } };
32、把數(shù)組排成最小的數(shù)
輸入一個正整數(shù)數(shù)組,把數(shù)組里所有數(shù)字拼接起來排成一個數(shù),打印能拼接出的所有數(shù)字中最小的一個。例如輸入數(shù)組{3,32,321},則打印出這三個數(shù)字能排成的最小數(shù)字為321323。
class Solution { public: //sort中的比較函數(shù)compare要聲明為靜態(tài)成員函數(shù)或全局函數(shù),不能作為普通成員函數(shù) string PrintMinNumber(vector<int> numbers) { string res = ""; sort(numbers.begin(),numbers.end(),cmp); for(int i=0;i<numbers.size();i++){ res += to_string(numbers[i]); } return res; } static bool cmp(int &i,int &j) { string si = to_string(i); string sj = to_string(j); return si+sj<sj+si; // 2 23和23 2 } };
33、丑數(shù)
把只包含質(zhì)因子2、3和5的數(shù)稱作丑數(shù)(Ugly Number)。例如6、8都是丑數(shù),但14不是,因為它包含質(zhì)因子7。 習慣上我們把1當做是第一個丑數(shù)。求按從小到大的順序的第N個丑數(shù)。
/* 如果p是丑數(shù),那么p=2^x * 3^y * 5^z, 且x,y,z需滿足是前面的丑數(shù) 初始x=y=z=1, 2^x、3^y、5^z最小的數(shù)2^x加進結(jié)果,x在結(jié)果中位置后移一位 */ class Solution { public: int GetUglyNumber_Solution(int index) { if(index < 7) return index; vector<int> res(index); res[0] = 1; int x=0, y=0, z=0; for(int i=1;i<index;i++){ res[i] = min(min(res[x]*2,res[y]*3),res[z]*5); if(res[i] == res[x]*2) x++; if(res[i] == res[y]*3) y++; if(res[i] == res[z]*5) z++; } return res[index-1]; } };
34、第一個只出現(xiàn)一次的字符
在一個字符串(0<=字符串長度<=10000,全部由字母組成)中找到第一個只出現(xiàn)一次的字符,并返回它的位置, 如果沒有則返回 -1(需要區(qū)分大小寫).
class Solution { public: int FirstNotRepeatingChar(string str) { //字符在計算機中以ASCII碼的形式存儲,當字符作為數(shù)組下標時,其表示的下標值為該字符的ASCII碼的十進制值 //0-9: 48-57, A-Z: 65-90, a-z: 97-122 map<char,int> map; //map支持int,char,string for(int i=0;i<str.size();i++){ map[str[i]]++; } for(int i=0;i<str.size();i++){ if(map[str[i]] == 1) return i; } return -1; } };
35、數(shù)組中的逆序?qū)?/p>
在數(shù)組中的兩個數(shù)字,如果前面一個數(shù)字大于后面的數(shù)字,則這兩個數(shù)字組成一個逆序?qū)Α]斎胍粋€數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對1000000007取模的結(jié)果輸出。 即輸出P%1000000007
輸入描述:
題目保證輸入的數(shù)組中沒有的相同的數(shù)字
數(shù)據(jù)范圍:對于%50的數(shù)據(jù),size<=10^4對于%75的數(shù)據(jù),size<=10^5對于%100的數(shù)據(jù),size<=2*10^5
示例:
輸入 1,2,3,4,5,6,7,0
輸出 7
/* 先把數(shù)組分割成子數(shù)組,先統(tǒng)計出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目,然后再統(tǒng)計出兩個相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目 在統(tǒng)計逆序?qū)Φ倪^程中,還需要對數(shù)組進行排序,每一次比較的時候 都把較大的數(shù)字從后面往前復制到一個輔助數(shù)組中,確保輔助數(shù)組copy中的數(shù)字是遞增排序的 交換copy和data:在每次的操作中,當前傳入函數(shù)中第一項,比較的結(jié)果都存放到第二項中,需要交叉保證下一次是排序的 輸入[7,5,6,4], 最后的結(jié)果copy[4,5,6,7], data[5,7,4,6] */ class Solution { public: int InversePairs(vector<int> data) { if(data.size()==0) return 0; vector<int>copy(data); //使用data初始化copy long long P = InversePairsCore(data,copy,0,data.size()-1); return P%1000000007; } long long InversePairsCore(vector<int> &data,vector<int> ©,int l,int r) { if(l == r){ copy[l] = data[l]; return 0; } int mid = (l+r)/2; long long left = InversePairsCore(copy,data,l,mid); long long right = InversePairsCore(copy,data,mid+1,r); int i = mid,j = r; long long count = 0; //需要long long,int的話最后一個例子會溢出測試不通過 int cur = r; while(i>=l && j>=mid+1){ if(data[i]>data[j]){ //3 8,4 6 8>6 count += j-mid; copy[cur--] = data[i]; i--; } else{ copy[cur--] = data[j]; j--; } } while(i>=l){ copy[cur--] = data[i]; i--; } while(j>=mid+1){ copy[cur--] = data[j]; j--; } return left+right+count; } };
36、兩個鏈表的第一個公共節(jié)點
輸入兩個鏈表,找出它們的第一個公共結(jié)點。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { //找出2個鏈表的長度,然后讓長的先走兩個鏈表的長度差,然后再一起走 int len1 = getlen(pHead1); int len2 = getlen(pHead2); int dis = len1-len2>0?len1-len2:len2-len1; while(dis!=0){ if(len1>len2) pHead1 = pHead1->next; else pHead2 = pHead2->next; dis--; } while(pHead1){ if(pHead1 == pHead2) return pHead1; pHead1 = pHead1->next; pHead2 = pHead2->next; } return NULL; } int getlen(ListNode* p) { int res = 0; ListNode* root = p; while(root){ res++; root = root->next; } return res; } };
37、數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
class Solution { public: int GetNumberOfK(vector<int> data ,int k) { if(data.empty()) return 0; return findk(data,k,0,data.size()-1); } int findk(vector<int> data ,int k, int l, int r){ if(l>r) return -1; int mid = (l+r)/2; if(data[mid] == k){ //找到了一個k,往data兩邊擴展,統(tǒng)計k的個數(shù) int i = mid-1; //往左找 while(i >= l){ if(data[i] == k) i--; else break; } int j = mid+1; //往右找 while(j <= r){ if(data[j] == k) j++; else break; } return j-i-1; } if(findk(data,k,l,mid-1)>0) return findk(data,k,l,mid-1); if(findk(data,k,mid+1,r)>0) return findk(data,k,mid+1,r); return 0; } };
38、二叉樹的深度
輸入一棵二叉樹,求該樹的深度。從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點(含根、葉結(jié)點)形成樹的一條路徑,最長路徑的長度為樹的深度。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: int TreeDepth(TreeNode* pRoot) { if(!pRoot) return 0; return max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+1; } };
39、平衡二叉樹
輸入一棵二叉樹,判斷該二叉樹是否是平衡二叉樹。
class Solution { public: //左右子樹均為平衡二叉樹,且左右子樹層高不超過1 bool IsBalanced_Solution(TreeNode* pRoot) { if(!pRoot) return true; return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right) && abs(getlen(pRoot->left)-getlen(pRoot->right))<=1; } int getlen(TreeNode* p){ if(!p) return 0; return max(getlen(p->left),getlen(p->right))+1; } };
40、數(shù)組中只出現(xiàn)一次的數(shù)字
一個整型數(shù)組里除了兩個數(shù)字之外,其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。
/* 異或性質(zhì): 交換律:a ^ b ^ c <=> a ^ c ^ b,倆兩相同的移到一起 相同的數(shù)異或為0: n ^ n => 0 任何數(shù)于0異或為任何數(shù) 0 ^ n => n 遍歷異或后,只剩下兩單個的異或了,結(jié)果res的二進制至少有一位為1 取第一個1所在的位數(shù)index,原數(shù)組分成第index位為1和為0 相同的數(shù)肯定在一個組,兩個單的在不同的組 */ class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { int res = 0; for(int i=0;i<data.size();i++){ res ^= data[i]; } int index = findbit1(res); for(int i=0;i<data.size();i++){ if((data[i] >> index & 1)== 1) num1[0]^=data[i]; else num2[0]^=data[i]; } } int findbit1(int n) { int index = 0; while((n&1) == 0 && index<32){ //當前位為0且未溢出 index++; n >>= 1; } return index; } };
41、和為S的連續(xù)正數(shù)序列
小明很喜歡數(shù)學,有一天他在做數(shù)學作業(yè)時,要求計算出9~16的和,他馬上就寫出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個數(shù))。沒多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22?,F(xiàn)在把問題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!
輸出描述:
輸出所有和為S的連續(xù)正數(shù)序列。序列內(nèi)按照從小至大的順序,序列間按照開始數(shù)字從小到大的順序
class Solution { public: vector<vector<int> > FindContinuousSequence(int sum) { vector<vector<int> > res; vector<int> part; int i = 1,j = 2; while(i < j){ int count = (i+j)*(j-i+1)/2; //i~j的和 if(count == sum){ //將i~j插入res part.clear(); for(int k=i;k<=j;k++){ part.push_back(k); } res.push_back(part); i++; } else if(count < sum) j++; //右窗口右移 else i++; //左窗口右移 } return res; } };
42、和為S的兩個數(shù)字
輸入一個遞增排序的數(shù)組和一個數(shù)字S,在數(shù)組中查找兩個數(shù),使得他們的和正好是S,如果有多對數(shù)字的和等于S,輸出兩個數(shù)的乘積最小的。
輸出描述:
對應每個測試案例,輸出兩個數(shù),小的先輸出。
class Solution { public: vector<int> FindNumbersWithSum(vector<int> array,int sum) { vector<int> res; int i = 0, j = array.size()-1; while(i<j){ if(array[i]+array[j] == sum){ //1 3 4 6,1*6<3*4,越邊邊乘積越小 res.push_back(array[i]); res.push_back(array[j]); break; } else if(array[i]+array[j] > sum) j--; else i++; } return res; } };
43、左旋轉(zhuǎn)字符串
匯編語言中有一種移位指令叫做循環(huán)左移(ROL),現(xiàn)在有個簡單的任務,就是用字符串模擬這個指令的運算結(jié)果。對于一個給定的字符序列S,請你把其循環(huán)左移K位后的序列輸出。例如,字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果,即“XYZdefabc”。是不是很簡單?OK,搞定它!
class Solution { public: string LeftRotateString(string str, int n) { int len = str.size(); if(len == 0) return ""; n = n%len; //str = ”abcXYZ”, n = 1 str += str; //str = ”abcXYZabcXYZ” return str.substr(n, len); //從下標n開始的len個字符 } };
44、翻轉(zhuǎn)單詞順序列
??妥罱鼇砹艘粋€新員工Fish,每天早晨總是會拿著一本英文雜志,寫些句子在本子上。同事Cat對Fish寫的內(nèi)容頗感興趣,有一天他向Fish借來翻看,但卻讀不懂它的意思。例如,“student. a am I”。后來才意識到,這家伙原來把句子單詞的順序翻轉(zhuǎn)了,正確的句子應該是“I am a student.”。Cat對一一的翻轉(zhuǎn)這些單詞順序可不在行,你能幫助他么?
class Solution { public: string ReverseSentence(string str) { string res; stack<string> stack; string tmp; for(int i=0;i<str.size();i++){ if(str[i] == ' '){ stack.push(tmp); tmp.clear(); } else tmp.push_back(str[i]); } stack.push(tmp); while(!stack.empty()){ res += ' ' + stack.top(); stack.pop(); } return res.erase(0,1); } };
45、撲克牌順子
LL今天心情特別好,因為他去買了一副撲克牌,發(fā)現(xiàn)里面居然有2個大王,2個小王(一副牌原本是54張_)…他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿??!“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子…LL不高興了,他想了想,決定大\小 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”。LL決定去買體育彩票啦。 現(xiàn)在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運氣如何, 如果牌能組成順子就輸出true,否則就輸出false。為了方便起見,你可以認為大小王是0。
/* max 記錄 最大值,min 記錄 最小值,min ,max 都不記0 滿足條件 max - min <5;除0外沒有重復的數(shù)字(牌);數(shù)組長度 為5 */ class Solution { public: bool IsContinuous( vector<int> numbers ) { // 5張牌 if(numbers.size()!=5) return false; int max = -1, min = 14; int* flag = new int[14](); //初始化數(shù)組全為 0 for(int i=0;i<numbers.size();i++){ if(numbers[i] == 0) continue; int tmp = numbers[i]; if(flag[tmp] == 1) return false; //重復 else{ if(tmp < min) min = tmp; if(tmp > max) max = tmp; flag[tmp] = 1; } } delete[] flag; return max-min<5; } };
46、孩子們的游戲(圓圈中最后剩下的數(shù))
每年六一兒童節(jié),??投紩蕚湟恍┬《Y物去看望孤兒院的小朋友,今年亦是如此。HF作為??偷馁Y深元老,自然也準備了一些小游戲。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數(shù)m,讓編號為0的小朋友開始報數(shù)。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續(xù)0…m-1報數(shù)…這樣下去…直到剩下最后一個小朋友,可以不用表演,并且拿到??兔F的“名偵探柯南”典藏版(名額有限哦!!_)。請你試著想下,哪個小朋友會得到這份禮品呢?(注:小朋友的編號是從0到n-1)
class Solution { public: int LastRemaining_Solution(int n, int m) { if (m == 0 || n == 0) return -1; int* flag = new int[n]();//初始化數(shù)組全為 0 int i = -1,left = n,step = 0; while(left>0){ i++; //0 if(i == n) i = 0; //模擬環(huán) if(flag[i] == 1) continue; //跳過被刪除的對象 step++; if(step == m){ step = 0; flag[i] = 1; left--; } } return i; } };
47、求1+2+3+…+n
求1+2+3+…+n,要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字及條件判斷語句(A?B:C)。
/* int Sum_Solution(int n) { if(n == 0) return 0; return n+Sum_Solution(n-1); } 將此段代碼改寫成不使用for、while、if、else、switch、case等關(guān)鍵字及條件判斷語句 */ class Solution { public: int Sum_Solution(int n) { int res = n; res && (res+=Sum_Solution(n-1)); //當n==0時,只執(zhí)行前面的判斷,為false,然后直接返回0; //當n>0時,執(zhí)行sum+=Sum_Solution(n-1),實現(xiàn)遞歸計算Sum_Solution(n) return res; } };
48、不用加減乘除做加法
寫一個函數(shù),求兩個整數(shù)之和,要求在函數(shù)體內(nèi)不得使用+、-、*、/四則運算符號。
/* 兩數(shù)相與再左移一位,表示相加進位的值 101&111=101 左移1,1010 兩數(shù)異或,表示相加不算進位的值 101^111=010 兩者相加為和,(101&111)<<1 + 101^111 = 1100,即調(diào)用函數(shù)本身,直到進位為0 */ class Solution { public: int Add(int num1, int num2) { while(num2!=0){ int tmp = num1^num2; //相加不算進位的值 num2 = (num1&num2)<<1; //相加進位的值 num1 = tmp; } return num1; } };
49、把字符串轉(zhuǎn)換成整數(shù)
將一個字符串轉(zhuǎn)換成一個整數(shù)(實現(xiàn)Integer.valueOf(string)的功能,但是string不符合數(shù)字要求時返回0),要求不能使用字符串轉(zhuǎn)換整數(shù)的庫函數(shù)。 數(shù)值為0或者字符串不是一個合法的數(shù)值則返回0。
輸入描述:
輸入一個字符串,包括數(shù)字字母符號,可以為空
輸出描述:
如果是合法的數(shù)值表達則返回該數(shù)字,否則返回0
輸入: +2147483647 , 1a33
輸出: 2147483647 , 0
/* 字符"0123456789"的值是連續(xù)的,如果c"0123456789"范圍內(nèi) int a = c - '0'就是對應整數(shù)值 從后往前,最后判斷符號位 */ class Solution { public: int StrToInt(string str) { if(str.empty()) return 0; int res = 0,base = 1; for(int i = str.size()-1;i>=0;i--){ if(str[i]>='0' && str[i]<='9'){ res += base*(int)(str[i]-'0'); base *= 10; } else if(str[i] == '-'){ if(i == 0) return -res; //-123 } else if(str[i] == '+'){ if(i == 0) return res; //+123 } else return 0; //1a3 } return res; //123 } };
50、數(shù)組中重復的數(shù)字
在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復的,但不知道有幾個數(shù)字是重復的。也不知道每個數(shù)字重復幾次。請找出數(shù)組中任意一個重復的數(shù)字。 例如,如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3},那么對應的輸出是第一個重復的數(shù)字2。
/* 數(shù)字的范圍保證在0 ~ n-1 之間,所以可以利用現(xiàn)有數(shù)組設置標志 當一個數(shù)字i被訪問過后,可以設置對應位上的數(shù)numbers[i] += n 再次訪問i時,發(fā)現(xiàn)numbers[i] >=n,直接返回i */ class Solution { public: // Parameters: // numbers: an array of integers // length: the length of array numbers // duplication: (Output) the duplicated number in the array number // Return value: true if the input is valid, and there are some duplications in the array number // otherwise false bool duplicate(int numbers[], int length, int* duplication) { for(int i=0;i<length;i++){ //2,3,1,0,2,5,3 int cur = numbers[i]; if(cur >= length) cur = cur-length; if(numbers[cur] >= length){ *duplication = cur; return true; } numbers[cur] += length; } return false; } };
51、構(gòu)建乘積數(shù)組
給定一個數(shù)組A[0,1,…,n-1],請構(gòu)建一個數(shù)組B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。
/* 1 第一項左側(cè) a[0] 第二項左側(cè) a[0]*a[1] a[0]*a[1]*a[2] a[0]*a[1]*a[2]...*a[n-2] 第n項左側(cè) 1 第n項右側(cè) a[n-1] a[n-1]*a[n-2] a[n-1]*a[n-2]*a[n-3]...*a[2] 第二項左側(cè) a[n-1]*a[n-2]*a[n-3]...*a[1] 第一項右側(cè) */ class Solution { public: vector<int> multiply(const vector<int>& A) { vector<int> res; if(A.empty()) return res; int tmp = 1; for(int i=0;i<A.size();i++){ //左邊乘 res.push_back(tmp); tmp *= A[i]; } tmp = 1; for(int i=A.size()-1;i>=0;i--){ //右邊乘 res[i] *= tmp; tmp *= A[i]; } return res; } };
52、正則表達式匹配
請實現(xiàn)一個函數(shù)用來匹配包括’.‘和’‘的正則表達式。模式中的字符’.‘表示任意一個字符,而’'表示它前面的字符可以出現(xiàn)任意次(包含0次)。 在本題中,匹配是指字符串的所有字符匹配整個模式。例如,字符串"aaa"與模式"a.a"和"abaca"匹配,但是與"aa.a"和"ab*a"均不匹配
/* 當?shù)诙€字符不是“*”時: 1、第一個字符匹配,字符串和模式后移1個字符,繼續(xù)匹配 2、第一個字符不匹配,返回false 當?shù)诙€字符是“*”時: 1、第一個字符不匹配,模式后移2個字符,繼續(xù)匹配 2、第一個字符匹配,可以有3種情況: (1)模式后移2字符,相當于x*被忽略,x出現(xiàn)0次; (2)字符串后移1字符,模式后移2字符,相當于x出現(xiàn)一次; (3)字符串后移1字符,模式不變,相當于x出現(xiàn)多次次; 注:匹配指值相同,或pattern為'.',字符串未到尾 */ class Solution { public: bool match(char* str, char* pattern) { if(*str == '\0' && *pattern == '\0') return true; if(*str != '\0' && *pattern == '\0') return false; if(*(pattern+1) != '*'){ if(*str==*pattern || *pattern=='.'&&*str!='\0'){ return match(str+1,pattern+1); } else return false; } else{ if(*str==*pattern || *pattern=='.'&&*str!='\0'){ return match(str,pattern+2)|| match(str+1,pattern+2)|| match(str+1,pattern); } else return match(str,pattern+2); } } };
53、表示數(shù)值的字符串
請實現(xiàn)一個函數(shù)用來判斷字符串是否表示數(shù)值(包括整數(shù)和小數(shù))。例如,字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示數(shù)值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。
/* 1、+、- 第一次出現(xiàn)+-符號,且不在首位,必須緊接在e之后 第二次出現(xiàn)+-符號,必須緊接在e之后 2、e、E e后不為空 不能雙e 3、. .前不能有.或e 4、其他 return false */ class Solution { public: bool isNumeric(char* string) { // 標記符號、小數(shù)點、e是否出現(xiàn)過 bool hasSign = false, hasPoint = false, hasE = false; for(int i=0;string[i];i++){ if(string[i] == '+' || string[i] == '-'){ if(!hasSign && i>0 && string[i-1]!='e' && string[i-1]!='E') return false; if(hasSign && string[i-1]!='e' && string[i-1]!='E') return false; hasSign = true; } else if(string[i] == 'e' || string[i] == 'E'){ if(string[i+1] == '\0' || hasE) return false; hasE = true; } else if(string[i] == '.'){ if(hasPoint || hasE) return false; hasPoint = true; } else if(string[i] < '0' || string[i] > '9') return false; } return true; } };
54、字符流中第一個不重復的字符
請實現(xiàn)一個函數(shù)用來找出字符流中第一個只出現(xiàn)一次的字符。例如,當從字符流中只讀出前兩個字符"go"時,第一個只出現(xiàn)一次的字符是"g"。當從該字符流中讀出前六個字符“google"時,第一個只出現(xiàn)一次的字符是"l"。
輸出描述:
如果當前字符流沒有存在出現(xiàn)一次的字符,返回#字符。
/* 字符在計算機中以ASCII碼的形式存儲,當字符作為數(shù)組下標時,其表示的下標值為該字符的ASCII碼的十進制值 0-9: 48-57 ,A-Z: 65-90 ,a-z: 97-122 ASCII碼:0~127 */ class Solution { public: string s; char flag[128] = {0}; void Insert(char ch) { s += ch; flag[ch]++; } char FirstAppearingOnce() { for(int i=0;i<s.size();i++){ if(flag[s[i]] == 1) return s[i]; } return '#'; } };
55、鏈表中環(huán)的入口結(jié)點
給一個鏈表,若其中包含環(huán),請找出該鏈表的環(huán)的入口結(jié)點,否則,輸出null。
/* 如果有環(huán),快慢指針總會相遇 1——2——3——4——5——6 | | 9——8——7 假設快慢指針相遇在6,有1~6走的=6~6走的 1~6走的 = 1~入環(huán)點+入環(huán)點~6 6~6走的 = 6~入環(huán)點+入環(huán)點~6 則當快指針從1重新開始,兩指針速度相同,再次相遇即為入口節(jié)點 */ /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { //快慢指針,判斷是否有環(huán) bool hasLoop = false; ListNode* fast = pHead; ListNode* slow = pHead; while(fast && fast->next){ fast = fast->next->next; slow = slow->next; if(fast == slow){ hasLoop = true; break; } } //尋找環(huán)的入口節(jié)點 if(hasLoop){ fast = pHead; while(fast != slow){ fast = fast->next; slow = slow->next; } return slow; } return NULL; } };
56、刪除鏈表中重復的結(jié)點
在一個排序的鏈表中,存在重復的結(jié)點,請刪除該鏈表中重復的結(jié)點,重復的結(jié)點不保留,返回鏈表頭指針。 例如,鏈表1->2->3->3->4->4->5 處理后為 1->2->5
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { ListNode* root = new ListNode(0);//設為幾無所謂 ListNode* h = root; //標記當前位置 h->next = pHead; while(h->next && h->next->next){//至少兩個節(jié)點 ListNode* tmp = h->next->next; if(h->next->val == tmp->val){//兩節(jié)點相同 while(tmp && h->next->val == tmp->val){ tmp = tmp->next; } h->next = tmp; //刪除操作 } else h = h->next; } return root->next; } };
57、二叉樹的下一個結(jié)點
給定一個二叉樹和其中的一個結(jié)點,請找出中序遍歷順序的下一個結(jié)點并且返回。注意,樹中的結(jié)點不僅包含左右子結(jié)點,同時包含指向父結(jié)點的指針。
/* 3種情況: 1 1 1 / \ / \ / \ 2 3 2 4 2 5 / \ / / \ 4 5 3 3 4 cur=1,next=4 cur=2,next=1 cur=4,next=1 情況1,有右子樹,返回右子樹的左下角 情況2,無右子樹,且是父結(jié)點的左子樹,返回父結(jié)點 情況3,無右子樹,且是父結(jié)點的右子樹,返回父結(jié)點的左上角的父結(jié)點 */ /* struct TreeLinkNode { int val; struct TreeLinkNode *left; struct TreeLinkNode *right; struct TreeLinkNode *next; TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { } }; */ class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { if(pNode->right){ TreeLinkNode* res = pNode->right; while(res->left){ res = res->left; } return res; } else{ while(pNode->next && pNode->next->right == pNode){ pNode = pNode->next; } return pNode->next; } } };
58、對稱的二叉樹
請實現(xiàn)一個函數(shù),用來判斷一顆二叉樹是不是對稱的。注意,如果一個二叉樹同此二叉樹的鏡像是同樣的,定義其為對稱的。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NUL L) { } }; */ class Solution { public: bool isSymmetrical(TreeNode* pRoot){ if(!pRoot) return true; return ismoir(pRoot->left,pRoot->right); } bool ismoir(TreeNode* l,TreeNode* r){//是鏡像的 if(!l && !r) return true;//都不存在 if(l && r) return l->val==r->val && ismoir(l->left,r->right) && ismoir(r->left,l->right); return false;// 有且僅有1個存在 } };
59、按之字形順序打印二叉樹
請實現(xiàn)一個函數(shù)按照之字形打印二叉樹,即第一行按照從左到右的順序打印,第二層按照從右至左的順序打印,第三行按照從左到右的順序打印,其他行以此類推。
/* 1 ——> stack1 存奇數(shù)層,順序 / \ 2 3 <—— stack2 存偶數(shù)層,逆序,先left后right / \ / \ 4 5 6 7 ——> stack1 存奇數(shù)層,順序,先right后left */ /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int> > res; if(!pRoot) return res; stack<TreeNode*> stack1,stack2; stack1.push(pRoot); while(!stack1.empty() || !stack2.empty()){ if(!stack1.empty()){ vector<int> tmp; while(!stack1.empty()){ if(stack1.top()->left) stack2.push(stack1.top()->left); if(stack1.top()->right) stack2.push(stack1.top()->right); tmp.push_back(stack1.top()->val); stack1.pop(); } res.push_back(tmp); } if(!stack2.empty()){ vector<int> tmp; while(!stack2.empty()){ if(stack2.top()->right) stack1.push(stack2.top()->right); if(stack2.top()->left) stack1.push(stack2.top()->left); tmp.push_back(stack2.top()->val); stack2.pop(); } res.push_back(tmp); } } return res; } };
60、把二叉樹打印成多行
從上到下按層打印二叉樹,同一層結(jié)點從左至右輸出。每一層輸出一行。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int> > res; if(!pRoot) return res; queue<TreeNode*> queue; queue.push(pRoot); while(!queue.empty()){ int num = queue.size(); vector<int> tmp; while(num!=0){ if(queue.front()->left) queue.push(queue.front()->left); if(queue.front()->right) queue.push(queue.front()->right); tmp.push_back(queue.front()->val); queue.pop(); num--; } res.push_back(tmp); } return res; } };
61、序列化二叉樹
請實現(xiàn)兩個函數(shù),分別用來序列化和反序列化二叉樹
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: char* Serialize(TreeNode *root) { if(!root) return NULL; string s; queue<TreeNode*> queue; queue.push(root); while(!queue.empty()){ if(queue.front()){ queue.push(queue.front()->left); queue.push(queue.front()->right); s += to_string(queue.front()->val)+","; } else s += "#,"; queue.pop(); } char* res = strdup(s.c_str()); /* 另一種寫法,不用strdup() char* res = new char[s.size() + 1]; int i; for(i=0;i<s.size();i++) res[i]=s[i]; res[i] = '\0'; */ return res; } TreeNode* Deserialize(char *str) { if(!str) return NULL; int i = 0; auto head = getnode(str,i); queue<TreeNode*> queue; queue.push(head); while(!queue.empty()){ queue.front()->left = getnode(str,i); queue.front()->right = getnode(str,i); if(queue.front()->left) queue.push(queue.front()->left); if(queue.front()->right) queue.push(queue.front()->right); queue.pop(); } return head; } TreeNode* getnode(char *str,int &i){ if(str[i] == ',') i++; if(str[i] == '#'){ i += 2; return NULL; } string s; while(str[i] != ',' && str[i] != '\0'){ s += str[i]; i++; } if(!s.empty()) return new TreeNode(stoi(s)); return NULL; } };
62、二叉搜索樹的第k個結(jié)點
給定一棵二叉搜索樹,請找出其中的第k小的結(jié)點。例如, (5,3,7,2,4,6,8) 中,按結(jié)點數(shù)值大小順序第三小結(jié)點的值為4。
/* 二叉搜索樹:左子樹上所有結(jié)點的值均小于它的根結(jié)點的值,右子樹上所有結(jié)點的值均大于它的根結(jié)點的值 二叉搜索樹按照中序遍歷得到遞增的順序,壓入棧,第k個結(jié)點就是結(jié)果 */ /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: stack<TreeNode*> stack; TreeNode* KthNode(TreeNode* pRoot, int k){ if(k <= 0) return NULL; sortmid(pRoot,k); if(stack.size() < k) return NULL; //k大于節(jié)點數(shù) return stack.top(); } void sortmid(TreeNode* pRoot, int k) { if(!pRoot) return; if(stack.size()!=k) sortmid(pRoot->left,k); if(stack.size()!=k) stack.push(pRoot); if(stack.size()!=k) sortmid(pRoot->right,k); } };
63、數(shù)據(jù)流中的中位數(shù)
如何得到一個數(shù)據(jù)流中的中位數(shù)?如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值,那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值,那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流,使用GetMedian()方法獲取當前讀取數(shù)據(jù)的中位數(shù)。
/* 使用大小頂堆,中位數(shù)是大頂堆的根節(jié)點與小頂堆的根節(jié)點和的平均數(shù) 大頂堆,由大到小,存較小的數(shù) 7 6 5 小頂堆,由小到大,存較大的數(shù) 8 9 10 步驟: 第一個插入的元素裝大頂堆 1、每來一個插入的元素,比大頂堆堆頂元素小的裝大頂堆,否則裝小頂堆(保證大頂堆的數(shù)都比小頂堆的數(shù)小) 2、判斷是否大頂堆裝多了,大頂堆最多比小頂堆多一個,如果是,將大頂堆堆頂元素插入小頂堆 3、判斷是否小頂堆裝多了,小頂堆小于等于大頂堆,如果是,將小頂堆堆頂元素插入大頂堆 */ class Solution { public: priority_queue<int,vector<int>,less<int> > big_heap; priority_queue<int,vector<int>,greater<int> > small_heap; void Insert(int num) { if(big_heap.empty() || num < big_heap.top()) big_heap.push(num); else small_heap.push(num); if(big_heap.size() == small_heap.size()+2){ small_heap.push(big_heap.top()); big_heap.pop(); } if(big_heap.size() == small_heap.size()-1){ big_heap.push(small_heap.top()); small_heap.pop(); } } double GetMedian() { return small_heap.size()==big_heap.size()?(small_heap.top()+big_heap.top())/2.0:big_heap.top(); } };
64、滑動窗口的最大值
給定一個數(shù)組和滑動窗口的大小,找出所有滑動窗口里數(shù)值的最大值。例如,如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3,那么一共存在6個滑動窗口,他們的最大值分別為{4,4,6,6,6,5}; 針對數(shù)組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。
class Solution { public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<int> res; deque<int> q;//隊首為當前窗口下最大值下標 for(unsigned int i=0;i<num.size();i++){ while(!q.empty() && num[i]>num[q.back()]){//q刪掉所有比當前元素小的,保證q降序 q.pop_back(); } if(!q.empty() && q.front()+size == i){ //若隊首超過窗口位置,刪掉 q.pop_front(); } q.push_back(i); if(size && i+1>=size) res.push_back(num[q.front()]); //防止size=0 } return res; } };
65、矩陣中的路徑
請設計一個函數(shù),用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始,每一步可以在矩陣中向左,向右,向上,向下移動一個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子,則之后不能再次進入這個格子。 例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字符串"bcced"的路徑,但是矩陣中不包含"abcb"路徑,因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后,路徑不能再次進入該格子。
class Solution { public: //用一個狀態(tài)數(shù)組保存之前訪問過的字符,然后再分別按上,下,左,右遞歸 bool hasPath(char* matrix, int rows, int cols, char* str) { if(!matrix || rows<=0 || cols<=0 || !str) return false; bool* flag = new bool[rows*cols]; //bool* flag=(bool*)malloc(rows*cols*sizeof(bool)); memset(flag,false,rows*cols); for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(helper(matrix,rows,cols,i,j,0,str,flag)) return true; } } delete[] flag; //free(flag); return false; } bool helper(char* matrix, int rows, int cols, int i, int j, int k, char* str, bool* flag) { int index = i*cols+j; if(i<0||i>=rows||j<0||j>=cols||flag[index]||matrix[index]!=str[k]) return false; if(str[k+1] =='\0') return true; flag[index] = true; if( helper(matrix,rows,cols,i-1,j,k+1,str,flag) || helper(matrix,rows,cols,i+1,j,k+1,str,flag) || helper(matrix,rows,cols,i,j-1,k+1,str,flag) || helper(matrix,rows,cols,i,j+1,k+1,str,flag)){ return true; } flag[index] = false; return false; } };
66、機器人的運動范圍
地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動,每一次只能向左,右,上,下四個方向移動一格,但是不能進入行坐標和列坐標的數(shù)位之和大于k的格子。 例如,當k為18時,機器人能夠進入方格(35,37),因為3+5+3+7 = 18。但是,它不能進入方格(35,38),因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子?
class Solution { public: int movingCount(int threshold, int rows, int cols) { if(rows<=0 || cols<=0 || threshold<0) return 0; bool* flag = new bool[rows*cols]; memset(flag,false,rows*cols); return helper(threshold,rows,cols,0,0,flag); } int helper(int threshold, int rows, int cols,int i, int j, bool* flag) { int index = i*cols+j; if(i<0||i>=rows||j<0||j>=cols||flag[index]||count(i)+count(j)>threshold) return 0; flag[index] = true; return helper(threshold,rows,cols,i-1,j,flag)+ helper(threshold,rows,cols,i+1,j,flag)+ helper(threshold,rows,cols,i,j-1,flag)+ helper(threshold,rows,cols,i,j+1,flag)+1; } int count(int n) { int res = 0; while(n!=0){ res += n%10; n /= 10; } return res; } };
以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
- 這篇文章主要介紹了騰訊公司c++面試小結(jié),小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2020-03-02
- 這篇文章主要介紹了 C++ 面試題目(整理自??途W(wǎng)),小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2020-02-13
華為校招 C++崗面試經(jīng)歷總結(jié)【筆試+一面+二面+Offer】
這篇文章主要介紹了華為校招 C++崗面試經(jīng)歷,總結(jié)分析了華為校招C++崗位的筆試題,以及一面、二面到最終拿到Offer的經(jīng)歷與相關(guān)經(jīng)驗感想,需要的朋友可以參考下2019-11-28- 這篇文章主要介紹了C++面試常見算法題與參考答案,總結(jié)分析了C++面試中遇到的常見算法題與相應的參考答案,需要的朋友可以參考下2019-11-20
- 這篇文章主要介紹了C++必備面試題與參考答案,結(jié)合大量經(jīng)典實例總結(jié)分析了C++面試過程中經(jīng)常遇到的各種概念、原理、算法相關(guān)問題及參考答案,需要的朋友可以參考下2019-10-31
- 這篇文章主要介紹了C/C++經(jīng)典面試題(附答案),小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2019-10-23
- 這篇文章主要介紹了C/C++求職者必備的20道面試題與參考答案,總結(jié)分析了C/C++相關(guān)的常見概念、原理、知識點與注意事項,需要的朋友可以參考下2019-10-10
- 這篇文章主要介紹了騰訊的外包c++面試經(jīng)歷,總結(jié)記錄了一次騰訊C++面試的經(jīng)歷,包括面試的流程、面試題目與相應的參考答案,需要的朋友可以參考下2019-09-29
- 這篇文章主要介紹了阿里面試必會的20道C++面試題與參考答案,涉及C++指針、面向?qū)ο?、函?shù)等相關(guān)特性與使用技巧,需要的朋友可以參考下2019-09-26
- 這篇文章主要介紹了經(jīng)典C++筆試題目與參考答案,總結(jié)分析了C++常見的各種面試題目,包含C++常見知識點、技術(shù)難點、算法等,需要的朋友可以參考下2019-09-10