1 给定字符串s1和s2,要求判定s2是否能够被s1做循环移位得到的字符串包含。例如,给定s1=AABCD和s2=CDAA,返回true;给定s1=ABCD,s2=ACBD,返回false;
解法一:这类题目最简单的做法就是将s1做循环移位,每移位一次就做一下比较,但是这样当字符串的长度很长时,效率会很低。
解法二:以s1=ABC为例,我们对s1进行一次循环移位之后,有以下过程:
ABC-》CAB-》BCA-》ABC,如果我们保留每次移位后的前缀,再把它加到s1那里就有,s1s1=ABCABC,可以看出,其实s1循环之后的结果都是s1s1的字串,那么问题就变成了s2是否是s1s1的字串,这是典型的用空间来换时间的方法。
2 从无头单链表中删除节点。
解法,注意到链表的节点中没有前趋节点的信息,只有后继节点的信息,又不是一个循环节点,看似是无法删除节点而保证链表不截断成两半的。但是,细心想一下,我们无法得知前驱节点的信息,但是我们可以知道后继节点的信息,那么我们可以删除这个后继的节点,然后将这个后继节点的信息填充到我们要删除的节点那里,可以说,这是一种变相的删除了。
3 电话号码对应的英语单词
电话的号码盘一般可以用于输入字母。如用2可以输入A,B,C,用3可以输入D,E,F等,请你罗列出这些号码盘所能代表的字母集合。
其实这个问题就是一个简单的循环遍历过程,我们其实可以用一个二维数组来表示0-9这九个数字所代表的字母,如下所示:
char c[10][10]={
"abc",
"def"
......
}
定义一个数组来表示每个数字所能代表的字符总数:
int total[10]= {....};
一个用来记录电话位数的数组
int number[TelLength];
一个用来记录对应字符位置的数组
int answer[TelLength],
对应代码如下
while(true){
for(int i = 0;i < TelLength-1;i++){
print(c[number[i],answer[i]])
}
int k = TelLength - 1;
while(k>0){
if(answer[k] < total[number[k]] - 1){
answer[k] ++;
break;
}else{
answer[k] = 0;k--;
}
}
if(k<0)
break;
}
4 假设有这样一个拥有三个操作队列:
一 EnQueue(v):将v加入队列中
二 DeQueue:使队列中的队首元素删除并返回此元素
三 MaxElement:返回队列中的最大元素
思路:这里介绍两种解决的方法
第一种:就是用传统的队列,用两个指针分别指向队列的队首和队尾,然后找最大的元素的过程,实际上就是遍历整个队列的过程,时间复杂度为O(n)
第二种:其实可以用一个堆来存储这些数据,构造一个大顶堆,那么其实取最大值的的时间复杂度便变成了O(1),每次入队和出队的时间复杂度变成了O(logn);
5 二分法找错
int bisearch(char** arr,int b,int e,char *v)
{
int minIndex = b,maxIndex = e,midIndex;
//这里要特别注意循环结束的条件,如果查找个数是偶数,那么结束的条件是minIndex = maxIndex
//如果查找个数是奇数,minIndex == maxIndex - 1
while(minIndex < maxIndex - 1){
//这里本来可以可以写成(maxIndex+minIndex)/2,但是为了避免可以出现的溢出,所以先减后加
midMax = minIndex;
}else {
//这里并没有加一或减一
midMax = maxIndex;
}
}
if(arr[midIndex] == v){
return midMax;
}else if(arr[maxIndex] == v){
return maxIndex;
}else {
return -1;
}
}
阅读(300) | 评论(0) | 转发(0) |