2019【京東】【アルゴリズム】【筆記試験】

一、選択問題:

シリアルトレーニングに該当しないオプションは、AdaBoost、Random Forest、XGBoost、GBDT

です.
random foreast(ランダム森林)アルゴリズム:各決定ツリーは独立しており、各決定ツリーはサンプルスタックの中でランダムにサンプルを選択し、ランダムに特徴を選択して独立訓練を行い、各決定ツリーの間に毛糸関係はない.
残りの3つのアルゴリズムは,前回の弱学習器の誤差(残差)に基づいて次の弱学習器を訓練する.

赤と黒のツリーノードの色

次のコードの出力は何ですか

は、30,24,15,27,29,46および15,27,29,30,46の順であることが知られている.

以下のどのアルゴリズムがサンプルのアンバランス問題を回避したのか

intが4バイトであることが知られています.unsigned charは1バイトです.次のコードのoffset=?

核化線形降次元、流行学習.

二、プログラミング問題
1.消消楽
消楽ゲームをしたことがありますか.2 D配列を指定します.その中の数字は(0~4).1つの数字を上/下/左/右と同時に連通と呼びます.3つの数字が連通している場合は消滅し、消滅している場合はすべての連通数字が同時に消滅します.消滅後、上の数字は下に落ちます.異なる消滅順序は異なる結果をもたらします.与えられた配列を求め、連通数字を消滅させ、最後に残りの数字が最も少ない場合はいくつの数字がありますか?
例:

num = [[3, 1, 2, 1, 1],
       [1, 1, 1, 1, 3],
       [1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1],
       [3, 1, 2, 2, 2]]

考え方:
ステップごとに異なる数字を消滅させると結果が異なるため、この問題は動的計画思想であり、すなわち、各数字の消滅方式から最後までの残りの最小数を計算することである.(例えば上の例では、まず1を消滅させた後に2を消滅させ、残りは3つ、先に2を消滅させた後に1を消滅させ、残りは3つと1つの2の計4つの数字を残す.最小限の場合を取るので、上の例の答えは3)
手順:

現在の状況で消滅できる数字

を計算します.

再帰計算各場合の最後の残りの最小数

解題プロセス:
プライマリ関数を先に書きます.

print(min_step(num))
# min_step()                

so easy~
再書き込みmin_Step(num)関数:

def min_step(num):
    #      find_lt()，            
    #       ，  [[0, 1], [4, 2]],      1 2         
    list_lt = find_lt(num)

    #         ，           
    if len(list_lt) == 0:
        return int(np.count_nonzero(num))

    #             ，           
    m = []
    for i in list_lt:
        #    i       
        liantong(num, i[0], i[1])
        #     
        num = drop(num)
        n = num.copy()
        #                    
        m.append(min_step(n))
    #      
    return min(m)

上のコードには3つの関数が必要です.つまり、消滅可能な数字のfind_を検索します.lt(num)、消滅数のliantong(num,i,j)関数、および落下関数drop(num).
 
消去可能な数値のfindを検索します.lt(num):

def find_lt(num):
    n = num.copy()
    result = []
    for i in range(len(n)):
        for j in range(len(n[0])):
            if n[i][j] == 0:
                continue
            if liantong(n, i, j) > 2:
                result.append([i, j])
    return result

数値関数の消滅:

def liantong(n, i, j):
    k = n[i][j]
    n[i][j] = 0
    v = []
    v.append([i, j])
    re = 1
    while len(v) != 0:
        # downw
        if i < len(n)-1 and n[i+1][j] == k:
            i += 1
            re += 1
            n[i][j] = 0
            v.append([i, j])
            continue
        # right
        if j < len(n[0])-1 and n[i][j+1] == k:
            j += 1
            re += 1
            n[i][j] = 0
            v.append([i, j])
            continue
        # up
        if i > 0 and n[i-1][j] == k:
            i -= 1
            re += 1
            n[i][j] = 0
            v.append([i, j])
            continue
        # left
        if j > 0 and n[i][j-1] == k:
            j -= 1
            re += 1
            n[i][j] = 0
            v.append([i, j])
            continue
        i, j = v.pop()
    return re

 
 
ドロップ関数drop(num):

def drop(num):
    for j in range(len(num[0])):
        slow = len(num) -1
        while num[slow][j] != 0 and slow >= 0:
            slow -= 1
        fast = slow
        while fast >= 0:
            if num[fast][j] == 0 or fast == slow:
                fast -= 1
                continue
            num[slow][j] = num[fast][j]
            num[fast][j] = 0
            slow -= 1
            fast -= 1
    return num