一.数据结构
1.数组与字符串
1.1 实现一个算法,确定一个字符串的所有字符是否全都不同。假使不允许使用额外的数据结构,又该如何处理?
/* 假设字符集为ASCII字符串,那么字符串至多有256个字符,因为一旦大于256个则必定有两个是相同的 */ #include<iostream> #include<string> using namespace std; bool isUniqueChars(string str){ if (str.size() > 256) return false; bool char_set[256]; for(int i = 0; i < str.size; ++i) { int val = str[i]; //获取字符对应得ASCII码 if (char_set[val]) //这个字符已经在字符串中出现 return false; char_set[val] = 1; } return true; } /* 假如输入的字符只含有小写字母a到z,则我们只需要用一个int型变量 */ bool isUniqueChar2(string str) { int flag = 0; if (str.size() > 26) return false; for (int i = 0; i < 26; ++i) { int val = str[i] - 'a'; if (flag&(1 << val) > 0) return false; flag |= (1 << val); } return true; }
1.2 用C或C++实现void reverse(char* str)函数,即反转一个null结尾的字符串。
/*假设原地反转,不分配额外空间,下面为C语言实现*/ #include<stdio.h> void reverse(char* str) { char* end = str; char* start = str; char tmp; if (str) { while (*end) ++end; } --end; /*回退一个字符,因为最后的字符为null*/ /*从首尾开始交换*/ while (start < end) { tmp = *end; *end = *start; *start = tmp; ++start; --end; } }
1.3 给定两个字符串,请编写程序,确定其中一个字符串的字符重新排列后,能否变成另外一个字符串。
/*给定两个字符串,请编写程序,确定其中一个字符串的字符重新排列后,能否变成另外一个字符串。*/ /*假设字符区分大小写,空白字符也考虑在内,以下是两种解法,使用C++*/ #include<iostream> #include<string> #include <algorithm> using namespace std; /*解法一:排序字符串,将两个字符串进行排序后再进行比较*/ bool permutation1(string s, string t) { if (s.size() != t.size()) return false; string s1 = s; string t1 = t; /*进行排序*/ sort(s1.begin(), s1.end()); sort(t1.begin(), t1.end()); if (s1 == t1) return true; return false; } /*解法二:比较两个字符串各字符数是否相同*/ bool permutation2(string s, string t) { if (s.size() != t.size()) return false; int count[256] = { 0 }; /*计算s中各个字符出现的次数*/ for (string::size_type i = 0; i !=s.size(); ++i) { int val = (int)s[i]; count[val]++; } for (string::size_type j = 0; j != t.size(); ++j) { int c = (int) t[j]; if (--count[c] < 0) return false; } return true; }
1.4 编写一个方法,将字符串中的空格全部替换成“%20”。假定该字符串尾部有足够的空间存放新增字符,并且知道字符串的真实长度。例如,输入:"Mr Jone Smith",输出:“Mr20%Jone20%Smith”。
/*编写一个方法,将字符串中的空格全部替换成“%20”。假定该字符串尾部有足够的空间存放新增字符,并且知道字符串的真实长度。*/ /*例如,输入:"Mr Jone Smith",输出:“Mr20%Jone20%Smith”。*/ #include<iostream> #include<string> using namespace std; void replaceSpaces(char* str,int length) { int spaceCount = 0; for (int i = 0; i < length; ++i) { if (str[i] == ' ') ++spaceCount; } int newLength = length + spaceCount * 2; str[newLength] = '