面试笔试

迷南。 2022-08-05 04:29 255阅读 0赞

最近需要找工作了，特将遇到的面试笔试题总结在这里，后续会陆续添加。。希望对大家也有帮助

**1：不能被继承只能被实例化3次**

分析：不能被继承，只需要将该类的构造函设置为私有的就可以了，那么如何得到它呢，只能通过静态函数得到了(不能创建对象，自然不能用对象调用该函数)。。当然如果用指针，必须得有析构，析构函数当然可以不为私有(但是为了对称，一般写成私有)。。。(为了防止赋值和复制，复制构造函数及赋值操作符都要为私有)。此外代码中也可以用引用类型。

代码：

#include<iostream> 
    using namespace std; 
    class Singleton {
    	public:
    		static int count;  
    		static Singleton* GetInstance() { 
    			if(count>0){    
    				count--;    
    				return new Singleton();   
    			}else{    
    				return NULL;   
    			}  
    		}  
    		static void DeleteInstance(Singleton *PInstance){   
    			if(PInstance!=NULL){    
    				delete PInstance;    
    				PInstance=NULL;   
    			}else{    
    				cout<<"is NULL"<<endl;   
    			}  
    		}  
    		static void Getcount(int n){   
    			count=n;  
    		} 
    	private:  
    		Singleton()  
    		{   
    			cout<<"Singleton is constructed"<<endl;  
    		}  
    		~Singleton()  
    		{   
    			cout<<"Singleton is deconstructed"<<endl;  
    		} 
    };  
    int Singleton::count=0; 
    int main() {  
    	Singleton::Getcount(3);  
    	Singleton *p1=Singleton::GetInstance();     
    	Singleton *p2=Singleton::GetInstance();  
    	Singleton *p3=Singleton::GetInstance();  
    	Singleton *p4=Singleton::GetInstance();  
    	if(p3==NULL) 
    	{   
    		cout<<"p3 NULL"<<endl;  
    	}  
    	else{   
    		cout<<"p3 not NULL"<<endl;  
    	}  
    	if(p4==NULL)  
    	{   
    		cout<<"p4 NULL"<<endl;  
    	}  
    	else  
    	{   
    		cout<<"p4 not NULL"<<endl;  
    	}  
    	Singleton::DeleteInstance(p1);  
    	Singleton::DeleteInstance(p2);  
    	Singleton::DeleteInstance(p3);  
    	Singleton::DeleteInstance(p4);  
    	return 0; 
    }

**2： 以下代码调用了几次构照函数和析构函数**

#include<iostream>
    #include<vector>
    using namespace std;
    
    class Test
    {
    public:
    	Test()
    	{
    		cout<<"Test 被构建！"<<endl;
    	}
    	~Test()
    	{
    		cout<<"Test 被析构！"<<endl;
    	}
    
    };
    
    int main(int argc,char *argv[])
    {
    	
    	vector<Test> (*vec)=new vector<Test>();
    	Test a1,a2;
    
    	vec->push_back(a1);
    
    	vec->push_back(a2);
    
    
    	delete vec;
    	return 0;
    }

分析：  
答案是调用了两次构造函数，却调用了5次析构函数，

![Center][]

如果将最后delete vec;去掉 则只调用3次析构函数。为什么会调用了5次构造函数呢，原因是vector容器的自增长，当将a1 push到容器中时，会复制a1，调用复制构造函数，此时当push a2的时候，容器预分配的容量(capacity)为1，因此需要重新找一块更大的内存空间来存放两个元素，并且将第一个元素复制过来，再撤销第一个元素，依次会调用依次复制构造函数，并且立刻析构，再调用复制构造函数a2.如下：

