文章目錄

360筆試題
- 1. 正方體的表面積
- 2. m進制加法
騰訊筆試題
- 1. 比較簡單的滑動視窗
- 2. 拆零件
- 3. 雜貨店冰淇淋個數
- 4. 飛機航線
- 5. n*3的網格求最高得分
小紅書筆試題
- 1. 字元串倒序（劍指offer59）
- 2. leetcode198 搶劫犯（重要）
- 3.擊敗魔物（重要）

360筆試題

1. 正方體的表面積

給個二維數組，數組值代表目前位置的正方體（邊長為1）個數，求表面積

leetcode 892 原題 https://leetcode.com/problems/surface-area-of-3d-shapes/

class Solution(object):
    def surfaceArea(self, grid):
        n, res = len(grid), 0
        for i in range(n):
            for j in range(n):
                if grid[i][j]: res += 2 + grid[i][j] * 4
                if i:
                    res -= min(grid[i][j], grid[i - 1][j]) * 2
                if j :
                    res -= min(grid[i][j], grid[i][j - 1]) * 2
        return res

2. m進制加法

兩個m進制數都有n位，調整數字順序，每位分别對應相加取模，得到最大的傳回值。

例如：給定兩個數[4,4,1,1,1]和[4,3,0,1,2]，都是5進制的，通過調整順序，得到最大的和為 [4, 4, 3, 3, 2]

(解釋：将[4,4,1,1,1]調整為[1,4,1,4,1]，将[4,3,0,1,2]調整為[3,0,2,4,1]，相加并取模可以得到最大值[4, 4, 3, 3, 2])

解法（遞歸）：【參考】

例如m=5（五進制），最大數字分别為4,3,2,1,0，兩個數字為[4,4,1,1,1],[4,3,0,1,2]

首先嘗試構造4，求出第一個數[4,4,1,1,1]的對應數放入數組 count_0 ，即為[0,0,3,3,3]， count_1 = [4,3,0,1,2]，找這兩個數組的重合數字為0,3，因而遞歸兩個數字變成了[4,1,1],[4,1,2])
嘗試構造3，求出第一個數[4,1,1]的對應數放入數組 count_0 ，即為[4,2,2]，這個地方有個技巧，需判斷元素是否大于3， count_1 = [4,1,2]，找這兩個數組的重合數字為4,2，因而遞歸兩個數字變成了[1],[1]
嘗試構造2，1+1 = 2，此時遞歸兩個數字變成了[],[]。以此類推
遞歸的結束條件為：兩個數字的長度為0。

import copy
def func(nums, m, num): # nums裡面存放的是兩個數組，m表示m進制，num表示正在湊的數字
    res = []
    count_0, count_1 = [], copy.deepcopy(nums[1]) # count_0存的是第一個數字的“內插補點”，count_1直接存第二個數
    if len(count_1) == 0:     # 遞歸終止條件
        return []

    for i in range(len(nums[1])):
        if nums[0][i] <= num:         # 需判斷元素是否大于num
            count_0.append(num - nums[0][i])             # 直接相加的值
        else:             # 相加之後-模運算的值
            count_0.append(num + m - nums[0][i])

    for i in range(len(nums[1])): # 查詢數組裡面相同的數字，找到之後指派為-1
        if nums[1][i] in count_0:
            res.append(num)
            count_0[i] = -1
            count_1[i] = -1
   	# 傳回已經删減相同元素的原數組
    count_0 = [nums[0][i] for i in range(len(count_0)) if count_0[i] != -1]
    count_1 = [nums[1][i] for i in range(len(count_1)) if count_1[i] != -1]
    return res + func([count_0, count_1], m, num - 1) # 遞歸 num-1表示湊下一個更小數字（從4開始，然後湊3,2,1）

nums = [[4,4,1,1,1],[4,3,0,1,2]]
m = 5
print(func(nums, m, m - 1)) # [4, 4, 3, 3, 2]

騰訊筆試題

1. 比較簡單的滑動視窗

2. 拆零件

3. 雜貨店冰淇淋個數

小明開了個店，冰淇淋有 n 個配料，店裡每個配料的原材料數量為 wi ，每個原材料在商店的價格為 vi, 小明有 m 元錢，問可以最多做多少冰淇淋？

