异度部落格

【IT笔试面试题整理】数字在排序数组中出现的次数

Posted on 2012-10-06 In 面试题整理

【试题描述】统计一个数字在排序数组中出现的次数。例如输入的排序数组{1, 2, 3, 3, 3, 3, 4, 5}

和数字3,由于3在这个数组中出现了4次，因此输出4。

【试题来源】未知

【参考代码】

int GetFirstK(int array[], int length, int start, int end, int k) {

	if(start > end) {
		return -1;   //No Found
	}

	int middle = (start + end) / 2;
	if(array[middle] == k) {

		if((middle > 0 && array[middle - 1] != k)
				|| middle == 0) {
			return middle;
		} else {
			end = middle - 1;
		}
	} else if(array[middle] < k) {
		start = middle + 1;
	} else {
		end = middle - 1;
	}

	return GetFirstK(array, length, start, end, k);
}

int GetLastK(int array[], int length, int start, int end, int k) {

	if(start > end) {
		return -1;   //No Found
	}

	int middle = (start + end) / 2;
	if(array[middle] == k) {

		if((middle < length - 1 && array[middle + 1] != k)
				|| middle == length - 1) {
			return middle;
		} else {
			start = middle + 1;
		}
	} else if(array[middle] < k) {
		start = middle + 1;
	} else {
		end = middle - 1;
	}

	return GetLastK(array, length, start, end, k);
}

int GetNumOfK(int array[], int length, int k) {

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

	int first = GetFirstK(array, length, 0 , length - 1, k);
	int last = GetLastK(array, length, 0 , length - 1, k);

	if(first > -1 && last > -1) {
		return last - first + 1;
	}

	return -1;
}

【IT笔试面试题整理】数组中出现次数超过一半的数字

Posted on 2012-10-06 In 面试题整理

【试题描述】数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

【试题来源】未知

【试题分析】时间复杂度O(n),空间复杂度O(1)

【参考代码】

int findMoreThanHalf(int array[], int n) {

	if(array == NULL || n <= 0) {
		throw ("Invalid input.");
	}

	int num = array[0];
	int times = 1;

	for(int i = 1; i < n; i++) {
		if(array[i] == num) {
			++times;
		} else {
			--times;
			if(times == 0) {
				num = array[i];
				times = 1;
			}
		}
	}

	return num;
}

【IT笔试面试题整理】最小K个数

Posted on 2012-10-06 In 面试题整理

【试题描述】输入n个整数，找出其中最小的k个数。

【试题来源】未知

【参考代码】

void leastKNum(int array[], int n, int k) {

	if(array == NULL || n < k || n <= 0) {
		throw ("Invalid input.");
	}

	priority_queue<int> heap;  //大顶堆

	for(int i = 0; i < n; i++) {

		if(i < k) {
			heap.push(array[i]);
		} else {
			if(array[i] < heap.top()) {
				heap.pop();
				heap.push(array[i]);
			}
		}
	}

	//Print the reslut
	while(!heap.empty()) {
		cout << heap.top() << " ";
		heap.pop();
	}
	cout << endl;
}

最大K个数代码如下：

void topKNum(int array[], int n, int k) {

	if(array == NULL || n < k || n <= 0) {
		throw ("Invalid input.");
	}

	priority_queue< int, vector<int>, greater<int> > heap;  //小顶堆

	for(int i = 0; i < n; i++) {

		if(i < k) {
			heap.push(array[i]);
		} else {
			if(array[i] > heap.top()) {
				heap.pop();
				heap.push(array[i]);
			}
		}
	}

	//Print the reslut
	while(!heap.empty()) {
		cout << heap.top() << " ";
		heap.pop();
	}
	cout << endl;
}

【IT笔试面试题整理】连续子数组的最大和

Posted on 2012-10-06 In 面试题整理

【试题描述】输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。要求时间复杂度O(n)。

【试题来源】未知

【参考代码】

int findGreastestSumOfSubArray(int array[], int n) {

	if(array == NULL || n <= 0) {
		throw ("Invalid Inptut.");
	}

	int *dp = new int[n];
	int maxSum = array[0];
	for(int i = 0; i < n; i++) {
		if(i == 0 || dp[i - 1] <= 0) {
			dp[i] = array[i];
		} else if(i > 0 && dp[i - 1] > 0){
			dp[i] = dp[i - 1] + array[i];
		}
		if(dp[i] > maxSum) {
			maxSum = dp[i];
		}
	}

	return maxSum;
}

【IT笔试面试题整理】二叉排序树的后序遍历

Posted on 2012-09-23 In 面试题整理

【试题描述】输入一个整数数组，判断该数组是不是某二叉排序树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字互不相同。

【试题来源】未知

【参考代码】

#include <iostream>
using namespace std;

bool verifySquenceOfBST(int sequence[], int length) {

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

	int root = sequence[length - 1];

	int i = 0;
	while(i < length - 1) {
		if(sequence[i] > root) {
			break;
		}
		i++;
	}

	int j = i;
	while(j < length - 1) {
		if(sequence[j] < root) {
			return false;
		}
		j++;
	}

	//判断左子数
	bool left = true;
	if(i > 0) {
		left = verifySquenceOfBST(sequence, i);
	}

	//判断右子数
	bool right = true;
	if(i > 0) {
		right = verifySquenceOfBST(sequence + i, length - i - 1);
	}

	return left && right;
}

int main() {
	int seq[] = {5, 7, 6, 9, 11, 10, 8};
	//int seq[] = {5, 7, 6, 11, 9, 10, 8};
	int length = 7;

	if(verifySquenceOfBST(seq, length)) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}

【IT笔试面试题整理】二叉树镜像

Posted on 2012-09-23 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;
}

【IT笔试面试题整理】从上往下打印二叉树

Posted on 2012-09-23 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);
		}
	}
}

【IT笔试面试题整理】包含min函数的栈

Posted on 2012-09-23 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;
}

【IT笔试面试题整理】合并两个排序的链表

Posted on 2012-09-23 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;
}

【IT笔试面试题整理】栈的压入、弹出序列

Posted on 2012-09-23 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;
}