东方财富 2020 春季校园招聘后端开发在线笔试【Python】【C++】【字符串】【动态规划】

一、单选题

  • 一共有 256 个结点的二叉树高度最小是多少：8。
  • 读程题，选出正确的程序输出结果。
  • 不记得了。

二、不定项选择

  • 哪些属于设计模式。
  • 不记得了。

三、填空题

  • 20*6 = 140 是几进制：八。
  • 给定二叉树的前序和中序遍历，写出后序遍历。
  • 305个同学，1-2 报数，去掉报 2 的，再 1-2 报数，如此往复，最后剩下的是原来第几个同学。（这题没做出来）。
  • 不记得了。

四、编程题

问题一：字符串判断

str1 和 str2 组合之后变成 str3，但是相对顺序不能改变。

示例:

输入：abc defg adebfcg
输出：TRUE
思路

字符串

直接单独判断是否在 str3 中。
考试的时候因为不太清楚 Python 怎么直接把输入的一长串字符串根据空格分割成三个字符串，所以这题并没有做出来。
后来改用 C++ 写了下，还是有问题。所以代码不确定对。
Python3代码
def JudgeString(str:str) -> bool:
    new_list = str.split(' ')
    str1 = list(new_list[0])
    # print(str1)
    str2 = list(new_list[1])
    # print(str2)
    str3 = list(new_list[2])
    # print(str3)
    m, n, length = len(str1), len(str2), len(str3)
    if m + n != length:
        print("FALSE")
        return
    for i in str1:
        if i in str3:
            str3.remove(i)
        else:
            print("FALSE")
            return
    for i in str2:
        if i in str3:
            str3.remove(i)
        else:
            print("FALSE")
            return
    print("TRUE")
    return

if __name__ == "__main__":
    # str1 = "aabcc"
    # str2 = "dbbca"
    # str3 = "aadbbcbcac"
    str = input()
    # str2 = input()
    # str3 = input()
    JudgeString(str)

问题二：股票问题

思路

动态规划

参考 LeetCode 0123: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
一模一样的题目，昨天刚做过，上面那道苦于 Python 的输入格式，所以这题改用 C++ 写了下代码，过了。

具体分析可以参考我的这篇博客：LeetCode | 0123. Best Time to Buy and Sell Stock III买卖股票的最佳时机 III【Python】

空间复杂度: O(1)

C++代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;

int main(){
    int n;
    cin >> n;
    int prices[101];
    for(int i = 0; i < n; ++i){
        cin >> prices[i];
    }
    int dp_i_1_0 = 0;
    int dp_i_2_0 = 0;
    int dp_i_1_1 = -0x7fffff;
    int dp_i_2_1 = -0x7fffff;
    //int dp_i_0_0 = 0;
    //int dp_i_0_1 = 0;
    for(int i = 0; i < n; ++i){
        dp_i_2_0 = max(dp_i_2_0, dp_i_2_1 + prices[i]);
        dp_i_2_1 = max(dp_i_2_1, dp_i_1_0 - prices[i]);
        dp_i_1_0 = max(dp_i_1_0, dp_i_1_1 + prices[i]);
        dp_i_1_1 = max(dp_i_1_1, -prices[i]);
    }
    cout << dp_i_2_0;
    return 0;
}

五、感想

还是习惯 LeetCode 这种给定函数的输入参数及类型、输出参数类型，只需实现函数的功能，而不需在意输入格式。

最近都是用 Python 刷的 LeetCode ，今天 C/C++ 写起来感觉生疏了很多。

前段时间在 拉勾 上投了几家招 Python 的，简历都没过，还是要官网校招一个个申请容易通过啊，虽然填信息麻烦了一点。

比起前面几场还没怎么准备笔试就参加了，结果可想而知，这次准备还行。

LeetCode 还要继续刷，希望早点收到 Dream Offer！