异度部落格

学习是一种生活态度。

0%

Posted on In

【试题描述】完成一个函数，输入一个二叉树输出它的镜像。

【试题来源】未知

【参考代码】

#include <iostream>
using namespace std;

struct BinaryTreeNode
{
	int value;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
};

BinaryTreeNode* rebulidBinaryTreeCore(int* startPreOrder, int* endPreOrder,
		int* startInOrder, int* endInOrder) {

	//先序遍历的第一个节点为根节点
	//创建根节点
	BinaryTreeNode* rootNode = new BinaryTreeNode();
	rootNode->value = startPreOrder[0];
	rootNode->left = NULL;
	rootNode->right = NULL;

	if(startPreOrder == endPreOrder) {
		if(startInOrder == endInOrder
				&& *startPreOrder == *startInOrder) {
			return rootNode;
		} else {
			throw ("Invalid input.");
		}
	}

	//在中序查找根节点
	int* rootIndex = startInOrder;
	while(rootIndex <= endInOrder && *rootIndex != rootNode->value) {
		rootIndex++;
	}
	if(rootIndex == endInOrder && *rootIndex != rootNode->value) {
		throw ("Invalid input.");
	}

	//重建左子树
	int leftTreeLength = rootIndex - startInOrder;
	if(leftTreeLength > 0) {
		rootNode->left = rebulidBinaryTreeCore(startPreOrder + 1,
				startPreOrder + leftTreeLength,
				startInOrder,
				rootIndex - 1);
	}

	//重建右子树
	if(leftTreeLength < endPreOrder - startPreOrder) {
		rootNode->right = rebulidBinaryTreeCore(startPreOrder + leftTreeLength + 1,
				endPreOrder,
				rootIndex + 1,
				endInOrder);
	}

	return rootNode;
}

BinaryTreeNode* rebulidBinaryTree(int* preOrder, int* inOrder, int n) {
	if(preOrder == NULL || inOrder == NULL || n <= 0) {
		return NULL;
	}

	return rebulidBinaryTreeCore(preOrder, preOrder + n -1,
			inOrder, inOrder + n - 1);
}

void mirrorRecursively(BinaryTreeNode* rootNode) {

	if(rootNode == NULL || (rootNode->left == NULL && rootNode->right)) {
		return ;
	}

	BinaryTreeNode* tempNode = rootNode->left;
	rootNode->left = rootNode->right;
	rootNode->right = tempNode;

	if(rootNode->left != NULL) {
		mirrorRecursively(rootNode->left);
	}

	if(rootNode->right != NULL) {
		mirrorRecursively(rootNode->right);
	}
}

void printInOrder(BinaryTreeNode* root) {
	if(root!= NULL) {
		cout << root->value << " ";
		if(root->left != NULL) {
			printInOrder(root->left);
		}
		if(root->right != NULL) {
			printInOrder(root->right);
		}
	}
	return ;
}

int main() {
	//建立一颗二叉树
	int preOrder[8] = {1,2,4,7,3,5,6,8};
	int inOrder[8] = {4,7,2,1,5,3,8,6};
	BinaryTreeNode* root = rebulidBinaryTree(preOrder, inOrder, 8);

	mirrorRecursively(root);
	printInOrder(root);
	return 0;
}

Posted on In

【试题描述】从上往下打印二叉树

【试题来源】未知

【参考代码】

void printBinaryTree(const BinaryTreeNode* rootNode) {

	if(rootNode == NULL) {
		return ;
	}

	queue<const BinaryTreeNode*> nodesQueue;
	nodesQueue.push(rootNode);
	while(!nodesQueue.empty()) {
		const BinaryTreeNode* node = nodesQueue.front();
		cout << node->value << " ";
		nodesQueue.pop();

		if(node->left != NULL) {
			nodesQueue.push(node->left);
		}
		if(node->right != NULL) {
			nodesQueue.push(node->right);
		}
	}
}

Posted on In

【试题描述】定义的数据结构，请在类型中实现一个能够得到栈的最小元素的函数。 在该栈中，调用min、push、pop的时间复杂度都是O(1)。

【试题来源】未知

【参考代码】

#include <iostream>
#include <stack>
using namespace std;

template<typename T>
class StackWithMin {

private:
	stack<T> dataStack;
	stack<T> minStack;

public:
	void push(const T &element);
	T pop();
	T min();
};

template<typename T>
void StackWithMin<T>::push(const T &element) {

	dataStack.push(element);

	if(minStack.empty()) {
		minStack.push(element);
	} else if(element < minStack.top()) {
		minStack.push(element);
	} else {
		minStack.push(minStack.top());
	}
}

template<typename T>
T StackWithMin<T>::pop() {

	if(dataStack.empty()) {
		throw "Stack is empty.";
	}

	T topValue = dataStack.top();
	dataStack.pop();
	minStack.pop();

	return topValue;
}

template<typename T>
T StackWithMin<T>::min() {

	if(dataStack.empty()) {
		throw "Stack is empty.";
	}

	return minStack.top();
}


