1. 赋值运算符函数（或应说复制拷贝函数问题）
class A
{
private:
int value;
public:
A(int n) : value(n) {}
A(A O) { value = O.value; } // Compile Error : (const A& O)
};
因为，A a(0); A b = a; 就会使程序陷入死循环。
2. 实现 Singleton 模式 (C#)
（博客待加设计模式总结）
3.二维数组中的查找
Sample:
二维数组：Matrix[4][4]，行列都是递增。
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
判断 value = 7 是否在数组。
思路：从右上角开始，若大于 7 删去一列； 若小于 7 删去一行。
代码：
#include<iostream>
const int N = ;
int data[][N] = {{, , , },{ , , , },{, , , }, {, , , }}; bool find(int (*matrix)[N], int row, int column, int value)
{
int r = , c = column - ;
while(r < row && c >= )
{
if(matrix[r][c] == value) return true;
if(matrix[r][c] > value) --c;
else ++r;
}
return false;
} int main()
{
std::cout << find(data, , , ) << std::endl;
return ;
}
4.替换空格 时间：O(n) 空间：O(1)
Sample:
输入: S:"We are happy."
输出：S:"We%20are%20happy."
#include<stdio.h>
#include<string.h>
const int N = ;
/* length is the full capacity of the string, max number of elements is length-1*/
void ReplaceBank(char s[], int length){
if(s == NULL && length <= ) return; // program robustness
int nowLength = -, numberOfBlank = ;
while(s[++nowLength] != '\0'){
if(s[nowLength] == ' ') ++numberOfBlank;
}
int newLength = nowLength + numberOfBlank * ; // newLength is the number of elements
if(newLength >= length) return; int idOfNow = nowLength, idOfNew = newLength; // both point to '/0'
while(idOfNow >= ){ /* key program */
if(s[idOfNow] == ' ') {
strncpy(s+idOfNew-, "%20", );
idOfNew -= ;
--idOfNow;
}else
s[idOfNew--] = s[idOfNow--];
}
} int main(){
char s[N] = "We are happy.";
puts(s);
ReplaceBank(s,N);
puts(s);
return ;
}
Code
5.从尾到头打印链表
1. 询问是否可以改变链表结构，若可以，则空间O(1)；否则，
2. 使用栈，或者递归。
a. 使用栈：
#include <iostream>
#include <string>
#include <stack> struct LinkNode{
char e;
LinkNode *next;
}; void print(LinkNode *Head)
{
std::stack<char> st;
while(Head != NULL)
{
st.push(Head->e);
Head = Head->next;
}
while(!st.empty())
{
printf("%c ", st.top());
st.pop();
}
printf("\n");
} LinkNode* init(const std::string &s)
{
size_t i = ;
LinkNode *head, *p;
p = head = NULL;
while(i < s.length())
{
LinkNode *p2 = new LinkNode;
p2->e = s[i++]; p2->next = NULL;
if(head == NULL)
head = p = p2;
else
{
p->next = p2;
p = p->next;
}
}
return head;
}
void release(LinkNode *Head){
if(Head == NULL) return;
release(Head->next);
delete[] Head;
Head = NULL;
}
int main()
{
const std::string s = "ABCDEFG";
LinkNode *Head = init(s);
print(Head);
release(Head);
return ;
}
Code
b. 使用递归:
void RecursivePrint(LinkNode *Head)
{
if(Head == NULL) return;
RecursivePrint(Head->next);
printf("%c ", Head->e);
}
6. 重建二叉树
a. 前序 && 中序
#include <cstdio>
#include <queue>
struct BTNode{
int value;
BTNode *pLeft;
BTNode *pRight;
BTNode(int x) : value(x), pLeft(NULL), pRight(NULL) {}
}; BTNode* constructCore(int *startPreOrder, int *endPreOrder, int *startInOrder, int *endInOrder)
{
int rootValue = startPreOrder[];
BTNode *root = new BTNode(rootValue);
int *rootInOrder = startInOrder;
while(*rootInOrder != rootValue && rootInOrder <= endInOrder) ++rootInOrder;
if(*rootInOrder != rootValue) { printf("Invalid Input!"); return NULL; } int leftLength = rootInOrder - startInOrder;
if(leftLength > )
{
root->pLeft = constructCore(startPreOrder + , startPreOrder + leftLength,
startInOrder, startInOrder + leftLength - );
}
if(rootInOrder != endInOrder)
{
root->pRight = constructCore(startPreOrder + leftLength + , endPreOrder,
rootInOrder + , endInOrder);
}
return root;
} BTNode* construct(int *preOrder, int *inOrder, int length)
{
if(preOrder == NULL || inOrder == NULL || length <= )
return NULL;
return constructCore(preOrder, preOrder + length - , inOrder, inOrder + length -);
}
void print(BTNode *root)
{
if(root == NULL) return; std::queue<BTNode*> qu;
qu.push(root);
while(!qu.empty())
{
BTNode *p = qu.front();
qu.pop();
if(p->pLeft) qu.push(p->pLeft);
if(p->pRight) qu.push(p->pRight);
printf("%d ", p->value);
}
}
void release(BTNode *root)
{
if(root == NULL) return;
release(root->pLeft);
release(root->pRight);
delete[] root;
root = NULL;
} int main()
{
int preOrder[] = {, , , , , , , };
int inOrder[] = {, , , , , , , };
BTNode *root = construct(preOrder, inOrder, );
print(root);
release(root);
return ;
}
Code
二叉树的各种遍历：
#include <cstdio>
#include <queue>
#include <stack>
struct BTNode{
int value;
BTNode *pLeft;
BTNode *pRight;
BTNode(int x) : value(x), pLeft(NULL), pRight(NULL) {}
}; BTNode* constructCore(int *startPreOrder, int *endPreOrder, int *startInOrder, int *endInOrder)
{
int rootValue = startPreOrder[];
BTNode *root = new BTNode(rootValue);
int *rootInOrder = startInOrder;
while(*rootInOrder != rootValue && rootInOrder <= endInOrder) ++rootInOrder;
if(*rootInOrder != rootValue) { printf("Invalid Input!\n"); return NULL; } int leftLength = rootInOrder - startInOrder;
if(leftLength > )
{
root->pLeft = constructCore(startPreOrder + , startPreOrder + leftLength,
startInOrder, startInOrder + leftLength - );
}
if(rootInOrder != endInOrder)
{
root->pRight = constructCore(startPreOrder + leftLength + , endPreOrder,
rootInOrder + , endInOrder);
}
return root;
} BTNode* construct(int *preOrder, int *inOrder, int length)
{
if(preOrder == NULL || inOrder == NULL || length <= )
return NULL;
return constructCore(preOrder, preOrder + length - , inOrder, inOrder + length -);
}
void levelOrderPrint(BTNode *root)
{
if(root == NULL) return;
printf("BFS：");
std::queue<BTNode*> qu;
qu.push(root);
while(!qu.empty())
{
BTNode *p = qu.front();
qu.pop();
if(p->pLeft) qu.push(p->pLeft);
if(p->pRight) qu.push(p->pRight);
printf("%-3d ", p->value);
}
printf("\n");
}
void preORderPrint2(BTNode *root) // preORder
{
if(root == NULL) return;
printf("DLR: ");
std::stack<BTNode*> st;
st.push(root);
while(!st.empty())
{
BTNode *p = st.top();
st.pop();
if(p->pRight) st.push(p->pRight);
if(p->pLeft) st.push(p->pLeft);
printf("%-3d ", p->value);
}
printf("\n");
}
void inOrderPrint3(BTNode *root) // inOrder
{
if(root == NULL) return;
printf("LDR: ");
std::stack<BTNode*> st;
st.push(root);
BTNode *p = root;
while(p->pLeft)
{
st.push(p->pLeft);
p = p->pLeft;
}
while(!st.empty())
{
p = st.top();
st.pop();
if(p->pRight)
{
BTNode *q = p->pRight;
st.push(q);
while(q->pLeft) { st.push(q->pLeft); q = q->pLeft; }
}
printf("%-3d ", p->value);
}
printf("\n");
}
void postOrderPrint4(BTNode *root) // postOrder
{
if(root == NULL) return;
printf("LRD: ");
std::stack<BTNode*>st;
st.push(root);
BTNode *p = root;
while(p->pLeft || p->pRight)
{
while(p->pLeft) { st.push(p->pLeft); p = p->pLeft; }
if(p->pRight) { st.push(p->pRight); p = p->pRight; }
}
//bool tag = true;
while(!st.empty())
{
BTNode *q = st.top();
st.pop();
if(!st.empty())
{
p = st.top();
if(p->pRight && p->pRight != q)
{
st.push(p->pRight); p = p->pRight;
while(p->pLeft || p->pRight)
{
while(p->pLeft) { st.push(p->pLeft); p = p->pLeft; }
if(p->pRight) { st.push(p->pRight); p = p->pRight; }
}
}
}
printf("%-3d ", q->value);
}
printf("\n");
}
void DFSPrint(BTNode *root,const int nVertex)
{
if(root == NULL) return;
printf("DFS: ");
bool *visit = new bool[nVertex];
memset(visit, false, nVertex);
std::stack<BTNode*> st;
st.push(root);
visit[root->value] = true;
while(!st.empty())
{
BTNode *p = st.top();
st.pop();
if(p->pRight && !visit[p->pRight->value]) { st.push(p->pRight); visit[p->pRight->value] = true; }
if(p->pLeft && !visit[p->pLeft->value]) { st.push(p->pLeft); visit[p->pLeft->value];}
printf("%-3d ", p->value);
}
printf("\n");
}
void release(BTNode *root)
{
if(root == NULL) return;
release(root->pLeft);
release(root->pRight);
delete[] root;
root = NULL;
} int main()
{
int preOrder[] = {, , , , , , , , , , , , , , };
int inOrder[] = {, , , , , , , , , , , , , , };
BTNode *root = construct(preOrder, inOrder, );
levelOrderPrint(root);
preORderPrint2(root);
inOrderPrint3(root);
postOrderPrint4(root);
DFSPrint(root, +);
release(root);
return ;
}
Code
7.用两个栈实现队列
#include <cstdio>
#include <stack>
#include <exception>
template<typename T> class CQueue
{
public:
void appendTail(T x);
T deleteHead();
private:
std::stack<T> st1;
std::stack<T> st2;
};
template<typename T>void CQueue<T>::appendTail(T x)
{
st1.push(x);
}
template<typename T>T CQueue<T>::deleteHead()
{
if(st2.empty())
{
if(st1.empty()) throw new std::exception("queue is empty!");
while(!st1.empty())
{
st2.push(st1.top());
st1.pop();
}
}
T v = st2.top();
st2.pop();
return v;
} int main()
{
printf("Test int:\n");
CQueue<int> qu;
qu.appendTail();
qu.appendTail();
printf("%d\n",qu.deleteHead());
printf("%d\n",qu.deleteHead()); printf("Test char*:\n");
CQueue<char*> qu2;
qu2.appendTail("Hello");
qu2.appendTail("World!");
printf("%s\n",qu2.deleteHead());
printf("%s\n",qu2.deleteHead());
//printf("%s\n",qu2.deleteHead());
return ;
}
Code
8.旋转数组的最小数字
#include <iostream>
using namespace std; int MinInorder(int *numbers, int low, int high)
{
int minNum = numbers[low];
while(++low <= high)
{
if(numbers[low] < minNum)
minNum = numbers[low];
}
return minNum;
} int Min(int *numbers, int length)
{
if(numbers == NULL || length <= ) throw new exception("Invalid parameters!");
int low = , high = length - ;
int mid = low; // note
while(numbers[low] >= numbers[high]) // note >=
{
if(high - low == )
{
mid = high;
break;
}
mid = (low + high) >> ;
if(numbers[mid] == numbers[low] && numbers[mid] == numbers[high]) return MinInorder(numbers, low, high);
else if(numbers[mid] >= numbers[low]) low = mid;
else if(numbers[mid] <= numbers[high]) high = mid;
}
return numbers[mid];
} int main()
{
int test1[] = {, , , , };
cout << "Test1: " << Min(test1, sizeof(test1)/) << endl; int test2[] = {, , , , };
cout << "Test2: " << Min(test2, sizeof(test2)/) << endl; return ;
}
Code
9.斐波那契数列第 n 项
a. 动态规划（从低到高保存结果）
int Fibonacci1(unsigned long long N)
{
long long fibN;
long long a[] = {0, 1};
if(N < 2) return a[N];
while(N >= 2)
{
fibN = (a[0] + a[1]) % M;
a[0] = a[1];
a[1] = fibN;
--N;
}
return (int)fibN;
}
b1.矩阵二分乘（递归）
const int M = 1e+9 +7 ;
struct Matrix{
long long e[2][2];
};
Matrix Mat; Matrix multiplyMatrix(Matrix &A, Matrix &B)
{
Matrix C;
for(int i = 0; i < 2; ++i){
for(int j = 0; j < 2; ++j){
C.e[i][j] = ((A.e[i][0] * B.e[0][j]) % M + (A.e[i][1] * B.e[1][j]) % M) % M;
}
}
return C;
}
Matrix getMatrix(long long n)
{
if(n == 1) return Mat;
Matrix tem = getMatrix(n>>1);
tem = multiplyMatrix(tem,tem);
if((n & 0x1) == 0) return tem;
else
return multiplyMatrix(Mat,tem);
} int Fibonacci2(long long N)
{
if(N == 0) return 0;
if(N == 1) return 1;
Mat.e[0][0] = 1; Mat.e[0][1] = 1;
Mat.e[1][0] = 1; Mat.e[1][1] = 0;
Matrix result = getMatrix(N-1);
return (int)result.e[0][0];
}
b2. 矩阵二分乘(非递归)
const int M = 1000000007;
struct Matrix{
long long e[2][2];
};
Matrix Mat; Matrix multiplyMatrix(Matrix &A, Matrix &B)
{
Matrix C;
for(int i = 0; i < 2; ++i){
for(int j = 0; j < 2; ++j){
C.e[i][j] = ((A.e[i][0] * B.e[0][j]) % M + (A.e[i][1] * B.e[1][j]) % M) % M;
}
}
return C;
}
Matrix getMatrix(Matrix base, long long N)
{
Matrix T; // set one unit matrix
T.e[0][0] = T.e[1][1] = 1;
T.e[0][1] = T.e[1][0] = 0;
while(N - 1 != 0)
{
if(N & 0x1) T = multiplyMatrix(T, base);
base = multiplyMatrix(base, base);
N >>= 1;
}
return multiplyMatrix(T, base);
} int Fibonacci2(long long N)
{
if(N == 0) return 0;
if(N == 1) return 1;
Mat.e[0][0] = 1; Mat.e[0][1] = 1;
Mat.e[1][0] = 1; Mat.e[1][1] = 0;
Matrix result = getMatrix(Mat, N-1);
return (int)result.e[0][0];
}
两种方法效率的比较：
#include <iostream>
#include <ctime>
using namespace std;
const int M = ;
struct Matrix{
long long e[][];
};
Matrix Mat; Matrix multiplyMatrix(Matrix &A, Matrix &B)
{
Matrix C;
for(int i = ; i < ; ++i){
for(int j = ; j < ; ++j){
C.e[i][j] = ((A.e[i][] * B.e[][j]) % M + (A.e[i][] * B.e[][j]) % M) % M;
}
}
return C;
}
Matrix getMatrix(Matrix base, long long N)
{
Matrix T; // set one unit matrix
T.e[][] = T.e[][] = ;
T.e[][] = T.e[][] = ;
while(N - != )
{
if(N & 0x1) T = multiplyMatrix(T, base);
base = multiplyMatrix(base, base);
N >>= ;
}
return multiplyMatrix(T, base);
} int Fibonacci2(long long N)
{
if(N == ) return ;
if(N == ) return ;
Mat.e[][] = ; Mat.e[][] = ;
Mat.e[][] = ; Mat.e[][] = ;
Matrix result = getMatrix(Mat, N-);
return (int)result.e[][];
} int Fibonacci1(long long N)
{
long long fibN;
long long a[] = {, };
if(N < ) return (int)a[N];
while(N >= )
{
fibN = (a[] + a[]) % M;
a[] = a[];
a[] = fibN;
--N;
}
return (int)fibN;
} int main()
{
unsigned long long N;
while(cin >> N)
{
/* method 1: DP */
clock_t start = clock();
int fibN = Fibonacci1(N);
clock_t end = clock();
cout << "method1：" << fibN << " time: " << end-start << "ms" << endl;
/* method 2 */
start = clock();
fibN = Fibonacci2(N);
end = clock();
cout << "method2：" << fibN << " time: " << end-start << "ms" << endl;
}
return ;
}
Code
10.一个整数的二进制表示中 1 的个数。（包含正负数）
需要注意的是：—1 >> (任意位) == —1； 负数 >> +∞ == —1。 （（—1）10 == （0xffffffff）16 ）
a. 利用辅助变量，每次判断 n 的一位。
int numberOf1(int n)
{
int count = ;
int flag = ;
while(flag)
{
if(n & flag) count ++;
flag <<= ;
}
return count;
}
Code
b. 利用 n 的性质。
#include <iostream>
int numberOf1(int n){
int count = ;
while(n){
count ++;
n &= (n-);
}
return count;
}
int main(){
int N;
while(std::cin >> N){
std::cout << "has 1: " << numberOf1(N) << std::endl;
}
return ;
}
Code