1.1Implement an algorithm to determine if a string has all unique characters What if you can not use additional data structures?
bool isUniqueChars(string str) {
unsigned int checklittle = ;
unsigned int checklarger = ;
for(int i = ; i < str.size();i++)
{
bool flag = str[i] - 'a' >= ;
unsigned int temp;
temp = flag ? << (str[i] - 'a') :
<< (str[i] - 'A');
if(flag){
if( checklittle & temp ) return false;
else checklittle |= temp;
}else {
if(checklarger & temp) return false;
else checklarger |= temp;
}
}
return true;
1.2 Write code to reverse a C-Style String
void reverse(char *str){
if(NULL == str) return;
char *p = str;
while(*p)++p;
--p;
while(str < p){
char temp = *p;
*p = *str;
*str = temp;
--p;
++str;
}
}
1.3 Design an algorithm and write code to remove the duplicate characters in a string without using any additional bufer NOTE: One or two additional variables are fine .An extra copy of the array is not
void removeDuplicates(char[] str){
if(NULL == str) return ;
int len = strlen(str);
if(len < ) return ;
int tail = ;
for(int i = ; i < len ; i++){
int j;
for(j = ; j < tail ; j++){
if(str[j] == str[i]) break;
}
if(j == tail){
str[tail] = str[i];
++tail;
}
}
str[tail] = '\0';
}
这道题里面判断重复也可以使用1.1的思想，不过要提前搞清楚输入参数的字符集
1.4Write a method to decide if two strings are anagrams or not
bool anagram(string s, string t){
if( s.size() != t.size()) return false;
if( s.size() == ) return true;
int table[];
memset(table, , sizeof(int) * );
for(char c : s){
table[c]++;
}
for(char c: t){
table[c]--;
}
for (int c : table){
if(c != ) return false;
}
return true;
}
1.5
1.6Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees Can you do this in place?
void rotate(vector<vector<int> > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = matrix.size();
if(n <= ) return;
for( int lay = ; lay < n/; lay++){
int start = lay;
int end = n - lay -;
for(int i = start ; i < end ; i++){
// record top
int temp = matrix[start][i];
//left to top
matrix[start][i] = matrix[n -- i][start];
// bottom to left
matrix[n -- i][start] = matrix[end][n --i];
//right to bottom
matrix[end][n--i] = matrix[i][end];
// top to right
matrix[i][end] = temp;
}
}
}
1.7Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0
void setZeroes(vector<vector<int> > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int m = matrix.size();
if(m < ) return ;
int n = matrix[].size();
bool zeroR = false, zeroC = false;
for(int i = ; i< n ; i++)
if(matrix[][i] == ){
zeroR = true;
break;
}
for( int i = ; i< m ; i++){
if(matrix[i][] ==){
zeroC = true;
break;
}
}
for(int i = ; i< m; i++)
for(int j = ; j< n; j++)
if(matrix[i][j] == ){
matrix[][j] = ;
matrix[i][] = ;
}
for(int i = ; i< m;i++)
for( int j = ; j< n; j++)
if(matrix[][j] == || matrix[i][] == )
matrix[i][j] = ;
for(int i = ; i< n && zeroR ; i++) matrix[][i] = ;
for(int i = ; i< m && zeroC ; i++) matrix[i][] = ;
}
1.8 Assume you have a method isSubstring which checks if one word is a substring of another Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using
only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”)
bool isRotation(string s1, string s2){
if(s1.size() != s2.size()) return false;
if(s1.size() == ) return true;
string ss = s1+ s1;
if(string::npos != ss.find(s2)) return true;
return false ;
}