代码片段day13-day15

1. 判断是否是树的子树

#include<iostream>
#include<cassert>
using namespace std;
struct BinaryTreeNode
{
struct BinaryTreeNode *_pLeft;
struct BinaryTreeNode *_pRight;
char _data;
BinaryTreeNode(int data) :
_pLeft(nullptr),
_pRight(nullptr),
_data(data)
{}
};
typedef BinaryTreeNode Node;

class BinaryTree
{
public:
BinaryTree() :_pRoot(nullptr)
{}
BinaryTree(char *arr, char valid, int size)
{
assert(arr);
size_t index = 0;
_CreateTree(_pRoot, arr, '#', size, index);
}
void PreOrder()
{
_PreOrder(_pRoot);
}
protected:
void _CreateTree(Node *&pRoot, char *arr, const char valid, int size, size_t &index)
{
if (index < size&&arr[index] != valid)
{
pRoot = new Node(arr[index]);
_CreateTree(pRoot->_pLeft, arr, valid, size, ++index);
_CreateTree(pRoot->_pRight, arr, valid, size, ++index);
}
}

void _PreOrder(Node *pRoot)
{
if (pRoot)
{
cout << pRoot->_data << " ";
_PreOrder(pRoot->_pLeft);
_PreOrder(pRoot->_pRight);
}
}
private:
Node *_pRoot;
};
bool isEqual(float a, float b)
{
if (abs(a - b) < 0.001)
return true;
return false;
}
bool doesHasSubTree(Node *pRoot1, Node *pRoot2)
{
if (pRoot2 == nullptr)
return true;
if (pRoot1 == nullptr)
return false;
if (!isEqual(pRoot1->_data, pRoot2->_data))
return false;
return doesHasSubTree(pRoot1->_pRight, pRoot2->_pRight)
&& doesHasSubTree(pRoot1->_pLeft, pRoot2->_pLeft);
}
bool hasSubTree(Node *pRoot1, Node *pRoot2)
{
bool res = false;
if (pRoot1&&pRoot2)
{
if (isEqual(pRoot1->_data, pRoot2->_data))
{
res = doesHasSubTree(pRoot1, pRoot2);
}
if (!res)
res = hasSubTree(pRoot1->_pLeft, pRoot2);
if (!res)
res = hasSubTree(pRoot2->_pRight, pRoot2);
}
}
int main()
{
char arr[] = { '1', '2', '4', '#', '#', '#', '3', '5', '#', '#', '6' };
size_t sz = sizeof(arr) / sizeof(arr[0]);
BinaryTree b(arr,'#', sz );
b.PreOrder();
system("pause");
}

合并两个有序链表 删除重复元素

