`

百度面试算法题

阅读更多

#include "stdafx.h"
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#include <string.h>
#include <io.h>
/**************************************/
/*****   面试题1:两数组归并排序   ****/
/**************************************/
template<typename T>
void PrintArray(T *array, int len)
{
	int i;
	for(i=0; i<len; i++)
	{
		printf("%6d", array[i]); /* printf("%6.2f", array[i]);  printf("%6c", array[i]);*/
		if(9==i%10)   /* 每输出5个数据后,就换行 */
			printf("\n");
	}
	printf("\n"); /* 数组全部输出后,换行 */
}
/*******  算法实现1: 升(降)序判定法,时间复杂度为O(n)   *******/
template<typename T>
void MergySort(T *array1, int len1, T *array2, int len2, T *array3, int len3)
{
	int i, j, k;
	int flag1, flag2;
	/* 记录数组Array1和Array2的升序或降序规则(首尾两个元素相比较) */
	/* 表示规则:1表示升序,0表示降序 */
	flag1=(array1[0]<array1[len1-1]) ? 1 : 0;
	flag2=(array2[0]<array2[len2-1]) ? 1 : 0;
	k=0; /* 目标数组Array3的下标初始化 */
	/* if只比较一次,即进入for循环,因此时间复杂度为O(n) */
	if(1==flag1 && 1==flag2) /* 升-升: 数组Array1升序,数组Array2升序,则数组Array3仍为升序 */
	{
		i=0;
		j=0;
		while(i<len1 && j<len2)
		{
			if(array1[i]<array2[j])
				array3[k++]=array1[i++];
			else
				array3[k++]=array2[j++];
		}
		while(i<len1)
			array3[k++]=array1[i++];
		while (j<len2)
			array3[k++]=array2[j++];
	}
	else if(1==flag1 && 0==flag2) /* 升-降: 数组Array1升序,数组Array2降序,则数组Array3仍为升序 */
	{
		i=0;
		j=len2-1; /* 从末尾开始升序向前比较,依次都为升序进行排序 */
		while (i<len1 && j>=0)
		{
			if(array1[i]<array2[j])
				array3[k++]=array1[i++];
			else
				array3[k++]=array2[j--];
		}
		while(i<len1)
			array3[k++]=array1[i++];
		while (j>=0)
			array3[k++]=array2[j--];
	}	
	else if(0==flag1 && 1==flag2) /* 降-升: 数组Array1降序,数组Array2升序,则数组Array3仍为降序 */
	{
		i=0;
		j=len2-1; /* 从末尾开始倒序向前比较,依次都为降序进行排序 */
		while (i<len1 && j>=0)
		{
			if(array1[i]>array2[j])
				array3[k++]=array1[i++];
			else
				array3[k++]=array2[j--];
		}
		while(i<len1)
			array3[k++]=array1[i++];
		while (j>=0)
			array3[k++]=array2[j--];
	}
	else if(0==flag1 && 0==flag2) /* 降-降: 数组Array1降序,数组Array2降序,则数组Array3仍为降序 */
	{
		i=0;
		j=0;
		while (i<len1 && j<len2)
		{
			if(array1[i]>array2[j])
				array3[k++]=array1[i++];
			else
				array3[k++]=array2[j++];
		}
		while(i<len1)
			array3[k++]=array1[i++];
		while (j<len2)
			array3[k++]=array2[j++];
	}
}
/* 归并两个有序数组(升序或降序)到一个大数组 */
void MergeArray()
{
	/*************************************************/
	/* 测试用例1:等价划分(升升、升降、降升、降降) */
	/*************************************************/
	/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
	int array2[5]={0,3,6,9,12};*/
	int array1[10]={1,2,3,4,5,6,7,8,9,10};
	int array2[5]={12,9,6,3,0};
	/*int array1[10]={10,9,8,7,6,5,4,3,2,1};
	int array2[5]={0,3,6,9,12};*/
	/*int array1[10]={10,9,8,7,6,5,4,3,2,1};
	int array2[5]={12,9,6,3,0};*/
	int array3[15]={0};
	/*************************************************/
	/* 测试用例2:边界值分析(左边界、包含、右边界) */
	/*************************************************/
	/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
	int array2[5]={1,3,6,9,12};*/
	/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
	int array2[5]={2,3,6,8,9};*/
	/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
	int array2[5]={1,3,6,9,10};*/
	/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
	int array2[5]={0,3,6,9,10};*/
	/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
	int array2[5]={1,1,1,1,1};*/
	/*int array1[10]={10,10,10,10,10,10,10,10,10,10};
	int array2[5]={1,1,1,1,1};*/
	/*int array1[10]={10,10,10,10,10,10,10,10,10,10};
	int array2[5]={10,10,10,10,10};*/
	
	//int array3[15]={0};
	/*************************************************************/
	/* 测试用例3:经验评估测试(浮点型、字符型等非整型异常数据) */
	/*************************************************************/
	/*float array1[10]={1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9, 10.0};
	float array2[5]={1.2, 3.4, 6.7, 9.8, 12.0};
	float array3[15]={0.0};*/
	/*char array1[10]={'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};
	char array2[5]={'0', 'A', 'J', 'a', 'z'};
	char array3[15]={0.0};*/
	
	printf("\n有序数组Array1:\n");
	PrintArray(array1, 10);
	
	printf("\n有序数组Array2:\n");
	PrintArray(array2, 5);
	MergySort(array1, 10, array2, 5, array3, 15);
	printf("\n归并Array1和Array2后的有序数组:\n");
	PrintArray(array3, 15);
}

/****************************************************************/
/*****   面试题2:不借助第三方变量,交换两个整型数x和y的值   ****/
/****************************************************************/
void swap()
{
	int x, y;
	x=5;
	y=10;
	/*函数声明,引用传地址但未用第三方变量*/
	void swap1(int &x, int &y); /* 方法1 */
	void swap2(int &x, int &y); /* 方法2 */
	void swap3(int &x, int &y); /* 方法3 */
	printf("\n原始值:x=%d, y=%d\n", x, y);
	swap3(x, y);
	printf("\n交换后:x=%d, y=%d\n", x, y);
}

/****************************************/
/*******  方法1:算术运算(加减)   *******/
/****************************************/
void swap1(int &x, int &y)
{
	x=x+y; /* x存储x与y的和值(核心思想:x同时先把x和y两者的信息都存储下来) */
	y=x-y; /* 保持x内存和值不变,y先赋值,即减去y的原始值使其等于x原始的值 */
	x=x-y; /* 保持x内存和值不变,x再赋值,即减去y现在存储的原始x值,更新x值为原始y的值 */
}
/**************************************************************/
/*******  方法2:算术运算(乘除、指数运算、三角运算等)   *******/
/**************************************************************/
void swap2(int &x, int &y)
{
	x=x*y; /* x存储x与y的积值,核心思想同方法1,x同时先把x和y两者的信息都存储下来,本方法以乘除为例 */
	y=x/y; /* 保持x内存积值不变,y先赋值,即除去y的原始值使其等于x原始的值 */
	x=x/y; /* 保持x内存积值不变,x再赋值,即除去y现在存储的原始x值,更新x值为原始y的值 */
}
/****************************************/
/*******  方法3:逻辑运算(异或)   *******/
/****************************************/
void swap3(int &x, int &y)
{
	x^=y; /* x存储x与y的异或值(核心思想同上,即x先存储x和y两者信息(异或表示)) */
	y^=x; /* 保持x内存和值不变,y先赋值,即利用x异或反转y的原始值使其等于x原始的值 */
	x^=y; /* 保持x内存和值不变,x再赋值,即利用x异或反转y的原始值使其等于y原始的值 */
}
/*********************************************************/
/*******  方法4:Linux系统下,利用Python语言实现   *******/
/*********************************************************/
/**********   源代码  **********/
/*
# !/bin/sh/python
# FileName: swap.py
# Function: swap x and y not by other variable
x=5
y=10
print("swap before...")
print("x=%d, y=%d") % (x,y)
x,y=y,x  # swap x and y
print("swap after...")
print("x=%d, y=%d") % (x,y)
*/
/**********   编译方法  **********/
/*
说明:
编译环境:Redhat Linux Server 5.2
代码工具:vim文本编辑器
因为绝大部分Linux系统在安装时都会默认自带安装python
在python语言中,#表示注释
第一行 # !/bin/sh/python 告诉系统:编译此py文件的解释器路径,来编译此py源文件
第二行 Filename 注释表示此程序的文件名称为 swap.py,文件执行时不执行
第三行 Filename 注释表示此程序实现的功能,即不利用其它变量交换x和y的值
具体编译运行方法
1、登陆进入Linux系统的终端 Shell 命令界面
2、python swap.py
*/
/**********   运行结果  **********/
/*
[root@localhost python]# python swap.py
swap before...
x=5, y=10
swap after...
x=10, y=5
*/

/****************************************************************/
/*****     面试题3:统计单词出现过的文件,并给出其文件名     ****/
/****************************************************************/
/* 查找匹配文件中是否包含word单词,如果第一次查找匹配成功,则立即返回文件名 */
const char *Find_Word(const char *filePath, const char *word)
{
	FILE *pf=NULL;
	const char *pword=word;
	char ch;
	int i, len, flag;
	if (NULL==(pf=fopen(filePath, "r"))) /* 判断是否成功以只读方式打开文件 */
	{
		printf("Sorry! Cannot open file...\n");
		return NULL;
	}
	i=0;
	while (pword[i++]!='\0')
	;
	len=i-1;
	i=0;
	flag=1;
	ch=fgetc(pf);
	while(ch!=EOF) /* 循环单个字符读取文件 */
	{
		if(ch==' ') /* 英文单词以空格分隔,每当遇到空格,则flag=1表示开始匹配新单词 */
		{
			flag=1;
			ch=fgetc(pf);
			continue;
		}
		if(ch==pword[i] && i<len) /* 依次匹配单个字符,成功 */
			i++;
		else /* 匹配失败,则重置i=0 */
		{
			i=0;
			flag=0;
		}		
			
		if(i>=len && flag) /* 如果全部匹配成功,则i>=len 返回文件名 */
		{
			fclose(pf); /* 关闭打开文件 */
			pf=NULL;    /* 防止野指针 */
			return filePath;
		}
		ch=fgetc(pf);
	}
	fclose(pf);
	pf=NULL;
	return NULL;
}
/* 遍历文件夹下的所有*.txt格式文件 */
void Search_TxtFiles(const char *dirPath, const char *word)
{
	char *filePath=NULL;
	const char *findFileName=NULL;
	struct _finddata_t c_file;
	long hFile;
	if((hFile=_findfirst("*.txt", &c_file))==-1)
	{
		printf( "There is no *.txt files in current directory!\n" );
		return;
	}
	else
	{
		printf( "\nListing of files\n" );
		printf( "\n%-12s  %9ld\n", c_file.name, c_file.size );
		findFileName=Find_Word(c_file.name, word);	/* 读取第一个文件 */
		if(NULL!=findFileName)
			printf("\n\n%s is found in file: %s\n\n", word, findFileName);
		while( _findnext( hFile, &c_file ) == 0 ) /* 循环读取其它剩余文件 */
		{
			printf( "\n%-12s  %9ld\n", c_file.name, c_file.size );
			findFileName=Find_Word(c_file.name, word);	
			if(NULL!=findFileName)
				printf("\n\n%s is found in file: %s\n\n", word, findFileName);
		}
		
		_findclose( hFile );
	}
	printf("\n");
}
/* 显示目录文件夹下(相对路径)所有包含单词word的文件名(*.txt) */
void Display_FileName()
{
	char *dirPath="..\\..\\data\\txt\\*.txt";
	char *word="baidu"; /* 匹配文件中是否含有baidu的单词 */
	Search_TxtFiles(dirPath, word);
}
/* 主函数,实现面试三道C语言算法题 */
int _tmain(int argc, _TCHAR* argv[])
{
	MergeArray(); /* 算法题1: 归并两个有序数组(升序或降序) */
	
	swap();       /* 算法题2: 不借助第三方变量,交换两个整型数x和y的值 */
	Display_FileName(); /* 算法题3: 统计单词出现过的文件,并给出其文件名 */
	return 0;
}
 
分享到:
评论

相关推荐

    百度面试算法题汇总

    本资源“百度面试算法题汇总”旨在为面试者提供一系列的算法题目和解决方案,帮助他们提升在面试中的表现。下面将详细探讨这些算法题目涉及的知识点,并给出相应的解题思路。 首先,面试中常见的算法题型包括但不...

    百度面试题大收集算法

    【知识点详解】 ...以上各个知识点涵盖了算法、数据结构、操作系统、网络、数学和概率等多个IT领域,都是程序员在面试中可能会遇到的问题。理解和掌握这些知识点对于提升编程技能和解决实际问题具有重要意义。

    百度微软等算法面试题及答案

    【算法面试题】在计算机科学领域,特别是在面试过程中,算法能力是评估程序员技能的重要标准。题目涉及到了将二元查找树(BST)转换为排序的双向链表,这是一个典型的树结构转换问题,常出现在诸如百度、微软等科技...

    大厂面试算法100题

    在准备一线大厂如微软、百度的面试时,算法和数据结构是不可或缺的重点部分。下面将详细讲解两道典型的面试题及其解决方案。 1. **二元查找树转化为排序双向链表** 这道题目的核心在于如何利用二元查找树的特性...

    算法面试题100道for阿里、百度、腾讯、京东、美团、今日头条.pdf

    本书《算法面试题100道for阿里、百度、腾讯、京东、美团、今日头条.pdf》是一份面向希望进入中国顶尖互联网公司(如阿里、百度、腾讯、京东、美团、今日头条等)工作,尤其是软件开发岗位的求职者,所准备的面试材料...

    百度面试软件测试题

    "百度面试软件测试题" 标题解读 "百度面试软件测试题"是指百度公司在面试软件测试工程师时所使用的面试题库。这份文件包含了面试官在面试过程中所需的题目和答案,涵盖了软件测试的各个方面,旨在评估面试者的技术...

    2021最新面试经验,包括百度、阿里、美团、字节跳动算法面试题总结经验

    一、百度面试题 百度作为国内搜索引擎巨头,其算法面试题往往注重实际问题的解决能力。可能涉及的题目类型包括动态规划、图论、排序算法、搜索算法等。例如,可能会问到如何设计一个高效的网页爬虫系统,或者在海量...

    百度面试题

    【标题】:“百度面试题”通常指的是百度公司在招聘过程中可能会问到的问题集合,这些题目涵盖了技术、产品、设计、运营等多个领域,旨在测试应聘者的专业技能、思维逻辑以及问题解决能力。百度作为中国互联网巨头之...

    百度面试题总结

    "百度面试题总结"这个资料包很可能包含了百度在招聘过程中对C++程序员的考察点,帮助应聘者更好地准备面试。 C++的基础知识点包括: 1. **基本语法**:C++的基础始于了解变量、数据类型、运算符、流程控制(如if...

    百度微软等算法面试题及答案1.pdf

    百度微软等算法面试题及答案1.pdf

    百度面试题大全

    【百度面试题大全】涵盖了多个IT领域的知识点,包括数据结构、算法、数据库理论以及市场营销策略。以下是这些知识点的详细说明: 1. **堆和栈的区别**:堆和栈是计算机内存管理的两种基本数据结构。栈是后进先出...

    iOS 面试必看算法题

    这份"iOS面试必看算法题"集合,旨在帮助你全面了解并掌握iOS面试中可能出现的算法问题,助你顺利通过BATJ(百度、阿里巴巴、腾讯、京东)等大厂的面试。 首先,我们要理解算法是什么。算法是一系列解决问题的清晰...

    java经典算法90题含源码及答案.rar

    通过解决这些算法题,开发者可以锻炼逻辑思维,理解和掌握数据结构,如数组、链表、栈、队列、树、图等,以及排序、搜索、图论、动态规划等核心算法。 在JAVA经典算法40题.doc中,可能包含的题目类型有递归、分治、...

    百度java面试查找算法代码

    本题目的核心是一个经典的查找问题,它出现在百度的面试环节中,目的是考察候选人的逻辑思维和算法实现能力。下面将详细讨论这个问题以及提供的三种解决方案。 题目描述了一个数字序列,包含从1到1000的999个乱序的...

    C++百度面试题

    【C++百度面试题】涉及的知识点主要包括C++语言特性、操作系统原理以及算法设计。 1. **数据库死锁原理及避免策略**: - 死锁是由于资源竞争导致的两个或更多进程无法继续执行的现象。产生死锁的必要条件包括互斥...

    算法面试题精讲

    文档中是云分享的链接,其中包含了算法面试的精讲题目,能够帮助程序员理清算法的思路。

    百度校招面试笔试题

    《百度校招面试笔试题解析》 在求职竞争激烈的今天,各大互联网公司的招聘流程往往包含一系列严谨的面试和笔试环节,其中,百度作为中国互联网巨头之一,其招聘标准更是备受关注。本文将针对“百度校招面试笔试题”...

    微软百度腾讯等公司面试题和经典数据结构算法归总 chm

    微软百度腾讯等公司面试题和经典数据结构算法归总 chm格式 还有很多网页链接 你值得拥有!

Global site tag (gtag.js) - Google Analytics