从博客中整理，并不断的更新，供大家学习和交流，随后会给出部分算法题的参考代码。
腾讯
1、请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在 中所处的位置和变化。队伍可能随时有人加入和退出，当有人退出影响到用户的位置排名时需要即时反馈到用户。
2、A、B两个整数集合，设计一个算法求他们的交集，尽可能的高效。
百度
1.使用C/C++编写函数，实现字符串反转，要求不使用任何系统函数，且时间复杂度最小，函数原型：char* reverse_str(char* str)。
2.给定一个如下格式的字符串(1,(2,3),(4,(5,6),7))括号内的元素可以是数字，也可以是另一个括号，请实现一个算法消除嵌套的括号，比如把上面的表达式变成：(1,2,3,4,5,6,7)，如果表达式有误请报错。
3.分别实现二叉查找数root中两个节点的最近相连的双亲节点：递归，非递归函数。
4.给出任意一个正整数，算出大于它的最小不重复数（即不存在相邻两个数相同的情况）
5.给出一个长度为N的字符串，求里面最长的回文子串长度。
6.一幢大楼的底层有1001根电线，这些电线一直延伸到大楼楼顶，你需要确定底层的1001个线头和楼顶的1001次线头的对应关系。你有一个电池，一个灯泡，和许多很短的电线，你需要上下楼几次才能确定电线接头的对应关系.
解答：
注明：这里每次上下楼都带着电池和灯泡，以及每次接口连接，对应接口的之前连接过的线都将拆除，所以下面不再说明。
首先将底层一对接口（这里假设为（buttom1，buttom2））连接起来，然后上楼，根据提供的电池和灯泡的亮灭，确定顶层的一对（这里假设为（top1，top2）），接着将顶层的另一对连接起来（假设为（top3，top4）），然后下底层，确定和（top3，top4）对应的一对（假设为（buttom3，buttom4）），然后将底层的 buttom1和buttom3连接，底层的buttom2和buttom4连接，上楼，分别将确定过的两对交换对接，即依次测试（top1，top4），（top2，top3）或者（top1，top3),(top2,top4)，直接灯泡亮为止即可确定这四个接口的对接关系。这样第一次确定4个接口需要上下楼3次。
然后根据第一次确定的4个接口，在顶层分别和剩余的接口中的其中四个接口连接，下到底层，和第一次确定四个接口一样，即可确定8个接口。这时确定8根只需要在上面的基础上加1次就可以。接下来就可以确定16个接口，并以此指数增加，从而到2的10次方，即1024，即可全部确定1001个接口，而从2的3次方到2的10次方，共8次.
最后得出第一次确定的3次加上接下来的8次，共需11次即可确定他们的对应关系。
科大讯飞
1.求一个整数数组的最大元素，用递归方法实现。
#include <cmath>
using namespace std;
int maxnum(int a[], int n)
{
if(n == 1)
return a[0];
if(n>1)
{
return max(a[0], maxnum(a+1,n-1));
}
}
int main()
{
int num[10] = {0,1,2,3,4,5,6,7,8,9};
cout<<maxnum(num,10)<<endl;
return 0;
}
2. 已知一个整数数组A[n]，写出算法实现将奇数元素放在数组的左边，将偶数放在数组的右边。要求时间复杂度为O(n)。
void partition(int A[], int n)
{
int x;
int i = 0;
int j = n-1;
while(i != j)
{
while( a[i]%2 == 1)
i++;
while (a[j]%2 == 0)
j++;
if(i < j)
{
x = a[i];
a[i] = a[j];
a[j] = x;
}
}
}
金山办公
1.[长沙理工站]给定 一个int型的整数，编程输出其LED显示屏形式。如0为：
---
| |
| |
| |
---
每个数字之间用空格分开。
2.[湖南大学站]有一个函数：
void unique(std::vector<int> &v);
用来给数组去重，试写一段测试代码检查其正确性。
提示1：尽可能找出bug
提示2：你的代码应该返回int型，0表示测试通过，1表示出错。
3.有如下函数原型:
void transferToChinese(int num);（ps:函数名记不太清了，但是无关紧要）
该函数把小于一亿的int型数字转换成中文表示，如：
17：一十七；
110：一百一十；
12345：一万两千三百四十五；
10101：一万零一百零一
提示：注意零的情况。
拓展：考虑缩写情况，如：
17：十七
美团网
1.链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现。
#include <iostream>
using namespace std;
struct ListNode
{
int m_nValue;
ListNode *m_pNext;
};
ListNode* CreateList(int val)
{
ListNode *pHead = new ListNode;
pHead->m_nValue = val;
pHead->m_pNext = NULL;
return pHead;
}
void InsertNode(ListNode **pHead, int val)
{
ListNode *pNode = new ListNode;
pNode->m_nValue = val;
pNode->m_pNext = NULL;
while ((*pHead)->m_pNext != NULL)
{
(*pHead) = (*pHead)->m_pNext;
}
(*pHead)->m_pNext = pNode;
(*pHead) = pNode;
}
void PrintList(ListNode *pHead)
{
while (pHead != NULL)
{
cout<<pHead->m_nValue<<" ";
pHead = pHead->m_pNext;
}
cout<<endl;
}
ListNode* Reverse(ListNode *pHead)
{
if (pHead == NULL || pHead->m_pNext == NULL)
{
return pHead;
}
ListNode *pPre = NULL;
ListNode *pCurrent = pHead;
ListNode *pPost = pHead->m_pNext;
while (pCurrent->m_pNext != NULL)
{
pCurrent->m_pNext = pPre;
pPre = pCurrent;
pCurrent = pPost;
pPost = pPost->m_pNext;
}
pCurrent->m_pNext = pPre;
return pCurrent;
}
ListNode* ReverseList(ListNode *pHead, int k)
{
if (pHead==NULL || pHead->m_pNext==NULL)
{
return pHead;
}
ListNode *pPre = NULL;
ListNode *pCurrent = pHead;
ListNode *pPost = pHead->m_pNext;
ListNode *pStart = NULL;
ListNode *pEnd = NULL;
int n = 0;
pEnd = pCurrent;
pEnd->m_pNext = NULL;
while (pPost != NULL)
{
++n;
if (n == (k+1))
{
pStart = pPre;
pEnd->m_pNext = ReverseList(pCurrent, k);
return pStart;
}
else
{
pCurrent->m_pNext = pPre;
pPre = pCurrent;
pCurrent = pPost;
pPost = pPost->m_pNext;
}
}
pCurrent->m_pNext = pPre;
pStart = Reverse(pCurrent);
return pStart;
}
int main()
{
ListNode *pHead = NULL;
ListNode *head = NULL;
int n;
cout<<"输入链表中节点的个数 n："<<endl;
cin>>n;
cout<<"请输入n个整数值："<<endl;
for (int i=0; i<n; ++i)
{
int data;
cin>>data;
if (pHead == NULL)
{
pHead = CreateList(data);
head = pHead;
}
else
{
InsertNode(&pHead, data);
}
}
int k;
cout<<"请输入k:"<<endl;
cin>>k;
head = ReverseList(head, k);
PrintList(head);
system("pause");
return 0;
}
2.一个函数access(),调用频率不能超过R次/sec，用程序实现一个函数，当超过R次/sec时返回access false，不超过时返回success
#define false 0
#define success 1
int getcurrentms()
{
struct timeval tv;
gettimeofday(&tv,NULL);
return tv.tv_sec*1000+tv.tv_usec/1000; //得到毫秒数
}
bool count_access()
{
static int count=0;
static int time_ms_old=0,time_ms_now;
if(count==0)
{
time_ms_old=getcurrentms();
}
count++;
access();
if(count>=R)
{
time_ms_now=getcurrentms();
if(time_ms_now-time_ms_pld>=1000)
return false;
else
return success;
}
return success;
}
3. 一个m*n的矩阵，从左到右从上到下都是递增的，给一个数elem，求是否在矩阵中，给出思路和代 码.
去哪儿网
1.写一个函数，转换相对路径为绝对路径，比如：/home/abs/../temp/new/../,输出路径为：/home/temp。
2.一个10*10的矩阵（可以理解为棋盘），随时生成一组数据填入矩阵，任何一个位置的数字除4进行计算，按余数着色，余数为0着色为red，1为blue，2为green，3为black，可以理解为生成4中颜色的棋子放入棋盘，如果存在其中同色五星连珠的情况（规则通五子棋），找出任意一组，输出5个棋子的位置下标值。
3.
有两个文件context.txt和words.conf,请尝试将他们合并成为一段文字，并打印出来。
这两个文件内容如下：
context.txt
“并不是每个人都需要$(qunar)自己的粮食，$(flight.1)每个人都需要做自己穿的$(fight.2)，我们说着别人发明的$(hotel)，使用别人发明的数学......我们一直在$(tuan)别人的成果。使用人类的已有经验和知识$(travel.1)来进行，是一件$(travel.2)的事情”
word.conf
flight=也不是：衣服
qunar=种植
hotel=语言
tuan=使用
travel=发明创造：很了不起
4.
一个文件里有10万个随机正整数，按照以下规则能组合出一份新的数据：
A． 如果当前数字能被3整除，那么它和文件中所有数字（包括自己）两两相加后生成一组数字替代自己的位置。
B． 如果不能被3整除，则它只需要乘以二，生成一个数字替代自己的位置。
例如：[3,7,6] 会组合出[6,10,9,14,9,13,12]
再如：[5,12,9,6,2]会组合出[10,17,24,21,18,14,14,21,18,15,11,11,18,15,12,8,4]
写一个程序找出并打印出新数据的最小的前200个数字。请考虑优化算法复杂度。
5.已知字母序列【d, g, e, c, f, b, o, a】，请实现一个函数针对输入的一组字符串 input[] = {"bed", "dog", "dear", "eye"}，按照字母顺序排序并打印。
本例的输出顺序为：dear, dog, eye, bed。
6. 有一万个北京单身男女向你提交了基本资料，包括：姓名、性别、年龄、星座，写一段程序尝试找出他们最匹配的一对。
华为
1.
通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。
比如字符串“abacacde”过滤结果为“abcde”。
要求实现函数：void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr);
【输入】 pInputStr： 输入字符串
lInputLen： 输入字符串长度
【输出】 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；
【注意】只需要完成该函数功能算法，中间不需要有任何IO的输入输出
示例
输入：“deefd” 输出：“def”
输入：“afafafaf” 输出：“af”
输入：“pppppppp” 输出：“p”
main函数已经隐藏，这里保留给用户的测试入口，在这里测试你的实现函数，可以调用printf打印输出
当前你可以使用其他方法测试，只要保证最终程序能正确执行即可，该函数实现可以任意修改，但是不要改变函数原型。
一定要保证编译运行不受影响
//////////////////////////////////////////////////////////////////////////华为第一题 19:19-19:36 17分钟
#include <iostream>
#include <cassert>
using namespace std;
bool g_flag[26];
void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr)
{
assert(pInputStr != NULL);
int i = 0;
if (pInputStr == NULL || lInputLen <= 1)
{
return;
}
const char *p = pInputStr;
while(*p != '\0')
{
if (g_flag[(*p - 'a')])
{
p++;
}else{
pOutputStr[i++] = *p;
g_flag[*p - 'a'] = 1;
p++;
}
}
pOutputStr[i] = '\0';
}
int main()
{
memset(g_flag,0,sizeof(g_flag));
char input[] = "abacacde";
char *output = new char[strlen(input) + 1];
stringFilter(input,strlen(input),output);
cout<<output<<endl;
delete output;
return 0;
}
2.
通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。
压缩规则：
1、仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc"。
2、压缩字段的格式为"字符重复的次数+字符"。例如：字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。
要求实现函数：
void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr);
【输入】 pInputStr： 输入字符串
lInputLen： 输入字符串长度
【输出】 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；
【注意】只需要完成该函数功能算法，中间不需要有任何IO的输入输出
示例
输入：“cccddecc” 输出：“3c2de2c”
输入：“adef” 输出：“adef”
输入：“pppppppp” 输出：“8p”
//////////////////////////////////////////////////////////////////////////华为第二题 19:40 - 20:10 中间耽误3分钟
#include <iostream>
#include <cassert>
using namespace std;
void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr)
{
const char *p = pInputStr;
int num = 1;
int i = 0;
p++;
while(*p != NULL)
{
while(*p == *(p-1)&& *p != NULL)
{
num++;
p++;
}
if (num > 1)
{
int size = 0;
int temp = num;
while(num) //计算位数
{
size++;
num /= 10;
}
num = 1;
for (int j = size; j > 0; j--)
{
pOutputStr[i+j-1] = '0'+ temp%10;
temp /= 10;
}
i +=size;
pOutputStr[i++] = *(p-1);
p++;
}else{
pOutputStr[i++] = *(p-1);
p++;
}
}
pOutputStr[i] = '\0';
}
int main()
{
char input[] = "cccddecc";
char *output = new char[strlen(input) + 1];
stringZip(input,strlen(input),output);
cout<<output<<endl;
return 0;
}
3. 通过键盘输入100以内正整数的加、减运算式，请编写一个程序输出运算结果字符串。
输入字符串的格式为：“操作数1 运算符 操作数2”，“操作数”与“运算符”之间以一个空格隔开。
补充说明：
1、操作数为正整数，不需要考虑计算结果溢出的情况。
2、若输入算式格式错误，输出结果为“0”。
要求实现函数：
void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr);
【输入】 pInputStr： 输入字符串
lInputLen： 输入字符串长度
【输出】 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；
【注意】只需要完成该函数功能算法，中间不需要有任何IO的输入输出
示例
输入：“4 + 7” 输出：“11”
输入：“4 - 7” 输出：“-3”
输入：“9 ++ 7” 输出：“0” 注：格式错误
//////////////////////////////////////////////////////////////////////////华为第三题 20:29 - 20:40
#include <iostream>
using namespace std;
void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr)
{
const char *input = pInputStr;
char *output = pOutputStr;
int sum = 0;
int operator1 = 0;
int operator2 = 0;
char *temp = new char[5];
char *ope = temp;
while(*input != ' ') //获得操作数1
{
sum = sum*10 + (*input++ - '0');
}
input++;
operator1 = sum;
sum = 0;
while(*input != ' ')
{
*temp++ = *input++;
}
input++;
*temp = '\0';
if (strlen(ope) > 1 )
{
*output++ = '0';
*output = '\0';
return;
}
while(*input != '\0') //获得操作数2
{
sum = sum*10 + (*input++ - '0');
}
operator2 = sum;
sum = 0;
switch (*ope)
{
case '+':itoa(operator1+operator2,pOutputStr,10);
break;
case '-':itoa(operator1-operator2,pOutputStr,10);
break;
default:
*output++ = '0';
*output = '\0';
return;
}
}
int main()
{
char input[] = "4 - 7";
char output[] = " ";
arithmetic(input,strlen(input),output);
cout<<output<<endl;
return 0;
}
4.输入1--50个数字，求出最小数和最大数的和
//华为2014年机试题1：输入1--50个数字，求出最小数和最大数的和
//输入以逗号隔开
#include<stdio.h>
#define N 50
void sort(int a[],int n);
int main(void)
{
char str[100];
int a[N]={0};
gets(str); //要点1：动态的输入1--50个整数，不能确定个数，只能用字符串输入，然后分离出来
int i=0;
int j=0;
int sign=1;
while(str[i]!='\0')
{
if(str[i]!=',') //输入时要在半角输入
{
if(str[i] == '-') //要点:2：有负整数的输入
{
// i++; //易错点1
sign=-1;
}
else if(str[i]!='\0') //不用else的话，负号也会减去‘0’
{
a[j]=a[j]*10 + str[i]-'0'; //要点3：输入的可以是多位数
}
}
i++;
if(str[i]==',' || str[i]=='\0') //这个判断是在i自加以后
{
a[j]=a[j]*sign; //易错点2
sign=1; ////易错点3
j++; //j就是a数组的个数 范围0到j-1
}
}
sort(a,j);
printf("Max number + Min number = %d",a[0]+a[j-1]);
return 0;
}
void sort(int a[],int n) //选择排序
{
int i,j;
int k;
int temp;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
{
if(a[k]>a[j])
k=j;
}
if(i!=k)
{
temp = a[k];
a[k] = a[i];
a[i] = temp;
}
}
for(i=0;i<n;i++)
printf("%-5d",a[i]);
puts("");
}
暴风影音
1.自定义实现字符串转为整数的算法，例如把“123456”转成整数123456.(输入中可能存在符号，和数字)
//返回结果的有效标志
enum Status {VALID,IN_VALID};
int gStatus = VALID;
int strToInt(const char* str)
{
long long result = 0;//保存结果
gStatus = IN_VALID; //每次调用时都初始化为IN_VALID
if(str != NULL)
{
const char* digit = str;
bool minus = false;
if(*digit == '+')
digit++;
else if(*digit == '-')
{
digit++;
minus = true;
}
while(*digit != '\0')
{
if(*digit >= '0' && *digit <= '9')
{
result = result * 10 + (*digit -'0');
//溢出
if(result > std::numeric_limits<int>::max())
{
result = 0;
break;
}
digit++;
}
//非法输入
else
{
result = 0;
break;
}
}
if(*digit == '\0')
{
gStatus = VALID;
if(minus)
result = 0 - result;
}
}
return static_cast<int>(result);
}
2. 给出一棵二叉树的前序和中序遍历，输出后续遍历的结果，假设二叉树中存储的均是ASCII码。如前序：ABDHECFG，中序：HDBEAFCG，则输出后序为：HDECFGCA。
思路：先利用前序和中序构建出二叉树，然后后序遍历输出结果
/**
*返回二叉树的根节点
*preOrder:前序遍历序列
*inOrder:中序遍历序列
*len:节点数目
*/
Node* getBinaryTree(char* preOrder, char* inOrder, int len)
{
if(preOrder == NULL || *preOrder == '\0' || len<=0)
return NULL;
Node* root = (Node*) malloc(sizeof(Node));
if(root == NULL)
exit(EXIT_FAILURE);
//前序遍历的第一个节点就是根节点
root->data = *preOrder;
int pos = 0;//找到根节点在中序遍历中的位置，其值也代表了左子树的节点数目
while(true)
{
if(*(inOrder+pos) == root->data)
break;
pos++;
}
//通过递归找到左子树和右子树，注意子树的前序中序的下标的计算
if(pos == 0)
root->lchild = NULL;
else
root->lchild = getBinaryTree(preOrder+1, inOrder, pos);
if(len-pos-1 == 0)
root->rchild = NULL;
else
root->rchild = getBinaryTree(preOrder+pos+1, inOrder+pos+1,len-pos-1);
return root;
}
/**
*后续遍历二叉树
*
*/
void postOrder(Node* root)
{
if(root == NULL)
return;
postOrder(root->lchild);
postOrder(root->rchild);
printf("%c", root->data);
}
/**
*根据前序遍历和中序遍历输出后续遍历
*
*/
void printPostOrderViaPreOrderAndInorder(char* preOrder, char* inOrder)
{
Node* root = getBinaryTree(preOrder, inOrder, strlen(preOrder));
postOrder(root);
}
3. 给出了一个n*n的矩形，编程求从左上角到右下角的路径数（n > =2），限制只能向右或向下移动，不能回退。例如当n=2时，有6条路径。
一是利用数学知识，从左上角到右下角总共要走2n步，其中横向要走n步，所以总共就是C2n~n。
二是利用递归实现
/**
*返回总路径数
*参数m:表示矩形的横向格子数
*参数n:表示矩形的纵向格子数
*/
int getTotalPath(int m, int n)
{
//如果横向格子数为1，则类似“日”字，此时路径数为纵向格子数加1
if(m == 1)
return n + 1;
//如果纵向格子数为1，此时路径数为横向格子数加1
if(n == 1)
return m + 1;
//由于从当前点出发，只能向右或向下移动：
//向右移动，则接下来就是getTotalPath(m-1, n)的情形
//向下移动，则接下来就是getTotalPath(m, n-1)的情形
return getTotalPath(m-1, n) + getTotalPath(m, n-1);
}
阿里巴巴
1.两棵二叉树T1和T2，T1的节点数是百万量级，T2的节点数一千以内，请给出判断T2是否T1子树的可行算法。
分析：首先想到的是递归，但是T1的数量级太大，递归会导致栈溢出，于是以非递归实现。
bool IsSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) {
if (pRoot1 == NULL || pRoot2 == NULL) {
return false;
}
stack<BinaryTreeNode*> stk;
stk.push(pRoot1);
while (!stk.empty()) {
BinaryTreeNode *tmp = stk.top();
stk.pop();
if (tmp->m_nValue == pRoot2->m_nValue) {
stack<BinaryTreeNode*> first;
BinaryTreeNode *f;
stack<BinaryTreeNode*> second;
BinaryTreeNode *s;
first.push(tmp);
second.push(pRoot2);
bool find = true;
while (!first.empty()) {
f = first.top();
first.pop();
s = second.top();
second.pop();
if (f->m_nValue != s->m_nValue) {
find = false;
break;
}
if (s->m_pLeft != NULL) {
if (f->m_pLeft == NULL) {
find = false;
break;
} else {
first.push(f->m_pLeft);
second.push(s->m_pLeft);
}
}
if (s->m_pRight != NULL) {
if (f->m_pRight == NULL) {
find = false;
break;
} else {
first.push(f->m_pRight);
second.push(s->m_pRight);
}
}
}
if (find == true && first.empty()) {
return true;
}
}
if (tmp->m_pLeft != NULL) {
stk.push(tmp->m_pLeft);
}
if (tmp->m_pRight != NULL) {
stk.push(tmp->m_pRight);
}
}
return false;
}
2.
从1到500的500个数，第一次删除奇数位，第二次删除剩下来的奇数位，以此类推，最后剩下的唯一一位数是：
A.500 B.256C.250 D.128
3.
人人网
1.给出一个有序数组啊，长度为len，另外给出第三个数X，问是否能在数组中找到两个数，这两个数之和等于第三个数X。
我们首先看到第一句话，这个数组是有序的，所以，我们可以定义两个指针，一个指向数组的第一个元素，另一个指向应该指向的位置（这个需要看具体的实现和数组给定的值），首先计算两个位置的和是否等于给定的第三个数，如果等于则算法结束，如果大于，则尾指针向头指针方向移动，如果小于，则头指针向尾指针方向移动，当头指针大于等于尾指针时算法结束，没有找到这样的两个数。
解法一：
#include <stdio.h>
int judge(int *a, int len, int k, int *num1, int *num2);
int main(int argc, char **argv)
{
int test_array[] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
int result = -1;
int num1, num2;
result = judge(test_array, sizeof(test_array) / sizeof(int), 12, &num1, &num2);
if(result == 0)
{
printf("%d\t%d\n", num1, num2);
}
else if(result == -1)
{
printf("can't find");
}
else
{
printf("error");
}
}
int judge(int *a, int len, int k, int *num1, int *num2)
{
int *low = NULL;
int *high = NULL;
int i = 0;
int result = -1;
if(a == NULL || len < 2)
{
return result;
}
if(a[0] >= k)
{
return result;
}
while(a[i] <= k && i < len)
{
i++;
}
low = a;
high = a + i - 1;
while(low < high)
{
*num1 = *low;
*num2 = *high;
if((*low + *high) == k)
{
result = 0;
break;
}
else if((*low + *high) > k)
{
high--;
}
else if((*low + *high) < k)
{
low++;
}
}
return result;
}
解法二：
#include <iostream>
using namespace std;
int hash_table[100];
bool judge(int *a, int len, int x)
{
memset(hash_table, 0, sizeof(hash_table));
for (int i=0; i<len; ++i)
{
hash_table[x - a[i]] = 1;
}
for (int i=0; i<len; ++i)
{
if (hash_table[i] == 1)
{
return true;
}
}
return false;
}
int main()
{
int len = 10;
int a[10] = {1, 3, 5, 7, 9, 4, 2, 8, 10, 6};
int x = 19;
if (judge(a, len, x))
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
system("pause");
return 0;
}
本题解决方法：hash table。
时间复杂度：O(N)
空间复杂度：O(N)
2.给定有n个数的数组a，其中有超过一半的数为一个定值，在不进行排序，不开设额外数组的情况下，以最高效的算法找出这个数。
int find(int* a, int n);
#include <iostream>
using namespace std;
int find(int *a, int n)
{
int t = a[0];
int count = 0;
for (int i=0; i<n; ++i)
{
if (count == 0)
{
t = a[i];
count = 1;
continue;
}
else
{
if (a[i] == t)
{
count++;
}
else
{
count--;
}
}
}
return t;
}
int main()
{
int n = 10;
int a[10] = {1, 3, 2, 3, 3, 4, 3, 3, 3, 6};
cout<<find(a, n)<<endl;
system("pause");
return 0;
}
Time Complexity: O(n)
Space Complexity:O(1)
美团
1.利用两个栈，模拟queue
#include <iostream>
#include <stack>
using namespace std;
template <class T>
class Queue
{
public:
Queue()
{
}
~Queue()
{
}
void add(const T& t);
T remove();
private:
stack<T> s1;
stack<T> s2;
};
template <class T>
void Queue<T>::add(const T& t)
{
s1.push(t);
}
template <class T>
T Queue<T>::remove()
{
if (s2.size() <= 0)
{
while (s1.size() > 0)
{
T t = s1.top();
s2.push(t);
s1.pop();
}
}
if (s2.size() == 0)
{
throw new exception("empty queue");
}
T t = s2.top();
s2.pop();
return t;
}
int main()
{
Queue<char> q;
q.add('A');
q.add('B');
q.add('C');
cout<<q.remove()<<endl;
cout<<q.remove()<<endl;
cout<<q.remove()<<endl;
system("pause");
return 0;
}
2.求两个字符串的最长公共子串
public class MaxConString {
/**
* 计算两字符串最大公共字符串长度
*/
public static void main(String[] args) {
char[] s1 = "jiajiangayaoyao".toCharArray(); //测试数据
char[] s2 = "jiangyaoyao".toCharArray();
int c = new MaxConString().getCount(s1, s2);
System.out.println("两字符串的共同字符串长度为:"+c);
}
private int getSubCount(char[] s1,char[] s2, int i ,int j){//计算两字符串从s1的第i位置s2的第j位置的之后字符串长度
//如“abc”和“ab”则返回conut为2
int count=1;
while(++i<s1.length&&++j<s2.length&&s1[i]==s2[j]){
count++;
}
return count;
}
private int getCount(char[]s1,char[]s2){ //计算两字符串的共同字符串长度
int count = 0;
for(int i=0;i<s1.length;i++)
for(int j=0;j<s2.length;j++)
if(s1[i]==s2[j]){
if(this.getSubCount(s1, s2, i, j)>count)
count = this.getSubCount(s1, s2, i, j);
}
return count;
}
}
创新工场
1. 堆排序
#include<iostream>
usingnamespace std;
void SwapValue(int &m, int &n)
{
int temp = m;
m = n;
n = temp;
}
void max_heap(vector<int> &vec, int i, int heap_size)
{
int l = 2*i;
int r = 2*i+1;
int largest = i;
if(l<=heap_size && vec[l-1]>vec[largest-1])
largest = l;
if(r<=heap_size && vec[r-1]>vec[largest-1])
largest = r;
if(largest!=i)
{
SwapValue(vec[largest-1],vec[i-1]);
max_heap(vec, largest, heap_size);
}
}
void heapSort(vector<int> &vec)
{
int heap_size = vec.size();
for(int i=heap_size/2; i>=1; i--)
max_heap(vec, i, heap_size);
for(int i=heap_size; i>=1; i--)
{
SwapValue(vec[0],vec[i-1]);
max_heap(vec, 1, i);
}
}
void print(vector<int> vec)
{
for(int i=0; i<vec.size(); i++)
cout<<vec[i]<<" ";
cout<<endl;
}
int main()
{
vector<int> vec;
vec.push_back(23);
vec.push_back(5);
vec.push_back(1);
vec.push_back(10);
vec.push_back(13);
vec.push_back(32);
vec.push_back(21);
vec.push_back(14);
vec.push_back(19);
vec.push_back(20);
cout<<"排序前： "<<endl;
print(vec);
heapSort(vec);
cout<<"排序后： "<<endl;
print(vec);
return 0;
}
2.求一个正整数N的开方，要求不能用库函数sqrt()，结果的精度在0.001
解析：牛顿迭代
#include<iostream>
using namespace std;
int main()
{
int N;
cout<<"输入N的值：";
cin>>N
double x1 = 1;//初值
double x2 = x1/2.0+N/2.0/x1;
while( fabs(x2-x1)>0.001)
{
x1 = x2;
x2 = x1/2.0+N/2.0/x1;
}
cout<<x1<<endl;
return 0;
}
3.给定一个矩阵intmaxtrixA[m][n],每行和每列都是增序的，实现一个算法去找矩阵中的某个元素element.
解法一：
#include<iostream>
using namespace std;
const int M = 4;
const int N = 4;
int main
{
int matrix[M][N] = {};
double element;
int flag = 1;
for(int j=0; j<N; j++)
{
if(matrix[i][j] == element)
cout<<"位置"<<endl;
while( flag<M && matrix[i][j]<element )
--flag;
while( flag<M && matrix[i][j]>element )
++flag;
}
}
解法二：
bool Find(int *matrixA, int m, int n, int element)
{
bool found = false;
if(matrixA != NULL & m & n)
{
int i,j;
i=0;j=n-1;
while(i<m;j>=0)
{
if(maxtrixA[i*n+j] == element)
{
found = true;
break;
}
else if(matrix[i*n+j]>element
--j;
else
++i
}
}
}
优酷
1.N个台阶，1<=N<90,每次一个台阶或两个台阶，求到达台阶N共有多少种方法
2.将long型整数转换成字符串，不能使用库函数
3.含有n个元素的整型数组，将这个n个元素重新组合，求出最小的数，如{321,3,32}，最小的数为 321323
4.有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。 木杆很细，不能同时通过一只蚂蚁。开始 时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头， 但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。 编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间。
网易
1、f(0)=0;f(1)=1；f(n)=f(n-1)+f(n-2)，求f（n）。
2、有主字符串A，子字符串B，在A中查找B
3、写出你熟悉的排序算法，并说明其优缺点