开学前的最后一次做算法题吧，不知道开学后的复赛有没有时间打了

不过能拿到一件阿里的纪念T恤还是蛮开心的，赛题也很友好，适合我这种养老选手~

描述

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

树木的棵树为 \(b\)，\(1\le n\le 10^5\)。 树木的坐标用 \(trees\) 表示，\(0\le tresss_i\le 10^9\)。 最小美观间隔为 \(d\) ，\(1\le d\le 10^9\)。 保证输入的坐标是排好序的，且两两不相同。

说明

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

示例

输入：

[1,2,3,5,6]
2

输出：

2

——————————————————————————————————

第一道难度不会太大，解题目标是 “移除树数量最小” ，换言之就是 “保留树数量最大”

于是很自然想到首先保存每棵树的原定坐标到数组，然后贪心地遍历保留各种较多的树

贪心的策略是：首先选取最靠左的树，然后在美观的条件下向右选择最近的树并保留

代码如下

class Solution {
public:
    /**
     * @param trees: the positions of trees.
     * @param d: the minimum beautiful interval.
     * @return: the minimum number of trees to remove to make trees beautiful.
     */
    int treePlanning(vector<int> &trees, int d) {
        int n=(int)trees.size(),cnt=1,now=trees[0];
	    for (int i=1;i<n;i++)
		    if (now+d<=trees[i]) cnt++,now=trees[i];
	    return n-cnt;
    }
};

正三角形拼接

描述

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

一开始的木棍根数为 \(n，3 ≤ n ≤ 1000\) 。所有木棍的长度为一个整型数组 \(lengths，1 \le length_i ≤ 10^9\) 。

切割必须要将木棍分成 \(2\) 根整数长度的木棍，而且总长度要和原木棍相等。

说明

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

示例

输入：

[2,3,7,5]

输出：

2

——————————————————————————————————

对简单思维能力的考察，首先注意到 \(n ≥ 3\)，而显而易见三根以上的木棍至多切割两次就可以凑出正三角（以最短木棍长为边长）

由于切割情况只有零次、一次、两次，我们可以从简单的开始下手

首先是零次，需要初始就有三根等长的木棍，这个判断可以在遍历中完成（cnt 为计数变量）

然后考虑一次，有以下两种情况：

（1）初始有两根等长的木棍，并且任意存在一根比它们长的木棍

（2）对半切割某偶数长度的木棍后正好能与另一长度为其一半的木棍凑出（例如 [3,6] -> [3,3,3] ）

其他情况均需要两次切割

确定了思路之后，代码就不难按个人习惯写出了，要注意下各种细节就好了

代码如下

class Solution {
public:
    /**
     * @param lengths: the lengths of sticks at the beginning.
     * @return: return the minimum number of cuts.
     */
    int makeEquilateralTriangle(vector<int> &lengths) {
        int n=(int)lengths.size(),cnt=1,book=0;
        sort(lengths.begin(),lengths.end()); //首先进行排序
        for (int i=1;i<n;i++) {
            if (lengths[i]==lengths[i-1]) cnt++;
            else cnt=1;
            if (cnt==3) return 0; 
            if (cnt==2 && i!=n-1) book=1;
            if (!(lengths[i]&1))
                for (int j=0;j<i;j++)
                    if (lengths[j]*2==lengths[i]) book=1;
        }
        if (cnt==3) return 0;
        else if (book) return 1;
        else return 2;
    }
};

大楼间穿梭

描述

蜘蛛侠在大楼间穿梭。大楼的高度可以看作是一个从左到右排列的数组。

现在蜘蛛侠站在第一栋大楼上，他想跳到最后一栋上。

蜘蛛侠的视野为 \(k\)，他可以花费 \(x\) 点体力，用蛛丝移动到右侧 \(k\) 幢建筑中第一栋比当前位置高的大楼

（此处题目有问题，应是大于等于当前高度的大楼）。

或者蜘蛛侠可以花费 \(y\) 点体力，跳跃到右侧接下来两栋大楼其中一栋。

请计算蜘蛛侠最少花费多少体力，到达最后一栋上。

大楼的高度为数组 \(heights\)，一共有 \(n\) 栋大楼，\(2 ≤ n ≤ 10^5，1 <= heights_i ≤ 10^9\)；

蜘蛛侠的视野为 \(k\)，\(1 ≤ k ≤ n\)。两种行动的体力花费满足 \(1 ≤ x，y ≤ 10^9\)。

说明

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

示例

输入：

heights = [1,5,4,3,3,5]
k = 3
x = 10
y = 6

输出：

16

——————————————————————————————————

开口就是老最优化问题了，题意也很清晰，可以直接上 DP

若 \(nxt[i]\) 记录了 \(i\) 楼之后第一座高度大于等于 \(i\) 的楼号，则可以直接状态转移