int main() {
	StackWithMin<int> stackWithMin;
	stackWithMin.push(3);
	stackWithMin.push(4);
	stackWithMin.push(2);
	stackWithMin.push(6);
	cout << stackWithMin.min() << endl;
	stackWithMin.pop();
	stackWithMin.pop();
	cout << stackWithMin.min() << endl;
	return 0;
}

Posted on In

【试题描述】合并两个递增排序的链表，合并这两个链表使得新链表的节点也是按递增的顺序拍列的。

【试题来源】未知

【参考代码】

#include <iostream>
using namespace std;

struct ListNode {
	int value;
	ListNode* next;
};

ListNode* createList(int* data, int n) {

	ListNode* headNode = NULL;
	ListNode* lastNode = NULL;

	for(int i = 0; i < n; i++) {
		ListNode* node = new ListNode();
		node->value = data[i];
		node->next = NULL;
		if(i == 0) {
			headNode = node;
		} else {
			lastNode->next = node;
		}
		lastNode = node;
	}

	return headNode;
}

void printList(ListNode* headNode) {

	if(headNode == NULL) {
		return ;
	}
	ListNode* node = headNode;
	while(node != NULL) {
		cout << node->value << " ";
		node = node->next;
	}
}

ListNode* mergeSortedList(ListNode* headNodeA, ListNode* headNodeB) {

	if(headNodeA == NULL) {
		return headNodeB;
	} else if(headNodeB == NULL) {
		return headNodeA;
	}

	ListNode* nodeIndexA = headNodeA;
	ListNode* nodeIndexB = headNodeB;
	ListNode* headNode = NULL;
	ListNode* node = NULL;

	if(headNodeA->value < headNodeB->value) {
		headNode = node = headNodeA;
		nodeIndexA = nodeIndexA->next;
	} else {
		headNode = node = headNodeB;
		nodeIndexB = nodeIndexB->next;
	}

	while(nodeIndexA != NULL && nodeIndexB != NULL) {

		if(nodeIndexA->value < nodeIndexB->value) {
			node->next = nodeIndexA;
			node = node->next;
			nodeIndexA = nodeIndexA->next;
		} else {
			node->next = nodeIndexB;
			node = node->next;
			nodeIndexB = nodeIndexB->next;
		}
	}

	if(nodeIndexA != NULL) {
		node->next = nodeIndexA;
	} else if(nodeIndexB != NULL) {
		node->next = nodeIndexB;
	}

	return headNode;
}

int main() {

	int data1[] = {1, 3, 5, 7, 9, 11, 13};
	int n1 = 7;
	ListNode* headNodeA = createList(data1, n1);
	int data2[] = {2, 4, 6, 8, 10, 12, 14};
	int n2 = 7;
	ListNode* headNodeB = createList(data2, n2);

	ListNode* headNode = mergeSortedList(headNodeA, headNodeB);
	printList(headNode);

	return 0;
}

Posted on In

【试题描述】输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出序列。

【试题来源】未知

【参考代码】

#include <iostream>
#include <stack>
using namespace std;

bool isPopOrder(const int* pushOrder, const int* popOrder, int length) {

	if(pushOrder == NULL || popOrder == NULL || length <= 0) {
		return false;
	}

	int i = 0;
	int j = 0;
	stack<int> tmpStack;

	tmpStack.push(pushOrder[i++]);

	while(i < length || j < length) {

		if(tmpStack.top() != popOrder[j]) {
			tmpStack.push(pushOrder[i]);
			i++;
		} else {
			if(!tmpStack.empty()) {
				tmpStack.pop();
			} else {
				return false;
			}
			j++;
		}
	}

	if(tmpStack.empty()) {
		return true;
	} else {
		return false;
	}
}