#include<iostream>
    #include<vector>
    using namespace std;
    
    class Test
    {
    public:
    	Test()
    	{
    		cout<<"Test 被构建！"<<endl;
    	}
    	Test(const Test &a){
    		*this = a;
    		cout << "复制构照函数被调用！" << endl;
    	}
    	~Test()
    	{
    		cout<<"Test 被析构！"<<endl;
    	}
    
    };
    
    int main(int argc,char *argv[])
    {
    	
    	vector<Test> (*vec)=new vector<Test>();
    	Test a1,a2;
    
    	vec->push_back(a1);
    
    	vec->push_back(a2);
    
    
    	delete vec;
    	return 0;
    }

![Center 1][]

第一次复制构照函数被调用，是push a1发生复制，第二次复制构照函数被调用和析构是重新分配内存是复制a1并撤销原有的a1，第三次复制构照函数被调用是push a2.

vector是在内存中连续存储，中的函数reserve()用来设置容器预分配容量的大小，resize()是设置容器实际的大小，size()是返回容器实际大小，capacity()是得到容器预分配容器大小。当前实际容器大小为n，也等于预分配的大小时，当调用push\_back()会将容器预分配的容量变成n+n/2，此时会复制n个元素，并加上push新的元素，共有n+1个实际元素。

**3：函数调用过程与函数返回值过程**

函数返回过程：函数返回值如果是函数中普通的变量---假设为类类型，那么普通变量的范围只能在函数内部，因此此时会产生一个全局的临时变量(如果是类类型则调用复制构造函数并析构该局部普通变量)，，然后会调用赋值操作符将临时的全局变量赋值我们的变量，并且赋值操作符调用后会析构临时的全局变量。。

函数调用过程：将函数的下一个地址入栈，并将函数形参从右到左依次入栈，(不会产生临时全局构造函数),,,函数返回过程会逆序出栈。。

代码：

#include<iostream>
    using namespace std;
    template <class T>
    class Test
    {
    public:
    	Test(T _t){t=_t;}
    	Test(){}
    	~Test(){cout<<"_析构函数调用了！"<<endl;}
    	Test(const Test<T>& _test){ 
    		cout << "复制构照函数被调用！" << endl;
    		t=_test.t;
    	}
    	Test& operator=(const Test<T>& _test)
    	{
    	   cout<<"赋值操作符函数被调用！"<<endl;
    	   t=_test.t;
    	   return *this;
    	}
    	// 友元需要重写模板type
    	template<class Type> friend Test<Type> operator+(const Test<Type>&,const Test<Type>&);
    
    	void print(Test<T> test);
    	T t;
    };
    
    template <class T>
    Test<T> operator+(const Test<T>&obj1,const Test<T> &obj2)
    {
    	Test<T> obj;
    	obj.t=obj1.t+obj2.t;
    	return obj;   // 会产生一个临时的全局变量temp，会调用复制构造函数将obj赋给temp，然后析构obj，————函数返回过程---产生全局临时变量
    }
    
    template <class T>
    void Test<T>::print(Test<T> test){    
    	cout << test.t << endl;
    }
    
    int main(int argc,char** argv)
    {
    	Test<int> test_1(2);
        Test<int> test_2(3);
    	Test<int> test_3;
    	test_3 = test_1+test_2;   // 然后将全局变量temp赋值给test_3 赋值操作符结束 临时变量temp被析构 ——函数返回过程 
    	test_3.print(test_2);   // 模拟函数调用过程，将函数的下一个地址入栈，并将display的形参从右到左依次入栈，(直接将test_2复制，不会产生临时全局构造函数)
    	char c;
        cin>>c;
    	return 0;
    }

结果：

![Center 2][]

第一次调用复制构照函数是由于operator+中返回obj时会产生一个全局的临时变量，调用复制构照函数，并将局部变量obj析构掉，然后调用赋值操作符将全局临时变量赋值给给test\_3,并析构掉全局临时变量( 第二次析构函数调用)，然后print实参传形参调用复制构照函数。。

注意当一个类还没有定义完全时，不能使用该类类型定义该类的成员，但可以用指针或其引用，，也可以声明(而不是定义)使用该类型作为形参类型或者返回类型的函数。如例子中的print函数

