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;
};

#笔经##网易##算法工程师#