题意：有一个隐藏数字N，2<=N<=100。要求在20次查询后，确定N是否为支数。
每一次你可以输出一个数字a，系统会判定a是否为N的除数（YES or NO）。

思路：N只有两种可能，合数或质数。
其中，质数是的除数只有1和本身。合数的除数至少有3个（1，本身，K）。
因此，合数=质数*质数。
所以，可以枚举小于50的所有质数，依次询问这些质数是否为N的除数，如果是除数的次数>=2，则即可判定为合数。

注意点：2^n,3^n,5^n,7^n,都是有相同的质数乘积得到。所以按照上面的逻辑判断后，最后得到次数只有1次。
显然是错误的，因此需要再添加4，9，15，49。
因此，最会需要查询的数字包括[2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49];

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

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

int main()
{
	//freopen("in.txt", "r", stdin);
	int num[] = {2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49};
	string str;
	int cnt = 0;
	for (int i = 0; i < 19; ++i)
	{
		cout<<num[i]<<endl;
		cin>>str;
		if(str == "yes")
			cnt++;
	}
	if(cnt >=2)
		cout<<"composite"<<endl;
	else
		cout<<"prime"<<endl;
	//fclose(stdin);  
	return 0;
}

1、关于大整数问题

1
2
3

long long a;
unsigned long long b;
cin>>a>>b;

2、关于输出精度问题

1
2
3
4
5
6

#include <iomanip.h> 
int main()
{
	cout.setf(ios::fixed); 
	cout<<<<setprecision(6)<<endl;  //固定小数点后6位
}

3、关于vector的二维数组

1
2
3

vector<vector<int> >dp(n);//定义n维的数组,每一维列数未定（初始为0），GCC
vector<vector<int> >dp(n,0);//与上相同，但是在GCC中编译不过，VS2010可以通过
vector<vector<int> >dp(n,vector<int>(m,0));//n行m列数组，初始都为0;GCC,VS2010

4、关于std::assign用法

1
2
3

vector<int> a(10,9);
vector<int> b;
b.assign(a.begin(),a.end());//The range used is [first,last)

5、关于字符串截取

1
2

string str("abcdf");
str.substr(0,3); //函数原型string substr (size_t pos = 0, size_t len = npos) const;

6、关于三角函数

1
2
3

#include <cmath>
const double pi = acos(-1);  //获取pi的值
double thea = angle * pi / 180; //angle的弧度制

7、关于幂

1
2

#include <cmath>
pow(double x, Int y); //x^y,x必须是浮点数，不能为整数

8、关于int最大值，最小值的表示方法

1
2

int a = 1<<31;            //32位int最小值
int b = int(1<<31) - 1;	  //32位int最大值

9、关于大数

1
2

typedef long long LL;
const LL Inf = (LL)1e18;

10、个人出WA后，犯的错误总结
（1）、逻辑错误（例如：微软员工福利，把结果放在了循环里面）
（2）、题意理解错误（仔细读题）
（3）、容易被样例误导（例如，腾讯的简单游戏，样例只有两组护卫队，其实实际数据有n支护卫队，导致逻辑错误）
（4）、几何题（把数学公式推导完毕后，再写）
（5）、关于图、树的问题（建树，建图比较重要）
（6）、对于小规模的题，一般暴力枚举可以搞定。

11、重定向输入输出流

1
2
3
4

freopen("in.txt", "r", stdin);
freopen("out.txt", "W", stdout);
fclose(stdin);
fclose(stdout);

这几天做了计蒜客编程比赛，被一道题目卡了很久，辗转很久，找管理看了源码后，感悟非ACM选手，写算法题真的是会丧智啊！！
不过呢，积累点知识也是不错的，毕竟再过几个月还要参加校招，肯定回有所帮助的。ps,刷题真的超级费时间哦~~

今天，写点关于最大公约数的知识点，这个是很常见的文题了，一般的算法题绝对不会赤裸裸的考你最大公约数，不过有些题目是会用到的。

说到最大公约数，不知道欧几里得算法，想必也有耳闻吧。哈哈，博主其实就是后者啦。数学渣~~~
简单来说下这个定理。
先给出结论：gcd(a,b) = gcd(b,a mod b); gcd表示求最大公约数。
证明：任意的数a可以写成 a = kb + r,其中k = a/b,r = a%b
那么，r = a - kb.
假设，d是a,b的最大公约数。即d也是r的公约数
所以，gcd(a,b) = gcd(b,r);

代码：

1
2
3
4

int gcd(int a, int b)
{
	return b==0 ? a ? gcd(b,a%b); 
}

题意:给定一个排序数组（小->大），取数组中的三个元素a,b,c;满足a+b+c=0,a<=b<=c;
举例：A=[-1,-1,-1,0,1,2,3],result=[-1,-1,2],[-1,0,1];
思路：双指针思想+枚举。
当枚举数组的第一个元素时，设置两个指针left,right分别指向数组的第一元素和最后一个元素。
当a[left]+a[right] > (-a[i]),right– (0<=i0时，直接结束，因为数组是递增的，绝不会再出现a+b+c=0的情况；
（2）去掉重复判断，当a[i-1]==a[i],可以直接跳过第i次循环

代码：

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	while(cin>>n)
	{
		if(n == 0) continue;
		vector<int> dp(n,0);
		for (int i = 0; i < n; ++i)
		{
			cin>>dp[i];
		}
		sort(dp.begin(),dp.end());
		//双指针
		for (int i = 0; i < n; ++i)
		{
			if(dp[i] >0) break;
			if(i>0 && dp[i-1]==dp[i])
				continue;
			int a = dp[i];
			int left = i+1;
			int right = n-1;
			while(left < right)
			{
				int b = dp[left];
				int c = dp[right];
				if(-a < b + c)
					right--;
				else if(-a > b + c)
					left++;
				else 
				{
					cout<<a<<" "<<b<<" "<<c<<endl;
					do
					{
						left++;
					} while (left < right && dp[left-1] == dp[left]);
					do
					{
						right--;
					} while (left < right && dp[right+1] == dp[right]); 
				}
			}
		}
	}
}