此外注意的是友元函数，可以将非成员函数，类及成员函数声明为友元，当将非成员函数和类声明为友元时，我们无需提前声明，友元会将该非成员函数及类引入到外围作用域，，而将成员函数设为友元，则需要事先定义包含该友元函数的类A，然后定义所需要的类B，最终定义类A中被当做友元的成员函数。

**4(阿里面试题)：约瑟夫问题**

n个人(编号为0,1,...,n-1)围成一个圈子，从0号开始依次报数，每数到第m个人，这个人就得自杀，之后从下个人开始继续报数，直到所有人都死亡为止。问最后一个死的人的编号(其实看到别人都死了之后最后剩下的人可以选择不自杀……)。

分析：这是典型的约瑟夫问题，可以用单循环链表来进行求解，但此时时间复杂度过高，会达到O(n\*m)的时间复杂度——这是我在面试的时候所说的方法。这里我们给出一种时间复杂度为O(n),空间复杂度为O(1)的解法——这里是我主要想讲解的方法。当然也有两种O(lgn)的解法，但是这两种解法我还没有看，参看[http://maskray.me/blog/2013-08-27-josephus-problem-two-log-n-solutions][http_maskray.me_blog_2013-08-27-josephus-problem-two-log-n-solutions]

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人（编号一定是（m-1） mod n)出列之后，剩下的n-1个人组成了一个新的[约瑟夫环][Link 1]（以编号为k=m mod n的人开始）：

k k+1 k+2 ... n-2,n-1,0,1,2,... k-2

并且从k开始报0。

我们把他们的编号做一下转换：

k --> 0

k+1 --> 1

k+2 --> 2

...

k-2 --> n-2

变换后就完完全全成为了（n-1）个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k) mod n

如何知道（n-1）个人报数的问题的解？对，只要知道（n-2）个人的解就行了。（n-2）个人的解呢？当然是先求（n-3）的情况 \---- 这显然就是一个倒推问题！好了，思路出来了，下面写[递推公式][Link 2]：

令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f\[n\]

递推公式

f\[1\]=0;

f=(f+m) mod i; (i>1）

有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f\[n\]。因为实际生活中编号总是从1开始，我们输出f\[n\]+1

由于是逐级递推，不需要保存每个f，程序也是异常简单：

#include <iostream>
    using namespace std;
    const int m = 3;
    int main()
    {
        int n, f = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) f = (f + m) % i;
        cout << f + 1 << endl;
    	return 0;
    }

