用C++完成算法：给定一个只包含小写字母的字符串，请你找到第一个仅出现一次的字符。如果没有，输出no。

可以使用哈希表来解决这个问题。首先遍历一遍字符串，将每个字符出现的次数记录在哈希表中。然后再遍历一遍字符串，找到第一个出现次数为1的字符即可。

C 代码实现如下：

#include <stdio.h>
#include <string.h>

#define MAXN 100005

int cnt[26]; // 哈希表，记录每个字符出现的次数

int main()
{
char s[MAXN];
scanf("%s", s);
int n = strlen(s);
for (int i = ; i < n; i++) {
cnt[s[i] - 'a']++;
}
int ans = -1;
for (int i = ; i < n; i++) {
if (cnt[s[i] - 'a'] == 1) {
ans = i;
break;
}
}
if (ans == -1) {
printf("no\n");
} else {
printf("%c\n", s[ans]);
}
return ;
}

相关问题

使用【c++】写【给定一个仅包含小写字母的字符串 s s，每次你可以选出一个回文子串，并将其删去；此时余下的字符串会自动前后拼接成一个新的字符串。 请问，最少需要多少步才能将原字符串全部删完？】的代码

在 C++ 中，解决这个问题可以采用动态规划的方法，尤其是使用 Manacher's Algorithm，这是一种用于寻找最短回文子串的高效算法。不过，由于题目允许删除任意回文子串，我们不需要使用这个专门的算法，可以直接遍历字符串并记录每个位置能够形成的最大回文子串长度。

以下是简单的步骤和代码实现：

1. 初始化两个变量 `max_len` 和 `center` 来存储当前已知的最大回文子串长度和它的中心位置。
2. 遍历输入字符串 `s`，对于每个字符 i：
- 计算左边界 `left[i]` 和右边界 `right[i]`，它们分别是从中心位置到 i 的最长回文子串的左右边界。
- 如果 `i + right[i] < s.size()`，则更新 `max_len` 和 `center`。
- 更新 `dp[i] = min(right[i], max_len)`，这是以字符 i 为中心的最长回文子串长度。
3. 最终答案就是字符串长度减去所有最长回文子串的总长度。

以下是相应的 C++ 代码示例：

#include <iostream>
#include <vector>

int main() {
    std::string s;
    // 输入只包含小写字母的字符串 s
    cin >> s;

    int n = s.size();
    std::vector<int> dp(n);
    int max_len = 0, center = 0;

    for (int i = 0; i < n; ++i) {
        if (i < center + max_len) {
            dp[i] = std::min(dp[2 * center - i], max_len - (i - center));
        } else {
            dp[i] = 1;
        }

        while (i - dp[i] >= 0 && i + dp[i] < n && s[i - dp[i]] == s[i + dp[i]]) {
            dp[i]++;
        }

        if (i + dp[i] > center + max_len) {
            center = i;
            max_len = dp[i];
        }
    }

    int steps = n - std::accumulate(dp.begin(), dp.end(), 0);

    std::cout << "最少需要 " << steps << " 步才能将原字符串全部删完。\n";
    return 0;
}

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。

算法思路：

我们可以使用递归的思想来解决这个问题。首先，我们考虑只有两个元素的情况。我们可以把这两个元素交换位置，得到两个不同的排列，然后再交换回来，得到另外两个不同的排列。对于 n 个元素，我们可以先将第一个元素和其他元素依次交换，然后对剩余元素进行全排列。这样可以把问题转化为一个规模更小的问题。具体来说，我们可以固定第一个元素，对剩余元素进行全排列；然后再将第一个元素和其他元素交换，对剩余元素进行全排列，以此类推。

算法实现：

我们可以定义一个递归函数 permute，用来求出给定字符串的所有全排列。该函数接受三个参数，分别为字符串 s、当前访问到的位置 pos，以及存储结果的列表 res。初始时 pos=0，res=[]。在函数 permute 中，我们首先判断 pos 是否等于字符串 s 的长度，如果是，说明已经访问到字符串的末尾，此时将当前排列加入到结果列表 res 中；否则，我们对剩余的元素进行全排列，然后将第一个元素和其他元素依次交换，对剩余元素进行全排列。具体的实现如下：

C++ 代码

class Solution {
public:
vector<string> permutation(string s) {
vector<string> res;
permute(s, 0, res);
return res;
}

void permute(string s, int pos, vector<string>& res) {
if (pos == s.size()) {
res.push_back(s);
return;
}
for (int i = pos; i < s.size(); i++) {
if (i != pos && s[i] == s[pos]) continue;
swap(s[i], s[pos]);
permute(s, pos + 1, res);
}
}
};

Python 代码

class Solution:
def permutation(self, s: str) -> List[str]:
res = []
def permute(s, pos):
if pos == len(s):
res.append(''.join(s))
return
for i in range(pos, len(s)):
if i != pos and s[i] == s[pos]:
continue
s[i], s[pos] = s[pos], s[i]
permute(s, pos + 1)
s[i], s[pos] = s[pos], s[i]
permute(list(s), 0)
return res

复杂度分析：

时间复杂度：O(n*n!)，其中 n 是字符串 s 的长度。全排列的个数是 n!，对于每个排列，我们需要 O(n) 的时间来复制字符串，因此总时间复杂度是 O(n*n!)。

空间复杂度：O(n*n!)，其中 n 是字符串 s 的长度。空间复杂度取决于结果列表 res 的大小，结果列表中最多包含 n! 个字符串，每个字符串的长度是 n，因此总空间复杂度是 O(n*n!)。