删除字符串使字符串变好

从前到后扫描一遍, 如果cnt >= 3了就贪心删掉当前位置即可

class Solution {
public:
    string makeFancyString(string s) {
        string ans;
        for(int i = 0, cnt = 0, now = -1;i < s.size(); ++ i){
            if(now == s[i] - 'a') cnt ++ ;
            else cnt = 1, now = s[i] - 'a';
            if(cnt >= 3) continue;
            else ans += s[i];
        }
        return ans;
    }
};

检查操作是否合法

一共有八个方向
int dx[8] = {-1, 0, 1, 0, -1, 1, -1, 1};
int dy[8] = {0, 1, 0, -1, -1, 1, 1, -1};
分别check一下即可

class Solution {
public:
    int dx[8] = {-1, 0, 1, 0, -1, 1, -1, 1};
    int dy[8] = {0, 1, 0, -1, -1, 1, 1, -1};
    bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        bool flag = false;
        int n = board.size(), m = board[0].size();
        board[rMove][cMove] = color;
        for(int k = 0;k < 8; ++ k){
            int x = rMove + dx[k], y = cMove + dy[k];
            if(x >= n || x < 0) continue;
            if(y >= m || y < 0) continue;
            int cnt = 0;
            while(board[x][y] != board[rMove][cMove] && board[x][y] != '.'){
                cnt ++ ;
                x = x + dx[k], y = y + dy[k];
                if(x >= n || x < 0){
                    cnt = -1;
                    break;
                }
                if(y >= m || y < 0){
                    cnt = -1;
                    break;
                }
            }
            // if(k == 0) cout << board[x][y] << endl;
            if(x < n && x >= 0 && y < m && y >= 0 && board[x][y] == '.') cnt = -1;
            if(cnt >= 1) flag = true;
        }
        return flag;
    }
};

K 次调整数组大小浪费的最小总空间

通过分析发现,其实就是把数组分成k段每一段的值相同,使得总代价最小
n 和 k 只有 200 显然可以 dp
dp[i][j] 表示枚举到 i 当前分成了 j 段的最小代价
dp[i][j] = dp[t - 1][j - 1] + w;
假设 mx 是 [t, i] 的最大值
那么 w = mx * (i - t + 1) - (sum[i] - sum[t - 1]);
sum 可以预处理出前缀和, O(1) 查询

using LL = long long;

const int MAXN = 210;

LL dp[MAXN][MAXN];

class Solution {
public:
    int minSpaceWastedKResizing(vector<int>& nums, int k) {
        int n = nums.size();
        if(k + 1 >= n) return 0;
        k ++ ;
        for(int i = 0;i <= n; ++ i){
            for(int j = 0;j <= k; ++ j)
                dp[i][j] = 1e9;
        }
        vector<int> num(1, 0);
        for(auto t: nums) num.push_back(t);
        nums = num;

        dp[0][0] = 0;
        for(int i = 1;i <= n; ++ i){
            for(int j = 1;j <= k; ++ j){
                LL sum = 0, cnt = 0, mx = 0;
                for(int t = i;t >= 1; -- t){
                    sum += nums[t]; cnt += 1; mx = max(mx, (LL)nums[t]);
                    dp[i][j] = min(dp[i][j], dp[t - 1][j - 1] + cnt * mx - sum);
                }
            }
        }
        return dp[n][k];
    }
};

两个回文子字符串长度的最大乘积

枚举每个 i 做为 center 
然后通过二分判断左右长度的字符串是否相等( 可以使用字符串 hash )
之后求出长度
pre[i] 表示以 i 结尾的最长奇数回文长度
suf[i] 表示以 i 开头的最长奇数回文长度
之后 pre 从前到后扫一遍维护前缀最大值
     suf 从后到前扫一遍维护后缀最大值
pre[i] = max(pre[i - 1], pre[i];
suf[i] = max(suf[i + 1], suf[i]);
还有一种转移就是 pre[i] 从 pre[i + 1] - 2 转移过来,  suf[i] 从 suf[i - 1] - 2 转移过来
那么 ans = pre[i] + suf[i + 1]  i 属于 [2, n]

const int N = 2e5 + 10, base = 131;

typedef unsigned long long ULL;

char str[N];
ULL hl[N], hr[N], p[N];

ULL get(ULL h[],int l,int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}

class Solution {
public:
    long long maxProduct(string s) {
        for(int i = 1;i <= s.size();i ++ ) str[i] = s[i - 1];
        int n = s.size();
        p[0] = 1;
        for(int i = 1,j = n;i <= n;i ++ ,j -- ){
            hl[i] = hl[i - 1] * base + str[i] - 'a';
            hr[i] = hr[i - 1] * base + str[j] - 'a';
            p[i] = p[i - 1] * base;
        }

        vector<long long> pre(n + 1, 1), suf(n + 1, 1);
        for(int i = 1;i <= n;i ++ ){
            long long l = 0, r = min(i - 1, n - i);
            while(l < r){
                long long mid = (l + r + 1) / 2;
                if(get(hl, i - mid, i - 1) != get(hr, n - (i + mid) + 1, n - (i + 1) + 1)) r = mid - 1;
                else l = mid;
            }
            pre[i + l] = max(pre[i + l], 2 * l + 1), suf[i - l] = max(suf[i - l], 2 * l + 1);
        }
        for(int i = 1;i <= n; ++ i){
            if(i - 1 >= 1) pre[i] = max(pre[i], pre[i - 1]);
        }
        for(int i = n;i >= 1; -- i){
            if(i + 1 <= n) pre[i] = max(pre[i], pre[i + 1] - 2);
        }
        for(int i = n;i >= 1; -- i){
            if(i + 1 <= n) suf[i] = max(suf[i], suf[i + 1]);
        }
        for(int i = 1;i <= n; ++ i){
            if(i - 1 >= 1) suf[i] = max(suf[i], suf[i - 1] - 2);
        }
        // for(int i = 1;i <= n;i ++ ) cout << pre[i] << ' ' << suf[i] << endl;
        // cout << endl;
        long long res = 0;
        for(int i = 2;i <= n; ++ i) res = max(res, pre[i - 1] * suf[i]);
        return res;
    }
};