面试题10面试题11面试题12面试题13面试题14
面试题10斐波那契数列，这题难度低，重点在于分析时间复杂度，以f(10)为例，画树状图。
1.递归
2.循环，避免重复计算
时间O(n)，空间O(1)，做表就是O(n)
class Solution {
public:
int Fibonacci(int n) {
vector v={0,1};
if(n<2)
return v[n];
int f1 = 0;
int f2 = 1;
int f0 = 0;
for(int i=2; i<=n; ++i){
f0 = f2;//f(n-1)存进f0
f2 = f1 + f2;//f(n)=f(n-1)+f(n-2)
f1 = f0;//f(n-1)代替原来的f(n-2)
}
return f2;
//不断更新f(n-1)和f(n-2)
}
};
面试题11
牛客网链接
查找：顺序、二分、哈希表、二叉排序树
排序：快排、冒泡、归并，冒泡和快排要能迅速手写
二分时间复杂度是logn，所以需要把时间复杂度从n减少到logn的时候可以考虑
思路1：
暴力遍历，O(n)
class Solution {
public:
int minNumberInRotateArray(vector rotateArray) {
int ans = rotateArray[0];
for(int i=0; i rotateArray[i]){
ans = rotateArray[i];
}
}
return ans;
}
};
思路2：
二分法：
如果有目标值target，那么直接让arr[mid] 和 target 比较即可。
如果没有目标值，一般可以考虑端点
考虑到剩下2个数的时候，mid是左边那个，所以更新左边的话是first = mid + 1，右边是last = mid
参考题解
class Solution {
public:
int minNumberInRotateArray(vector rotateArray) {
int len = rotateArray.size();
int first = 0, last = len-1;
while(first < last){//最后剩下一个元素，是答案
if(rotateArray[first] < rotateArray[last])
//提前退出
return rotateArray[first];
int mid = (first + last)/2;
//注意这个mid的位置，放在循环里面
if(rotateArray[mid] < rotateArray[last])
last = mid;
if(rotateArray[mid] > rotateArray[last])
first = mid+1;
else{
first += 1;
}
}
return rotateArray[first];
}
};
面试题12
回溯法
一般来说dfs，bfs都可，这里用dfs，一般dfs好写点。
牛客网链接
参考题解
class Solution {
public:
bool dfs(vector >& matrix, string word, int index, int i, int j){
if( i<0 || i>=matrix.size() || j<0 || j>=matrix[0].size() || index>=word.length() || word[index] != matrix[i][j]){
//这里，边界判断要写在matrix[i][j]前面，否则容易栈溢出
return false;
}
if(index == word.length()-1)
return true;
//注意这行，到这里如果word每个字符扫描完了，就返回true，上面已经判断word[index]==matrix[i][j]
auto tmp = matrix[i][j];
matrix[i][j] = '.';
//这个改'.'是因为进了一个格子以后不能再进这个格子
bool ans = (dfs(matrix, word, index+1, i-1, j) ||
dfs(matrix, word, index+1, i+1, j) ||
dfs(matrix, word, index+1, i, j-1) ||
dfs(matrix, word, index+1, i, j+1));
matrix[i][j] = tmp;
return ans;
}
bool hasPath(vector >& matrix, string word) {
// write code here
for(int i=0; i
面试题13
牛客网链接
初始化二维数组
vector v(rows, vector(cols, 0));
思路：
和上题类似，DFS，建立一张rows * cols的表，先算每个点能否进入，用getIn函数，能进入的点为1，不能的为0，然后dfs，从（0,0）遍历，访问过的点改为2，即为能到达的点。
最后再扫描一次表，把值为2的点计数。
时间O(m * n)
空间O(m * n)
class Solution {
public:
bool getIn(int threshold, int rows, int cols){
int sum = 0;
while(rows > 0){
sum += rows % 10;
rows /= 10;
}
while(cols > 0){
sum += cols % 10;
cols /= 10;
}
return sum <= threshold;
}
void dfs(int row, int col, vector> &v){
if(row < 0 || row >= v.size() || col < 0 || col >= v[0].size())
return;
if(v[row][col] == 2)
return;
//注意这个退出点，访问过的不用再访问，否则容易无限循环
if(v[row][col] != 0){
v[row][col] = 2;
dfs(row-1, col, v);
dfs(row+1, col, v);
dfs(row, col-1, v);
dfs(row, col+1, v);
}
}
int movingCount(int threshold, int rows, int cols) {
if(rows == 0 || cols == 0)
return 0;
vector> v(rows, vector(cols, 0));
for(int i=0; i
面试题14
显然可以动态规划，这里用自底向上效率更高，一般来说都是自底向上效率高。
建一个长度为n的数组，存储f(n)，从1到n-1计算max(f(i)xf(n-i))
先把前几个值存进去
两层循环能看出，时间复杂度O(n²)，空间复杂度O(n)
牛客网地址
class Solution {
public:
int cutRope(int number) {
vector ans(number+1);//注意答案直接放在表里面
ans[1]=1;
ans[2]=2;
ans[3]=3;
for(int i=4;i<=number;++i){
int max = 0;
for(int j=1;j
贪心：思路见书
试探就是5以后都要切一刀3能保证最大，这个试探做到7就可以了
切3以后3种情况，2，3，4，分别处理，实际只有切出来以后剩了4需要单独处理
class Solution {
public:
int cutRope(int number) {
if(number == 2)
return 2;
if(number == 3)
return 3;
if(number == 4)
return 4;
int timesOf3 = number/3;
if(number - timesOf3 * 3 == 1)
timesOf3 -= 1;//处理切3以后剩余4的情况
int ans1 = pow(3, timesOf3);//3的倍数乘积
int ans2 = number - 3 * timesOf3;
if(ans2 == 0) ans2 = 1;//剩余的乘积，如果是0，则设为1，否则剩余2保留，剩余4保留，切2+2和4一样
return ans1*ans2;
}
};
