テンセント0407実習生筆記試験問題--技術研究とデータ分析(アルゴリズム)--python版

今晩テンセントの筆記試験をして、方向は技術研究とデータ分析(私自身が投げたアルゴリズム職)です.まさか25題の不定項選択問題があるとは思わなかった.不定項選択問題には、データ構造、微積分、線形代数、確率論が含まれている.全然準備ができていないので、選択問題はほとんどできません.点数は25*3+3*20=135点です.人柄を集めて、プログラミングの問題を整理して便利にして、後でどの大物がテンセントに入って私の中でハハハを押してくれたのか.古い規則で、前はテーマで、自分でプログラミングをするのに便利で、後ろは解析とコードです.PS:時間統一C/C++1秒その他2秒第一題:小Q手に1つの整数Nがあり、それは毎回この数に対して以下の操作を行うことができる:1現在の手の上のすべての数に対して1を減らす②すべての数を2つのもっと小さい数の和に分割する.このうち、分割回数はk回以下である.QさんにNを完全に消すには、少なくとも何回の操作が必要ですか.説明を入力:1行に2つの正数n、kはスペースで区切られます.出力説明:出力の最小回数.試験例:①5 2-->4;②15 4 -->6.PS:本題は理解しにくいので、テストの例を出して、個人的にはテーマの表現が明確ではないと思っています.私の同級生も理解を間違えたからです.正しい理解(必ずしも正しいとは限らないが、ACになったので、誰がもっと正しい考えを持っているか教えてください)私が解析したときに説明します.第二題:小Qがいる町には道路がすべてのnの村を結んでいる.一部の村では果物を売る必要があり、一部の村では果物を買う必要があり、数はAiで表されている(Ai>0は果物を売る必要があることを示し、Ai<0は果物を買う必要があることを示し、すべてのAiの和は0である).k単位の果物を隣接する村に運ぶのに費用はkです.すべての村が売買需要を満たす最低費用はいくらですか.1行目は村の数、2行目は村に必要な果物の数で、スペースで区切られています.1<=n<=10000.テスト例:5-4-31-31-->9第3題:小Q手にn個の数があり、これらの数に対してk回以下の操作を行う:毎回ゼロでない最小数を出力し、すべての非0数に対してこの数値を減算し、すべての数が0であれば0を出力する.説明を入力します.第1の動作n,kは、スペースで区切られ、第2の動作はスペースで区切られたnの数です.説明:k行、行ごとに1つの数を言います.数1<=Ai<=10000
第1題:小さいQ手の上で1つの整数Nがあって、それは毎回この数に対して以下の操作をすることができます:1現在の手の上ですべての数に対して1を減らします②すべての数を2つのもっと小さい数の和に分割します.このうち、分割回数はk回以下である.QさんにNを完全に消すには、少なくとも何回の操作が必要ですか.説明を入力:1行に2つの正数n、kはスペースで区切られます.出力説明:出力の最小回数.試験例:①5 2-->4;②15 4 -->6.
問題説明:第1題の問題は第2のテスト例にあり、理解方法は以下のいくつかある.1つ目:最初の理解は、ステップごとに分割を選択すると、kは1だけ加算されます.では、15=8+7=4+4+3=2+2+2+2+2+2+2+2+1です.2の場合は2ステップが必要なので、必要なステップ数は3(3つ=番号説明で3ステップをこすった)+2=5ステップであり、試験例で与えられた6ステップではない.2つ目は、奇数が分割できない場合(例えば3=2+1であれば、1は分割できず、2回も減算できないため、偶数だけが分割できる可能性があると考えられる)、奇数が1を減らし、偶数が2を割ってkが切れるまで遭遇することである.15->14-->7+7->6+6->3->3-->2+2で、最後に2ステップを加えると7ステップになります.3つ目は、ボリュームを提出しようとしたときに、最後の可能性のある理解方法を考え出したことです.分割カウントは1つの数を分割して1回計算することです.では15-8+7-4+4+4+3、分割15は1回、分割8と7は2回、kは1回しか残っていないので、後で分割することはできません.4->4ステップ必要です.2+4=6です.3つの方法は私がすべて実験して、第1の方法は80%を通じて(PS:牛客の上でこのような方法でACした人がいて、まだ70%を通じて、判題システムがわけがわからないとしか言えません);2つ目の方法は60%を通過し、3つ目の方法はACを通過しました.3つ目の方法のコードを添付します

# -*- coding:utf8 -*-
#          
# 15 4->6    ？  5  7 
#      
nk = input().strip().split()
n = int(nk[0])
k = int(nk[1])
res = 0
cnt = 0
base = 1
while n > 2 and cnt + base <= k:
    n = (n+1) // 2
    res += 1  #           
    cnt += base
    base *= 2
