4.10 网易算法岗笔试全A经
斐波那契数列
题目
定义一个新的斐波那契数列。F[i]=i, when i<3。 F[i] = F[i-3]+F[i-2]+F[i-1], when i>=3。求F(n)
code
//dp解法
class Solution {
public:
int solution(int n) {
// write code here
vector<int> dp(n+1);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<=n;i++)
dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
return dp[n];
}
}; 煎饼果子
题目
一个煎饼果子5块钱。初始有2张5块。数组bills表示顾客的钱。顾客可能拿一张5块，10块，或20块，买一个煎饼。当钱找不开时停止营业。求能卖几个人。
code
//贪心。有10块找10块，没10块找5块
class Solution {
public:
int billsChange(vector<int>& bills) {
int len = bills.size();
int coins[2];
coins[0] = 2;
coins[1] = 0;
int i=0, remain;
for(i=0;i<len;i++)
{
if(bills[i]==5)
coins[0]++;
else if(bills[i]==10){
coins[1]++;
coins[0] -= 1;
}
else if(bills[i]==20){
remain = 3;
if(coins[1]>0)
{
coins[1]--;
remain -= 2;
}
coins[0] -= remain;
}
if(coins[0]<0)
break;
}
return i;
}
}; 接雨水
题目
同lc接雨水。区别在于原题求全部雨水的大小，本题求最大水箱的大小。
考场上没仔细看题，耽误了不少时间。
code
//我用的单调栈法。打了一些补丁。
class Solution {
public:
//对于每个点，需要找min(l,r)。l,r分别是左侧最大和右侧最大柱子
//数据结构选择递增stack，从左向右遍历，保存对每个点的左侧最大
//然后从右往左遍历数组，维护一个右侧最大
//当前格子没水时表示水箱分隔线。
//O(2n)=O(n)
int maxWater(vector<int>& height) {
// write code here
int len = height.size();
stack<int> st;
for(int i=0;i<len;i++)
{
if(st.empty()||height[i]>height[st.top()])
st.push(i);
}
int r = height[len-1];
int edge;
int ret = 0;
int cur = 0;
for(int i=len-1;i>=1;i--)
{
while(st.top()>=i)
st.pop();
edge = min(r,height[st.top()]);
cur += max(0, edge-height[i]);
if(edge-height[i]<=0)
{
ret = max(ret, cur);
cur = 0;
}
r = max(r, height[i]);
}
ret = max(ret, cur);
return ret;
}
}; 最优路径
题目
root表示一颗二叉树。path表示一条路径。在二叉树中找一条最优路径。最优路径指包含path并且最长的路径。树中可能有值重复的节点。
code
我感觉我的代码有问题，不能解决重复节点的问题。但是测试用例全A了，估计是测试数据量太少吧。还是说测试用例全A不代表最终结果全A？求大佬解释。
class Solution {
public:
vector<int> solution(TreeNode* root, vector<int>& path) {
// write code here
p_len = path.size();
dfs(root, path, 0);
return ret;
}
void dfs(TreeNode* node, vector<int>& path, int p)
{
if(node==nullptr)
{
if(p_len==p&&ret.size()<cur.size())
ret = cur;
return ;
}
cur.push_back(node->val);
if(p==p_len)
{
dfs(node->left, path, p);
dfs(node->right, path, p);
}
else if(node->val==path[p])
{
dfs(node->left, path, p+1);
dfs(node->right, path, p+1);
}
//这个else可以去掉，对每个点都当作path第一个点遍历一次，解决重复节点问题，但是复杂度比较高
else
{
dfs(node->left, path, 0);
dfs(node->right, path, 0);
}
cur.pop_back();
}
int p_len;
vector<int> cur;
vector<int> ret;
}; 
