【解题报告】【lintcode61】 Search for a Range

题意 在一个有序数组中,找到给出的范围值的开始和结束点下标 nlogn的复杂度 解答 看到nlogn和有序数组,那么就能想象到二分查找,但是需要对二分查找做一些改动 当找到目标时不停止,而是继续对左右区间进行二分,并维护找到区间边缘的最小/最大下标 那么,一次二分进行完毕之后,我们就可以得到最[......]Re...

【解题报告】lintcode82落单的数

题意 数组里所有数都出现了两次,但是其中有一个只出现了一次,找出它 时间复杂度O(n) 解答 使用位运算,异或运算 由于其结合律 结合律:A^(B^C)=(A^B)^C 且如果两个数字相同,异或结果为0,0与仍和数字的异或为这个数字本身 我们把所有数字异或起来,就是我们要找的结果了 代码[......]Read...

【解题报告】lintcode46主元素

题意 给出一组数字,其中某个数字占据了总数的1/2以上,就是主元素,找出它 o(n)复杂度 思路 使用贪心的思路,每次从数组中拿一个数字,就认为它是主元素,然后继续拿,如果不同,就把计数器减一,如果相同,就把计数器加一,当计数器到0,就把下一个数字又作为主元素,继续这个过程,到最后,拿在手上的[......]Re...

【解题报告】lintcode105复制带随机指针的链表

题意 给出一个链表,每个节点带一个随机指针,复制它 解法 由于有随机指针,如果顺序复制的话,有可能随机指针指向的节点还没有存在,会有问题 解法,首先复制每个节点,插入到其后 此时所有节点都初始化了,再初始化随机指针,把新节点和原来的节点分开 代码 [crayon-5cba190e00e[......]Re...

【解题报告】lintcode245子树

题意 给出两个树,求树二是否为树一的子树 判断是否为子树的条件是从某一结点切断,剩下的部分与树二相同 例子 此时,t2是t1的子树 解法 首先,拿到t2的root,在t1中查找值相同的节点,存入数组,因为可能不止一个起点 然后再从这些节点出发,对比t2,来求是否为子树 代码 [crayo[......]Re...