摘要：買糖果題目來(lái)源京東實(shí)習(xí)生招聘原題鏈接可在線提交賽碼網(wǎng)問(wèn)題描述某糖果公司專門生產(chǎn)兒童糖果，它最受兒童歡迎的糖果有兩個(gè)序列，均采用盒式包裝。小東希望你能幫她解決這一問(wèn)題。

最近比較忙，又有一段時(shí)間沒(méi)寫題目了，終于在前幾天把賽碼網(wǎng)上，JD的2016秋招和2017實(shí)習(xí)生招聘剩下的4星難度題目做了，至此所有4星難度題目都解決了，5星難度題目還剩下一個(gè)應(yīng)該是計(jì)算幾何學(xué)的題目，因?yàn)檫@塊我不熟悉，后面找時(shí)間再處理。
鑒于賽碼網(wǎng)的難度分類不是特別準(zhǔn)確，接下里我把1-3星難度的題目過(guò)一次，如果有價(jià)值的就和大家一起分享。
這次的解析包含了4個(gè)題目，相對(duì)比較簡(jiǎn)單，但需要考慮全面，否則容易掉坑。

<題目來(lái)源: 京東2016實(shí)習(xí)生招聘 原題鏈接-可在線提交(賽碼網(wǎng))>

某糖果公司專門生產(chǎn)兒童糖果，它最受兒童歡迎的糖果有A1、A2兩個(gè)序列，均采用盒式包裝。包裝好的A1類糖果體積為一個(gè)存儲(chǔ)單位，而包裝好的A2類糖果體積正好是A1類的兩倍。
這兩類糖果之所以廣受兒童歡迎，是因?yàn)樘枪泻泄惊?dú)家研發(fā)的魔幻因子。A1或A2序列中的糖果，看起來(lái)包裝可能是一樣的，但因?yàn)槠渲械哪Щ靡蜃雍坎煌患?xì)分為不同的產(chǎn)品。
臨近傳統(tǒng)節(jié)日，公司的糖果供不應(yīng)求。作為一個(gè)精明的糖果分銷商，小東希望能夠借此大賺一筆，于是帶著現(xiàn)金開著貨車來(lái)公司提貨。貨車的容量是確定的，小東希望采購(gòu)的糖果能夠盡可能裝滿貨車，且糖果的魔幻因子總含量最高。只要不超出貨車容量，糖果總可以裝入貨車中。
小東希望你能幫她解決這一問(wèn)題。

這個(gè)題目的描述似乎不是太準(zhǔn)確，其實(shí)題目就是說(shuō)有n個(gè)糖果，每個(gè)糖果有個(gè)體積(1或者2)，此外，有個(gè)魔幻因子。最后我們需要解決是在體積不超過(guò)v的情況下，選擇若干糖果并且盡可能的獲得最大的魔幻因子總量。

這看起來(lái)是個(gè)01背包問(wèn)題*[1]，觀察數(shù)據(jù)規(guī)模后發(fā)現(xiàn)，n <= 10^5，v <= 10^9這個(gè)用于狀態(tài)轉(zhuǎn)移的枚舉量實(shí)在太大，而且單就一個(gè)v的上限就足以撐爆空間。看來(lái)問(wèn)題似乎不是直接使用01背包的動(dòng)態(tài)規(guī)劃可以解決的，再觀察題目條件，一個(gè)比較特別的地方是糖果的體積只有1和2的兩種情況，我們從這個(gè)比較特殊的條件來(lái)解決問(wèn)題。

a.考慮一種最簡(jiǎn)單的情況：只有體積為1的糖果。
顯然我們只需要對(duì)所有的糖果按照魔幻因子從大到小排序，從魔幻因子最大的糖果開始選擇，由于體積都是1，那么給定的v一定可以達(dá)到。這些選擇出來(lái)的糖果的魔幻因子的和就是我們的求解目標(biāo)。

b.再考慮另外一種罪簡(jiǎn)單的情況，只有體積為2的糖果。
同樣我們需要按魔幻因子的大小進(jìn)行排序，然后從魔幻因子最大的糖果開始選擇，但是不同于a，由于是每個(gè)糖果的體積是2，那么選出來(lái)糖果的體積和不一定可以剛好為v，如果剛好為v則問(wèn)題已經(jīng)解決。如果超過(guò)v，顯然是總體積比v大了1，那么最后選擇的這一種糖果就不要了。這時(shí)我們選擇的糖果的總體積為v-1，盡管浪費(fèi)了1，但是我們沒(méi)有任何辦法再放入糖果了。