参考：[http://baike.baidu.com/view/213217.htm][http_baike.baidu.com_view_213217.htm]

**5.1(阿里面试题)：请在一个小时内实现atoi的c函数**

以下是我的代码：当时处理溢出的时候用了long long，但是MAXINT+1,没有转换成long long

#define MAXINT (int)0x7fffffff
    int strToInt(const string &str){
    	if(str == "")return 0;
    	int i = 0;
    	bool isMinus = false;
    	if(str[i]=='+' || str[i] == '-'){
    		if(str[i] == '-')
    			isMinus = true;
    		i++;
    	}
    	long long int result = 0;
    	for(; i < str.size(); i++)
    	{
    		if(str[i] < '0' || str[i] > '9') return 0;
    		result = result * 10 + str[i] - '0';
    		if(result > (long long)(MAXINT)+1)
    			return 0;
    	}
    	result = isMinus ? -result : result;
    	
    	return result == (long long)(MAXINT)+1 ? 0 : result;
    
    }

或者更直接的，因为unsigned int的范围为0~0xffffffff = 4294967295，而int的范围为-2147483648(0x80000000)~2147483647(0x7fffffff) 所以我们可以直接将result 先设置为unsigned int, 这样就不会超过0x7fffffff了。MAX+1也不需要进行转换了。代码如下：

#define MAX (unsigned int)0x7fffffff
    
    int strToInt2(const string &str){
    	if(str == "")return 0;
    	int i = 0;
    	bool isMinus = false;
    	if(str[i]=='+' || str[i] == '-'){
    		if(str[i] == '-')
    			isMinus = true;
    		i++;
    	}
    	unsigned int result = 0;
    	for(; i < str.size(); i++)
    	{
    		if(str[i] < '0' || str[i] > '9') return 0;
    		result = result * 10 + str[i] - '0';
    		if(result > MAX+1)
    			return 0;
    	}
    	result = isMinus ? -result : result;
    	
    	return result == MAX+1 ? 0 : result;
    
    }

5.2 实现strcpy函数(注意:strcpy基于dst已经有足够的空间容纳src了，否则会出现运行上的错误)

代码如下：要考虑从后往前还是从前往后进行copy

// strcpy函数中源代码调用的是memcpy(dst, src, count) 其中count = strlen(src)+1  === strncpy
    //  其中strcpy基于dst已有足够空间容纳src的长度，否则运行出错
    //其实现等同于下面的代码  其中已经确保dst有足够空间容纳src了
    char *my_mecpy(const char *src, char *dst){      // 最好用void* 然后再在代码中强制将void*转换成char*
    	if(NULL == dst || NULL == src) return dst;
    
    	int len = strlen(src)+1;     // 注意strcpy拷贝的空间包括\0 字符所以长度为strlen(str)+1
    	char *ret = dst;
    	if(src + len <= dst || dst <= src){   // 这两种情况从前往后进行copy
    		while(len--){
    			*dst++ = *src++;
    		}
    	}
    	else{                         // 反之从后往前进行copy
    		dst = dst + len - 1;
    		src = dst + len - 1;
    		while(len--){
    			*dst-- = *src--;
    		}
    	}
    	return ret;
    }

注意memcpy不考虑复制的重叠部分，memmove才考虑重叠部分，所以上面的是memmove

参考文献：1：http://blog.csdn.net/xinpo66/article/details/8551788

2：http://blog.csdn.net/gpengtao/article/details/7464061/

int *myIntArray()
    {
        int buffer[6] = {0};
        for (int i = 1; i <= sizeof(buffer); i++)
        {
            buffer[i-1] = i;
        }
        return buffer;
    }
    
    
    int *myInt()
    {
    	int i = 10;
        int *buffer = &i;
        return buffer;
    }

以上两段函数调用的时候，会返回什么样的结果？

cout << myIntArray()\[0\] << endl;

cout << \* myInt() << endl;

其中myIntArray()没有使用new或者malloc分配内存，所有buffer数组的内存区域在栈区随着char\*myIntArray()的结束，栈区内存释放，字符数组也就不存在了，所以会产生也指针，输出结果未知. 而myInt会返回正常结果10(为什么？？按常理int i的值也被释放了啊，为什么还能返回正确值。 可能是编译器的原因，，如果是类类型 则也会出现野指针)

class SolutionTest{
    public:
    	SolutionTest():x(10){
    		cout << "构照函数被调用" << endl;}
    	SolutionTest(const SolutionTest &st){
    		this->x = st.x;
    		cout << "赋值构照函数被调用" << endl;
    	}
    	SolutionTest& operator=(const SolutionTest& st){
    		this->x = st.x;
    		cout << "赋值操作符被调用" << endl;
    		return *this;
    	}
    	~SolutionTest(){
    		cout << "析构函数被调用" << endl;
    	}
    	int x;
    
    
    };
    
    
    SolutionTest* getPtr(){
    	SolutionTest st;
    	SolutionTest *pst = &st;
    	return pst;
    }

此时调用SolutionTest \*st = getPtr(); cout << st->x << endl; 也会是野指针

**7(360研发)**在写一个函数，根据两文件的绝对路径算出相对路径。如 a="/qihoo/app/a/b/c/d/new.c",b="/qihoo/app/1/2/test.c'，那么b相对于a的相对路径是"../../../../1/2/test.c"

分析：相对路径就是从a的文件开始，../表示到a文件的上一层，所以相对路径为a和b字符串不相同的字符开始a后面/个数就有多少个../作为b的前缀。而后半部分为b开始不相同字符所对应的上一个/开始到字符串b的结尾。。

代码：

#include <iostream>
    #include <string>
    using namespace std;
    
    void getRelativeString(const string &a, const string &b){
    	int i = 0, j = 0;
    	while(i < a.size() && j < b.size()){     // 不相同的字符位置
    		if(a[i] == b[j]){
    			i++;
    			j++;
    		}else break;
    	}
    	// 计算a在不同点后面有多少个/  
    	int remain_a = 0;
    	while( (i = a.find_first_of('/', i)) != string::npos){  // 找到a后面还有多少'/' 结果即为a有多少个/ 那么b的前缀就有多少个../  即为pre_str
    		remain_a ++;
    		i++;
    	}
    	string pre_str = "";
    	for(int k = 0; k < remain_a; k++){
    		pre_str += "../";
    	}
    
    	// 计算b的后半部分
    	//cout << remain_a << endl;
    	while(j < b.size() && b[j] != '/')j++;       // 找到b不相同的地方到上一个/的单词  结果就为pre_str 加上从该单词开始的b后面的字符串。
    	string str = b.substr(0, j);
    	str = b.substr(str.find_last_of('/')+1);
    
    	// 得到结果
    	str = pre_str + str;
    	cout << str << endl;
    
    }
    
    int main(){
    	string a = "/qihoo/app/a/b/c/d/new.c";
    	string b = "/qihoo/app/1/2/test.c";
    	getRelativeString(a, b);
    	return 0;
    }

8:已知rand7()可以产生1~7的7个数(均匀概率),利用rand7() 产 生 rand10() 1~10(均匀概率)。(腾讯笔试题)

分析：刚开始我是用(int)rand7()/7.0\*10,但是后来发现不对，这样生成到1-10不是均匀概率。可以这样7\*(rand7()-1)+rand7()这样会均匀的生成1-49之间数的均匀概率，这里减1的目的就是为了能产生1-7的数字，此时我们让1-40之间的数值模10且加1就能均匀的生成1-10之间的数字了(1-10,11-20.21-30,31-40),而对于大于40以上的数字它重新生成

代码：

int rand10()
    {
        int n=49;
        while(n>40){
            n=7*(rand7()-1)+rand7();
        }
        return n%10+1;
    }

变形： 给定能随机生成整数 1 到 5 的函数,写出能随机生成整数 1 到 7 的函数。  
同理：如下代码，这样21以下的元素对7取模再加1就能生成1-7之间的数字了。

int rand7()
    {
        int n=25;
        while(n>21){
            n=5*(rand5()-1)+rand5();
        }
        return (n%7)+1;
    }

9：找最长重复字串

分析：以下代码时间复杂度为O(N^3)

#include <iostream>
    #include <string>
    using namespace std;
    
    int main(){
    	string s;
    	cin >> s;
    
    	int len = 0;
    	for(int i = 0; i < s.size(); i++){    // 字串位置
    		for(int j = s.size()-i; j >= i; j--){   // 字串长度
    			string str = s.substr(i, j);
    			int front = s.find(str);      // 在s中从前往后找字串
    			int back = s.rfind(str);      // 在s中从后往前找字串
    			if(front != back && j > len){
    				len = j;
    			}
    		}
    	}
    	cout << len << endl;
    	return 0;
    	
    }

10：（美团模拟笔试题）求出一个给定的字符串如str = “ I love you ”;返回“I love you”;去掉首尾空格字符，字符串中间出现多个空格字符时，只保留1个。

代码:

char *eraseEmptySpace(char *str){
    	char *result = new char[256];   // 不知道大小是不是要固定。
    	int i = 0, t = 0;
    	while(str[i] != '\0'){
    		if(str[i] != ' ' || str[i+1] != ' '){   // 当前为空不为空或者当前不为空下一个为空 则加入  // 否则++
    			result[t++]= str[i];
    		}
    		i++;    
    	}
    	result[t]='\0';        //
    	if(result[0] == ' ')result = result+1;
    	return result;
    }
    
    int main(){
    	char *str = "    I   love   you    ";
    	char *result = eraseEmptySpace(str);
    	cout << result << endl;
    
    	return 0;
    }

11：N二维坐标系中的点对中求最近点对的距离

分析：/\*采用分治法，最主要的是计算一个点在S1中，一个点在S2中的最近距离，方法是我们先得到S1和S2内部最小的最近距离dis，然后在  
以mid为中心的dis距离内的点放入新数组T中，然后对T按照Y坐标轴排序，我们知道要想满足条件须要当前点最多与其后面的7个点比较就可以了  
\*/

代码：closePair.h

#define N 1000    // 最大节点数
    #define maxInt 0x7fffffff
    struct Point{
    	int x;
    	int y;
    };

closePair.cpp

Point V[N], T[N];
    
    
    inline bool sortByX(const Point &p1, const Point &p2){
    	return p1.x < p2.x;
    }
    
    
    inline bool sortByY(const Point &p1, const Point &p2){
    	return p1.y < p2.y;
    }
    
    
    double calc_dist(const Point &p1, const Point &p2){
    	return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y)+0.0);
    }
    
    
    // 二分 递归的求解s到t之间的
    double merge(int s, int t){
    	if(s >= t) return maxInt;
    	double dis = maxInt;
    	int mid = (s+t)>>1;
    	dis = min(dis, min(merge(s, mid), merge(mid+1,t)));  // 计算两边的最近点对距离
    
    	//将两边距离中心在dis距离以内的点作为候选并按照Y坐标进行排序
    	int len = 0;
    	for(int i = s; i <= t; i++){
    		if(V[i].x >= V[mid].x - dis && V[i].x <= V[mid].x+dis){
    			T[len++] = V[i];
    		}
    	}
    	sort(T, T+len, sortByY);
    	for(int i = 0; i < len; i++){  // 当前这个点按y轴排序好的最多8个点(dis*(2*dis)领域内)
    		for(int j = i+1; j < min(i+7, len) && T[j].y - T[i].y <= dis; j++){
    			dis = min(dis, calc_dist(T[i], T[j]));
    		}
    	}
    	return dis;
    
    }
    
    // 主函数
    
    double closestPair(){
    	int n;
    	cin >> n;
    	for(int i = 0; i < n; i++)
    		cin >> V[i].x >> V[i].y;
    	sort(V, V+n, sortByX);    // 按x轴进行排序
    
    	return merge(0, n-1);     // 归并
    
    }

