异度部落格

学习是一种生活态度。

0%

Posted on In

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

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

【试题来源】未知

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}

Posted on In

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

【试题来源】未知

【参考代码】

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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;
}

Posted on In

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

【试题来源】未知

【参考代码】

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#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

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

【试题来源】未知

【参考代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)。

【试题来源】未知

【参考代码】

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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

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

【试题来源】未知

【参考代码】

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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

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

【试题来源】未知

【参考代码】

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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

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

【试题来源】未知

【参考代码】

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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)复杂度内完成，因此需要转换思路，将后面一个节点的内容复制过来，然后删除其后面的那个节点，以达到删除节点的目的。

【参考代码】

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
26
27
28
29
30
31
32
33
34
35
36
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

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

【试题来源】未知

【参考代码】

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
26
27
28
29
30
31
32
33
34
35
36
#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;
}