c.考慮題目既有體積1和2的情況。
基于上述兩種基本情況的分析，我們?nèi)匀恍枰才拍Щ靡蜃哟笮∵M(jìn)行排序，盡可能選擇魔幻因子高的優(yōu)先選擇，再考慮臨界情況的處理。需要注意到，對(duì)于體積為2的糖果，我們不應(yīng)該直接按照其魔幻因子的總量進(jìn)行排序，而是按照單位體積的魔幻因子含量進(jìn)行排序。這是因?yàn)?，盡管可能體積為2的糖果魔幻因子可能很高，但是他占用2個(gè)體積，如果兩個(gè)體積為1的糖果魔幻因子沒(méi)有其高，但是兩個(gè)加起來(lái)就超過(guò)了，并且最終占用的體積都是2.

排序之后我們按照從大的開始選擇，如果可以剛好取到v，那么問(wèn)題就得到解決。如果得不到，那么顯然當(dāng)前取的是體積2的糖果，并且是超過(guò)1。這個(gè)時(shí)候，明顯我們可以有多種選擇，我們既可以在已經(jīng)選擇的糖果中去掉一個(gè)體積為1的且魔幻因子最小的糖果，也可以是在還沒(méi)有選擇的糖果中選擇一個(gè)體積為1的且魔幻因子最大的一個(gè)糖果。至于具體選擇哪種就看哪種方案可以獲得更高的魔幻因子總和了。

那么問(wèn)題似乎已經(jīng)解決了，然后我們并沒(méi)有考慮到選擇的和沒(méi)選擇的中都可能不存在體積為1的糖果。
...已選擇部分...| 體積為2的糖果| ...未選擇部分...

 ^已獲得的魔幻因子pm ^體積限制v

設(shè)已選擇的最小的體積為1的糖果的魔幻因子為l
設(shè)未選擇的最小的體積為1的糖果的魔幻因子為r
當(dāng)前體積2的糖果魔幻因子為p，體積不超過(guò)v獲得最大的魔幻因子總和為pm
i.l和r都不存在

= v
ii.l存在，r不存在

= max(pm, pm - l + p)

iii.l不存在，r存在

= pm + r
iv.l和r都存在

= max(pm + r, pm - l + p)

最后一個(gè)需要解決的問(wèn)題是輸出選擇糖果的序列問(wèn)題，這并不難，我們排序后依次記錄選擇了的糖果即可。pm - l + p的情況，刪除記錄中的l即可。但是，由于存在多種方案要得失編號(hào)盡可能的小，那么對(duì)與ii, iv中存在相等的情況時(shí)的處理原則時(shí)，選擇編號(hào)較小的即可。

排序時(shí)間復(fù)雜度為O(nlogn)，由于每個(gè)糖果只需要處理一次，計(jì)算部分時(shí)間復(fù)雜度為O(n)，非常理想。

import sys

const_n = 0
const_v = 1
const_p = 2


def main():
    while True:
        line = map(int, sys.stdin.readline().strip().split())
        n, vm = line[0], line[1]

        candies = []
        for i in range(n):
            line = map(int, sys.stdin.readline().strip().split())
            if len(line) < 2:
                break
            candies.append((i + 1, line[0], line[1]))

        candies = sorted(candies, key=lambda s: float(s[const_p]) / float(s[const_v]), reverse=True)
        # print candies

        seq = set([])
        v = p = 0
        l = r = -1
        for i, candy in enumerate(candies):
            if v + candy[const_v] >= vm:
                if v + candy[const_v] == vm:
                    seq.add(candy[const_n])
                    p += candy[const_p]
                else:
                    for j in range(i + 1, n):
                        if candies[j][const_v] == 1:
                            r = j
                            break

                    if l == -1 and r == -1:
                        pass
                    elif l == -1 and r != -1:
                        p += candies[r][const_p]
                        seq.append(candies[r][const_n])
                    elif l != -1 and r == -1:
                        if candy[const_p] - candies[l][const_p] > 0:
                            p = p - candies[l][const_p] + candy[const_p]
                            seq.remove(candies[l][const_n])
                            seq.add(candy[const_n])
                    else:
                        if candy[const_p] - candies[l][const_p] > candies[r][const_p]:
                            p = p - candies[l][const_p] + candy[const_p]
                            seq.remove(candies[l][const_n])
                            seq.add(candy[const_n])
                        else:
                            p += candies[r][const_p]
                            seq.add(candies[r][const_n])
                break

            seq.add(candy[const_n])
            v += candy[const_v]
            p += candy[const_p]

            if candy[const_v] == 1:
                l = i

        print p
        if p > 0:
            seq = sorted(seq)
            for s in seq:
                print s,
        else:
            print "No"
        print

