牛客的编辑器真是佛了。
1. 排序+二分
2. 分治
3. 拓扑排序
4. 最短路
1. 数组中两个元素和小于等于M的组合数
题目描述
对于一个整型数组,里面任何2个元素相加,小于等于M的组合有多少种;
如果有符合的,输出组合对数;
没有,输出0;
参考代码
import sys from bisect import bisect_right readline = sys.stdin.readline nums = list(map(int, readline().strip().split())) M = int(readline().strip()) nums.sort() ans = 0 for i, x in enumerate(nums): # ans += bisect_right(nums[:i], M - x) # 实际上 nums[:i] 的复杂度为 O(i),所以会导致整体的复杂度为 O(n^2),但是笔试时也过了,或者双指针可以达到 O(n) ans += bisect_right(nums, M - x, 0, i) # O(nlog(n)) print(ans)
2. 计算K位
题目描述
给你两个正整数 n 和 k,其中 1 =< n <= 26,字符串 Sn 的形成规则如下:
Li表示26个字母a-z,依次是:
L1 = "a"
L2 = "b"
L3 = "c"
...
L26="z"
S1 = "a"
当 i > 1 时,Si = Si-1 +Li + reverse(invert(Si-1))
其中 + 表示字符串的连接操作,reverse(x) 返回反转 x 后得到的字符串,而 invert(x) 则会翻转 x 中的每一位(例如:'a' 翻转为'z','b' 翻转为'y', ... 而 'z' 翻转为 'a')。
例如,符合上述描述的序列的前 4 个字符串依次是:
S1="a"
S2="abz"
S3="abzcayz"
S4="abzcayzdabzxayz"
请你返回 Sn 的 第 k 位字符 ,题目数据保证 k 一定在 Sn 长度范围以内。
示例1输入输出示例仅供调试,后台判题数据一般不包含示例
参考代码
B = [0] for i in range(1, 27): B.append(B[-1] * 2 + 1) class Solution: def findKthBit(self, n: int, k: int) -> str: mid = (B[n] + 1) // 2 if k == mid: return chr(n + ord("a") - 1) elif k < mid: return self.findKthBit(n - 1, k) return chr( ord("z") - ord(self.findKthBit(n - 1, B[n - 1] + 1 - (k - mid))) + ord("a") )
3. 纸张分配问题
题目描述
一群小朋友围成一圈准备开始画画,现在老师需要给这些孩子发纸张;
规则是如果一个小朋友的年龄比自己旁边的人大,那么这个小朋友就必须分到比身旁孩子更多的纸张;
所有孩子至少要有一个纸张,请帮助老师设计一个算法,算出最少需要多少张纸。
备注:
假设小朋友的总数量不会超过100个;
每个小朋友至少要求至少有一张纸;
当且仅当年龄大于相邻小朋友时,才会要求纸张数量更多(年龄相等的情况下,允许小于或者等于)。
参考代码
import sys from collections import deque readline = sys.stdin.readline a = list(map(int, readline().strip().split())) n = len(a) adj = [[] for _ in range(n)] indeg = [0] * n for i in range(n): l = (i - 1 + n) % n r = (i + 1) % n if a[i] > a[l]: adj[l].append(i) indeg[i] += 1 if a[i] > a[r]: adj[r].append(i) indeg[i] += 1 q = deque() for i in range(n): if indeg[i] == 0: q.append(i) b = [1] * n while q: u = q.popleft() for v in adj[u]: b[v] = max(b[v], b[u] + 1) indeg[v] -= 1 if indeg[v] == 0: q.append(v) print(sum(b))
4. 航海探险
题目描述
给你一个由 '0'(水)、'1'(陆地)和'2'(障碍物)组成的的二维网格,再给你一个两栖交通工具,走陆地费用为1,走水路费用为2,障碍物无法通行,请你计算从网格的起始位置行驶到最终位置的最小费用。
注意:仅可以水平方向 和 竖直方向行驶。如果无法到达目的地,则返回-1
另外,起始第1个位置不算,根据到达位置的属性来决定费用。
示例1输入输出示例仅供调试,后台判题数据一般不包含示例
参考代码
import heapq from typing import List class Solution: def minSailCost(self, g: List[List[int]]) -> int: n = len(g) m = len(g[0]) dist = [[float("inf") for _ in range(m)] for _ in range(n)] dist[0][0] = 0 q = [] heapq.heappush(q, (0, 0)) dx = [0, -1, 0, 1] dy = [-1, 0, 1, 0] while q: d, u = heapq.heappop(q) i, j = divmod(u, m) for k in range(4): r, c = i + dx[k], j + dy[k] if 0 <= r < n and 0 <= c < m and g[r][c] != 2: if d + 2 - g[r][c] < dist[r][c]: dist[r][c] = d + 2 - g[r][c] heapq.heappush(q, (dist[r][c], r * m + c)) if dist[-1][-1] == float("inf"): return -1 return dist[-1][-1]
全部评论
(3) 回帖