【优选算法】（第十九篇）

目录

消失的两个数字（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);
 }
}