if __name__ == "__main__":
    main()

<題目來(lái)源: 京東2017實(shí)習(xí)生招聘 原題鏈接-可在線提交(賽碼網(wǎng))>

收到情報(bào)，有批新造的機(jī)器人要運(yùn)輸?shù)角熬€。小C將去破壞機(jī)器人的運(yùn)輸。小C將激光炮放置在公路的一旁，等運(yùn)輸車經(jīng)過(guò)的時(shí)候發(fā)射（假設(shè)激光炮一定可以射穿車輛）。由于能源有限，激光炮只能發(fā)射兩次?？梢哉J(rèn)為激光炮放在坐標(biāo)軸的原點(diǎn)處，并向y軸正方向發(fā)射。每輛運(yùn)輸車可以看作是一個(gè)矩形，起始的x軸坐標(biāo)為Xi ,所有的車均位于第一象限，長(zhǎng)度為L(zhǎng)i,速度為1，朝x軸負(fù)方向運(yùn)動(dòng)。即經(jīng)過(guò)t時(shí)間后，該車車頭的x坐標(biāo)為Xi-t，車尾坐標(biāo)為Xi-t+Li 。只要打中車的任何一個(gè)部分就算擊中。
請(qǐng)你算算，他在哪兩個(gè)時(shí)刻發(fā)射，才能摧毀最多的運(yùn)輸車。

先簡(jiǎn)化下題目的意思，由于每個(gè)車輛的前進(jìn)速度是統(tǒng)一的，那么實(shí)際上我們就不用考慮車子移動(dòng)的情況了，只需要在x軸上選擇兩個(gè)點(diǎn)發(fā)射激光炮即可。此外，這個(gè)題目的數(shù)據(jù)規(guī)模是X、L<= 10^9 而不是109。

需要注意，第2次發(fā)射的激光炮不會(huì)擊毀被第一次發(fā)射的激光炮已經(jīng)擊毀的車子。也就是1輛車不能被擊毀兩次。我們就不能單純?cè)诎茨硞€(gè)點(diǎn)上的車輛最多和次多來(lái)選擇x軸上發(fā)射激光炮的位置了。考慮到只能發(fā)射兩枚激光炮，那么我們只需要枚舉這2個(gè)位置就可以了。

但是觀察X和L 10^9的限時(shí)，直接枚舉x軸上的兩個(gè)點(diǎn)顯然不可以。

我們考慮兩個(gè)車有重疊的情況，要判斷有沒(méi)有辦法一炮機(jī)會(huì)這兩個(gè)車子，實(shí)際上我們只需要判斷兩個(gè)位置即可，即某個(gè)車頭的點(diǎn)是在另外一個(gè)車的范圍內(nèi)即可。這是一種對(duì)于極限情況的考慮，如果該情況成立，就還會(huì)有若干其他的點(diǎn)可能滿足，但這部分點(diǎn)就不需要再判斷。換句話說(shuō)，兩個(gè)車如果有重疊，那么其中有個(gè)車的車頭一定在另外一個(gè)車的車身范圍內(nèi)。

擴(kuò)展到一般情況，根據(jù)上面的討論，對(duì)于所有的車，我們激光炮的發(fā)射位置只需要選擇每個(gè)車車頭的位置即可。枚舉之后再判斷哪些車子被擊毀，做上標(biāo)記。最后記錄一個(gè)最大的擊毀數(shù)目即可。由于車輛總數(shù)n僅僅200，先兩重循環(huán)枚舉2個(gè)車頭位置，再用一層循環(huán)檢查擊毀數(shù)目，算法的時(shí)間復(fù)雜度為O(n^3)是可以接受的。

import sys


