有段時(shí)間的筆記了，發(fā)出來(lái)與大家分享
這幾道題是去年11月份投實(shí)習(xí)生時(shí)的面試題目，自己表現(xiàn)不好自然無(wú)法通過(guò)面試，學(xué)會(huì)整理學(xué)習(xí)，希望今年春招能找到實(shí)習(xí)。
上來(lái)就是問(wèn)斐波那契數(shù)列
斐波那契數(shù)列
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) 的空間就加個(gè)滾動(dòng)數(shù)組，求余即可
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）的時(shí)間復(fù)雜度當(dāng)時(shí)沒(méi)想到用矩陣運(yùn)算，事后想搜了下，是用矩陣快速冪算的。還是太菜了。。
f0=0，f1=1，……..fn=f[n-1]+f[n-2]
矩陣運(yùn)算
#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）
第一個(gè)的方法是排個(gè)序選第K個(gè)。
面試官叫我說(shuō)第二個(gè)方法，提示了用二分，我還是不會(huì)。。（太菜了。。）
最后請(qǐng)教別人，是這樣寫(xiě)的（有點(diǎn)快排的味道）
#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;
}
更多面試題目請(qǐng)關(guān)注
