1.二维数组中的查找
/*
题目：在一个二维数组中，没一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
*/
#include<stdio.h>
#include<string.h> // 从右上角开始比较 bool Find(int *matrix, int rows, int columns, int number) {
bool found = false;
if (matrix != NULL && rows > && columns > ) {
int row = ;
int column = columns - ;
while (row < rows&&column >= ) {
if (matrix[row*columns + column] == number) {
found = true;
break;
}
else if (matrix[row*columns + column ]> number)
column--;
else
row++;
}
}
return found;
} // 从左下角开始比较
bool Find_2(int *arr, int rows, int columns, int number) {
bool find = false;
if (arr != NULL&&rows > && columns > ) {
int row = rows - ;
int column = ;
while (row >= && column <= columns - ) {
if (arr[row*columns + column] == number) {
find = true;
break;
}
else if (arr[row*columns+column] < number)
column++;
else
row--;
}
}
return find;
} int main() {
int arr [][]= {
{, , , },
{, , ,},
{, , , },
{, , , }
};
Find_2(*arr, , , );
return ;
}
2.字符串
C/C++中的每个字符串都以’\0’结尾。为了节省空间，C/C++经常把常量字符串放到一个单独的内存区域。当几个指针赋值给相同的常量字符串时，它们实际会指向相同的地址空间。例如：
#include<stdio.h>
int main() {
char str1[] = "Hello World";
char str2[] = "Hello world"; char *str3 = "Hello world";
char *str4 = "Hello world";
if (str1 == str2)
printf("str1 and str2 are same. \n");
else
printf("str1 and str2 are not same.\n");
if (str3 == str4)
printf("str3 and str4 are same.\n");
else
printf("str3 and str4 are not same.\n");
return ;
}
输出如下：
str1 and str2 are not same.
str3 and str4 are same.
题目：请实现一个函数，把字符串中的每个空格替换成”%20”。例如输入“We are happy.”，则输出为”We%20are%20%20happy.”。实现代码如下：
#include<stdio.h>
// lenght 为字符数组string的总容量
void ReplaceSpace(char string[], int length) {
if (string == NULL&&length <= )
return;
// originalLenght为字符串string的实际长度
int originalLenght = ;
int numOfBlank = ;
int i = ;
while (string[i] != '\0') {
originalLenght++;
if (string[i] == ' ')
numOfBlank++;
i++;
}
int newLenght = originalLenght + numOfBlank * ;
if (newLenght <= originalLenght)
return; int indexOfOriginal = originalLenght;
int indexOfNew = newLenght;
while (indexOfOriginal >= && indexOfNew > indexOfOriginal) {
if (string[indexOfOriginal] == ' ') {
string[indexOfNew--] = '';
string[indexOfNew--] = '';
string[indexOfNew--] = '%';
}
else
string[indexOfNew--] = string[indexOfOriginal];
indexOfOriginal--;
}
} int main() {
char string[] = "We are happy.";
int lenght = sizeof(string) / sizeof(char);
ReplaceSpace(string, lenght);
int j = ;
while (string[j] != '\0') {
printf("%c", string[j]);
j++;
}
printf("\n");
return ;
}
输出结果：
We%20are%20happy.
相关题目：有两个排序的数组A1和A2，内存在A1末尾有足够的空余空间容纳A2。请实现一个函数，把A2中的所有数字插入到A1中并且所有的数字是排序的。实现代码如下：
#include<stdio.h>
// len1为数组arr1的有效数字的长度
void unionArray(int arr1[], int len1, int arr2[], int len2) {
// arr1_all是啊让人整个数组的空间长度
int arr1_all = len1 + len2;
if (len2 ==)
return;
int index_1 = len1-;
int index_2 = arr1_all-;
int index_3 = len2-;
while (index_2 > index_1) {
if (arr1[index_1] > arr2[index_3]) {
arr1[index_2--] = arr1[index_1];
index_1--;
}
else
{
arr1[index_2--] = arr2[index_3];
index_3--;
} } } int main() {
int arr1[] = { ,,, };
int arr2[] = { ,,,, };
unionArray(arr1, , arr2, );
int len = sizeof(arr1) / sizeof(int);
int i = ;
while (i < len) {
printf("%d", arr1[i]);
++i;
}
printf("\n");
return ;
}
输出结果：
3.链表
// 单向链表的节点定义
struct ListNode
{
int m_nValue;
ListNode *m_pNext;
}; // 往链表的末尾添加一个节点
void AddToTail(ListNode** pHead, int value) {
ListNode* pNew = new ListNode(); // 定义一个新节点指针并为它分配内存
pNew->m_nValue = value;
pNew->m_pNext = NULL; // 如果链表为空，则新添加的节点为头节点，使头指针pHead指向该节点
if (pHead == NULL) {
pHead = &pNew;
}
else {
ListNode* pNode = *pHead;
while (pNode->m_pNext != NULL)
pNode = pNode->m_pNext;
pNode->m_pNext = pNew; }
}
// 删除节点函数
void RemoveNode(ListNode** pHead, int value) {
if (pHead == NULL || *pHead == NULL) {
return;
}
ListNode *pToBeDeleted = NULL;
if ((*pHead)->m_nValue == value) {
pToBeDeleted = *pHead;
*pHead = (*pHead)->m_pNext;
}
else {
ListNode* pNode = *pHead;
while (pNode->m_pNext != NULL&&pNode->m_pNext->m_nValue!=value)
pNode = pNode->m_pNext;
if (pNode->m_pNext != NULL&&pNode->m_pNext->m_nValue == value) {
pToBeDeleted = pNode->m_pNext;
pNode->m_pNext = pNode->m_pNext->m_pNext;
}
if (pToBeDeleted != NULL) {
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}
}
题目：输入一个链表的头节点，从尾到头打印出每个节点的值。
// 题目：输入一个链表的头节点，从尾到头打印出每个节点的值。
// 方法一：从头到尾遍历链表，把节点依次放进一个栈中，当遍历完整个链表后，再从栈顶开始输出节点的值
void PrintListReversingly_Interatively(ListNode *pHead) {
std::stack<ListNode*> nodes; ListNode *pNode = pHead;
while (pNode != NULL) {
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while (!nodes.empty()) {
pNode = nodes.top();
printf("%d\n", pNode->m_nValue);
nodes.pop();
}
} // 方法二：利用递归。每次访问一个节点时，先输出它后面的节点
void PrintListReversingly_Recursively(ListNode* pHead) {
if (pHead != NULL) {
if (pHead->m_pNext != NULL) {
PrintListReversingly_Recursively(pHead->m_pNext);
}
printf("%d\n", pHead->m_nValue);
}
} void haha(ListNode** pHead) {
while ((*pHead)->m_pNext != NULL)
{
printf("%d\n", (*pHead)->m_nValue);
(*pHead) = (*pHead)->m_pNext;
} }
4.树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果都不含重复的数字。
#include<stdio.h>
#include<iostream> // 二叉树结点定义
struct BinaryTreeNode
{
int m_nvalue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
}; // 函数声明
BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder,
int* startInorder, int* endInorder); // 用递归的方法构建左右子树和根节点 BinaryTreeNode* Construct(int *preorder, int *inorder, int length) {
if (preorder == NULL || inorder == NULL || length <= )
{
return NULL;
}
return ConstructCore(preorder,preorder+length-,inorder,inorder+length-);
}
BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder,
int* startInorder, int* endInorder)
{
// 前序遍历第一个数字即为根节点的值
int rootValue = startPreorder[];
BinaryTreeNode* root = new BinaryTreeNode();
root->m_nvalue = rootValue;
root->m_pLeft = NULL;
root->m_pRight = NULL;
if (startPreorder == endPreorder)
{
if (startInorder == endInorder&&*startPreorder == *startPreorder)
return root;
else
throw std::exception("Invalid input");
}
// 在中序遍历中找到根节点的值
int* rootInorder = startPreorder;
while (*rootInorder != rootValue && rootInorder <= endInorder)
{
++rootInorder;
}
if (*rootInorder != rootValue&&rootInorder == endInorder)
throw std::exception("Invalid input"); int leftLength = rootInorder - startInorder;
int* leftPreorderEnd = startInorder + leftLength;
if (leftLength > ) {
// 构建左子树
root->m_pLeft = ConstructCore(startPreorder + , endPreorder,
startInorder, leftPreorderEnd - );
}
if (leftLength < endInorder - startInorder)
{
// 构建右子树
root->m_pRight = ConstructCore(leftPreorderEnd+,endPreorder,
rootInorder+,endInorder);
}
}
5.栈和队列
题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入节点和在队列头部删除节点的功能。
// 队列的声明
template <typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void); // 在队列末尾添加一个结点
void appendTail(const T& node); // 删除队列的头结点
T deleteHead(); private:
stack<T> stack1;
stack<T> stack2;
}; template <typename T> CQueue<T>::CQueue(void)
{
} template <typename T> CQueue<T>::~CQueue(void)
{
}
接下来定义两个函数：
// 往第一个栈中插入元素
template<typename T> void CQueue<T>::appendTail(const T& element)
{
stack1.push(element);
} // 删除最先插入的元素
template<typename T> T CQueue<T>::deleteHead()
{
// 如果第二个栈为空，把栈一的元素依次弹出插入栈二
if (stack2.size() <= )
{
while (stack1.size()>)
{
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
} if (stack2.size() == )
throw new exception("queue is empty"); // 依次弹出并返回栈二栈顶元素
T head = stack2.top();
stack2.pop(); return head;
}
6.查找和排序
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3，4，5，1，2}为{1，2，3，4，5}的一个旋转，该数组的最小值为1。
// 利用二分查找法 #include<stdio.h>
#include<exception>
int MinInOrder(int* numbers, int index1, int index2); int Min(int* numbers, int length)
{
if (numbers == NULL || length <= )
throw new std::exception("Invalid parameters"); int index1 = ;
int index2 = length - ;
int indexMid = index1;
while (numbers[index1] >= numbers[index2])
{
// 如果index1和index2指向相邻的两个数，
// 则index1指向第一个递增子数组的最后一个数字，
// index2指向第二个子数组的第一个数字，也就是数组中的最小数字
if (index2 - index1 == )
{
indexMid = index2;
break;
} // 如果下标为index1、index2和indexMid指向的三个数字相等，
// 则只能顺序查找
indexMid = (index1 + index2) / ;
if (numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1])
return MinInOrder(numbers, index1, index2); // 缩小查找范围
if (numbers[indexMid] >= numbers[index1])
index1 = indexMid;
else if (numbers[indexMid] <= numbers[index2])
index2 = indexMid;
} return numbers[indexMid];
} int MinInOrder(int* numbers, int index1, int index2)
{
int result = numbers[index1];
for (int i = index1 + ; i <= index2; ++i)
{
if (result > numbers[i])
result = numbers[i];
} return result;
} // ====================测试代码====================
void Test(int* numbers, int length, int expected)
{
int result = ;
try
{
result = Min(numbers, length); for (int i = ; i < length; ++i)
printf("%d ", numbers[i]); if (result == expected)
printf("\tpassed\n");
else
printf("\tfailed\n");
}
catch (...)
{
if (numbers == NULL)
printf("Test passed.\n");
else
printf("Test failed.\n");
}
} int main()
{
// 典型输入，单调升序的数组的一个旋转
int array1[] = { , , , , };
Test(array1, sizeof(array1) / sizeof(int), ); // 有重复数字，并且重复的数字刚好的最小的数字
int array2[] = { , , , , , };
Test(array2, sizeof(array2) / sizeof(int), ); // 有重复数字，但重复的数字不是第一个数字和最后一个数字
int array3[] = { , , , , , };
Test(array3, sizeof(array3) / sizeof(int), ); // 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字
int array4[] = { , , , , };
Test(array4, sizeof(array4) / sizeof(int), ); // 单调升序数组，旋转0个元素，也就是单调升序数组本身
int array5[] = { , , , , };
Test(array5, sizeof(array5) / sizeof(int), ); // 数组中只有一个数字
int array6[] = { };
Test(array6, sizeof(array6) / sizeof(int), ); // 输入NULL
Test(NULL, , ); return ;
}
7.递归和循环
递归虽然有简洁的优点，但是缺点也是显著的。由于递归式函数调用自身，而函数的调用是由空间和时间消耗的，所以递归的效率不如循环。
题目一:写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列定义如下：
F()=，F()=, F(n)=F(n-)+F(n-)（n>=）
解答代码：
#include<stdio.h>
#include <cassert> // ====================方法1：递归====================
// 时间复杂度以n的指数方式递增 long long Fibonacci_Solution1(unsigned int n)
{
if (n <= )
return ; if (n == )
return ; return Fibonacci_Solution1(n - ) + Fibonacci_Solution1(n - );
} // ====================方法2：循环====================
// 时间复杂度为O(n) long long Fibonacci_Solution2(unsigned n)
{
int result[] = { , };
if (n < )
return result[n]; long long fibNMinusOne = ;
long long fibNMinusTwo = ;
long long fibN = ;
for (unsigned int i = ; i <= n; ++i)
{
fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
} return fibN;
} // ====================方法3：基于矩阵乘法====================
// 时间复杂度为O(logn) struct Matrix2By2
{
Matrix2By2
(
long long m00 = ,
long long m01 = ,
long long m10 = ,
long long m11 =
)
:m_00(m00), m_01(m01), m_10(m10), m_11(m11)
{
} long long m_00;
long long m_01;
long long m_10;
long long m_11;
}; Matrix2By2 MatrixMultiply
(
const Matrix2By2& matrix1,
const Matrix2By2& matrix2
)
{
return Matrix2By2(
matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
} Matrix2By2 MatrixPower(unsigned int n)
{
assert(n > ); Matrix2By2 matrix;
if (n == )
{
matrix = Matrix2By2(, , , );
}
else if (n % == )
{
matrix = MatrixPower(n / );
matrix = MatrixMultiply(matrix, matrix);
}
else if (n % == )
{
matrix = MatrixPower((n - ) / );
matrix = MatrixMultiply(matrix, matrix);
matrix = MatrixMultiply(matrix, Matrix2By2(, , , ));
} return matrix;
} long long Fibonacci_Solution3(unsigned int n)
{
int result[] = { , };
if (n < )
return result[n]; Matrix2By2 PowerNMinus2 = MatrixPower(n - );
return PowerNMinus2.m_00;
} // ====================测试代码====================
void Test(int n, int expected)
{
if (Fibonacci_Solution1(n) == expected)
printf("Test for %d in solution1 passed.\n", n);
else
printf("Test for %d in solution1 failed.\n", n); if (Fibonacci_Solution2(n) == expected)
printf("Test for %d in solution2 passed.\n", n);
else
printf("Test for %d in solution2 failed.\n", n); if (Fibonacci_Solution3(n) == expected)
printf("Test for %d in solution3 passed.\n", n);
else
printf("Test for %d in solution3 failed.\n", n);
} int main()
{
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, ); Test(, ); return ;
}
题目二：一只青蛙一次可以跳上1级台阶，也可以跳上2级.求该青蛙跳上一个n级台阶有多少种跳法。
其实这道题的解答就是求上面的斐波那契数列。
8.位计算
位运算是把数字用二进制表示之后，对每一位上0或者1的运算。
题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1.因此如果输入为9，输出为2.
/*考虑到有负数的情况，如果只是对输入进行简单的右移，那么负数的高位会自动的添加1则可能会进入死循环*/ /*常规解法:
不进行右移，先把输入与标志位进行与判断最低位是不是1，再把标志位进行左移判断次低位是不是1
依次类推直到最高位，即可计算出1的个数
*/ int NumberOf1(int n){
int count=;
unsigned int flag=;
while(flag){
if(n&flag)
count++;
flag<<;
}
return count; } /*进阶解法：
可进行论证把一个数减去1，再和原来数做与运算，会把该整数最右边一个1变成0。例如1100，减去1后为1011，两数与后为1000。
*/
int NumberOf2(int n){
int count=;
while(n){
++count;
n=(n-)&n;
}
return count;
}