1.实现一个算法 确定一个字符串的所有字符是否所有不同。如果不同意使用额外的数据结构，又应该怎么做呢？

首先应该问清楚使用ASCII还是Unicode字符串。

如果为前者，如果字符串的长度大于256，则返回0，第一种思路就是构建一个布尔型的数组，

索引值i表示该字符串是否含有字母表的第i个字符。若字符第二次出现，则为假。

bool isUniqueChar(string str){    if(str.length() > 256)        return false;    bool *char_set = new bool[256];    for(int i = 0;i
     
      (str[i]);        if(char_set[val])            return false;        char_set[val] = true;    }    return true;}
     

使用位向量，但是把空间缩短为原来的八分之中的一个。

此外还有两种方法可使用，

1）把字符串中的每个字符与其它字符比較，时间复杂度是O(n2)，空间复杂度是O(1)。

2）假设同意改动字符串，在可先排序，然后检查有无相邻字符同样来推断。

2.实现void reverse(char * str)函数，实现一个NULL结尾的字符串反转。

不应该忽略的是：不分配额外空间，直接就地反转，另外，还要注意NULL字符。void reverse(char *str){    char * end = str;    char temp;    if(str)    {        while(*end)            end++;        --end;//最后一个是NULL因此要回退一个字符。        while(str < end)        {            temp = *str;            *str = *end;            *end = temp;        }    }}

3.给定两个字符串，请编敲代码，确定当中一个字符串的字符又一次排列后，是否能变成另外一个字符串。

首先应该确认的是变位词是否区分大写和小写，还有空格是否考虑在内。

当然，假设两个字符串的长度不同，一定是不同的。

第一种方法我们考虑，排序字符串。在某种程度上，这个算法不算是最优，只是换个角度看，

这个算法也许更可取，由于它：清晰、简单、易懂。从实践的角度来看，这可能是解决问题的上佳之选。

只是，要是效率当头，我们能够换种做法。

方法2：检查两个字符串的各字符数是否同样。

bool permutation(string s,string t){    if(s.length != t.length())        return false;    int *letters = new [256];    for(int i = 0;i<256;i++)        letters[i] = 0;    for(int i = 0;i

4.编写一个算法，把字符串中的空格所有替换为“%20”。假定该字符串尾部有足够的空间存放新增字符，而且知道字符出串的"真实"长度。

在处理字符串的时候，应该考虑从字符串的尾部编辑，从后向前反向操作。这样的方法非常实用。

由于字符串尾部有额外的缓冲，能够直接改动，不用操心覆盖原有数据。

我们採用上面的做法，这样会有两次的扫描。第一次确定有多少空格，我们就知道，从什么位置開始复写。

第二次開始反向编辑字符串，检測到有空格之后将%20复写到下一个位置。若不是空白就复制原来的字符。

void replaceSpace(char str[],int length){    int spaceCount = 0,newLength,i;    for(i = 0;i
      
       =0;i--)    {        if(str[i] == ' ')        {            str[newLength - 1] = '0';            str[newLength - 2] = '2';            str[newLength - 3] = '%';            newLength -= 3;        }        else        {            str[newLength] = str[i];            newLength--;        }    }}
      

5.利用字符反复出现的次数，编写一个方法，实现主要的字符串压缩功能。比方，字符串aabcccccaaa会变为a2b5a3。若压缩之后的字符串没有变短则返回原来的字符串。

//针对上述问题，我们先回给出以下的过程，当然，则个过程没有比較压缩后的字符串与先前字符串的长度问题。string compressBad(string str){    string mystr = "";    char last = str[0];    int count = 1;    for(int i = 1;i

基于效率的原因，我们改动例如以下：

string compressAlternate(string str){    int size = countCompression(str);    if(size>=str.length())        return str;    char *array = new char[size];    int index = 0;    char last = str[0];    int count = 1;    fot(int i = 1;i
     
      < str.length();i++)    {        if(str[i] == last)            count++;        else        {            last = str[i];            size = 1 + count.Str.length();//这一行是伪码，方法见上            count = 1;        }    }    size = ...//同上    return size;}
     

6.给定一副n*n矩阵表示的图像，每一个像素的大小为4字节，将图像旋转90度，不占用额外的存储空间。

void rotate(int **matrix,int n){    for(int layer = 0;layer

7.编写一个算法，若M*N 矩阵中某个元素为0，则将其所在的行和列清零。

首先应该清楚的就是不能在第一次遍历矩阵的时候就把行列清零，由于这样会破坏原矩阵的信息，终于导致矩阵全都是零。

因此应该有两次遍历，第一次用两个数组记录零所在的行和所在的列，假设[i][j]是零元素，那么就让row[i]和column[j]都为true。经过一次遍历之后，就行标识可清零的行和列。假设[2][4],[2][6]为0，仅仅要在row[2]标记为true就可以，不须要标识两次，否则会存在多余的二次赋值。

void setZeros(int **matrix){    bool *row = new bool[matrix.length];    bool *column = new bool[matrix[0].length];    //记录0元素的位置    for(int i = 0;i < matrix.length;i++)    {        for(int j = 0;j < matrix[0].length;j++)        {            if(matrix[i][j] == 0)            {                row[i] = true;                column[j] = true;            }        }    }    for(int i = 0;i

8.假定有一个方法isSubstring,能够检查一个单词是否是其它字符串的子串，给定两个字符串， s1和s2。编写代码检查s2是否为s1旋转而来，要求仅仅能调用一次isSubstring.

 针对这个问题，我们首先应该抽象出来旋转的概念，所谓旋转就是从字符串的中间随意一个位置 切一刀，把切口前面的部分拿到字符串的末尾就可以，也就是xy组成元字符串，切口在xy之间，旋转之后 变成yx。加上题意给出的isSubstring我们能够推測是通过推断子串的方式来推断是否经过旋转而成。 yx一定是xyxy的子串，因此假设是旋转而成的话，上述表明一定成立。

bool isRotation(string s1,string s2) {    int len = s1.length();    if(len == s2.length() && len > 0)        return isSubstring(s1+s1,s2);    return false; }