有段时间的笔记了，发出来与大家分享
这几道题是去年11月份投实习生时的面试题目，自己表现不好自然无法通过面试，学会整理学习，希望今年春招能找到实习。
上来就是问斐波那契数列
斐波那契数列
int f[n]
f[0] = 0 , f[1] = 1;
for(int i = 0 ; i < n ; i ++)
f[i] = f[i-1] + f[i -2];
cout<<f[n]<<endl;
O(1) 的空间就加个滚动数组，求余即可
int f[3]
f[0] = 0 , f[1] = 1;
for(int i = 0 ; i < n ; i ++)
f[i%3] = f[(i-1)%3] + f[(i-2)%3];
cout<<f[n%3]<<endl;
log(n）的时间复杂度当时没想到用矩阵运算，事后想搜了下，是用矩阵快速幂算的。还是太菜了。。
f0=0，f1=1，……..fn=f[n-1]+f[n-2]
矩阵运算
#include <bits/stdc++.h>
using namespace std;
struct matrix
{
int a,b;
int c,d;
};
matrix multi(matrix x,matrix y)
{ // 2*2 矩阵乘法
int newa = x.a*y.a+x.b*y.c;
int newb = x.a*y.b+x.b*y.d;
int newc = x.c*y.a+x.d*y.c;
int newd = x.c*y.b+x.d*y.d;
return { newa,newb,newc,newd };
}
class Solution
{
public:
int fibonacci(int n)
{
if(n == 0)
return 0;
matrix ans = {1,0,0,1}; // 单位阵
matrix m = {1,1,1,0};
while(n)
{
if(n&1)
ans = multi(ans,m);
m = multi(m,m);
n >>= 1;
}
return ans.b;
}
};
int main()
{
Solution s;
cout<<"ans: "<<s.fibonacci(10)<<endl;
return 0;
}
第K大（Top K）
第一个的方法是排个序选第K个。
面试官叫我说第二个方法，提示了用二分，我还是不会。。（太菜了。。）
最后请教别人，是这样写的（有点快排的味道）
#include<bits/stdc++.h>
using namespace std;
class Solution
{
public:
int getTopk(vector<int> nums,int k)
{
// for(int num : nums)
// cout<<num<<" ";
// cout<<endl;
int siz = nums.size();
if(k > siz)
return -1;
int left = 0 , right = siz;
int pos = topk_partition(nums,left,right);
// for(int num : nums)
// cout<<num<<" ";
// cout<<endl;
while(pos != k - 1)
{
if(pos < k - 1)
left = pos + 1;
else
right = pos;
pos = topk_partition(nums,left,right);
// for(int num : nums)
// cout<<num<<" ";
// cout<<endl;
}
return nums[pos];
}
int topk_partition(vector<int>& nums,int left,int right)
{
if(left >= right)
return left;
int i = left,j = right , guard = nums[left];
while(i < j)
{
i++;
while( i < right && nums[i] > guard)
i++;
j--;
while( j >= left && nums[j] < guard)
j--;
if(i < j)
swap(nums[i],nums[j]);
}
swap(nums[left],nums[j]);
return j;
}
};
int main()
{
vector<int> nums = {4,3,2,6,7,8};
Solution s;
cout<<s.getTopk(nums,1);
return 0;
}
更多面试题目请关注
