小红书2024届秋招聘(8.19)【C++开发工程师】

1、输入一数n和n行单词，(顺序地)如果能在记忆第i个单词时背诵i次，则表示记住了。问这n个单词能记住几个

输入：
5
b
c
a
a
a
输出：
2
说明：
能记住单词b、a

输入：
5
a
a
a
b
c
输出：
1
说明：
只能记住单词a

写了一遍才看懂题目意思……不能全部存储到字典，需要逐个单词遍历。暴力解决

nDayNum = int(input())
arrstrList = []
for _ in range(nDayNum):
    arrstrList.append(input())

setstrRemembered = set()
dictstrRemembereTimes = {}

for strCur in arrstrList: 
    if strCur in setstrRemembered: 
        continue
    if strCur in dictstrRemembereTimes: 
        dictstrRemembereTimes[strCur] += 1
    else: 
        dictstrRemembereTimes[strCur] = 1
    if dictstrRemembereTimes[strCur] == len(setstrRemembered) + 1: 
        setstrRemembered.add(strCur)

print(len(setstrRemembered))

2、输入数n和n行单词，每个单词可以经过任意次变换，变换方法包括拆分(m->nn, w->vv)堆成和翻转(bdpq和nu)，判断经过变换后该单词是否能称为回文字符串。

输入：
1
qwovvb
输出：
YES
可以变换未bvvovvb

想到可以随意次数的变换，所以变成同一个字符就行

dictstrChangeStr = dict()
dictstrChangeStr['w'] = "vv"
dictstrChangeStr['m'] = "nn"
dictstrChangeStr['b'] = "q"
dictstrChangeStr['d'] = "q"
dictstrChangeStr['p'] = "q"
dictstrChangeStr['q'] = "q"
dictstrChangeStr['u'] = 'n'
dictstrChangeStr['n'] = 'u'

nNum = input()
for _ in range(int(nNum)): 
    strInputStr = input()

    for strCur in dictstrChangeStr:
        strInputStr = strInputStr.replace(strCur, dictstrChangeStr[strCur])
    
    if strInputStr[::-1] == strInputStr:
        print("YES")
    else: 
        print("NO")

3、输入，第一行三个数n、m、k，分别代表图中节点数、图中边数、旅行时间，第二行n个数，表示该节点权重，第三行n个数，表示需要在该节点花费多少旅行时间 后 才可以获得权重，接下来m行每行包含三个数，分别代表相连的两个节点(下标从1开始)和经过该边需要的旅行时间。求在不超过旅行时间的前提下，旅游任意三个相连的节点，能获得的最大权重。

输入：
4 4 8
4 3 2 1
1 2 3 4
1 2 1
2 3 1
2 4 1
3 4 1
输出：
9
路线123可行

这一题没A，时间复杂度高了或者就是python限制。

也只想到暴力……没想到直到最后一题会用的方法也这么朴实无华。

疑问：传统的图算法，比如prim之类的，没有同时涉及边和节点权重的，肯定要大改。如果使用动态规划，感觉包含经过节点（不能往回走）、花费旅行时间、获得权重三个信息，不能当作背包问题处理，不知道有没有改进方案。

strCurLine = input()
arrstrList = strCurLine.split()
nNodeNum, nLineNum, nMaxNum = int(arrstrList[0]), int(arrstrList[1]), int(arrstrList[2])
strCurLine = input()
arrstrList = strCurLine.split()
arrnValue = [int(arrstrList[i]) for i in range(nNodeNum)]
strCurLine = input()
arrstrList = strCurLine.split()
arrnNodeSpand = [int(arrstrList[i]) for i in range(nNodeNum)]

arrarrnAdjustList = [[] for _ in range(nNodeNum)]

for _ in range(nLineNum):
    strCurLine = input()
    arrstrList = strCurLine.split()
    nNode1, nNode2, nNodeSpand = int(arrstrList[0]) - 1, int(arrstrList[1]) - 1, int(arrstrList[2])
    if nNode1 > nNode2: 
        nNode1, nNode2 = nNode2, nNode1
    arrarrnAdjustList[nNode1].append([nNode2, nNodeSpand])
    arrarrnAdjustList[nNode2].append([nNode1, nNodeSpand])

nRes = 0
nCostAccumulate = 0
nCurRes = 0
visitedRoute = []
for nNode1Idx in range(len(arrarrnAdjustList)):
    nCostAccumulate += arrnNodeSpand[nNode1Idx]
    if nCostAccumulate > nMaxNum:
        nCostAccumulate -= arrnNodeSpand[nNode1Idx]
        continue
    nCurRes += arrnValue[nNode1Idx]
    if nRes < nCurRes: 
        nRes = nCurRes

    for nNode2Idx, nNode2Spand in arrarrnAdjustList[nNode1Idx]:
        nCostAccumulate += nNode2Spand + arrnNodeSpand[nNode2Idx]
        if nCostAccumulate > nMaxNum:
            nCostAccumulate -= nNode2Spand + arrnNodeSpand[nNode2Idx]
            continue
        nCurRes += arrnValue[nNode2Idx]
        if nRes < nCurRes: 
            nRes = nCurRes

        for nNode3Idx, nNode3Spand in arrarrnAdjustList[nNode2Idx]:
            if nNode3Idx == nNode1Idx or str(nNode3Idx) + str(nNode2Idx) + str(nNode1Idx) in visitedRoute:
                continue
            nCostAccumulate += nNode3Spand + arrnNodeSpand[nNode3Idx]
            if nCostAccumulate > nMaxNum:
                nCostAccumulate -= nNode3Spand + arrnNodeSpand[nNode3Idx]
                continue
            nCurRes += arrnValue[nNode3Idx]
            if nRes < nCurRes: 
                nRes = nCurRes
            nCurRes -= arrnValue[nNode3Idx]
            nCostAccumulate -= nNode3Spand + arrnNodeSpand[nNode3Idx]
            visitedRoute += str(nNode3Idx) + str(nNode2Idx) + str(nNode1Idx)

        nCurRes -= arrnValue[nNode2Idx]
        nCostAccumulate -= nNode2Spand + arrnNodeSpand[nNode2Idx]

    nCurRes -= arrnValue[nNode1Idx]
    nCostAccumulate -= arrnNodeSpand[nNode1Idx]

print(nRes)