参考文献：1：编程之美

2：http://noalgo.info/793.html

12：随机洗牌算法

思路：关键是从后往前进行遍历 这样某张牌被选中放在任何一个位置的概率都是1/n

/*
    随机的洗牌算法:从后往前进行更新某张排被选中放在第i个位置的概率为1/n
    */
    
    int arr[101];
    int n;
    
    void start(){
    	for(int i = 0; i < n; i++)
    		arr[i] = i;
    	for(int i = n-1; i >= 0; i--){   // 这里采用逆序遍历
    		int index = rand()%(i+1);
    		swap(arr[index], arr[i]);
    	}
    }

参考文献：

1：http://sumnous.github.io/blog/2014/05/13/random-pick-function/ 随机数生成函数面试题

2：等概率随机排列数组 http://www.gocalf.com/blog/shuffle-algo.html  
  
  
13: 实现stack，并由操作push，pop，top，getMin即取最小值

分析：此题用链表，关键是在head上进行操作，取最小值最佳情况也能达到O(1)时间内完成

myStack.h

#ifndef MYSTACK_H
    #define MYSTACK_H
    
    struct Node{
    	Node *next;
    	int value;
    	Node(int v):value(v), next(NULL){}
    };
    
    
    class myStack{
    public:
    	myStack():head(NULL){}
    	void push(int v);
    	void pop();
    	int top();
    	int getMin();
    private:
    	Node *head;
    };
    
    
    #endif

