数据结构 - 机器学习

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

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

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