小红书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)#小红书2024##小红书2024正式批#