myStack.cpp

/*
    实现栈，并模拟取出栈中的最小值;; 我们用链表来实现，head作为栈的头部
    */
    
    void myStack::push(int v){
    	Node *p =  new Node(v);
    	if(head == NULL) head = p;
    	else{
    		p->next = head;
    		head = p;
    	}
    }
    
    // O(1)时间内删除 
    void myStack::pop(){
    	if(head == NULL) return;
    	Node *p = head;
    	head = head->next;
    	delete p;
    }
    
    //  也是O(1)
    int myStack::top(){
    	if(head == NULL) return 0;
    	return head->value;
    }
    
    // 另外一种思路是在myStack中保存一个最小值，在push的时候动态更新它，
    // 此时取得最小值就是O(1)了，但是删除的时候就需要重新遍历stack更新最小值(O(N)) 但是很多情况下取的最小值就是O(1)了
    
    int myStack::getMin(){
    	if(head == NULL) return -1;
    	Node *p = head;
    	int result = head->value;
    	while(p != NULL){
    		result = min(result, p->value);
    		p = p->next;
    	}
    	return result;
    
    }

14: 已知n是个正整数，输出1/n的小数点后k位数字，如n = 5， k=3，则输出为200,； 如n=10， k=3，则输出010

分析：此题我用的思路直接得到1/n 为double类型，但是面试官说这个有可能精度不够，其实这是一个模拟人工算1/n的过程

