LeetCode冲刺：Day14

发布于 2022-11-21  114 次阅读

面试顺利通过！新的开始，继续努力。

1. 二叉树的中序遍历

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

前次用递归完成，这次用迭代实现。

递归实现前中后序的代码都大同小异。而迭代会有较大不同。

代码

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> st;
        TreeNode* cur=root;
        while (cur!=nullptr||!st.empty()) {
            if (cur!=nullptr) {
                st.push(cur);
                cur=cur->left;
            } else {
                cur=st.top();
                st.pop();
                ans.push_back(cur->val);
                cur=cur->right;
            }
        }
        return ans;
    }

};

2. 二叉树的后序遍历

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

迭代法完成后序遍历。前序遍历是中左右，后序遍历是左右中。因此可以使用前序遍历的框架，调整一下入栈顺序，使得访问顺序变成中右左，再反转数组，即变为左右中。

代码

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root==nullptr) return ans;
        stack<TreeNode*> st;
        TreeNode* cur=root;
        st.push(cur);
        while(!st.empty()) {
            cur=st.top();
            st.pop();
            ans.push_back(cur->val);
            if (cur->left) st.push(cur->left);
            if (cur->right) st.push(cur->right);
        }
        return vector<int>(ans.rbegin(),ans.rend());
    }

3. 二叉树的层序遍历

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

层序遍历使用队列，其先进先出的特性契合层序遍历的需求。

先将根节点入队。以后每一轮循环过后，当前队列中要么空，要么存在且仅存在某一层的所有元素。而上一层元素已经被放到ans中对应的数组里。

代码

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root==nullptr) return ans;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            int size=que.size(); //必须固定大小
            vector<int> vec(size);
            for (int i=0;i<size;++i) {
                TreeNode* cur=que.front();
                que.pop();
                vec[i]=cur->val;
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            ans.push_back(vec);
        }
        return ans;
    }
};

4. 二叉树的层序遍历 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

跟一般层序遍历几乎一样，只不过最后返回值是ans的反向。

代码

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if (root==nullptr) return ans;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            int size=que.size();
            vector<int> temp(size);
            for (int i=0;i<size;++i) {
                TreeNode* cur=que.front();
                que.pop();
                temp[i]=cur->val;
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            ans.push_back(temp);
        }
        return vector<vector<int>>(ans.rbegin(),ans.rend());
    }
};

5. 翻转二叉树

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

本想将每层结点存在一个数组里，再首尾依次交换，但这样只能交换值，遇到空结点会很麻烦，所以只能直接交换每个结点的左右子节点。

代码

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root==nullptr) return root;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            int size=que.size();
            for (int i=0;i<size;++i) {
                TreeNode* cur=que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                TreeNode* temp=cur->left;
                cur->left=cur->right;
                cur->right=temp;
            }
        }
        return root;
    }
};

6. 打家劫舍

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

dp表示到某个房子为止，可以获得的最大收益，其有两个来源，即，要么不偷当前房子，则最大收益是截至前一个房子的最大收益；要么偷这个房子，那么最大收益是截至i-2个房子的收益加上当前房子的金额，两者取最大即可。显然要初始化0和1位置，然后从2开始递推。

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if (n==1) return nums[0];
        if (n==2) return max(nums[0],nums[1]);
        vector<int> dp(n,0);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for (int i=2;i<n;++i) {
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[n-1];
    }
};

7. 打家劫舍 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

对于环形数组，分三种情况做考虑，一是考虑首元素不考虑尾元素；二是考虑尾元素不考虑首元素；三是既不考虑首元素也不考虑尾元素。在本题中，情况一和二包含了三，因此不用单独计算三。

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if (n==1) return nums[0];
        if (n==2) return max(nums[0],nums[1]);
        int res1=robRange(nums,0,n-2);
        int res2=robRange(nums,1,n-1);
        return max(res1,res2);
    }
    int robRange(vector<int>& nums,int start,int end) {
        if (start==end) return nums[start];
        vector<int> dp(end-start+1,0);
        if (start==end-1) return max(nums[start],nums[end]);
        dp[0]=nums[start];
        dp[1]=max(nums[start],nums[start+1]);
        for (int i=2;i<=end-start;++i) {
            dp[i]=max(dp[i-1],dp[i-2]+nums[i+start]);
        }
        return dp[end-start];
    }
};

8. 买卖股票的最佳时机

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

使用DP做。n*2的数组，i0表示第i天持有股票所能获得的最大现金，持有股票可能是前一天就已经持有，也可能是今天买入，在两种情况中取最大。i1表示第i天不持有股票所能获得的最大现金，不持有股票可能是昨天就没持有，也可能是今天才卖出，在两种里面取最大。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if (n==1) return 0;
        vector<vector<int>> dp(n,vector<int>(2,0));
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for (int i=1;i<n;++i) {
            dp[i][0]=max(dp[i-1][0],-prices[i]);
            dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]);
        }
        return dp[n-1][1];
    }
};

9. 买卖股票的最佳时机 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

先是贪心。

然后DP。如果当天持有股票，那么要么前一天就持有，保持原状；要么今天刚买的，那么就是昨天不持有的现金减掉今天买入股票的价格，两者取最大。如果当天不持有股票，要么前一天就不持有，保持原状；要么今天刚卖掉，那么就是昨天持有股票的现金，加上今天卖掉股票的收入，两者取最大。

代码

// 贪心
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans=0;
        int n=prices.size();
        for (int i=1;i<n;++i) {
            if (prices[i]>prices[i-1]) ans+=prices[i]-prices[i-1];
        }
        return ans;
    }
};

//DP
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans=0;
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2,0));
        dp[0][0]=-prices[0];
        for (int i=1;i<n;++i) {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[n-1][1];
    }
};

10. 最大子序列积

来自于今天的面试

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

子序列和只需考虑累加和是否大于零。而对于积，即便当前积为负，之后再乘一个负数，也可能变得更大，因此，我们不仅需要记录最大的积，也需要记录最小的积（也就是绝对值最大的负值）。

代码

int test(vector<int>& nums) {
    vector<int> minV(nums.size());
    vector<int> maxV(nums.size());
    int ans=INT_MIN;
    minV[0]=nums[0];
    maxV[0]=nums[0];
    for (int i=1;i<nums.size();++i) {
        maxV[i]=max(nums[i],nums[i]*maxV[i-1],nums[i]*minV[i-1]);
        minV[i]=min(nums[i],nums[i]*maxV[i-1],nums[i]*minV[i-1]);
        ans=max(ans,maxV[i]);
    }
    return ans;
}