当前位置:首页 » 面试笔试 - 第2页

03月01日

程序员面试题目:请实现一个函数,把字符串中的每个空格替换成"%20"。

发布 : xiaohuanglv | 分类 : 面试笔试 | 评论 : 0 | 浏览 : 1293次
程序员面试题目:请实现一个函数,把字符串中的每个空格替换成"%20"。

题目:请实现一个函数,把字符串中的每个空格替换成"%20"。例如输入“Wearehappy.”,则输出“We%20are%20happy.”。时间复杂度为O(n2)的解法,不足以拿到Offer现在我们考虑怎么做替换操作。最直观的做法是从头到尾扫描字符串,每一次碰到空格字符的时候做替换。由于是把1个字符替换成3个字符,我们必须要把空格后面所有的字符都后移两个字节,否则就有两个字符被覆盖了。举个例子,我们从头到尾把"Wearehappy."中的每一个空格替换成"%20"。为了形象起见,我们可以用一个表格来表示字符串,表格中的每个格子表示一个字符假设字符串的长度是n。对每个空格字符,需要移动后面O(n)个字符,因此对含有O(n)个

03月01日

程序员面试题-二维数组中的查找

发布 : xiaohuanglv | 分类 : 面试笔试 | 评论 : 0 | 浏览 : 1027次
程序员面试题-二维数组中的查找

题目描述在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。解题思路:比如在上图的二维数组中查找元素7,我们每次查找都使用当前数组右上角那个元素与目标元素作比较。比如第一次选右上角的9与7对比,7小于9,显然,9所在那一列不可能有7了,因为那一列最小的元素是9,7比9还小。我们就剔除了这一列!接下来,数组右上角的元素就变为8了,7比8小,因此再剔除这一列。此时数组右上角元素为2了,7比2大,那就剔除2所在的行,这是因为2是在这行的最右边,是这行的最大的元素,7比2大,就比这行所有元素都大,所以剔除这一行。总结一下上面的思路:当target==当前数组

08月18日

怎样判断两个链表相交并找到第一个相交点(微软数据结构面试题)

发布 : xiaohuanglv | 分类 : 面试笔试 | 评论 : 0 | 浏览 : 730次
怎样判断两个链表相交并找到第一个相交点(微软数据结构面试题)

1、给出两个单向链表的头指针pHead1和pHead2,判断这两个链表是否相交。假设两个链表均不带环。如果两个链表相交于某一节点,那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说,如果两个链表相交,那么最后一个节点肯定是共有的。先遍历第一个链表,记住最后一个节点,然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则不相交。时间复杂度为O(len1+len2),因为只需要一个额外指针保存最后一个节点地址,空间复杂度为O(1)。2、给出一个单向链表的头指针pHead,判断链表中是否有环。链表中有环,其实也就是自相交。我们用两个指针pslow和pfast从头开始遍历链表,pslow每次前进一个节点,pfast每次前进两个结点,若存在环,则psl

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!