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 = 0;
unsigned int checklarger = 0;
for(int i = 0; i < str.size();i++)
{
bool flag = str[i] - 'a' >= 0 ;
unsigned int temp;
temp = flag ? 1 << (str[i] - 'a') :
1 << (str[i] - 'A');
if(flag){
if( checklittle & temp ) return false;
else checklittle |= temp;
}else {
if(checklarger & temp) return false;
else checklarger |= temp;
}
}
return true;
View Code
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;
}
}
View Code
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 < 2) return ;
int tail = 1;
for(int i = 1; i < len ; i++){
int j;
for(j = 0; j < tail ; j++){
if(str[j] == str[i]) break;
}
if(j == tail){
str[tail] = str[i];
++tail;
}
}
str[tail] = ' ';
}
View Code
这道题里面判断重复也可以使用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() == 0) return true;
int table[256];
memset(table, 0, sizeof(int) * 256);
for(char c : s){
table[c]++;
}
for(char c: t){
table[c]--;
}
for (int c : table){
if(c != 0) return false;
}
return true;
}
View Code
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 <= 1) return;
for( int lay = 0; lay < n/2; lay++){
int start = lay;
int end = n - lay -1;
for(int i = start ; i < end ; i++){
// record top
int temp = matrix[start][i];
//left to top
matrix[start][i] = matrix[n -1- i][start];
// bottom to left
matrix[n -1- i][start] = matrix[end][n -1-i];
//right to bottom
matrix[end][n-1-i] = matrix[i][end];
// top to right
matrix[i][end] = temp;
}
}
}
View Code
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 < 1) return ;
int n = matrix[0].size();
bool zeroR = false, zeroC = false;
for(int i = 0; i< n ; i++)
if(matrix[0][i] == 0){
zeroR = true;
break;
}
for( int i = 0; i< m ; i++){
if(matrix[i][0] ==0){
zeroC = true;
break;
}
}
for(int i = 1; i< m; i++)
for(int j = 1; j< n; j++)
if(matrix[i][j] == 0){
matrix[0][j] = 0;
matrix[i][0] = 0;
}
for(int i = 1; i< m;i++)
for( int j = 1; j< n; j++)
if(matrix[0][j] ==0 || matrix[i][0] ==0 )
matrix[i][j] = 0;
for(int i = 0; i< n && zeroR ; i++) matrix[0][i] = 0;
for(int i = 0; i< m && zeroC ; i++) matrix[i][0] = 0;
}
View Code
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() == 0) return true;
string ss = s1+ s1;
if(string::npos != ss.find(s2)) return true;
return false ;
}
View Code
原文链接: https://www.cnblogs.com/graph/p/3264330.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/100432
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!