int main() {
	const int pushOrder[] = {1, 2, 3, 4, 5};
	//const int popOrder[] = {4, 5, 3, 2, 1};
	const int popOrder[] = {4, 3, 5, 1, 2};
	int length = 5;

	if(isPopOrder(pushOrder, popOrder, length)) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

Posted on In

【试题描述】定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点

【试题来源】未知

【参考代码】

#include <iostream>
using namespace std;

struct ListNode {
	int value;
	ListNode* next;
};

ListNode* createList(int* data, int n) {

	ListNode* headNode = NULL;
	ListNode* lastNode = NULL;

	for(int i = 0; i < n; i++) {
		ListNode* node = new ListNode();
		node->value = data[i];
		node->next = NULL;
		if(i == 0) {
			headNode = node;
		} else {
			lastNode->next = node;
		}
		lastNode = node;
	}

	return headNode;
}

void printList(ListNode* headNode) {

	if(headNode == NULL) {
		return ;
	}
	ListNode* node = headNode;
	while(node != NULL) {
		cout << node->value << " ";
		node = node->next;
	}
}

ListNode* reverseList(ListNode* headNode) {

	if(headNode == NULL) {
		return NULL;
	}

	ListNode* curNode = headNode;
	ListNode* preNode = NULL;
	ListNode* nextNode = NULL;

	while(curNode != NULL) {

		nextNode = curNode->next;
		curNode->next = preNode;
		preNode = curNode;
		curNode = nextNode;

	}
	return preNode;
}

int main() {
	int data[] = {1, 2, 3, 4, 5, 6, 7};
	int n = 7;
	ListNode* headNode = createList(data, n);
	ListNode* reverseNode = reverseList(headNode);
	printList(reverseNode);
	return 0;
}

Posted on In

【试题描述】给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。

【试题来源】 未知

【试题分析】按照常规删除链表节点的方法没有办法在O(1)复杂度内完成，因此需要转换思路，将后面一个节点的内容复制过来，然后删除其后面的那个节点，以达到删除节点的目的。

【参考代码】

struct ListNode
{
	int value;
	ListNode* next;
};

void deleteLinkNode(ListNode** pHeadNode, ListNode* pDeleteNode) {

	if(pHeadNode == NULL || pDeleteNode == NULL) {
		return ;
	}

	//删除节点在头部
	if(pDeleteNode == *pHeadNode) {
		delete pDeleteNode;
		pDeleteNode = NULL;
		*pHeadNode = NULL;
	//删除节点在末尾
	} else if(pDeleteNode->next == NULL) {
		ListNode* pNode = *pHeadNode;
		while(pNode->next != pDeleteNode) {
			pNode = pNode->next;
		}
		pNode->next = NULL;
		delete pDeleteNode;
		pDeleteNode = NULL;
	} else {
		ListNode* pNode = pDeleteNode->next;

		pDeleteNode->value = pNode->value;
		pDeleteNode->next = pNode->next;

		delete pNode;
		pNode = NULL;
	}
}

Posted on In

【试题描述】 输入一个整数数组，实现一个函数来调整该数组中数字的顺序。使得所有奇数位于数组的前半部分，所有偶数位于数组后半部分。

【试题来源】未知

【参考代码】

#include <iostream>
using namespace std;

void reorder(int* data, int length) {

	int i = 0;
	int j = length - 1;

	while(i < j) {
		while(i < j && (data[i] & 1)) {
			i++;
		}

		while(i < j && !(data[j] & 1)) {
			j--;
		}

		if(i < j) {
			int tmp = data[i];
			data[i] = data[j];
			data[j] = tmp;
		}
	}
}

int main() {
	int data[] = {1,2,3,4,5,6,7,8,9,10};
	int length = 10;
	reorder(data, length);

	for(int i = 0; i < length; i++) {
		cout << data[i] << " ";
	}

	return 0;
}

Posted on In

【试题描述】把一个数组最开始的若干个元素搬到末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小元素为1.

【试题来源】未知

【参考代码】

#include <iostream>
using namespace std;

int findMinNumber(int* numbers, int length) {

	if(numbers == NULL || length <= 0) {
		throw "Invalid parameters.";
	}

	int index1 = 0;
	int index2 = length - 1;
	int indexMid = (index1 + index2) / 2;
	while(numbers[index1] >= numbers[index2]) {

		if(index2 - index1 == 1) {
			return numbers[index2];
		}

		indexMid = (index1 + index2) / 2;
		if(numbers[index1] == numbers[index2]
		    && numbers[index1] == numbers[indexMid]) {
			int result = numbers[index1 + 1];
			for(int i = index1 + 1; i <= index2; ++i) {
				if(result > numbers[i]) {
					result = numbers[i];
				}
			}
		} else if(numbers[indexMid] >= numbers[index1]) {
			index1 = indexMid;
		} else if(numbers[indexMid] <= numbers[index2]) {
			index2 = indexMid;
		}
	}
	return numbers[indexMid];
}

int main() {
	int array[] = {3, 4, 5, 1, 2};
	//int array[] = {3, 4, 4, 5, 5, 6, 7, 8, 1, 2, 2, 2, 3, 3, 3};
	cout << findMinNumber(array, 5) << endl;
	return 0;
}

Posted on In

【试题描述】用两个栈实现一个队列。队列声明如下，请实现它的两个函数appendTail，deleteHead，分别完成在队列尾部插入节点和在头部删除节点。

【试题来源】未知

【参考代码】

#include <iostream>
#include <stack>
using namespace std;

template <typename T>
class MyQueue
{

public:
	void appendTail(const T& element);
	T deleteHead();

private:
	stack<T> inStack;
	stack<T> outStack;
};

template <typename T>
void MyQueue<T>::appendTail(const T& element) {

	inStack.push(element);
}

template <typename T>
T MyQueue<T>::deleteHead() {

	if(outStack.empty()) {
		//将inStack里面的数据放入outStack中
		if(!inStack.empty()) {
			while(!inStack.empty()) {
				T element = inStack.top();
				outStack.push(element);
				inStack.pop();
			}
		} else {
			throw "The Queue is empty.";
		}
	}
	T element = outStack.top();
	outStack.pop();

	return element;
}

int main() {
	MyQueue<int> queue;
	queue.appendTail(1);
	queue.appendTail(3);
	queue.appendTail(5);
	cout << queue.deleteHead() << endl;
	cout << queue.deleteHead() << endl;
	cout << queue.deleteHead() << endl;

	return 0;
}