void RemoveAllRepeate(ListNode *&pHead)
{
if (pHead == nullptr || pHead->_pNext == nullptr)
return;
ListNode *pCur = pHead;
ListNode *pPre = nullptr;
while (pCur)
{
ListNode *pNext = pCur->_pNext;
bool needDel = false;
if (pNext&&pCur->_data == pNext->_data)
needDel = true;
if (!needDel)
{
pPre = pCur;
pCur = pCur->_pNext;
}
else
{
int data = pCur->_data;
ListNode *delNode = pCur;
while (delNode->_data == data)
{
pNext = delNode->_pNext;
delete delNode;
delNode = nullptr;
delNode = pNext;
}
if (pPre == nullptr)
pHead = pNext;
else
pPre->_pNext = pNext;
pCur = pNext;
}
if (pPre == nullptr)
pHead = pNext;
else
pPre->_pNext = pNext;
pCur = pNext;

}
}
void merge(ListNode *&pHead1, ListNode *&pHead2)
{
assert(pHead1&&pHead2);
ListNode *head = pHead1->_data < pHead2->_data ? pHead1 : pHead2;
ListNode *head1 = head;
ListNode *head2 = pHead1 == head ? pHead2 : pHead1;
ListNode *pPre = nullptr;
ListNode *pNext = nullptr;
while (head1&&head2)
{
if (head1->_data < head2->_data)
{
pPre = head1;
head1 = head1->_pNext;
}
else
{
pNext = head2->_pNext;
pPre->_pNext = head2;
head2->_pNext = head1;
head1 = head2;
head2 = pNext;
}
}
pPre->_pNext = head1 == nullptr ?

3. 位运算实现加法

#include<iostream>
using namespace std;
int getNum(int a, int b)
{
int wei = a ^ b;
int jinwei = (a&b) <<1;
if (jinwei == 0)
return wei;
else
return getNum(wei, jinwei);
}
int main()
{
int a;
int b;
while (cin>>a&&cin>>b)
cout

4. 顺时针打印矩阵

/*******************************************************************
Copyright(c) 2016, Harry He
All rights reserved.

Distributed under the BSD license.
(See accompanying file LICENSE.txt at
https://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
*******************************************************************/

//==================================================================
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 作者：何海涛
//==================================================================

// 面试题29：顺时针打印矩阵
// 题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

#include <cstdio>
#include<iostream>
using namespace std;
void PrintMatrixInCircle(int** numbers, int columns, int rows, int start);
void printNumber(int number);

void PrintMatrixClockwisely(int** numbers, int columns, int rows)
{
if (numbers == nullptr || columns <= 0 || rows <= 0)
return;

int start = 0;

while (columns > start * 2 && rows > start * 2)
{
PrintMatrixInCircle(numbers, columns, rows, start);

++start;
}
}

void PrintMatrixInCircle(int** numbers, int columns, int rows, int start)
{
int endX = columns - 1 - start;
int endY = rows - 1 - start;

// 从左到右打印一行
for (int i = start; i <= endX; ++i)
{
int number = numbers[start][i];
printNumber(number);
}

// 从上到下打印一列
if (start < endY)
{
for (int i = start + 1; i <= endY; ++i)
{
int number = numbers[i][endX];
printNumber(number);
}
}

// 从右到左打印一行
if (start < endX && start < endY)
{
for (int i = endX - 1; i >= start; --i)
{
int number = numbers[endY][i];
printNumber(number);
}
}

// 从下到上打印一行
if (start < endX && start < endY - 1)
{
for (int i = endY - 1; i >= start + 1; --i)
{
int number = numbers[i][start];
printNumber(number);
}
}
}

void printNumber(int number)
{
printf("%d\t", number);
}

// ====================测试代码====================
void Test(int columns, int rows)
{
printf("Test Begin: %d columns, %d rows.\n", columns, rows);

if (columns < 1 || rows < 1)
return;

int** numbers = new int*[rows];
for (int i = 0; i < rows; ++i)
{
numbers[i] = new int[columns];
for (int j = 0; j < columns; ++j)
{
numbers[i][j] = i * columns + j + 1;
}
}

PrintMatrixClockwisely(numbers, columns, rows);
printf("\n");

for (int i = 0; i < rows; ++i)
delete[](int*)numbers[i];

delete[] numbers;
}

int main(int argc, char* argv[])
{
/*
1
*/
Test(1, 1);

/*
1 2
3 4
*/
Test(2, 2);

/*
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
*/
Test(4, 4);

/*
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
*/
Test(5, 5);

/*
1
2
3
4
5
*/
Test(1, 5);

/*
1 2
3 4
5 6
7 8
9 10
*/
Test(2, 5);

/*
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
*/
Test(3, 5);

/*
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
*/
Test(4, 5);

/*
1 2 3 4 5
*/
Test(5, 1);

/*
1 2 3 4 5
6 7 8 9 10
*/
Test(5, 2);

/*
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
*/
Test(5, 3);

/*
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
*/
Test(5, 4);
system("pause");
return 0;
}

5. 树的镜像

void _Mirror(Node *pRoot)
{
if (pRoot == nullptr)
return;
if (pRoot->_pLeft == nullptr&&pRoot->_pRight == nullptr)
return;
swap(pRoot->_pLeft, pRoot->_pRight);
if (pRoot->_pLeft)
_Mirror(pRoot->_pLeft);
if (pRoot->_pRight)
_Mirror(pRoot->_pRight);
}
bool _isDuichen(Node *pRootR,Node *pRootL)
{
if (pRootR == nullptr&&pRootL == nullptr)
return true;
if (pRootL == nullptr || pRootR == nullptr)
return false;
if (pRootL->_data != pRootR->_data)
return false;
return _isDuichen(pRootR->_pRight, pRootL->_pLeft)
&& _isDuichen(pRootR->_pLeft, pRootL->_pRight);
}

6. 判断树是否对称

bool _isDuichen(Node *pRootR,Node *pRootL)
{
if (pRootR == nullptr&&pRootL == nullptr)
return true;
if (pRootL == nullptr || pRootR == nullptr)
return false;
if (pRootL->_data != pRootR->_data)
return false;
return _isDuichen(pRootR->_pRight, pRootL->_pLeft)
&& _isDuichen(pRootR->_pLeft, pRootL->_pRight);
}

7. 不用判断语句while和乘法计算1+..n

法一：使用递归
#include<iostream>
using namespace std;
int getRes(int n)
{
n && (n += getRes(n - 1));
return n;
}
int main()
{
int n;
while (cin>>n)
cout << getRes(n) << endl;
}
法二：使用构造函数
#include<iostream>
using namespace std;
class Sum
{
public:
Sum()
{
++N;
res += N;
}
static int res;
static int N;
~Sum()
{}
};
int Sum::res = 0;
int Sum::N = 0;

int main()
{
Sum s[5];
cout << s->res<< endl;
system("pause");
}

8. 是否为栈的弹出序列

#include<iostream>
#include<stack>
using namespace std;
//pPush,压栈的顺序序列
//pPop弹栈的顺序序列
//Length序列的长度
bool IsPopOrder(const int *pPush, const int *pPop, int Length)
{
bool pPossible = false;
if (pPush != nullptr&&pPop != nullptr&&Length > 0)
{
const int *pNextPush = pPush;
const int *pNextPop = pPop;
stack<int> stackData;
while (pNextPop - pPop < Length)
{
//如果栈为空或者栈顶元素不等于弹出序列的值，则继续将压栈序列压栈
//直到压栈序列的值都压完了，或者栈顶等于弹出序列的值为止
while (stackData.empty() || stackData.top() != *pNextPop)
{
if (pNextPush - pPush == Length)
break;
stackData.push(*pNextPush);
pNextPush++;
}

if (stackData.top() != *pNextPop)
break;
stackData.pop();
pNextPop++;
}
//如果栈中元素都一出栈，并且弹出序列都已经访问完毕则是压栈序列的弹出序列
if (stackData.empty() && pNextPop - pPop == Length)
pPossible = true;
}
return