示例資料：

我當時的解法：暴力解法，AC40%，逾時。

AC代碼思路：二分查找；【參考】

def cost(num, w, v):
    price = 0
    for i in range(n):
        if w[i] > num:
            continue
        price += v[i]*(num-w[i])
    return price

if __name__ == "__main__":
    n, m = 3, 10
    w, v = [2,5,3], [2,1,3]
    l = min(w) # 最少做這麼多
    r = 1 + m // sum(v) + max(w)  # 最多可以做這麼多
    while l < r:
        mid = (l + r + 1) >> 1
        if cost(mid, w, v) < m:
            l = mid
        else:
            r = mid - 1
    print(l)

牛客AC代碼思路：每次取1或者買全部材料做冰淇淋能做多少，不斷更新exist數組，【參考】

#coding=utf-8
# 本題為考試多行輸入輸出規範示例，無需送出，不計分。
import sys
if __name__ == "__main__":
    # 讀取第一行的n
    line = sys.stdin.readline().strip()
    # 把每一行的數字分隔後轉化成int清單
    nm = list(map(int, line.split()))
    n = nm[0]
    m = nm[1]
    line = sys.stdin.readline().strip()
    exist = list(map(int, line.split()))
    line = sys.stdin.readline().strip()
    money = list(map(int, line.split()))
 
    total_money = sum(money)
 
    ans = 0
    min_num = min(exist)
    ans += min_num
 
    exist_buf = [i - min_num for i in exist]
    exist = exist_buf
 
    while m > 0:
        min_num = max(1, m // total_money)
        ans += min_num
        need = [i - min_num for i in exist]
        need_money = 0
        for i in range(n):
            exist_buf[i] = max(exist[i] - min_num, 0)
            if need[i] < 0:
                need_money += abs(need[i]) * money[i]
 
            exist = exist_buf
        m -= need_money
    if m < 0:
        ans -= 1
    print(ans)

4. 飛機航線

【筆試代碼題記錄】20190815/17/18 360/騰訊/小紅書360筆試題騰訊筆試題小紅書筆試題

5. n*3的網格求最高得分

有n*3的格子，每個格子都有一定的分數，最開始從第一行的任意一個格子進入，每一步隻能向左下，正下，右下這三個方向走，遇到了分數為0的格子，之後所得的分數都要取相反數，分數可以多次反轉，問，到達最後一行時，得到的最大分數是多少？

這題不會，看到牛客上的解法是從後往前動态規劃，初始狀态是最後一行，用兩個狀态，一個最大，一個最小，如果遇到0就互相調換。

代碼不會寫

https://www.nowcoder.com/discuss/226306?type=post&order=time&pos=&page=1

https://www.nowcoder.com/discuss/226319?type=post&order=time&pos=&page=1

記錄一下臨時代碼，這個是錯的：

# ref https://www.nowcoder.com/discuss/226319?type=post&order=time&pos=&page=1
def func(nums, n): # nums數組是n行3列的
    dp_max = [[0 for _ in range(3)] for _ in range(n)]
    dp_min = [[0 for _ in range(3)] for _ in range(n)]

    dp_max[-1] = nums[-1]
    dp_min[-1] = nums[-1]
    # print(dp_max)
    for i in range(n - 1, -1, -1):
        for j in range(3):
            dp_max[i][j] = dp_max[i - 1][j]
            dp_min[i][j] = dp_min[i - 1][j]
            if j < 2:
                dp_max[i][j] = max(dp_max[i][j], dp_max[i - 1][j + 1])
                dp_min[i][j] = min(dp_min[i][j], dp_min[i - 1][j + 1])
            if j < 0:
                dp_max[i][j] = min(dp_max[i][j], dp_max[i - 1][i - 1])
                dp_min[i][j] = min(dp_min[i][j], dp_min[i - 1][i - 1])

            if nums[j] == 0:
                dp_max[i][j], dp_min[i][j] = - dp_min[i][j], - dp_max[i][j]
            else:
                dp_max[i][j] += nums[i][j]
                dp_min[i][j] += nums[i][j]
    return dp_max, dp_min

nums = [[1, 2, 3],[8, 9, 10],[5, 0, 5],[-9, -8, -10], [0, 1, 2],[5, 4, 6]]
print(func(nums, 6))

小紅書筆試題

有大神分享了AC解法 https://blog.csdn.net/qq_17550379/article/details/99708185

1. 字元串倒序（劍指offer59）

2. leetcode198 搶劫犯（重要）

那一題，不過多了一個要求，除了輸出最大金額，還需要輸出偷了多少家，如果有多種情況都能滿足最大金額，則輸出最少需要偷多少家。

我的思路(隻AC了27%)：動态規劃，構造一個res數組，每個都是二維的，對于res[i][j]，有兩種情況，一種是不更新，則res[i][j] = res[i - 1]，另一種是更新，res[i][j] = [res[i - 2][0] + nums[i], count]，這個count是不斷累加的（後來發現不能用count這樣加，應該是res[i - 2][1] + 1才對。

def func(nums):
    if not nums:
        return 0, 0
    if len(nums) == 1:
        return 1, 1
    if len(nums) == 2:
        return max(nums[0], nums[1]), 1
    res = [[]] * len(nums)
    res[0] = [nums[0],1]
    res[1] = [max(nums[0], nums[1]), 1]
    count = 1
    for i in range(2, len(nums)):
        if res[i - 1][0] >= res[i - 2][0] + nums[i]:
            res[i] = res[i - 1]
        else:
            count += 1
            res[i] = [res[i - 2][0] + nums[i], count]

    if res[-1][0] != res[-2][0]:
        return res[-1]
    return res[-1] if res[-1][1] <= res[-1][1] else res[-2]

牛客上的AC解法一（基于我的思路修改）：

def func(nums):
    res = [[]] * len(nums)
    res[0] = [nums[0],1]
    res[1] = [max(nums[0], nums[1]), 1]
    for i in range(2, len(nums)):
        cur = res[i - 2][0] + nums[i]
        count = res[i - 2][1] + 1
        if cur > res[i - 1][0] or (cur == res[i - 1][0] and count < res[i - 1][1]): # 如果cur == res[i - 1][0]，并且count大于res[i-1][1]的話，也沒必要更新，隻有count小于res[i-1][1]才需要更新。
            res[i] = [cur, count] #  這個count是res[i - 2][1] + 1來的，不是直接累加
        else:
            res[i] = res[i - 1]
    return res[-1]

代碼可以優化下（也是一個AC代碼）： https://blog.csdn.net/qq_17550379/article/details/99708185

def func(nums):
    pre, cur = [0,0],[0,0]
    for i in range(len(nums)):
        tmp, pre = pre[::], cur[::]
        if tmp[0] + nums[i] > cur[0]:
            cur[0] = tmp[0] + nums[i]
            cur[1] = tmp[1] + 1
    return cur[0], cur[1]

牛客上的AC解法二（維護兩個dp數組）：

def func(nums):
    res = [0] * len(nums)
    count = [1] * len(nums)
    res[0] = nums[0]
    res[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        res[i] = max(res[i - 1], res[i - 2] + nums[i])
        if res[i] > res[i - 1]:
            count[i] = count[i - 2] + 1
        else:
            count[i] = count[i - 1]
    return res[-1], count[-1]

3.擊敗魔物（重要）

【筆試代碼題記錄】20190815/17/18 360/騰訊/小紅書360筆試題騰訊筆試題小紅書筆試題

本題解法：貪心+二分。 H為怪物的血量數組，T為回合數，M為法力，X為每次施法造成的傷害，我們要求符合條件的最小的X。具體思路是：

第一步，判斷特殊條件，如果 M + sum(H[M:]) > T ，說明即使一次殺一個，也殺不完所有怪物（回合數T太小了），直接傳回-1.
對怪物的血量排一個降序（二分查找必須數組有序，貪心算法一般要求排降序）
使用二分法的思想，X的左邊界 l =(sum(H) - (T - M)) // M ，右邊界r為最大的怪物血量 r = H[0] ；然後求出 mid = l + ((r - l) >> 1)
，判斷X=mid時能否殺完，如果可以，将右邊界縮為mid，如果不能，将左邊界擴至mid + 1。

關于左右邊界初始值的思考：對于左邊界有，M*X + (T - M) * 1 >= sum(H)），解出X的下界。

對于右邊界有，如果X等于最大的怪物的血量，那麼一次殺一個，肯定能殺完。
問題的關鍵就變成了：給定X = mid時，計算能否在T回合内殺完所有怪物，使用貪心的思想，先周遊一遍數組，用每個怪物的血量整除X，計算能整除幾次，累計一個值成為fali_need，然後将數組的每個元素都對X求餘，得到餘數的血量數組，并對這個數組繼續降序排列（這個數組中的所有值都要比X小），此時的剩餘法力為M - fali_need，用這些剩餘法力解決前M-fali_need個怪物（每個怪物血量都小于X，是以都可以一次解決），如果後面還有剩餘的怪物，那麼隻能計算血量和sum，用實體攻擊來解決，假設實體攻擊使用了wuli_need次，那麼最後統計M + wuli_need是否超過了回合數，如果沒有超過，則傳回True，證明目前的X是可以殺完怪物的。

分享牛客網上的AC代碼：【參考】

def list2gen(a):
    for n in a:
        yield n
 
def ismatch(X):
    # 在達到目标時輸出X
    fali_need = 0
    for Hi in list2gen(H):
        fali_need += Hi // X
#        fali_need = sum([Hi // X for Hi in H])
    # 法力不夠，用實體攻擊彌補
    if fali_need >= M:
        wuli_need = X * (fali_need - M)
        for Hi in list2gen(H):
            wuli_need += Hi % X
#            wuli_need += sum([Hi % X for Hi in H])
        if M + wuli_need <= T: # M表示法力攻擊輪數，wuli_need表示實體攻擊輪數
            return True
        else:
            return False
    # 法力超出，多出來的這樣用
    # X=3，Hi=2,這樣使用一次
    else:
        yushu = sorted([Hi % X for Hi in H])# 對餘數降序排列（所有餘數都比M要小，是以要用法力優先解決餘數大的怪物）
        wuli_need = sum(sorted(yushu)[::-1][M - fali_need :]) #剩餘的法力為M-fali_need，用這些搞定前面的，後面剩餘的全靠實體
        if M + wuli_need <= T:
            return True
        else:
            return False
 
def solution(N, T, M, H):
     
    H = sorted(H)[::-1]
     
    # 特殊情況
    if M + sum(H[M:]) > T:
        return -1
         
    l = (sum(H) - (T - M)) // M
    r = H[0]
#    print(l, r)
     
    while l < r:
        mid = l + ((r - l) >> 1)
#        print(f'mid: {mid}')
        if ismatch(mid):
            r = mid
        else:
            l = mid + 1
    return l
 
import sys
line = sys.stdin.readline().strip()
N, T, M = list(map(int, line.split()))
line = sys.stdin.readline().strip()
H = list(map(int, line.split()))
print(solution(N, T, M, H))

【筆試代碼題記錄】20190815/17/18 360/騰訊/小紅書360筆試題騰訊筆試題小紅書筆試題

文章目錄

360筆試題

1. 正方體的表面積

2. m進制加法

騰訊筆試題

1. 比較簡單的滑動視窗

2. 拆零件

3. 雜貨店冰淇淋個數

4. 飛機航線

5. n*3的網格求最高得分

小紅書筆試題

1. 字元串倒序（劍指offer59）

2. leetcode198 搶劫犯（重要）

3.擊敗魔物（重要）

繼續閱讀

快速排序非遞歸實作

2015騰訊線上筆試的一道程式設計題

程式設計将二進制IP位址轉換成十進制

嵌入式軟體工程師筆試面試指南-問題答疑（持續更新中）

Java集合面試總結 Java集合面試總結

String類中的compareTo方法總結String類的定義：

排列組合總結組合全排列：

華為筆試題:括号的排列組合

C/Python實作的一道筆試題

校招hr面試必備

面試：atoi() 與 itoa()函數的内部實作

合并兩個已排序的數組為同一個數組

結構體位元組對齊詳解為什麼要對齊？記憶體對齊的三條重要原則

關于IO流的筆試面試題

【leetcode】高頻題目整理_設計篇( High Frequency Problems, Design )相關/參考連結

Java筆試題庫（03期）