res += n
print(res)

第二題:小Qがいる町には道路がすべてのnの村を結んでいる.一部の村では果物を売る必要があり、一部の村では果物を買う必要があり、数はAiで表されている(Ai>0は果物を売る必要があることを示し、Ai<0は果物を買う必要があることを示し、すべてのAiの和は0である).k単位の果物を隣接する村に運ぶのに費用はkです.すべての村が売買需要を満たす最低費用はいくらですか.1行目は村の数、2行目は村に必要な果物の数で、スペースで区切られています.1<=n<=10000.試験例:5-4 1-31-->9
第二題私が使っている暴力法は、時間の複雑さがO(n 2)なので、規定時間内に60%しか通過しません.後で他の人のC++コードを見て、O(n)の貪欲な方法を使っています.自分の理解に基づいてpythonコードを書きます.まず考えを説明してください.そうしないと、コードが理解できない人が多いかもしれません.テスト例を例に挙げます.
暴力法:5-4 1-3-->1 0 1-3 1次に一番左の1を最初の負数-3に与え、0 0 0 1-2 1にする.最初の0でないステップを見つけて、上記の手順を続行します.
欲張り思想:5-4 1-3-->0 1-3 1-->0 1-3 1、1番目の位置の5は2番目の位置を通過しなければならないので、直接すべてを2番目の位置に与え、次に2番目の位置から輸送すると考えられます.このとき問題はn-1村の輸送問題に相当するので,上記の考え方で行えばよい.

# -*- coding:utf8 -*-
#          
def other(n, nums):
    res = 0
    cur = 0
    for i in range(n):
        cur += nums[i]
        res += abs(cur)
    print(res)


def mine(n, nums):
    i = 0
    res = 0
    while i < n:
        if nums[i] == 0:
            i += 1
            continue
        j = i + 1
        if nums[i] > 0:
            while j < n and nums[i] > 0:
                if -nums[i] <= nums[j] < 0:
                    res += -nums[j] * (j - i)
                    nums[i] += nums[j]
                    nums[j] = 0
                elif nums[j] < -nums[i]:
                    res += nums[i] * (j - i)
                    nums[j] += nums[i]
                    nums[i] = 0
                j += 1
        else:
            while j < n and nums[i] < 0:
                if 0 < nums[j] <= -nums[i]:
                    res += nums[j] * (j - i)
                    nums[i] += nums[j]
                    nums[j] = 0
                elif nums[j] > -nums[i]:
                    res += -nums[i] * (j - i)
                    nums[j] += nums[i]
                    nums[i] = 0
                j += 1
        i += 1
    print(res)


n = int(input())
line = input().strip().split()
nums = list(map(int, line))
other(n, nums)
mine(n, nums)

第3題:小さいQ手の上でn個の数があって、それはこれらの数に対してk回以下の操作をします:毎回0以外の小数を出力して、更にすべての0以外の数に対してこの数値を減らして、もしすべての数がすべて0ならば0を出力します.説明を入力します.第1の動作n,kは、スペースで区切られ、第2の動作はスペースで区切られたnの数です.説明:k行、行ごとに1つの数を言います.数1<=Ai<=10000
考え方:すべての非0数から最小値を減算するたびに、同じ数があると言えば、明らかに同時に1つの数になるので、先に重くすることを考えて、何度も最小値を探すので、ソートは明らかにindexのたびにより便利で、重くなってからソートするのは多くの人が考えることができます.この問題は難しくありませんが、最も巧みな方法では考えにくいです.コードは数行しかありません.例:2 3 7 10
2 3 7 10-->2
0 1 5 8-->1
0 0 4 7-->4
0 0 0 3-->3
2=2-0であることがわかります.1=3-2;4=7-3;3=10-7.すなわち、出力値はnums[i]-nums[i-1]に等しく、最初はnums[0]-0である.具体的に何が分からないのかは自分で考えることをお勧めします.

# -*- coding:utf8 -*-
#          
nk = input().strip().split()
n = int(nk[0])
k = int(nk[1])
line = input().strip().split()
number = list(map(int, line))
nums = list(set(number))
nums.sort()
res = 0
#             0，      1<=Ai
#   k  set  ，      0
if k <= len(nums):
    for i in range(k):
        print(nums[i]-res)
        res = nums[i]
else:
    for i in range(len(nums)):
        print(nums[i]-res)
        res = nums[i]
    for i in range(k-len(nums)):
        print(0)