由于使用的是刷表法，所以直接用代码来表示比较方便

        w[0]=0;
        for (int i=0;i<n;i++) {
            w[i+1]=min(w[i+1],w[i]+y);
            w[i+2]=min(w[i+2],w[i]+y);
            if (nxt[i]!=-1) w[nxt[i]]=min(w[nxt[i]],w[i]+x);
        }

但是问题在于 \(nxt[]\) 数组如何生成，若是使用朴素的 \(O(n^2)\) 在随机数据下大概率能过（期望复杂度大概 \(O(nlogn)\)），

但是这道题数据是刻意构造过的，会 TLE，所以我这里用的是单调队列来优化）

我们维护一个以坐标为第一关键字，高度为第二关键字的单调队列，即

对于队列内任意靠向队首的元素 \(i\)，靠向队尾的元素 \(j\)，满足：

\(position_i < position_j\;,\;\;\;height_i < height_j\)

且任意时刻队列元素个数小于等于 \(k\)，在遍历时要从后向前，具体处理方式同一般的单调队列

这样就能用 \(O(n)\) 的时间处理好 \(nxt[]\) 数组了，加上前述的 DP 本题就完成了

代码如下

class Solution {
public:
    /**
     * @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.
     */
    long long shuttleInBuildings(vector<int> &heights, int k, int x, int y) {
        long long w[100007];
        int n=(int)heights.size(),nxt[100007];
        deque<int> q1,q2;
        for (int i=0;i<100007;i++) w[i]=9223372036854775807;
 
        for (int i=n-1;i>=0;i--) {
            if ((!q2.empty()) && i+k<q2.back()) 
                q1.pop_back(),q2.pop_back();
            while ((!q1.empty()) && q1.front()<heights[i])
                q1.pop_front(),q2.pop_front();
            nxt[i]=q2.empty()?-1:q2.front();
            q1.push_front(heights[i]),q2.push_front(i);
	    }
        
        w[0]=0;
        for (int i=0;i<n;i++) {
            w[i+1]=min(w[i+1],w[i]+y);
            w[i+2]=min(w[i+2],w[i]+y);
            if (nxt[i]!=-1) w[nxt[i]]=min(w[nxt[i]],w[i]+x);
        }
        return w[n-1];
    }
};

对称前后缀

描述

给定一个字符串 \(s\)。我们令一个字符串的权值为一个字符串的最长对称前后缀长度。

请求出 \(s\) 的所有子串的权值的总和。

例如，“abcxyzcba” 的最长对称前后缀的长度为 \(3\) ，因为 “abc” 和 “cba” 对称。

字符串的长度为 \(n\)，\(1 ≤ n ≤ 3*10^3\)。字符串均由小写英文字符组成。

说明

样例中，单个字符的子串的权值为 \(1\) ，它们的和为 \(7\)。

另外的权值为："bacb"->1，"bacbdab"->2，"bdab"->1，"acbda'->1，所以权值和为 \(12\) 。

示例

输入：

bacbdab

输出：

12

——————————————————————————————————

考虑到子串前后缀的对称性，可以用区间 DP 来解决

用 \(w[i][j]\) 表示子串 \([i,j]\) 的最长对称前后缀长度，

从小区间开始向大区间扩展，\(w[i][j] \leftarrow w[i+1][j-1]\)

转移的条件是 \(s[i]==s[j]\)，具体有两种情况：

（1）中间未被隔开，前后缀重合，\(w[i][j]=w[i+1][j-1]+2\)

（2）中间被隔开，前后缀无交集，\(w[i][j]=w[i+1][j-1]+1\)

另外使用 \(vis[][]\) 数组标记区间中是否被非对称元素隔开（并在转移中继承下去），具体细节请见代码

class Solution {
public:
    /**
     * @param s: a string.
     * @return: return the values of all the intervals.
     */
    long long suffixQuery(string &s) {
        long long w[3007][3007];
        bool vis[3007][3007];
        long long len=(long long)s.size(),ans=len;
        memset(w,0,sizeof(w));
        memset(vis,0,sizeof(vis));
        for (int i=0;i<len;i++) w[i][i]=1;
        for (int k=2;k<=len;k++) {
            for (int i=0;i<=len-k;i++) { //[i,i+k-1]
                int j=i+k-1;
                if (s[i]==s[j]) {
	            if (!vis[i+1][j-1]) w[i][j]=w[i+1][j-1]+2;
		    else {
			  w[i][j]=w[i+1][j-1]+1;
                          vis[i][j]=true;	
	            } 
                }
	        else vis[i][j]=true;
	        ans+=w[i][j];
            }
        }
        return ans; 
    }
};

可爱的彩蛋：毛毛太强啦，这都能发现