给定一个数组，求去掉重复元素后数组的长度。

思路:双指针，设定两个指针i,j分别指向数组的初始的两个元素，当a[i] != a[j],累加j,i保持不变。当a[i]==a[j]，累加i,将a[i]=a[j],再累加j。
双指针的思想，O(n)的时间复杂度。
举例：
A=[1,1,2,3,3,4]
(1) i=0,j=1. a[i]==a[j],j++ 数组元素未变
(2) i=0,j=2, a[i]!=a[j],i++,a[i]=a[j],j++. 数组变为A[1,2,2,3,3,4]
(3) i=1,j=3, a[i]!=a[j],i++,a[i]=a[j],j++. 数组变为A[1,2,3,3,3,4]
(4) i=2,j=4, a[i]==a[j],j++, 数组元素未变
(5) i=2,j=5, a[i]!=a[j],i++,a[i]=a[j],j++, 数组变为A[1,2,3,4,3,4]
(6) j=6 结束循环，此时的i+1即是去重后元素的个数。

代码：

1
2
3
4
5
6
7
8
9
10
11
12

int RemeoveDuplicate(int*a, int size)
{
    int i=0,j;
    for(j=i+1; j<size; ++j)
    {
        if(a[i] != a[j])
        {
            a[++i] = a[j];
        }
    }
    return i+1;
}

本题题意

给出一个矩阵，再给定两个坐标，分别表示子矩阵左上角与右下角的坐标，求子矩阵元素总和。
例如：
矩阵 A=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]],子矩阵左上角坐标（0，1），右下角坐标（2，3）
那么，sum(0,1,2,3) = 2+3+4+6+7+8+10+11+12=63

思路：最直接的方法就是直接遍历子矩阵的所有元素，就可以搞定！时间复杂度为O(n^2)，但是超时了，因此需要优化。
受到积分图的启发，可以实现时间复杂度为O(1)!，什么！这么快。什么是积分图？
积分图的定义：矩阵中的某元素A的积分是矩阵左上角的顶点与A点围成的矩阵所有元素的总和。

本题的题意

给定两个数组，求数组的交集。

思路：假如有数组A，B，那么可以遍历数组B的元素，查看是否有在A中出现，如果有，就是交集中的一个元素。
注意点：
1、如果B中的某个元素是交集中的元素，且该元素在B中重复出现，就不要再讲其放入到交集中了，因为交集中的元素要保证唯一性。
可以采用std::set，先将A，B中重复的元素提前过滤掉，再讲B中元素一次插入到A中，如果插入失败，说明此元素是交集中的一元。

本题给你一个已经排好序的整形数组（元素不会出现重复），求其中数字连续的片段。
例如：A[0,1,2,4,5,7],返回[“0-2”,”4->5”,”7”].

本题思路：从头遍历一遍数组，如果a[i]+1 != a[i+1]，那么在a[i]与a[i+1]不连续，就输出a[start]->a[i]，其中start为开始的位置，提前记录下就好。
几个注意点：
1、如果连续片段只有一个数字，就只输出该数字，并非”数字->数字”
2、每次开始找连续片段前，可以提前判断下是否有丢失的数字，如果没有，就没必要遍历，直接可以返回。
例如：A[1,2,3,4,5] 因为，A[4]-A[0]+1 == A.size()。表示数组是连续的，没有数字丢失。因此就可以直接返回结果，节省时间。
3、整形数组，考虑它的范围
4、边缘条件：空数组，元素只要一个

本题的题意是给定一个整数N，将其拆分为至少两个正数，且这些正数的和为N，求所有拆分种类中这些正数的乘积最大！
思路，枚举发现规律。
如下：7 = 3+2+2 F(7)=3^1 2^2 = 12
8 = 3+3+2 F(8)=3^2 2^1 = 18
9 = 3+3+3 F(9)=3^3 2^0 = 27
10 = 3+3+2+2 F(10)=3^2 2^2 = 36
可以发现，N = 3a+2b,(a,b为数字3，数字2的个数)，F(N)=3^a+2^b。因此，可以先通过N/3求得有多少个3构成，如果余数为0，则没有数字2；余数为2，则有一个2；余数为1，则数字3减少1个，添加两个2（如10=3+3+3+1 转变成 3+3+2+2）。
最后考虑边缘条件，当N=2，N=3的情况。

周日笔试，周四收到电话通知，周五去面试。
面试的形式是一个部门经理，同时面两个学生。
和我主要聊了网络模型，其中的一个项目中的一些东西，操作系统，数据库，网络等的一些基础知识。
总体来说，恒生的面试偏简单，没有网易的复杂。而且，恒生这边还是蛮急用C/C++开发的。
不过比较遗憾的是，经理要求最好能够连续实习5-6个月，前两个月教你一些基础的业务，让你熟悉业务环境，基础技术。
后面就可以直接上手干项目。不过，由于我本人研究生，时间并没有那么多，所以去不成！！