异度部落格

【IT笔试面试题整理】不用加减乘除做加法

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

【试题描述】写一个函数，求两个整数的和，要求在函数体内不得使用加减乘除四则运算符合。

【试题来源】未知

【参考代码】

int add(int num1, int num2) {

	int sum;
	int carry;
	do {
		sum = num1 ^ num2;
		carry = (num1 & num2) << 1;

		num1 = sum;
		num2 = carry;
	} while(num2 != 0);

	return num1;
}

【IT笔试面试题整理】丑数

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

【试题描述】我们把只包含因子2、3和5的数称作丑数。求按从到大的顺序的第1500个丑数。例如6,8是丑数，而14不是，因为它包含因子7.习惯上把1当作第一个丑数。

【试题来源】未知

【参考代码】

int Min(int a, int b, int c) {

	return (a < b ? a : b) < c ? (a < b ? a : b) : c;
}

int uglyNumber(int n) {

	if(n <= 0) {
		throw ("Invalid Input.");
	}

	long* uglyNum = new long[n];
	uglyNum[0] = 1;

	int index2 = 0;
	int index3 = 0;
	int index5 = 0;
	int indexLast = 0;

	while(indexLast < n) {
		int min = Min(uglyNum[index2] * 2, uglyNum[index3] * 3, uglyNum[index5] * 5);
		uglyNum[++indexLast] = min;

		while(uglyNum[index2] * 2 <= uglyNum[indexLast]) {
			index2++;
		}

		while(uglyNum[index3] * 3 <= uglyNum[indexLast]) {
			index3++;
		}

		while(uglyNum[index5] * 5 <= uglyNum[indexLast]) {
			index5++;
		}
	}

	return uglyNum[n - 1];

}

【IT笔试面试题整理】二叉树中和为某一值的路径

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

【试题描述】输入一个二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成的一条路径。

【试题来源】未知

【参考代码】

void findPath(BinaryTreeNode* rootNode, int expectSum,
		vector<int>& path, int curSum) {

	if(rootNode == NULL) {
		return ;
	}

	path.push_back(rootNode->value);
	curSum += rootNode->value;

	if(rootNode->left == NULL && rootNode->right == NULL
			&& curSum == expectSum) {
		cout << "Find a path: ";
		for(vector<int>::iterator iter = path.begin(); iter != path.end(); iter++) {
			cout << *iter << " ";
		}
		cout << endl;
	}

	if(rootNode->left != NULL) {
		findPath(rootNode->left, expectSum, path, curSum);
	}

	if(rootNode->right != NULL) {
		findPath(rootNode->right, expectSum, path, curSum);
	}

	path.pop_back();
	curSum -= rootNode->value;
}

void findPaths(BinaryTreeNode* rootNode, int expectSum) {

	vector<int> path;
	findPath(rootNode, expectSum, path, 0);
}

【IT笔试面试题整理】二叉树的深度

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

【试题描述】输入一棵二叉树的根结点，求该树的深度。从根结点到叶子结点依次经过的结点（含根、叶子节点）形成树的一条路径，最长路径的长度为树的深度。

【试题来源】未知

【参考代码】

int treeDepth(BinaryTreeNode* rootNode) {

	if(rootNode == NULL) {
		return 0;
	}

	int leftSubTreeDepth = treeDepth(rootNode->left);
	int rightSubTreeDepth = treeDepth(rootNode->right);

	return leftSubTreeDepth > rightSubTreeDepth ? (leftSubTreeDepth + 1) : (rightSubTreeDepth + 1);
}

【IT笔试面试题整理】字符串的排列

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

【试题描述】输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出a，b，c所能排列出来的所有字符串abc，acb，bac，bca，cab，cba。

【试题来源】未知

【参考代码】

#include <iostream>
#include <cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;

void permutation(char* str, int begin) {

	if(begin == strlen(str)) {
		cout << str << endl;
	} else {
		for(int i = begin; i < strlen(str); ++i) {
			char tmp = str[i];
			str[i] = str[begin];
			str[begin] = tmp;

			permutation(str, begin + 1);

			tmp = str[i];
			str[i] = str[begin];
			str[begin] = tmp;
		}
	}
}

void permutation(char* str) {
	if(str == NULL) {
		return ;
	}

	permutation(str, 0);
}

int main() {
	char str[] = "abc";
	//char* str = "abc"; //Runtime Error
	permutation(const_cast<char*>(str));
	return 0;
}

【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笔试面试题整理】数字在排序数组中出现的次数

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笔试面试题整理】最小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;
}