2769. 找出最大的可达成数字 - 力扣（LeetCode）
给你两个整数 num 和 t 。
如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等，则称其为 可达成数字 ：
- 每次操作将
x的值增加或减少1，同时可以选择将num的值增加或减少1。
返回所有可达成数字中的最大值。可以证明至少存在一个可达成数字。
示例 1：
输入：num = 4, t = 1 输出：6 解释：最大可达成数字是 x = 6 ，执行下述操作可以使其等于 num ： - x 减少 1 ，同时 num 增加 1 。此时，x = 5 且 num = 5 。 可以证明不存在大于 6 的可达成数字。
示例 2：
输入：num = 3, t = 2 输出：7 解释：最大的可达成数字是 x = 7 ，执行下述操作可以使其等于 num ： - x 减少 1 ，同时 num 增加 1 。此时，x = 6 且 num = 4 。 - x 减少 1 ，同时 num 增加 1 。此时，x = 5 且 num = 5 。 可以证明不存在大于 7 的可达成数字。
一个简单的数学问题：
每次操作将 x 的值增加或减少 1 ，同时可以选择将 num 的值增加或减少 1 。
由题可知：要找num 可达最大的x取值， 因为可以进行T次操作后
max( num ) = num + T; min (num ) = num - T;
max(x) = x +T ; min(x) = x -T;
那么要找到最大num进行T次操作后可达的x ： x - T= num +T;
如果要找最小num进行T次操作后可达的x ： x + T= num - T;
1542. 找出最长的超赞子字符串 - 力扣（LeetCode）
给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
「超赞子字符串」需满足满足下述两个条件：
- 该字符串是
s的一个非空子字符串 - 进行任意次数的字符交换后，该字符串可以变成一个回文字符串
示例 1：
输入：s = "3242415" 输出：5 解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"
示例 2：
输入：s = "12345678" 输出：1
示例 3：
输入：s = "213123" 输出：6 解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"
示例 4：
输入：s = "00" 输出：2
由回文串可知：1.从左向右读 和从右向左读是相同的，2.每个字符出现偶数次或者 只有一个字符出现奇数次其他都出现偶数次
因为只有奇偶次分，且 奇 + 1 = 偶 偶 + 1 = 奇，所有我们可以进行状态压缩：{0为偶数次，1 为奇数次}
由题可知： 1.我们要找的是一个非空子串 2. 进行任意次数的字符交换后，该字符串可以变成一个回文字符串（这个说明我们可以忽略掉 （1.从左向右读 和从右向左读是相同的））
用位状态压缩且记录每一个状态，
S[i:j] 表示字符串 s 中从位置 i 到位置 j 组成的子串，T[i:j] 表示 S[i:j] 对中每个字符对应的状态。
假如 S[ i,j] = " 1222344" 那么T[i: j] = 0111( 4:0 3:1 2:1 1:1){0为偶数次，1 为奇数次}
但是如将所有状态都计算出来,那么时间复杂度为O(n*n);
所有我们可以采用类似前缀和的方式。
i < j 知道 T[0,i] 和 T[0,j] 的状态，那么 如果 i ~ j 为 超赞子字符串
那么T[0,i] 和 T[0,j] 的状态最多只有一位不同；
因为 由 奇 - 偶 = 偶 偶 - 偶 = 偶 奇 - 奇 = 偶； 且T[0,i] 和 T[0,j]的状态可知那么
T[i , j] 中某个字符出现的奇偶次也就可知了；
我们由要保证 最多只有一个字符出现偶数次那么T[0,i] 和 T[0,j] 的状态最多只有一位不同；
class Solution {
public:
int longestAwesome(string s) {
int n = s.size(),ox,ans = 1;
unordered_map<int,int> ox_map = {{0,-1}};
for(int j = 0;j < n; j += 1){
ox ^= 1 <<(s[j] - '0');
if(ox_map.count(ox)){
ans = std::max(ans,j - ox_map[ox]);
}else
{
ox_map[ox] = j;
}
for (int k = 0; k < 10; ++k) {
if (ox_map.count(ox ^ (1 << k))) {
ans = max(ans, j - ox_map[ox ^ (1 << k)]);
}
}
}
return ans;
}
};