数据结构和算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构和算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2436字,纯文字阅读大概需要4分钟。
内容图文
![数据结构和算法](/upload/InfoBanner/zyjiaocheng/1309/5bc382f1c8b3423dba9d7ef12b71cf20.jpg)
找出那个特殊的字母
给定两个字符串s和t,它们只包含小写字母。字符串t由字符串s随机重排,然后在随机位置添加一个字母。请找出在t中被添加的字母。
示例
如果字符串s = "abcd";
,t = "abdec";
,则输出为e
。
- 方法一:使用异或运算求和
char FindTheDiffAlp(const std::string s, const std::string t)
{
const std::string st = s + t;
char c = 0;
for (std::size_t i = 0; i < st.size(); ++i) {
c ^= st.at(i);
}
return c;
}
- 方法二:分别求和再相减
char FindTheDiffAlp(const std::string s, const std::string t)
{
int sum_s = 0;
int sum_t = 0; // 分别对s和t求和,使用int防止求和结果溢出
for (std::size_t i = 0; i < s.size(); ++i) {
sum_s += s.at(i);
}
for (std::size_t i = 0; i < t.size(); ++i) {
sum_t += t.at(i);
}
return (char)(sum_t - sum_s);
}
- 方法三:边加边减
char FindTheDiffAlp(const std::string s, const std::string t)
{
int c = t.at(s.size());
for (std::size_t i = 0; i < s.size(); ++i) {
c += t.at(i);
c -= s.at(i);
}
return (char)(c);
}
- 方法四:使用数组计数
char FindTheDiffAlp(const std::string s, const std::string t)
{
char c = '0';
int alps[26] = {0};
for (std::size_t i = 0; i < s.size(); ++i) {
alps[s.at(i) - 'a']++;
}
for (std::size_t i = 0; i < t.size(); ++i) {
if (--alps[t.at(i) - 'a'] < 0) {
c = t.at(i);
break;
}
}
return c;
}
找出字符串中的第一个唯一字符
给定一个字符串,找到它的第一个不重复的字符,并返回它的索引值。如果不存在,则返回-1。
示例
如果字符串s = "leetcode";
,则返回0
。
如果字符串s = "loveleetcode";
,则返回2
。
- 方法一:使用字符数组记录字符出现的次数
int FindTheUniqAlp(const std::string s)
{
int alps[26] = {0};
for (std::size_t i = 0; i < s.size(); ++i) {
++alps[s.at(i) - 'a'];
}
int i = 0;
while ((i < s.size()) && (alps[s.at(i) - 'a'] > 1)) {
++i;
}
return (i == s.size() ? -1 : i);
}
- 方法二:判断第一次出现和最后一次出现的序号是否相同
int FindTheUniqAlp(const std::string s)
{
for (std::size_t i = 0; i < s.size(); ++i) {
if (s.find_first_of(s.at(i)) == s.find_last_of(s.at(i))) {
return i;
}
}
return -1;
}
找出缺失数字
给定一个包含0,1,2,...,n中的n个数的序列,找出其中没有出现在序列中的那个数。
示例
输入:[3, 0, 1]
输出:2输入:[9, 6, 4, 2, 3, 5, 7, 0, 1]
输出:8
- 方法一:数组求和再逐一减去
int FindMissingNum(const int nums[], int size)
{
// int nums[] = {9, 6, 4, 2, 3, 5, 7, 0, 1};
// int size = sizeof(nums) / sizeof(nums[0]);
int sum = (0 + size) * (size + 1) / 2; // 假设最小值是0,那最大值就是size+1-1;假设最小值是1,那最大值就是size+1
for (int i = 0; i < size + 1; ++i) {
sum -= *(nums + i);
}
return sum;
}
- 方法二:把数组的值作为新数组的下标
int FindMissingNum(const int nums[], int size)
{
int arr[size + 1] = {0};
for (int i = 0; i < size + 1; ++i) {
arr[*(nums + i)] = 1;
}
for (int i = 0; i < size + 1; ++i) {
if (0 == arr[i]) {
return i;
}
}
return -1;
}
原文:https://www.cnblogs.com/dongshanzhishi/p/10759894.html
内容总结
以上是互联网集市为您收集整理的数据结构和算法全部内容,希望文章能够帮你解决数据结构和算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。