【优选算法】（第十九篇）
目录
消失的两个数字（hard）
题目解析
讲解算法原理
编写代码
替换所有的问号（easy）
题目解析
讲解算法原理
编写代码
消失的两个数字（hard）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个数组，包含从1到N所有的整数，但其中缺了两个数字。你能在O(N)时间内只⽤O(1)的空间找到它们吗？
以任意顺序返回这两个数字均可。
⽰例1:
输⼊:[1]
输出:[2,3]
⽰例2:
输⼊:[2,3]
输出:[1,4]
提⽰：
nums.length<=30000
讲解算法原理
解法（位运算）：
算法思路：
本题就是268.丢失的数字+260.只出现⼀次的数字III组合起来的题。先将数组中的数和 [1, n + 2] 区间内的所有数「异或」在⼀起，问题就变成了：有两个数出
现了「⼀次」，其余所有的数出现了「两次」。进⽽变成了260.只出现⼀次的数字III这道题。
编写代码
c++算法实现：
class Solution
{
public:vector<int> missingTwo(vector<int>& nums) {// 1. 将所有的数异或在⼀起int tmp = 0;for(auto x : nums) tmp ^= x;for(int i = 1; i <= nums.size() + 2; i++) tmp ^= i;// 2. 找出 a，b 中⽐特位不同的那⼀位int diff = 0;while(1){if(((tmp >> diff) & 1) == 1) break;else diff++;}// 3. 根据 diff 位的不同，将所有的数划分为两类来异或 int a = 0, b = 0;for(int x : nums)if(((x >> diff) & 1) == 1) b ^= x;else a ^= x;for(int i = 1; i <= nums.size() + 2; i++)if(((i >> diff) & 1) == 1) b ^= i;else a ^= i;return {a, b};}
};java算法代码：
class Solution
{public int[] missingTwo(int[] nums) {// 1. 先把所有的数异或在⼀起int tmp = 0;for(int x : nums) tmp ^= x;for(int i = 1; i <= nums.length + 2; i++) tmp ^= i;// 2. 找出 a，b 两个数⽐特位不同的那⼀位int diff = 0;while(true){if(((tmp >> diff) & 1) == 1) break;else diff++;}// 3. 将所有的数按照 diff 位不同，分两类异或int[] ret = new int[2];for(int x : nums)if(((x >> diff) & 1) == 1) ret[1] ^= x;else ret[0] ^= x;for(int i = 1; i <= nums.length + 2; i++)if(((i >> diff) & 1) == 1) ret[1] ^= i;else ret[0] ^= i;return ret;}
}
替换所有的问号（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个仅包含⼩写英⽂字⺟和'?'字符的字符串s，请你将所有的'?'转换为若⼲⼩写字⺟，使最终的字符串不包含任何连续重复的字符。
注意：你不能修改⾮'?'字符。题⽬测试⽤例保证除'?'字符之外，不存在连续重复的字符。在完成所有转换（可能⽆需转换）后返回最终的字符串。如果有多个解决⽅案，请返回其中任何⼀
个。可以证明，在给定的约束条件下，答案总是存在的。
⽰例1：
输⼊：s="?zs"输出："azs"
解释：该⽰例共有25种解决⽅案，从"azs"到"yzs"都是符合题⽬要求的。只有"z"是⽆效的修改，因为字符串"zzs"中有连续重复的两个'z'。
⽰例2：
输⼊：s="ubv?w"输出："ubvaw"
解释：该⽰例共有24种解决⽅案，只有替换成"v"和"w"不符合题⽬要求。因为"ubvvw"和"ubvww"都包含连续重复的字符。
提⽰：
1<=s.length<=100
s仅包含⼩写英⽂字⺟和'?'字符
讲解算法原理
解法（模拟）：
算法思路：
纯模拟。从前往后遍历整个字符串，找到问号之后，就⽤ a ~ z 的每⼀个字符去尝试替换即可。
编写代码
c++算法原理：
class Solution
{
public:string modifyString(string s) {int n = s.size();for(int i = 0; i < n; i++){if(s[i] == '?') // 替换{for(char ch = 'a'; ch <= 'z'; ch++){if((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i
+ 1])){s[i] = ch;break;}}}}return s;}
};java算法原理：
class Solution
{public String modifyString(String ss) {char[] s = ss.toCharArray();int n = s.length;for(int i = 0; i < n; i++){if(s[i] == '?') // 替换{for(char ch = 'a'; ch <= 'z'; ch++){if((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i
+ 1])){s[i] = ch;break;}}}}return String.valueOf(s);}
}