def calc(f, s, c, n):
    destroy = [False for i in range(n)]
    res = 0

    for i, elem in enumerate(c):
        if elem[0] <= f <= elem[1] or elem[0] <= s <= elem[1]:
            if not destroy[i]:
                res += 1
            destroy[i] = True

    return res


def main():
    n = map(int, sys.stdin.readline().strip().split())[0]
    cars = []
    segments = []

    for i in range(0, n):
        line = map(int, sys.stdin.readline().strip().split())
        cars.append((line[0], line[0] + line[1]))
        segments.append(line[0])

    r = 0
    for i in range(len(segments)):
        for j in range(i):
            r = max(r, calc(segments[i], segments[j], cars, n))

    print r


if __name__ == "__main__":
    main()

<題目來(lái)源: 京東2017秋招 原題鏈接-可在線提交(賽碼網(wǎng))>

小明同學(xué)學(xué)習(xí)了不同的進(jìn)制之后，拿起了一些數(shù)字做起了游戲。小明同學(xué)知道，在日常生活中我們最常用的是十進(jìn)制數(shù)，而在計(jì)算機(jī)中，二進(jìn)制數(shù)也很常用。現(xiàn)在對(duì)于一個(gè)數(shù)字x，小明同學(xué)定義出了兩個(gè)函數(shù)f(x)和g(x)。
f(x)表示把x這個(gè)數(shù)用十進(jìn)制寫出后各個(gè)數(shù)位上的數(shù)字之和。如f(123)=1+2+3=6。
g(x)表示把x這個(gè)數(shù)用二進(jìn)制寫出后各個(gè)數(shù)位上的數(shù)字之和。如123的二進(jìn)制表示為1111011，那么g(123)=1+1+1+1+0+1+1=6。
小明同學(xué)發(fā)現(xiàn)對(duì)于一些正整數(shù)x滿足f(x)=g(x)，他把這種數(shù)字稱為幸運(yùn)數(shù)，現(xiàn)在他想知道，小于等于n的幸運(yùn)數(shù)有多少個(gè)。

接下來(lái)的這兩個(gè)題目相對(duì)比較簡(jiǎn)單，數(shù)據(jù)范圍也不大，這個(gè)題目可以直接按照題目意思模擬即可。
注意以下兩點(diǎn)問(wèn)題：
1.這類題目都要采用離線的計(jì)算方式，一次性先把數(shù)據(jù)規(guī)模內(nèi)的數(shù)據(jù)全部計(jì)算到出來(lái)并保存，然后根據(jù)輸出直接輸出結(jié)果即可。
2.相對(duì)來(lái)說(shuō)這個(gè)題目的數(shù)據(jù)規(guī)模較弱，注意到在當(dāng)次計(jì)算時(shí)，如果個(gè)位沒(méi)有發(fā)生進(jìn)位的話，結(jié)果就是上次計(jì)算的結(jié)果+1，如果發(fā)生了進(jìn)位再全部計(jì)算一次即可。這樣可以節(jié)約非常大的一個(gè)計(jì)算量。

提交后我大致看了下運(yùn)行時(shí)間，我使用的python耗時(shí)369ms，而其他python和java耗時(shí)接近或者超過(guò)1000ms，其中一個(gè)C++的運(yùn)行時(shí)間為623ms。有時(shí)候一個(gè)很小的優(yōu)化帶來(lái)的性能提升是很顯著的。

import sys

const_max_n = 100000 + 1


def _next(bits, last_sum, base):
    next_add = 0
    bits[0] += 1
    last_sum += 1

    if bits[0] >= base:
        last_sum = 0
        for i in range(len(bits)):
            bits[i] += next_add
            if bits[i] >= base:
                bits[i] = 0
                next_add = 1
            else:
                next_add = 0
            last_sum += bits[i]

        if next_add == 1:
            bits.append(1)
            last_sum += 1

    return last_sum


def main():
    r = [0 for i in range(0, const_max_n)]
    _dec = [0]
    _bin = [0]
    last_bin_sum = last_dec_sum = 0

    for i in range(1, const_max_n):
        last_bin_sum = _next(_dec, last_bin_sum, 2)
        last_dec_sum = _next(_bin, last_dec_sum, 10)

        r[i] = r[i - 1]
        if last_bin_sum == last_dec_sum:
            r[i] += 1

    t_case = map(int, sys.stdin.readline().strip().split())[0]
    for i in range(0, t_case):
        n = map(int, sys.stdin.readline().strip().split())[0]
        print r[n]


