東方財(cái)富 2020 春季校園招聘后端開(kāi)發(fā)在線筆試【Python】【C++】【字符串】【動(dòng)態(tài)規(guī)劃】

一、單選題

• 一共有 256 個(gè)結(jié)點(diǎn)的二叉樹(shù)高度最小是多少：8。
• 讀程題，選出正確的程序輸出結(jié)果。
• 不記得了。

二、不定項(xiàng)選擇

• 哪些屬于設(shè)計(jì)模式。
• 不記得了。

三、填空題

• 20*6 = 140 是幾進(jìn)制：八。
• 給定二叉樹(shù)的前序和中序遍歷，寫(xiě)出后序遍歷。
• 305個(gè)同學(xué)，1-2 報(bào)數(shù)，去掉報(bào) 2 的，再 1-2 報(bào)數(shù)，如此往復(fù)，最后剩下的是原來(lái)第幾個(gè)同學(xué)。（這題沒(méi)做出來(lái)）。
• 不記得了。

四、編程題

問(wèn)題一：字符串判斷

str1 和 str2 組合之后變成 str3，但是相對(duì)順序不能改變。

示例:

輸入：abc defg adebfcg
輸出：TRUE

思路

字符串

直接單獨(dú)判斷是否在 str3 中。
考試的時(shí)候因?yàn)椴惶宄?Python 怎么直接把輸入的一長(zhǎng)串字符串根據(jù)空格分割成三個(gè)字符串，所以這題并沒(méi)有做出來(lái)。
后來(lái)改用 C++ 寫(xiě)了下，還是有問(wèn)題。所以代碼不確定對(duì)。

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)

問(wèn)題二：股票問(wèn)題

思路

動(dòng)態(tài)規(guī)劃

參考 LeetCode 0123: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
一模一樣的題目，昨天剛做過(guò)，上面那道苦于 Python 的輸入格式，所以這題改用 C++ 寫(xiě)了下代碼，過(guò)了。

具體分析可以參考我的這篇博客：LeetCode | 0123. Best Time to Buy and Sell Stock III買(mǎi)賣(mài)股票的最佳時(shí)機(jī) III【Python】

空間復(fù)雜度: 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;
}

五、感想

還是習(xí)慣 LeetCode 這種給定函數(shù)的輸入?yún)?shù)及類(lèi)型、輸出參數(shù)類(lèi)型，只需實(shí)現(xiàn)函數(shù)的功能，而不需在意輸入格式。

最近都是用 Python 刷的 LeetCode ，今天 C/C++ 寫(xiě)起來(lái)感覺(jué)生疏了很多。

前段時(shí)間在 拉勾 上投了幾家招 Python 的，簡(jiǎn)歷都沒(méi)過(guò)，還是要官網(wǎng)校招一個(gè)個(gè)申請(qǐng)容易通過(guò)啊，雖然填信息麻煩了一點(diǎn)。

比起前面幾場(chǎng)還沒(méi)怎么準(zhǔn)備筆試就參加了，結(jié)果可想而知，這次準(zhǔn)備還行。

LeetCode 還要繼續(xù)刷，希望早點(diǎn)收到 Dream Offer！