《剑指offer》刷题打卡第1天
面试题1:二维数组中的查找
题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
算法思想:
第一步:选取数组右上角的数字9,将7与9作比较,9>7,又因为9是第四列中最小的一个数,故可做出判断,7绝对不会出现在第四列,所以排除第四列。
第二步:选取第三列中右上角的数字8,8>7,同理,排除第三列。
第三步:选取第二列中右上角的数字2,因为2<7,故要查找的数字7有可能位于2的右或2的下边,因为2的右边已经被排除,故只能往2的下边查找,所以可以排除2所在的行。
第四步:选取第二行第二列数字4,因为4<7,所以同理,排除第二行。
第五步:选取第三行第二列的数字7,因为7=7,故结束查找。
总结规律:
首先选取数组中右上角的数字。如果该数字等于要查找的数字,则查找过程结束;如果该数字大于要查找的数字,则剔除这个数字所在的列;如果该数字小于要查找的数字,则剔除这个数字所在的行。
C++实现:
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
// array是二维数组,这里没做判空操作
int rows = array.size();//求得行大小
int cols = array[0].size();//求得列大小
int i=0,j=cols-1;//取得右上角元素
while(i<rows && j>=0)//使其不超出数组范围
{
if(target < array[i][j])
j--;//排除该列
else if(target > array[i][j])
i++;//排除该行
else
return true;//找到目标
}
return false;
}
};
面试题2:替换空格
题目:请实现一个函数,把字符串中的每个空格替换成“%20”,例如:we are happy
替换后:we20%are20%happy
算法思想:
有两种方法:
法一:如果是在原来的字符串上进行替换,就有可能覆盖修改在该字符串后面的内存。
法二:如果是创建新的字符串并在新的字符串上进行替换,那么我们可以自己分配足够多的内存。
假设面试官让我们在原来的字符串上进行替换,并且保证输入的字符串后面有足够多的内存。
解法一:时间复杂度为o(n^2)
从前向后替换:
首先从头到尾扫描字符串,每次碰到空格字符的时候进行替换。由于是把1个字符替换成3个字符,我们必须要把空格后面所有的字符都后移2个字节,否则就有两个字符被覆盖
此方法时间复杂度太大,效率太低。
解法2:时间复杂度为o(n)
从后向前替换
第1步:首先遍历一次字符串,统计出字符串中空格的总数;
第2步:每替换一个空格,长度增加2,因此替换以后的时间长度等于原来的长度加上2乘以空格数。
第3步:从字符串的后面开始复制和替换。首先准备两个指针:P1和P2,P1指向原始字符串的末尾,而P2指向替换之后的字符串的末尾。
第4步:向前移动P1,逐个把它指向的字符复制到P2指向的位置,直到碰到第一个空格为止。
C++实现:
class Solution {
public:
void replaceSpace(char string[],int length)
{
if(string == nullptr || length <= 0)
return;
//用于判断传进来的字符串是否是空字符串,以及字符数组的总容量是否小于等于0
int originalLength = 0;//字符串string实际长度
int numberOfBlank = 0;//空格数
int i = 0;
while(string[i] != '\0')
{
++ originalLength;//统计字符串的实际长度,除掉字符串末尾的空格
if(string[i] == ' ')
++ numberOfBlank;//统计空格的长度
++ i;//统计总长度
}
/*newLength 为把空格替换成20%之后的长度*/
int newLength = originalLength + numberOfBlank * 2;//空格替换后的总长度
if(newLength > length)//若替换后的总长度大于分配的长度,则直接返回。
return;
//类似于定义两个指针,第一个指针P1,指向字符串的末尾,第二个指针P2,指向替换后的字符串末尾
int indexOfOriginal = originalLength;//原始长度,第一个指针P1
int indexOfNew = newLength;//替换后的长度,第二个指针P2
while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
{
if(string[indexOfOriginal] == ' ')//第一个指针指向空格时,替换第二个指针指向的位置
{
//替换P2指向的位置,P2向前移动三个位置
string[indexOfNew --] = '0';
string[indexOfNew --] = '2';
string[indexOfNew --] = '%';
}
else
{
string[indexOfNew --] = string[indexOfOriginal];//否则,将P1指向的内容赋值给P2
}
-- indexOfOriginal;//每进行一次指针P1向前移动一格
}
}
};