劍指Offer66題C++面試題+答案總結(jié)
我要評(píng)論1、二維數(shù)組中的查找
在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長(zhǎng)度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
/*
3 4 5
4 5 6
6 7 8
從左下角開(kāi)始查找，當(dāng)target比左下角數(shù)字大時(shí)，右移；小時(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、替換空格
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的每個(gè)空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過(guò)替換之后的字符串為We%20Are%20Happy。
/*
從前往后替換，后面的字符要多次移動(dòng)，效率低下
從后往前，先計(jì)算需要多少空間，每個(gè)字符只移動(dòng)一次，效率更高
例如：a b c
從后往前，當(dāng)前第i位為'c'（非空格），前有n個(gè)空格，則i+2*n位為c
當(dāng)前第i位為' '（空格）,前有n個(gè)空格，則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、從尾到頭打印鏈表
輸入一個(gè)鏈表，按鏈表值從尾到頭的順序返回一個(gè)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、重建二叉樹(shù)
輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹(shù)并返回。
/*
前序遍歷序列{1,2,4,7,3,5,6,8} 1是根元素
中序遍歷序列{4,7,2,1,5,3,8,6} 1之前4,7,2是左子樹(shù)中序，之后5,3,8,6是右子樹(shù)中序
前序中1后的3個(gè)是左子樹(shù)前序，之后是右子樹(shù)前序
問(wèn)題轉(zhuǎn)換為根元素已知，求左子樹(shù)和右子樹(shù)的重建二叉樹(shù)，進(jì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ù)個(gè)數(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、用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類(lèi)型。
/*
用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列的功能
入隊(duì)：將元素進(jìn)棧A
出隊(duì)：判斷棧B是否為空，如果為空，則將棧A中所有元素pop，并push進(jìn)棧B，棧B出棧；
如果不為空，棧B直接出棧。
用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧的功能
入棧：將元素進(jìn)隊(duì)列A
出棧：判斷隊(duì)列A中元素的個(gè)數(shù)是否為1，如果等于1，則出隊(duì)列，否則將隊(duì)列A中的元素依次出隊(duì)列并放入隊(duì)列B，直到隊(duì)列A中的元素留下一個(gè)，然后隊(duì)列A出隊(duì)列，再把隊(duì)列B中的元素出隊(duì)列以此放入隊(duì)列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ù)字
把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱(chēng)之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請(qǐng)返回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)點(diǎn)在右，左順序
}
else if(rotateArray[mid] < rotateArray[j]){
j = mid; //7 8 1 2 3 4 旋轉(zhuǎn)點(diǎn)在左，右順序
}
else{ //1 0 1 1 1 或 1 1 1 0 1 順序部分為常數(shù)
i ++; //或 j --;
}
}
return rotateArray[i];
}
};
7、斐波那契數(shù)列
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)（從0開(kāi)始，第0項(xiàng)為0）。
n<=39
class Solution {
public:
int Fibonacci(int n) { //0 1 1 2 3 5 …,使用動(dòng)態(tài)規(guī)劃
int i = 0, j = 1;
while(n>0){
int tmp = j;
j = i+j;
i = tmp;
n--;
}
return i;
}
};
8、跳臺(tái)階
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法（先后次序不同算不同的結(jié)果）。
/*
最后一步跳1，有f(n-1)種情況
最后一步跳2，有f(n-2)種情況
共f(n)=f(n-1)+f(n-2)，1 1 2 3 5（斐波那契數(shù)列）使用動(dòng)態(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)跳臺(tái)階
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
//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的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？
/*
| | | | f(n-1)
| | | |
— — | | f(n-2)
— — | |
f(n) = f(n-1) + f(n-2),1 2 3 5 8…,動(dòng)態(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、二進(jìn)制中1的個(gè)數(shù)
輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。
/*
將n與n-1相與會(huì)把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進(jìn)制
return a.count(); //返回1的個(gè)數(shù)
}
};
12、數(shù)值的整數(shù)次方
給定一個(gè)double類(lèi)型的浮點(diǎn)數(shù)base和int類(lèi)型的整數(shù)exponent。求base的exponent次方。
/*
10^1101 = 10^0001*10^0100*10^1000，即base*1 * base^2 * base^4 * …
通過(guò)&1和>>1來(lái)逐位讀取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ù)前面
輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。
/*
要想保證原有次序，則只能順次移動(dòng)或相鄰交換。
1.i從左向右遍歷，找到第一個(gè)偶數(shù)。
2.j從i+1開(kāi)始向后找，找到第一個(gè)奇數(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個(gè)結(jié)點(diǎn)
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
/*
兩指針指向頭結(jié)點(diǎn)，
第一個(gè)指針走(k-1)步，到k節(jié)點(diǎn)
兩個(gè)指針同時(shí)往后移動(dòng)，當(dāng)?shù)谝粋€(gè)結(jié)點(diǎn)到達(dá)末尾的時(shí)候，第二個(gè)結(jié)點(diǎn)所在位置就是倒數(shù)第k個(gè)節(jié)點(diǎn)
*/
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)鏈表
輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
/*
1 2 3 4 5
遍歷鏈表，當(dāng)前值為4時(shí)，相當(dāng)于新建值為4的鏈表node，node->next = 前面鏈表反轉(zhuǎn)，node即為所求
當(dāng)前值為5時(shí)，相當(dāng)于新建值為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、合并兩個(gè)排序的鏈表
輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿(mǎn)足單調(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; //標(biāo)記位置
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、樹(shù)的子結(jié)構(gòu)
輸入兩棵二叉樹(shù)A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹(shù)不是任意一個(gè)樹(shù)的子結(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、二叉樹(shù)的鏡像
操作給定的二叉樹(shù)，將其變換為源二叉樹(shù)的鏡像。
二叉樹(shù)的鏡像定義： 源二叉樹(shù) 8 / \ 6 10 / \ / \ 5 7 9 11 鏡像二叉樹(shù) 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í)針打印矩陣
輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(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)，請(qǐng)?jiān)谠擃?lèi)型中實(shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)（時(shí)間復(fù)雜度應(yīng)為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不壓;小于等于，兩棧同時(shí)壓入
出棧，如果兩棧頂元素不等，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、棧的壓入、彈出序列
輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個(gè)序列的長(zhǎng)度是相等的）
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、從上往下打印二叉樹(shù)
從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。
/*
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ù)的后序遍歷序列
輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。
/*
二叉搜索樹(shù)BST 左子樹(shù)值都比root小，右子樹(shù)值都比root大。
去掉最后一個(gè)元素root，其他分成兩段:
前一段（左子樹(shù)）小于x，后一段（右子樹(shù)）大于x，且這兩段（子樹(shù)）都是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++; //找到滿(mǎn)足BST的右子樹(shù)開(kāi)頭
for(int j=i;j<r;j++) if(arr[j] < arr[r]) return false; //判斷剩下是否為右子樹(shù)
return isok(arr,l,i-1)&& isok(arr,i,r-1);
}
};
24、二叉樹(shù)中和為某一值的路徑
輸入一顆二叉樹(shù)的根節(jié)點(diǎn)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的list中，數(shù)組長(zhǎng)度大的數(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、復(fù)雜鏈表的復(fù)制
輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
/*
復(fù)制節(jié)點(diǎn)，如：復(fù)制節(jié)點(diǎn)A得到A1，將A1插入節(jié)點(diǎn)A后面
復(fù)制random，遍歷鏈表，A1->random = A->random->next;
將鏈表拆分成原鏈表和復(fù)制后的鏈表
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
if(!pHead) return NULL;
RandomListNode* cur = pHead;//從頭復(fù)制節(jié)點(diǎn) 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;//從頭復(fù)制random,A1->random = A->random->next;
while(cur){
if(cur -> random) cur -> next -> random = cur -> random -> next;
cur = cur -> next -> next;
}
cur = pHead;//從頭將鏈表拆分成原鏈表和復(fù)制后的鏈表
RandomListNode* res = cur -> next; //復(fù)制后的鏈表,標(biāo)記位置
RandomListNode* tmp;
while(cur -> next){
tmp = cur -> next;
cur -> next = tmp -> next;
cur = tmp;
}
return res;
}
};
26、二叉搜索樹(shù)與雙向鏈表
輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
//樹(shù)的線索化，利用了二叉樹(shù)結(jié)點(diǎn)中的空指針，讓它們分別指向本結(jié)點(diǎn)的前驅(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){ //中序遍歷第一個(gè)，即樹(shù)的左下角
head = root;
res = root;
}
else{
head -> right = root;
root -> left = head;
head = root;
}
helper(root->right);
}
};
27、字符串的排列
輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
輸入一個(gè)字符串,長(zhǎng)度不超過(guò)9(可能有字符重復(fù)),字符只包括大小寫(xiě)字母。
/*
問(wèn)題轉(zhuǎn)換為先固定第一個(gè)字符，求剩余字符的排列
再把第一個(gè)字符與后面每一個(gè)字符交換，并同樣遞歸獲得首位后面的字符串組合
a b b c:
a+f(bbc),b+f(abc),c+f(cbba); 遍歷出所有可能出現(xiàn)在第一個(gè)位置的字符
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ù)超過(guò)一半的數(shù)字
數(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。如果不存在則輸出0。
/*
如果重復(fù)的次數(shù)超過(guò)一半的話，一定有相鄰的數(shù)字相同這種情況的
對(duì)數(shù)組同時(shí)去掉兩個(gè)不同的數(shù)字，到最后剩下的一個(gè)數(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，其時(shí)間復(fù)雜度為O(NlogN)并非最優(yōu)
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
// 因?yàn)橛玫搅藄ort，時(shí)間復(fù)雜度O(NlogN)，并非最優(yōu)
if(numbers.empty()) return 0;
sort(numbers.begin(),numbers.end());
int middle = numbers[numbers.size()/2];//假設(shè)存在眾數(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個(gè)數(shù)
輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4,。
/*
基于堆排序算法，構(gòu)建最大堆。時(shí)間復(fù)雜度為O(nlogk)
用最大堆保存這k個(gè)數(shù)，每次只和堆頂比，如果比堆頂小，刪除堆頂，新數(shù)入堆
如果用快速排序，時(shí)間復(fù)雜度為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偶爾會(huì)拿些專(zhuān)業(yè)問(wèn)題來(lái)忽悠那些非計(jì)算機(jī)專(zhuān)業(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è)為止)。給一個(gè)數(shù)組，返回它的最大連續(xù)子序列的和，你會(huì)不會(huì)被他忽悠??？(子向量的長(zhǎng)度至少是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次,但是對(duì)于后面問(wèn)題他就沒(méi)轍了。ACMer希望你們幫幫他,并把問(wèn)題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)（從1 到 n 中1出現(xiàn)的次數(shù)）。
/*
n=10917 1~10917
所有數(shù)里在個(gè)位的1的數(shù)量：
前面為0~1090，個(gè)位后無(wú)，排列組合共1*1091種情況；前面為1091時(shí)，個(gè)位后為1。總共：1*1091+1(m=1，情況3)
所有數(shù)里在十位的1的數(shù)量：
前面為0~108，十位后為0~9，排列組合共10*109種情況；前面為109時(shí)，十位后為0~7。總共：10*109+8(m=8，情況2)
所有數(shù)里在百位的1的數(shù)量：
前面為0~9，百位后為0~99，排列組合共100*10種情況；前面為10時(shí)，百位后為0~99?？偣玻?00*10+100(m=100，情況3)
所有數(shù)里在千位的1的數(shù)量：
前面為0~0，千位后為0~999，排列組合共1000*1種情況；前面為1時(shí)，千位后沒(méi)有滿(mǎn)足的。總共：1000*1+0(m=0，情況1)
所有數(shù)里在萬(wàn)位的1的數(shù)量：
前面為無(wú)，萬(wàn)位后為0~917?？偣玻?000*0+918(m=918，情況2)
精髓在于后面部分m值分三種情況：
①當(dāng)前位為0時(shí)，m=0；②當(dāng)前位為1時(shí)，m=后面值+1；③當(dāng)前位為2~9時(shí)，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ù)
輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3，32，321}，則打印出這三個(gè)數(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ù)稱(chēng)作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，但14不是，因?yàn)樗|(zhì)因子7。 習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第N個(gè)丑數(shù)。
/*
如果p是丑數(shù)，那么p=2^x * 3^y * 5^z, 且x,y,z需滿(mǎn)足是前面的丑數(shù)
初始x=y=z=1， 2^x、3^y、5^z最小的數(shù)2^x加進(jìn)結(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、第一個(gè)只出現(xiàn)一次的字符
在一個(gè)字符串(0<=字符串長(zhǎng)度<=10000，全部由字母組成)中找到第一個(gè)只出現(xiàn)一次的字符,并返回它的位置, 如果沒(méi)有則返回 -1（需要區(qū)分大小寫(xiě)）.
class Solution {
public:
int FirstNotRepeatingChar(string str) {
//字符在計(jì)算機(jī)中以ASCII碼的形式存儲(chǔ)，當(dāng)字符作為數(shù)組下標(biāo)時(shí)，其表示的下標(biāo)值為該字符的ASCII碼的十進(jìn)制值
//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ù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)?。輸入一個(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對(duì)1000000007取模的結(jié)果輸出。 即輸出P%1000000007
輸入描述:
題目保證輸入的數(shù)組中沒(méi)有的相同的數(shù)字
數(shù)據(jù)范圍：對(duì)于%50的數(shù)據(jù),size<=10^4對(duì)于%75的數(shù)據(jù),size<=10^5對(duì)于%100的數(shù)據(jù),size<=2*10^5
示例:
輸入 1,2,3,4,5,6,7,0
輸出 7
/*
先把數(shù)組分割成子數(shù)組，先統(tǒng)計(jì)出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目，然后再統(tǒng)計(jì)出兩個(gè)相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目
在統(tǒng)計(jì)逆序?qū)Φ倪^(guò)程中，還需要對(duì)數(shù)組進(jìn)行排序,每一次比較的時(shí)候
都把較大的數(shù)字從后面往前復(fù)制到一個(gè)輔助數(shù)組中，確保輔助數(shù)組copy中的數(shù)字是遞增排序的
交換copy和data:在每次的操作中，當(dāng)前傳入函數(shù)中第一項(xiàng)，比較的結(jié)果都存放到第二項(xiàng)中,需要交叉保證下一次是排序的
輸入[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的話最后一個(gè)例子會(huì)溢出測(cè)試不通過(guò)
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、兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)
輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
//找出2個(gè)鏈表的長(zhǎng)度，然后讓長(zhǎng)的先走兩個(gè)鏈表的長(zhǎng)度差，然后再一起走
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)計(jì)一個(gè)數(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){ //找到了一個(gè)k，往data兩邊擴(kuò)展，統(tǒng)計(jì)k的個(gè)數(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、二叉樹(shù)的深度
輸入一棵二叉樹(shù)，求該樹(shù)的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過(guò)的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹(shù)的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹(shù)的深度。
/*
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、平衡二叉樹(shù)
輸入一棵二叉樹(shù)，判斷該二叉樹(shù)是否是平衡二叉樹(shù)。
class Solution {
public:
//左右子樹(shù)均為平衡二叉樹(shù)，且左右子樹(shù)層高不超過(guò)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ù)字
一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫(xiě)程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。
/*
異或性質(zhì)：
交換律：a ^ b ^ c <=> a ^ c ^ b,倆兩相同的移到一起
相同的數(shù)異或?yàn)?: n ^ n => 0
任何數(shù)于0異或?yàn)槿魏螖?shù) 0 ^ n => n
遍歷異或后，只剩下兩單個(gè)的異或了，結(jié)果res的二進(jìn)制至少有一位為1
取第一個(gè)1所在的位數(shù)index，原數(shù)組分成第index位為1和為0
相同的數(shù)肯定在一個(gè)組，兩個(gè)單的在不同的組
*/
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){ //當(dāng)前位為0且未溢出
index++; n >>= 1;
}
return index;
}
};
41、和為S的連續(xù)正數(shù)序列
小明很喜歡數(shù)學(xué),有一天他在做數(shù)學(xué)作業(yè)時(shí),要求計(jì)算出9~16的和,他馬上就寫(xiě)出了正確答案是100。但是他并不滿(mǎn)足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個(gè)數(shù))。沒(méi)多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22?，F(xiàn)在把問(wèn)題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!
輸出描述:
輸出所有和為S的連續(xù)正數(shù)序列。序列內(nèi)按照從小至大的順序，序列間按照開(kā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的兩個(gè)數(shù)字
輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S，在數(shù)組中查找兩個(gè)數(shù)，使得他們的和正好是S，如果有多對(duì)數(shù)字的和等于S，輸出兩個(gè)數(shù)的乘積最小的。
輸出描述:
對(duì)應(yīng)每個(gè)測(cè)試案例，輸出兩個(gè)數(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)字符串
匯編語(yǔ)言中有一種移位指令叫做循環(huán)左移（ROL），現(xiàn)在有個(gè)簡(jiǎn)單的任務(wù)，就是用字符串模擬這個(gè)指令的運(yùn)算結(jié)果。對(duì)于一個(gè)給定的字符序列S，請(qǐng)你把其循環(huán)左移K位后的序列輸出。例如，字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果，即“XYZdefabc”。是不是很簡(jiǎn)單？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); //從下標(biāo)n開(kāi)始的len個(gè)字符
}
};
44、翻轉(zhuǎn)單詞順序列
?？妥罱鼇?lái)了一個(gè)新員工Fish，每天早晨總是會(huì)拿著一本英文雜志，寫(xiě)些句子在本子上。同事Cat對(duì)Fish寫(xiě)的內(nèi)容頗感興趣，有一天他向Fish借來(lái)翻看，但卻讀不懂它的意思。例如，“student. a am I”。后來(lái)才意識(shí)到，這家伙原來(lái)把句子單詞的順序翻轉(zhuǎn)了，正確的句子應(yīng)該是“I am a student.”。Cat對(duì)一一的翻轉(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今天心情特別好,因?yàn)樗ベI(mǎi)了一副撲克牌,發(fā)現(xiàn)里面居然有2個(gè)大王,2個(gè)小王(一副牌原本是54張_)…他隨機(jī)從中抽出了5張牌,想測(cè)測(cè)自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買(mǎi)體育彩票,嘿嘿?。?ldquo;紅心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決定去買(mǎi)體育彩票啦。 現(xiàn)在,要求你使用這幅牌模擬上面的過(guò)程,然后告訴我們LL的運(yùn)氣如何， 如果牌能組成順子就輸出true，否則就輸出false。為了方便起見(jiàn),你可以認(rèn)為大小王是0。
/*
max 記錄 最大值,min 記錄 最小值,min ,max 都不記0
滿(mǎn)足條件 max - min <5;除0外沒(méi)有重復(fù)的數(shù)字(牌);數(shù)組長(zhǎng)度 為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; //重復(fù)
else{
if(tmp < min) min = tmp;
if(tmp > max) max = tmp;
flag[tmp] = 1;
}
}
delete[] flag;
return max-min<5;
}
};
46、孩子們的游戲（圓圈中最后剩下的數(shù)）
每年六一兒童節(jié),?？投紩?huì)準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準(zhǔn)備了一些小游戲。其中,有個(gè)游戲是這樣的:首先,讓小朋友們圍成一個(gè)大圈。然后,他隨機(jī)指定一個(gè)數(shù)m,讓編號(hào)為0的小朋友開(kāi)始報(bào)數(shù)。每次喊到m-1的那個(gè)小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個(gè)小朋友開(kāi)始,繼續(xù)0…m-1報(bào)數(shù)…這樣下去…直到剩下最后一個(gè)小朋友,可以不用表演,并且拿到?？兔F的“名偵探柯南”典藏版(名額有限哦!!_)。請(qǐng)你試著想下,哪個(gè)小朋友會(huì)得到這份禮品呢？(注：小朋友的編號(hào)是從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; //跳過(guò)被刪除的對(duì)象
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)鍵字及條件判斷語(yǔ)句（A?B:C）。
/*
int Sum_Solution(int n) {
if(n == 0) return 0;
return n+Sum_Solution(n-1);
}
將此段代碼改寫(xiě)成不使用for、while、if、else、switch、case等關(guān)鍵字及條件判斷語(yǔ)句
*/
class Solution {
public:
int Sum_Solution(int n) {
int res = n;
res && (res+=Sum_Solution(n-1));
//當(dāng)n==0時(shí)，只執(zhí)行前面的判斷，為false，然后直接返回0；
//當(dāng)n>0時(shí)，執(zhí)行sum+=Sum_Solution(n-1)，實(shí)現(xiàn)遞歸計(jì)算Sum_Solution(n)
return res;
}
};
48、不用加減乘除做加法
寫(xiě)一個(gè)函數(shù)，求兩個(gè)整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+、-、*、/四則運(yùn)算符號(hào)。
/*
兩數(shù)相與再左移一位，表示相加進(jìn)位的值 101&111=101 左移1，1010
兩數(shù)異或，表示相加不算進(jìn)位的值 101^111=010
兩者相加為和，(101&111)<<1 + 101^111 = 1100,即調(diào)用函數(shù)本身，直到進(jìn)位為0
*/
class Solution {
public:
int Add(int num1, int num2) {
while(num2!=0){
int tmp = num1^num2; //相加不算進(jìn)位的值
num2 = (num1&num2)<<1; //相加進(jìn)位的值
num1 = tmp;
}
return num1;
}
};
49、把字符串轉(zhuǎn)換成整數(shù)
將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)(實(shí)現(xiàn)Integer.valueOf(string)的功能，但是string不符合數(shù)字要求時(shí)返回0)，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫(kù)函數(shù)。 數(shù)值為0或者字符串不是一個(gè)合法的數(shù)值則返回0。
輸入描述:
輸入一個(gè)字符串,包括數(shù)字字母符號(hào),可以為空
輸出描述:
如果是合法的數(shù)值表達(dá)則返回該數(shù)字，否則返回0
輸入: +2147483647 , 1a33
輸出: 2147483647 , 0
/*
字符"0123456789"的值是連續(xù)的，如果c"0123456789"范圍內(nèi)
int a = c - '0'就是對(duì)應(yīng)整數(shù)值
從后往前，最后判斷符號(hào)位
*/
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ù)組中重復(fù)的數(shù)字
在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 例如，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2。
/*
數(shù)字的范圍保證在0 ~ n-1 之間，所以可以利用現(xiàn)有數(shù)組設(shè)置標(biāo)志
當(dāng)一個(gè)數(shù)字i被訪問(wèn)過(guò)后，可以設(shè)置對(duì)應(yīng)位上的數(shù)numbers[i] += n
再次訪問(wèn)i時(shí)，發(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ù)組
給定一個(gè)數(shù)組A[0,1,…,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。
/*
1 第一項(xiàng)左側(cè)
a[0] 第二項(xiàng)左側(cè)
a[0]*a[1]
a[0]*a[1]*a[2]
a[0]*a[1]*a[2]...*a[n-2] 第n項(xiàng)左側(cè)
1 第n項(xiàng)右側(cè)
a[n-1]
a[n-1]*a[n-2]
a[n-1]*a[n-2]*a[n-3]...*a[2] 第二項(xiàng)左側(cè)
a[n-1]*a[n-2]*a[n-3]...*a[1] 第一項(xiàng)右側(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、正則表達(dá)式匹配
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)匹配包括’.‘和’‘的正則表達(dá)式。模式中的字符’.‘表示任意一個(gè)字符，而’'表示它前面的字符可以出現(xiàn)任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個(gè)模式。例如，字符串"aaa"與模式"a.a"和"abaca"匹配，但是與"aa.a"和"ab*a"均不匹配
/*
當(dāng)?shù)诙€(gè)字符不是“*”時(shí)：
1、第一個(gè)字符匹配，字符串和模式后移1個(gè)字符，繼續(xù)匹配
2、第一個(gè)字符不匹配，返回false
當(dāng)?shù)诙€(gè)字符是“*”時(shí)：
1、第一個(gè)字符不匹配，模式后移2個(gè)字符，繼續(xù)匹配
2、第一個(gè)字符匹配，可以有3種情況：
（1）模式后移2字符，相當(dāng)于x*被忽略，x出現(xiàn)0次；
（2）字符串后移1字符，模式后移2字符，相當(dāng)于x出現(xiàn)一次；
（3）字符串后移1字符，模式不變，相當(dāng)于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ù)值的字符串
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示數(shù)值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。
/*
1、+、-
第一次出現(xiàn)+-符號(hào)，且不在首位，必須緊接在e之后
第二次出現(xiàn)+-符號(hào)，必須緊接在e之后
2、e、E
e后不為空
不能雙e
3、.
.前不能有.或e
4、其他
return false
*/
class Solution {
public:
bool isNumeric(char* string) {
// 標(biāo)記符號(hào)、小數(shù)點(diǎn)、e是否出現(xiàn)過(guò)
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、字符流中第一個(gè)不重復(fù)的字符
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)找出字符流中第一個(gè)只出現(xiàn)一次的字符。例如，當(dāng)從字符流中只讀出前兩個(gè)字符"go"時(shí)，第一個(gè)只出現(xiàn)一次的字符是"g"。當(dāng)從該字符流中讀出前六個(gè)字符“google"時(shí)，第一個(gè)只出現(xiàn)一次的字符是"l"。
輸出描述:
如果當(dāng)前字符流沒(méi)有存在出現(xiàn)一次的字符，返回#字符。
/*
字符在計(jì)算機(jī)中以ASCII碼的形式存儲(chǔ)，當(dāng)字符作為數(shù)組下標(biāo)時(shí)，其表示的下標(biāo)值為該字符的ASCII碼的十進(jìn)制值
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é)點(diǎn)
給一個(gè)鏈表，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)，否則，輸出null。
/*
如果有環(huán)，快慢指針總會(huì)相遇
1——2——3——4——5——6
| |
9——8——7
假設(shè)快慢指針相遇在6，有1~6走的=6~6走的
1~6走的 = 1~入環(huán)點(diǎn)+入環(huán)點(diǎn)~6
6~6走的 = 6~入環(huán)點(diǎn)+入環(huán)點(diǎn)~6
則當(dāng)快指針從1重新開(kāi)始，兩指針?biāo)俣认嗤?，再次相遇即為入口?jié)點(diǎn)
*/
/*
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é)點(diǎn)
if(hasLoop){
fast = pHead;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return slow;
}
return NULL;
}
};
56、刪除鏈表中重復(fù)的結(jié)點(diǎn)
在一個(gè)排序的鏈表中，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留，返回鏈表頭指針。 例如，鏈表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);//設(shè)為幾無(wú)所謂
ListNode* h = root; //標(biāo)記當(dāng)前位置
h->next = pHead;
while(h->next && h->next->next){//至少兩個(gè)節(jié)點(diǎn)
ListNode* tmp = h->next->next;
if(h->next->val == tmp->val){//兩節(jié)點(diǎn)相同
while(tmp && h->next->val == tmp->val){
tmp = tmp->next;
}
h->next = tmp; //刪除操作
}
else h = h->next;
}
return root->next;
}
};
57、二叉樹(shù)的下一個(gè)結(jié)點(diǎn)
給定一個(gè)二叉樹(shù)和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。注意，樹(shù)中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)，同時(shí)包含指向父結(jié)點(diǎn)的指針。
/*
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，有右子樹(shù)，返回右子樹(shù)的左下角
情況2，無(wú)右子樹(shù)，且是父結(jié)點(diǎn)的左子樹(shù)，返回父結(jié)點(diǎn)
情況3，無(wú)右子樹(shù)，且是父結(jié)點(diǎn)的右子樹(shù)，返回父結(jié)點(diǎn)的左上角的父結(jié)點(diǎn)
*/
/*
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、對(duì)稱(chēng)的二叉樹(shù)
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)判斷一顆二叉樹(shù)是不是對(duì)稱(chēng)的。注意，如果一個(gè)二叉樹(shù)同此二叉樹(shù)的鏡像是同樣的，定義其為對(duì)稱(chēng)的。
/*
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個(gè)存在
}
};
59、按之字形順序打印二叉樹(shù)
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹(shù)，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類(lèi)推。
/*
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、把二叉樹(shù)打印成多行
從上到下按層打印二叉樹(shù)，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行。
/*
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、序列化二叉樹(shù)
請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來(lái)序列化和反序列化二叉樹(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());
/* 另一種寫(xiě)法，不用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、二叉搜索樹(shù)的第k個(gè)結(jié)點(diǎn)
給定一棵二叉搜索樹(shù)，請(qǐng)找出其中的第k小的結(jié)點(diǎn)。例如， （5，3，7，2，4，6，8） 中，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4。
/*
二叉搜索樹(shù)：左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值,右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值
二叉搜索樹(shù)按照中序遍歷得到遞增的順序，壓入棧，第k個(gè)結(jié)點(diǎn)就是結(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é)點(diǎn)數(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ù)
如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流，使用GetMedian()方法獲取當(dāng)前讀取數(shù)據(jù)的中位數(shù)。
/*
使用大小頂堆，中位數(shù)是大頂堆的根節(jié)點(diǎn)與小頂堆的根節(jié)點(diǎn)和的平均數(shù)
大頂堆,由大到小，存較小的數(shù) 7 6 5
小頂堆,由小到大，存較大的數(shù) 8 9 10
步驟：
第一個(gè)插入的元素裝大頂堆
1、每來(lái)一個(gè)插入的元素，比大頂堆堆頂元素小的裝大頂堆，否則裝小頂堆（保證大頂堆的數(shù)都比小頂堆的數(shù)?。?
2、判斷是否大頂堆裝多了，大頂堆最多比小頂堆多一個(gè)，如果是，將大頂堆堆頂元素插入小頂堆
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、滑動(dòng)窗口的最大值
給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動(dòng)窗口的大小3，那么一共存在6個(gè)滑動(dòng)窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對(duì)數(shù)組{2,3,4,2,6,2,5,1}的滑動(dòng)窗口有以下6個(gè)： {[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;//隊(duì)首為當(dāng)前窗口下最大值下標(biāo)
for(unsigned int i=0;i<num.size();i++){
while(!q.empty() && num[i]>num[q.back()]){//q刪掉所有比當(dāng)前元素小的，保證q降序
q.pop_back();
}
if(!q.empty() && q.front()+size == i){ //若隊(duì)首超過(guò)窗口位置,刪掉
q.pop_front();
}
q.push_back(i);
if(size && i+1>=size) res.push_back(num[q.front()]); //防止size=0
}
return res;
}
};
65、矩陣中的路徑
請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來(lái)判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個(gè)格子開(kāi)始，每一步可以在矩陣中向左，向右，向上，向下移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過(guò)了矩陣中的某一個(gè)格子，則之后不能再次進(jìn)入這個(gè)格子。 例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因?yàn)樽址牡谝粋€(gè)字符b占據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能再次進(jìn)入該格子。
class Solution {
public:
//用一個(gè)狀態(tài)數(shù)組保存之前訪問(wèn)過(guò)的字符，然后再分別按上，下，左，右遞歸
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、機(jī)器人的運(yùn)動(dòng)范圍
地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開(kāi)始移動(dòng)，每一次只能向左，右，上，下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。 例如，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18。但是，它不能進(jìn)入方格（35,38），因?yàn)?+5+3+8 = 19。請(qǐng)問(wèn)該機(jī)器人能夠達(dá)到多少個(gè)格子？
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;
}
};
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
- 這篇文章主要介紹了騰訊公司c++面試小結(jié)，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2020-03-02
這篇文章主要介紹了 C++ 面試題目(整理自?？途W(wǎng)),小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2020-02-13華為校招 C++崗面試經(jīng)歷總結(jié)【筆試+一面+二面+Offer】
這篇文章主要介紹了華為校招 C++崗面試經(jīng)歷,總結(jié)分析了華為校招C++崗位的筆試題,以及一面、二面到最終拿到Offer的經(jīng)歷與相關(guān)經(jīng)驗(yàn)感想,需要的朋友可以參考下2019-11-28- 這篇文章主要介紹了C++面試常見(jiàn)算法題與參考答案,總結(jié)分析了C++面試中遇到的常見(jiàn)算法題與相應(yīng)的參考答案,需要的朋友可以參考下2019-11-20
- 這篇文章主要介紹了C++必備面試題與參考答案,結(jié)合大量經(jīng)典實(shí)例總結(jié)分析了C++面試過(guò)程中經(jīng)常遇到的各種概念、原理、算法相關(guān)問(wèn)題及參考答案,需要的朋友可以參考下2019-10-31
- 這篇文章主要介紹了C/C++經(jīng)典面試題(附答案)，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-10-23
- 這篇文章主要介紹了C/C++求職者必備的20道面試題與參考答案,總結(jié)分析了C/C++相關(guān)的常見(jiàn)概念、原理、知識(shí)點(diǎn)與注意事項(xiàng),需要的朋友可以參考下2019-10-10
騰訊的外包c(diǎn)++面試經(jīng)歷總結(jié)
這篇文章主要介紹了騰訊的外包c(diǎn)++面試經(jīng)歷,總結(jié)記錄了一次騰訊C++面試的經(jīng)歷,包括面試的流程、面試題目與相應(yīng)的參考答案,需要的朋友可以參考下2019-09-29- 這篇文章主要介紹了阿里面試必會(huì)的20道C++面試題與參考答案,涉及C++指針、面向?qū)ο?、函?shù)等相關(guān)特性與使用技巧,需要的朋友可以參考下2019-09-26
- 這篇文章主要介紹了經(jīng)典C++筆試題目與參考答案,總結(jié)分析了C++常見(jiàn)的各種面試題目,包含C++常見(jiàn)知識(shí)點(diǎn)、技術(shù)難點(diǎn)、算法等,需要的朋友可以參考下2019-09-10
