首页 > 代码库 > 面试中变相靠算法复杂度
面试中变相靠算法复杂度
一:题目:给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点。链表结点与函数的定义如下:
struct ListNode { int m_nValue; ListNode* m_pNext; }; void delete_note(ListNode *head,ListNode *current) { // 空的 if(head == null || current==null) { return; } else if(current->m_pNext != null) {// 非结尾 ListNode *tmp = current->m_pNext; current->m_nValue = http://www.mamicode.com/tmp->m_nValue;>
分析:如果待删除节点为最后一个节点,则不能按照以上思路,没有办法,只能按照常规方法遍历,时间复杂度为O(n),是不是不符合题目要求呢?可能很多人在这就会怀疑自己的思考,从而放弃这种思路,最后可能放弃这道题,这就是这道面试题有意思的地方,虽看简单,但是考察了大家的分析判断能力,是否拥有强大的心理,充分自信。其实
我们分析一下,仍然是满足题目要求的,如果删除节点为前面的n-1个节点,则时间复杂度为O(1),只有删除节点为最后一个时,时间复杂度才为O(n),所以平均的时间复杂度
为:(O(1) * (n-1) + O(n))/n = O(1);仍然为O(1)
单向链表中删除一个结点,最常规的方法是从头到尾扫描一遍找到结点,然后删除结点。对于给定的是值得结点,没有办法只能从头到尾扫描一个一个对比值得大小,如果链表
中存在,则删除结点。本题给出的是一个结点的指针,我们无需扫描就可以得到结点的指针,在这个过程中,只要把当前结点(p)的next结点(q)的值赋给当前结点,把q的
next结点连接到p的next域删,接下来删除结点q就满足题目的要求了。
但是这个题目中存在许多陷阱:首先是边界条件的考虑,然后是删除结点的位置,表头,表尾,和中间,不同的地方删除时处理不一样。
二:给定一个数组a[N],我们希望构造数组b[N],其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]。
在构造过程:
1、不允许使用除法;
2、要求O(1)空间复杂度和O(n)时间复杂度;
3、除遍历计数器与a[N] b[N]外,不可使用新的变量(包括栈临时变量、对空间和全局静态变量等);
void makeArray(int a[],int b[],int len) { int i,j; b[0] = 1; for(i=1;i<len;i++) { b[i] = b[i-1]*a[i-1]; //累乘a[0]*a[1]...a[i-1] } b[0] = a[len-1]; for(j=len-2;j>0;j--) { b[j] *= b[0]; b[0] *= a[j]; } }
学习心得
1 对于这种带要求的(要求苛刻的)问题,就要求我们不能应用常规的方法来思考它;
2 这种题,一般有一些特点,里面的技巧性很强,当然也比较容易发现,从递推公式中可以看出一些端倪;
3 你用常规的方法书写时 再加上 从递推公式中可以看出一些端倪 应该不难看出它的解法
4 平时一定要多多练习,在自己快速地写完一个算法题后,想一想有没有更优的方法,哪怕只有一点点代码优化;
5 代码优化,也是在面试的时候面试官,在你写完代码后,最爱问的一个问题。面试中变相靠算法复杂度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。