P1 树木规划

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

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

说明
样例中，将位置 2 2 2和 6 6 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 n n根木棍，每次切割可以将 1 1 1根木棍切成 2 2 2段。 请计算出最少切割几次，可以从所有木棍中选出 3 3 3根，组成一个 正三角形 。

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

说明
可以从长为 7 7 7的木棍中，切出 2 2 2根长为 3 3 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 k k，他可以花费 x x x 点体力，用蛛丝移动到右侧 k k k幢建筑中第一栋比当前位置高的大楼。 或者蜘蛛侠可以花费 y y y点体力，跳跃到右侧接下来两栋大楼其中一栋。 请计算蜘蛛侠最少花费多少体力，到达最后一栋上。

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

说明
样例中，先花费 6 6 6点体力跳到第三栋建筑，再花费 10 10 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 s。 我们令一个字符串的权值为一个字符串的最长对称前后缀长度。 请求出 s s s的所有子串的权值的总和。 例如，“abcxyzcba” 的最长对称前后缀的长度为 3 3 3，因为 “abc” 和 “cba” 对称。

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

说明
样例中，单个字符的子串的权值为 1 1 1，它们的和为 7 7 7。 另外的权值为： “bacb” -> 1 “bacbdab” -> 2 “bdab” -> 1 “acbda” -> 1 所以权值和为 12 12 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， 下次打比赛一定关注钉钉群。