代码1：

// 取出1/n 小数点后面k位数字  给定的n是个正整数
    
    void getKMod(int n, int k){
    	double t = 1/(n+0.0);    // 浮点型可能不够准确
    	int tmp = 0;
    	while(k--){
    		tmp = t*10;
    		cout << tmp;
    		t = t*10 - tmp;
    	}
    	cout << endl;
    }

模拟人工算的工程：

void getKMod2(int n, int k){    // 最为准确的解法，模仿1/n的过程
    	int t = 10;
    	while(k--){
    		cout << t/n;
    		t = (t%n)*10;
    	}
    	cout << endl;
    }

15：fibonacci数列变形，每步只能走一个台阶或者两个台阶，其中第5,8,13台阶不能走，问走到第20的台阶方法数有多少种  
方法一：迭代 f(n)= f(n-1)+f(n-2) 这样当n = 5, 8, 13的时候f(5)=f(8)=f(13)=0  
方法二：分别对1~4; 6~7;9~12;14~20计算fibonacci数列，然后进行相乘即可为3\*1\*3\*13 = 117

16：有A和B两个数组，如果A中有100个硬币，30个向上，现在有两种操作，一：直接将A中硬币移到B中，二：移到B中进行翻转，问什么样的操作才能是A与B中的硬币朝上数目相等  
假设从A中选择x个元素，有y个向上，此时将x移动到B中并翻转，此时30-y = x-y 导出x=30 因此只需要将30个硬币全部翻转移到B数组中即可

[Center]: /images/20220805/6a7448ea32cd44d5b910557dc9fed5f5.png
[Center 1]: /images/20220805/f43dfcac7aee41f0a55df56e253a6e1c.png
[Center 2]: /images/20220805/27a148ab1cd44bfa8b35d30161e3aae9.png
[http_maskray.me_blog_2013-08-27-josephus-problem-two-log-n-solutions]: http://maskray.me/blog/2013-08-27-josephus-problem-two-log-n-solutions
[Link 1]: http://baike.baidu.com/view/717633.htm
[Link 2]: http://baike.baidu.com/view/1692665.htm
[http_baike.baidu.com_view_213217.htm]: http://baike.baidu.com/view/213217.htm