if __name__ == "__main__":
    main()

<題目來(lái)源: 京東2016實(shí)習(xí)生招聘 原題鏈接-可在線提交(賽碼網(wǎng))>

三子棋是一種大家熟知的游戲，幾乎所有人都會(huì)玩。游戲規(guī)則相當(dāng)簡(jiǎn)單，兩人依次在一個(gè)3X3棋盤格上下棋，一個(gè)人畫叉，另一個(gè)人畫圈。任何一個(gè)人畫的三個(gè)記號(hào)如果形成構(gòu)成一條水平、垂直或?qū)堑闹本€則獲勝，游戲結(jié)束。畫叉的人先開始游戲，如果所有的棋盤格都畫滿了但兩人都不能獲勝，則游戲平局結(jié)束。
游戲在一個(gè)3X3的棋盤上進(jìn)行，每個(gè)棋盤格單元處于空白、畫叉或畫圈狀態(tài)中的一種，你的任務(wù)是確定下一輪由誰(shuí)下棋: 
1：輪到先手下棋；
2：輪到后手下棋；
或者是判定游戲的狀態(tài)： 
x：給定的棋局不是合法的棋局； 
1 won：先手獲勝； 
2 won：后手獲勝； 
Draw：平局；
小東對(duì)棋類游戲很有研究，這一次三子棋比賽中，她被邀請(qǐng)作為評(píng)判，為了提攜后進(jìn)，她請(qǐng)你幫忙判定。

本題看似簡(jiǎn)單，其實(shí)要注意的地方還比較多，包括如何比較優(yōu)雅的完成代碼的編寫(這我代碼也寫不太好)。

注意到本題的條件具有先后順序。應(yīng)該是下列順序：
1.給定的棋局是否合法；
2.是否有獲勝方；
3.平局
4.該誰(shuí)下棋

這類題目建議使用一個(gè)方向向量，方向向量可以指示要判斷的方向。比如，要判斷一個(gè)從上到下的對(duì)角線情況，我們可以設(shè)置一個(gè)(1,1)的方向向量，當(dāng)從(0,0)開始后：

= (0, 0)

sx = 0, sy = 0
for i <- 0 to 2:
sx += d[0]
sy += d[1]
即可，對(duì)于本題，設(shè)置一個(gè)判斷8個(gè)方向的起始位置后，再對(duì)應(yīng)設(shè)置8個(gè)方向向量即可。這樣對(duì)于我們編寫代碼十分有利。可以最大限度的減少代碼量，便于閱讀。

import sys

start = [(2, 0), (1, 0), (0, 0), (0, 0), (0, 0), (0, 1), (0, 2), (2, 0)]
vector = [(0, 1), (0, 1), (0, 1), (1, 1), (1, 0), (1, 0), (1, 0), (-1, 1)]

def main():

while True:
    x = o = 0
    board = []
    for i in range(3):
        line = map(str, sys.stdin.readline().strip().split())
        if len(line[0]) < 3:
            return
        for l in line[0]:
            if l == "X":
                x += 1
            elif l == "0":
                o += 1
        board.append(list(line[0]))

    legal = True
    w1 = w2 = False

    if 0 <= x - o <= 1:
        for i in range(8):
            d = {"0": 0, "X": 0, ".": 0}
            dx, dy = start[i][0], start[i][1]
            for j in range(3):
                t = d.get(board[dx][dy])
                d[board[dx][dy]] = t + 1
                dx += vector[i][0]
                dy += vector[i][1]

            if d.get("X") == 3:
                w1 = True
            if d.get("0") == 3:
                w2 = True

        if w1 and w2 or x > o and w2 or x == o and w1:
            legal = False

    else:
        legal = False

    if legal:
        if w1:
            print "1 won"
        elif w2:
            print "2 won"
        else:
            if x + o == 9:
                print "draw"
            elif x == o:
                print "1"
            else:
                print "2"
    else:
        print "x"

if name == "__main__":

main()

*[1] 關(guān)于01背包問(wèn)題及其擴(kuò)展可以參考下列文章:
http://blog.csdn.net/mu399/ar...
http://blog.csdn.net/insistgo...