深度学习
题目描述在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。解题思路:比如在上图的二维数组中查找元素7,我们每次查找都使用当前数组右上角那个元素与目标元素作比较。比如第一次选右上角的9与7对比,7小于9,显然,9所在那一列不可能有7了,因为那一列最小的元素是9,7比9还小。我们就剔除了这一列!接下来,数组右上角的元素就变为8了,7比8小,因此再剔除这一列。此时数组右上角元素为2了,7比2大,那就剔除2所在的行,这是因为2是在这行的最右边,是这行的最大的元素,7比2大,就比这行所有元素都大,所以剔除这一行。总结一下上面的思路:当target==当前数组
问题描述:在某个字符串中(字符串可能很长,比如有几千万个字符),请找出某个出现频率大于50%的那个字符。例如:在字符串"aabcdaa"中,字符串长为7,字符'a'出现了4次,其出现频率大于50%,因此'a'就是最终要输出的字符。问题分析:思路1:解决这个问题最简单的方法就是遍历一遍字符串,针对每个字符都统计出其出现的次数,最后再遍历一遍这些次数,看哪个字符的次数超过了总次数的50%。该方法的优点是思路简单明了,缺点是额外的存储空间耗费大,算法时间复杂度高。思路2:首先对这个字符串中的字符按照某种次序排序(比如字符的字典序),得到一个有序的字符串,显而易见,该字符串中间的那个字符一定就是我们要找的那个出现频率超过50%的字符。该方法的优点是
1、给出两个单向链表的头指针pHead1和pHead2,判断这两个链表是否相交。假设两个链表均不带环。如果两个链表相交于某一节点,那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说,如果两个链表相交,那么最后一个节点肯定是共有的。先遍历第一个链表,记住最后一个节点,然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则不相交。时间复杂度为O(len1+len2),因为只需要一个额外指针保存最后一个节点地址,空间复杂度为O(1)。2、给出一个单向链表的头指针pHead,判断链表中是否有环。链表中有环,其实也就是自相交。我们用两个指针pslow和pfast从头开始遍历链表,pslow每次前进一个节点,pfast每次前进两个结点,若存在环,则psl