Python3数据结构算法（树木规划、正三角形拼接）

P1 树木规划

描述
在一条直的马路上，有 $n$棵树，每棵树有一个坐标，代表它们距离马路起点的距离。 如果每相邻的两棵树之间的间隔不小于 $d$，那么我们认为这些树是美观的。 请计算出最少移除多少棵树，可以让这些树变得美观。

树木的棵树为 $n$，$1 \leq n \leq 10^{5}$。 树木的坐标用 $trees$表示$0 \leq$ trees $_{i} \leq 10^{9}$。 最小美观间隔为 $d$，$1 \leq d \leq 10^{\circ}$。 保证输入的坐标是排好序的，且两两不相同。

说明
样例中，将位置 $2$和 $6$的树木移走，剩下 [1,3,5]，它们是美观的。

class Solution: """
    @param trees: the positions of trees.
    @param d: the minimum beautiful interval.
    @return: the minimum number of trees to remove to make trees beautiful.
    """ def treePlanning(self, trees, d): # write your code here. rem = 0 pre = trees[0] for x in trees[1:]: if x - pre >= d: pre = x else: rem += 1 return rem 

P2 正三角形拼接

描述
给出 $n$根木棍，每次切割可以将 $1$根木棍切成 $2$段。 请计算出最少切割几次，可以从所有木棍中选出 $3$根，组成一个 正三角形 。

一开始的木棍根数为 $n$，$3 \leq n \leq 1000$。 所有木棍的长度为一个整型数组 $lengths$，$1 \leq$ length $_{i} \leq 10^{9}$。 切割必须要将木棍分成 根整数长度的木棍，而且总长度要和原木棍相等。

说明
可以从长为$7$的木棍中，切出$2$根长为$3$的木棍，那么木棍的长度应该为[2,3,1,3,3,5] ，可以拼出边长为 的正三角形。

class Solution: """
    @param lengths: the lengths of sticks at the beginning.
    @return: return the minimum number of cuts.
    """ def makeEquilateralTriangle(self, lengths): # write your code here. c = collections.Counter(lengths) for k, v in c.items(): if v >= 3: return 0 A2 = [k for k, v in c.items() if v == 2] if len(A2) > 0: m = min(A2) for x in lengths: if x > m: return 1 for x in lengths: if 2 * x in lengths: return 1 return 2 

P3 大楼间穿梭

描述
蜘蛛侠在大楼间穿梭。大楼的高度可以看作是一个从左到右排列的数组。 现在蜘蛛侠站在第一栋大楼上，他想跳到最后一栋上。 蜘蛛侠的视野为 $k$，他可以花费 $x$ 点体力，用蛛丝移动到右侧 $k$幢建筑中第一栋比当前位置高的大楼。 或者蜘蛛侠可以花费$y$点体力，跳跃到右侧接下来两栋大楼其中一栋。 请计算蜘蛛侠最少花费多少体力，到达最后一栋上。

大楼的高度为数组$heights$ ，一共有$n$栋大楼，$2 \leq n \leq 10^{5}$, $1 \leq$ heights $_{i} \leq 10^{9}$. 蜘蛛侠的视野为 $k$，$1 \leq k \leq n$。 两种行动的体力花费满足 $1 \leq x, y \leq 10^{9}$。

说明
样例中，先花费$6$点体力跳到第三栋建筑，再花费$10$点到达最后一栋。

解：

1. 单调栈 + 动态规划
2. 难点在题目的描述是错误的， k步范围内可以调到相同高度的楼。

class Solution: """
    @param heights: the heights of buildings.
    @param k: the vision.
    @param x: the energy to spend of the first action.
    @param y: the energy to spend of the second action.
    @return: the minimal energy to spend.
    """ def shuttleInBuildings(self, heights, k, x, y): # write your code here. n = len(heights) suf = [-1] * n
        inf = 10 ** 14 dp = [inf] * n
        dp[0] = 0 stack = [] # 1 first build for i in range(n-1, -1, -1): while stack and heights[i] > heights[stack[-1]]: stack.pop() if stack: suf[i] = stack[-1] stack.append(i) for i in range(0, n): if suf[i] != -1 and suf[i] - i <= k: dp[suf[i]] = min(dp[suf[i]], dp[i] + x) for di in [1, 2]: j = di + i if j < n: dp[j] = min(dp[j], dp[i] + y) return dp[-1] def baseline(self, heights, k, x,y): n = len(heights) inf = 10 ** 14 dp = [inf] * n
        dp[0] = 0 for i in range(n): for j in range(i+1, min(i+k+1, n)): if heights[j] >= heights[i]: dp[j] = min(dp[j], dp[i] + x) break for j in range(i+1, min(n, i+2+1)): dp[j] = min(dp[j], dp[i] + y) return dp[-1] if __name__ == "__main__": heights = [1,5,4,3,3,5,1] k = 3 x = 10 y = 6 print(Solution().shuttleInBuildings(heights, k, x, y)) print(Solution().baseline(heights, k, x, y)) 

P4 对称前后缀

描述
给定一个字符串 $s$。 我们令一个字符串的权值为一个字符串的最长对称前后缀长度。 请求出$s$的所有子串的权值的总和。 例如，“abcxyzcba” 的最长对称前后缀的长度为 $3$，因为 “abc” 和 “cba” 对称。

字符串的长度为$n$ ，$1 \leq n \leq 3 * 10^{3}$。 字符串均由小写英文字符组成。

说明
样例中，单个字符的子串的权值为$1$，它们的和为$7$。 另外的权值为： “bacb” -> 1 “bacbdab” -> 2 “bdab” -> 1 “acbda” -> 1 所以权值和为$12$。
解：

1. 常规dp
2. 修正回文串， “afa”=> 3. 将dp值大于等一半长的改为长。

class Solution: """
    @param s: a string.
    @return: return the values of all the intervals.
    """ def suffixQuery(self, s): # write your code here n = len(s) ret = 0 dp = [[0] * n for _ in range(n)] for k in range(1, n+1): for i in range(n): j = i + k -1 if j >= n: continue if k == 1: dp[i][j] = 1 if k == 2: dp[i][j] = 1 if s[i] == s[j] else 0 if k > 2: dp[i][j] = 1 + dp[i+1][j-1] if s[i] == s[j] else 0 lsub = (j - i + 1) // 2 if dp[i][j] >= lsub: dp[i][j] = j - i + 1 ret += dp[i][j] return ret def baseline(self, s): def f(s): L, R = 0, len(s) -1 k = 0 while L <n and R>=0 and s[L] == s[R]: k += 1 L, R = L+1, R-1 return k
        ret = 0 n = len(s) for i in range(n): for j in range(i, n): ret += f(s[i:j+1]) return ret import random def randnstr(n): return "".join(map(lambda x: chr(x), [random.randint(ord('a'), ord('e')) for _ in range(n)])) if __name__ == "__main__": for k in range(3, 20): for i in range(10000): s = randnstr(2) if Solution().suffixQuery(s) != Solution().baseline(s): print(s) s = "fdafas" print(Solution().suffixQuery(s), Solution().baseline(s)) print("finish") 

总结

1. 题目都是基础题， 但是坑一定是有的， 有些常规坑，有的是你想不到的坑，例如题目是错误的。
2. 一开始不能输入测试数据，以为这次比赛不能测， 结果发现是bug， 下次打比赛一定关注钉钉群。

本文地址：https://blog.csdn.net/weixin_42227482/article/details/108293156