1540 K次操作转变字符串 #计数

题目链接

题意

给定两字符串ss和tt，要求你在kk次操作以内将字符串ss转变为tt，其中第ii次操作时，可选择如下操作：

  • 选择字符串ss中满足1≤j≤s.length1 \leq j \leq s.length 且之前未被选过的任意下标jj（下标从1开始），并将此位置的字符恰好切换ii 次。切换 1 次字符即用字母表中该字母的下一个字母替换它（字母表环状接起来，所以$'z’切换后会变成′a′'a'）。

    请记住任意一个下标 j 最多只能被操作 1 次！！

  • 不进行任何操作。

如果在不超过 k 次操作内可以把字符串ss转变成tt ，那么请你返回 true ，否则请你返回 false

分析

此题有不少的坑点，起初我没有注意到每个jj只能操作一次，以为可以对jj进行分解操作。事实上，读准题意后不是很难。我们要注意到，对于每一个ii，只能有一个字符可恰好获得ii种操作。另外注意到两个串的长度是不一定相等的。

要使s[i]s[i]转变为t[i]t[i]，最初可分为两种情况：

  • 当s[i]≤t[i]s[i] \leq t[i]，至少需要t[i]−s[i]t[i] - s[i]次操作；
  • 当s[i]>t[i]s[i]>t[i]，需要先将s[i]s[i]转变为′z′'z'，再到达t[i]t[i]，故至少需要$(t[i] - s[i]+26)Mod26 $次操作

两种情况可总结为最初至少需要$(t[i] - s[i]+26)Mod26 $次操作。

但注意，如果一个串中出现不止一个字符需要m(1≤m≤26)m(1 \leq m \leq 26)次的话，第一个这样的字符可以在第mm次操作完成，但是，后面几个这样的字符(记为第xx个)，需要m+26∗(x−1)m+26*(x-1)次操作(跨越x次字母表)。比如说'aa'转变为bb，s[0]s[0]可以在一次操作(i=1i=1)完成，但是s[1]s[1]需要26+126+1次操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool canConvertString(string s, string t, int k) {
        if (s.length() != t.length()) return false;
        vector<int> cnt(27);
        for (int i = 0; i < s.length(); i++) {
            int delt = (t[i] - s[i] + 26) % 26;
            if (delt == 0) continue;
            cnt[delt] ++; //如此的差值，出现次数+1
            if (delt + (cnt[delt] - 1) * 26 > k) return false;
            //一旦发现，操作次数大于k即说明结果为false
        }
        return true;
    }
};

1541 平衡括号字符串的最少插入次数 #计数

题目链接

题意

给定括号字符串ss ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

  • 任何左括号'('必须对应两个连续的右括号'))' 。

  • 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

可在任意位置插入字符 ‘(’ 和 ‘)’ 使字符串平衡。现要返回让 s 平衡的最少插入次数。

样例

"()()))"需要三次插入；"(()))(()))()())))"需要四次插入

分析

这题看起来挺像括号匹配的，但此题如果只有栈去模拟的话，并不方便，因为你要考虑到')'的出现次数，且要保证他们的出现是连续的！

为了保证平衡条件二，我们可以倒序遍历(当然正序遍历也可以，但这样需要同时记录两种括号的出现次数)，遍历的过程中根据情况添补括号/记录右括号的出现次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minInsertions(string s) {
        int right = 0, ans = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] == ')') {
                if (i - 1 >= 0 && s[i - 1] == ')')
                    i--; //下一个右括号不用再管了
                else
                    ans++; //补上一个右括号
                right++; //一对连续的右括号
            }
            else {
                if (right >= 1)
                    right--;//左一右二括号配对
                else 
                    ans += 2; //为左一括号补上两个右括号
            }
        }
        return ans += right; //为剩下的几对右括号补上左括号
    }
};

1542 找出最长的超赞子字符串 #前缀和 #状态压缩 #哈希表

题目链接

题意

给定仅由数字组成的字符串 s 。求 s 中最长的 超赞子字符串 的长度。其中"超赞子字符串"需满足满足下述两个条件：

  • 该字符串是 s 的一个非空子字符串
  • 进行任意次数的字符交换后，该字符串可以变成一个回文字符串

比如"9498331"的长度为3，不是5

分析

审题，这题并不是在考察你经过任意次交换得到的回文串长度(见上方样例)，而是要你找到一个区间长度，使得这样长度的子串交换后能够变为回文串。

我们容易想到一个由数字组成的回文串，它的所有组成字符中，至多只有一个字符出现次数为奇数，其余字符出现次数均为偶数。

既然我们只关心各字符出现的次数是偶数还是奇数，那么我们只需要用01序列的数据结构去记录每个数字出现的次数是偶数还是奇数，若为偶数，则记录为0，反之为1——1−101-10数字的状态由01串去记录，从而实现状态压缩。此外，我们通过01串去记录奇偶性，也有个好处，当我们增添字符时，状态变化可以通过status = status ^ (1<<i)实现，偶+奇=奇，奇+奇=偶，与异或和的结果符合。

我们用哈希表记录每个状态最左出现的位置，设当前状态statusistatus_i，①如果在之前已经出现过该状态(记录该状态为statusjstatus_j)。说明区间[i,j][i, j]的字符出现次数都为偶数，即这个区间字符的出现并没有影响原来statusjstatus_j的奇偶性。②如果在之前存在一个状态statusjstatus_j，它与statusistatus_i之间只有一个字符的出现次数的奇偶性是不同的，说明该字符的出现次数为奇数，影响了statusjstatus_j的奇偶性，而其他字符出现次数的奇偶性没有变。我们的最新状态即是通过前缀和记录的位置来转移的。

提醒，如果使用map的话会超时…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
private: int cnt[11] = { 0 };
public:
    int longestAwesome(string s) {
        for (int i = 0; i < s.length(); i++) {
            int now = s[i] - '0';
            cnt[now] ++;
        }
        int len = 0;
        for (int i = 0; i <= 10; i++) {
            if (cnt[i] >= 2) {
                len += (cnt[i] / 2) * 2;
            }
        }
        if (len == s.length()) return len;
        else return len + 1;
    }
};