京东笔试:大小写最优输入策略的两种解法

在英文的输入中，我们经常会遇到大小写切换的问题，频繁切换大小写会增加我们的按键次数，也会降低我们的打字效率。 众所周知，切换大小写有两种方式，一种是按下"caps locks"，也就是大写锁定键，这样一来，之后的输入模式都会被切换。另一种是同时按下shift和需要打印的字母，可以临时切换大小写（算作按下两个键）。
已知初始状态下，打字模式是小写，现在给出需要打印的字符串（区分大小写），请你计算出最少需按键多少次才能打印出来。

输入：
输入第一行仅包含一个正整数n，表示字符串的长度（1<=n<=1000000)
输入第二行包含一个长度为n的字符串，仅包含大小写字母

输出：
输出仅包含一个正整数，即最少的按键次数。

样例输入：
6
AaAAAA

样例输出：
8
方法一:找到状态转移利用动态规划进行解决
方法二:用最直接的想法进行输入模拟以将损失最小化
下面给出代码,关键部分都给出了注释

#include <bits/stdc++.h>
using namespace std;

// 方法一:动态规划
int DP(int **dp, string s) {
    size_t sz = s.size();
    // 初始化,状态从小写开始
    dp[0][0] = isupper(s[0]) ? 2 : 1;
    dp[1][0] = 2;
    for (size_t i = 1; i < sz; i++) {
        if (isupper(s[i])) {
            dp[0][i] = min(dp[0][i - 1] + 2, dp[1][i - 1] + 2);
            dp[1][i] = min(dp[0][i - 1] + 2, dp[1][i - 1] + 1);
        } else {
            dp[0][i] = min(dp[0][i - 1] + 1, dp[1][i - 1] + 2);
            dp[1][i] = min(dp[0][i - 1] + 2, dp[1][i - 1] + 2);
        }
    }
    return min(dp[0][sz - 1], dp[1][sz - 1]);
}

// 方法二:压缩模拟
int compress(string s) {
    vector<int> vec;
    vec.push_back(1);
    for (size_t i = 1; i < s.size(); i++) { // 将连续的大小写压缩计数
        if(isupper(s[i]) != isupper(s[i - 1])) vec.push_back(1);
        else vec[vec.size() - 1]++;
    }
    int fp = isupper(s[0]) ? 1 : 0;
    int flag = 0, cnt = 0; // flag当前键盘大小写状态,cnt记录shift和capslock使用次数
    for (size_t i = 0; i < vec.size(); i++) {
        if (((i + fp) & 1) != (flag & 1)) { // 偶数位置代表小写,奇数位置代表大写
            cnt++;
            if (vec[i] > 1) flag ^= 1; // 同大小写的连续两个及以上则锁定capslock并切换大小写状态
        }
    }
    vec.clear();
    return cnt; 
}

int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    // 方法一:dp
    int **dp;
    dp = new int*[2];
    for (int i = 0; i < 2; i++) dp[i] = new int[s.size()];
    cout << DP(dp, s) << endl;
    // 方法二:压缩模拟
    cout << compress(s) + s.size() << endl; // shift+capslock使用次数加上字母数
    return 0;
}