很显然最终的排序结果必为交叉排布的，且符合[...低 高 低 高...]的形式；1.所以先对数列升序排序，很容易想到高的部分是数组的后一半，低的部分是数组的前一半。2.观察[...低1, 高1, 低2, 高2...]的形式，两两间差的绝对值之和=(高1-低1)+(高1-低2)+(高2-低2)......3.假设数组无穷多项，则显然高的那一半每个被加了两次，低的那一半每个被减了两次。4.但由于数组必然不是无穷多项，必会有断开的。要断开的部分必然在升序数组的中间部分： 4.1 若总项数为偶数，则前一半的最后一个被多减去了一次、后一半的第一个被多加上了一次，需要进行修正。 4.2 若总项数为奇数，...

def solution(arr, num): # 工作清单和工人数目 | O(N*logS), S=sum(arr) assert arr and len(arr) and num if len(arr) <= num: # 如果工人过多，则是取最长的一个工作返回 return max(arr) def get_need_num(limit): # 每个画师只能工作不超过limit的时间，问需要几个画师才能完成 res, worked = 1, 0 # 已用画师数目， 当前画师已工作时间 for v in...

两种方法：借用一个容器如队列、递归解决。【本题python给的时间太少，单IO就超时，不用尝试使用Python求解了】 先给出一个本题构建树的IO方法： # --BEG: INPUT AND BUILD TREE--- # class Node: def __init__(self, x=None): self.v = x self.left = None self.right = None def build_tree(): n = int(input()) nodes = [Node(i) for i in rang...

动态规划： a, b = input(), input() f = [[0] * (len(b) + 1) for _ in range(len(a) + 1)] # f[i][j] 以a[i]和b[j]结尾的共同子串长度 end, max_len = 0, 0 for i in range(len(a)): for j in range(len(b)): if a[i] == b[j]: f[i][j] = f[i - 1][j - 1] + 1 if f[i][j] > max_len: ...

给出一种非排序的方法，复杂度为O(NlogN)，但在实际执行时要比排序快(因为并不需要全排序)—— 找到一组数据的中位数，就是找到第lenth/2的数，因此参考此题即可： https://www.nowcoder.com/practice/673454422d1b4a168aed31e449d87c00 代码解释参考此篇： https://blog.nowcoder.net/n/731472d8574c4b32817431a3ec8eb6c2 def find_k(arr, k): def split(low, high, k=0): if low >= ...

其实不一定需要排序，采用类似快排的想法，随机挑选划分成三堆：比P小的、P、大等于P的。然后判断P在当前子序列中的位置距离，其右侧有几个比它大的: k-1个比它大的，返回P即可； 比k-1个少，在左侧序列中到k-1-offset个即可。offset是当前比P大的个数。 比k-1个多，迭代右侧序列。 （详见代码，复杂度O(NlogN)） def find_k(arr, k): def split(low, high, k=0): if low >= high: return arr[low] i, j, p = low, h...

参考 @ztxz16 的解答，改写了个简短的python代码： @ztxz16: https://blog.nowcoder.net/n/21d889d1febd4f9998e70280b813846a def cal(s1, s2): dp = [[0] * 26 for _ in range(26)] # 在某个位置上，有dp[x1][x2]个s1[x1]和s2[x2] sums, res = 0, 0 for i in range(len(s1)): dp[ord(s1[i]) - ord('a')][ord(s2[i]) - ord('a'...

python正则一行： import re # python:3 print(max([int(i, base=16) if len(i) > 0 else 0 for i in re.split(r'[^0123456789ABCDEF]', input())]))

暴力枚举可过： # a*b = x0 * y0 import math x0, y0 = map(int, input().split()) a_b = x0 * y0 cnt = 0 for i in range(2, a_b): j, j_y = divmod(a_b, i) if j_y == 0 and math.gcd(i, j) == x0: cnt += 1 print(cnt)

想了两个非暴力的解法：哈希表、前缀+二分查找，写法巧妙的话均能通过。 IO 部分都相同： n = int(input()) a = list(map(int, input().split())) # 左往右数第i堆有多少苹果 m = int(input()) q = list(map(int, input().split())) # 第qi个苹果属于哪一堆 哈希表：根据实现方式和语言的不同，可能会TLE。时间复杂度主要取决于苹果的总量。 hm, j = [0] * sum(a), 0 for i in range(n): # 第i堆 t = a[i] while t: ...

讲真没必要那么麻烦真的去构建一棵树，直接利用二叉搜索树的性质，python十几行就结束了。 满二叉树： 深度为n时共2^n-1个节点 二叉搜索树： 左节点所有<=根节点<所有右节点 核心思路：中序遍历二叉搜索树应单调递增 (由题意知道节点最小值为0，因此预设pre为-1)；同时，满二叉树可以保证不越界。（BTW，如果非满，需要加一些边界条件） pre, res = -1, True def search(t, i): global pre, res if i >= len(t): return search(t, 2*i+1) # 左 ...

贪心：未到达终点前每一次走的越远越好；由于步数从1~5，不担心直接越过终点， 所以直接对五求商向上取整就好。不过这种题目假设给个能否走到的变体条件可能就要靠动态规划才比较好解了。 from math import ceil x = int(input()) print(ceil(x/5)) 动态规划：TLE x = int(input()) steps = [1, 2, 3, 4, 5] dp = [float('inf')] * (x+1) # dp[i]还剩多少步需要走几次 dp[0] = 0 for i in range(x+1): for s in steps: ...