【解题报告】【lintcode28】Search a 2D Matrix

题意 写出一个高效的算法来搜索 m × n矩阵中的值。 这个矩阵具有以下特性: 每行中的整数从左到右是排序的。 每行的第一个数大于上一行的最后一个整数。 性能要求,时间复杂度O(logm+logn) 解答 两次二分,第一次确定所在行,第二次确定所在列 代码 [crayon-5b7ab7[......]Re...

【解题报告】【lintcode111】Climbing Stairs

题意 假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部? 解答 由于一次只能走一步或者两步,所以我们可以直接获得递归的公式,但是当楼梯太多的时候,递归层次太深,会超时。 我们又想到dp,由于一次走一步或者两步,所以可以从上一个状态或者上两个[......]Re...

【解题报告】【lintcode103】Linked List Cycle II

题意 给出一个链表,可能会有环(从某一点开始,经过一段之后又回到这个点),找出这个环的开始点 使用O(n)的复杂度解决 解答 我们可以设置两个指针,一个每次前进一步,一个每次前进两步 那么,如果有环,这两个指针必定在环里某一个点相遇,这时候 假设环外到环开始点的路程为a 假设慢指针在环内走了b[......]Re...

【解题报告】【lintcode362】Sliding Window Maximum

题意 给出一组数字,一个滑动窗口的大小,窗口从开始滑动到数字结束,返回每次窗口中的最大值 解答 由于时间复杂度的要求,我们不能暴力求解,因为这样的复杂度是n*n级别,而题目要求n级别 我们可以通过记录数组下标来解答这个题目 每次新的数字进入时,把小于它的数字下标全部移除,形成递减的结果数组[......]Re...

【解题报告】【lintcode81】Data Stream Median

题意 给出一组数字,逐一输入,每输入一个数字,就输出已经输入数字排序后的中位数,即中间那个数字 解答 直接暴力很简单,但是时间复杂度很高,不符合性能要求。 时间复杂度要求是nlogn,可以想到的是快速排序和堆排序两种排序,再结合题目,我们选择堆 维护两个堆,一个堆比中位数小,一个比中位数大,[......]Re...

【解题报告】【lintcode54】String to Integer II

题意 一个字符串中间含有一个整数数字,找出他,并转为数字返回 解答 主要分为三步来求解 1.使用正则表达式匹配字符串,看是否有符合条件的子串 2.根据匹配结果,再根据符号,小数点的位置确定执行操作串的长度和开始位置 3.对于每一个操作子串的字符进行处理,并加到结果上,最后处理边界和符号 代码[......]Re...