精选留言(11)

• 
  zhaozp

  2018-11-25

  [11,12,13,14,1]这个序列的最大上升子序列，用nlogn的方式求出（1,12,13,14)对吗？不是应该11,12,13,14吗

  作者回复: 长度是对的，但是最长序列本身不能直接用最后结果，而是需要记录每个数的前序数，然后专门生成最后需要的最长上升子序列。

  

   10
• 
  Cwift

  2019-01-31

  我觉得这题用二分法构造的结构每一次迭代都能得到唯一的局部最优结构，这是不是一种贪心的策略？

  作者回复: 用较小元素去替换的思想有和贪心是异曲同工之妙。

  

   4
• 
  crystaljing

  2018-11-26

  [11,12,13,14,1]这个序列的最大上升子序列，用nlogn的方式求出（1,12,13,14)对吗？不是应该11,12,13,14吗?
  最长子序列的长度仍然是4. 所以是正确的。题目只要求长度值，而不是序列。

  

   3
• 
  春风亭lx小树

  2019-06-25

  讲一下老师最后[11,12,13,14,1,2,3,4,5] 这个例子。
  假设这个数组到3为止，[11,12,13,14,1,2,3], 没有4，5，那么二分算法结果就是[1,2,3,14]。我想这大概就是最令人费解的地方，正常的逻辑都会想：不对啊，答案不应该是[11,12,13,14]吗？我看了很多地方的解答也没有解释这里。
  
  我的理解是：
  这里虽然结果是[1,2,3,14]，但是真实路径其实还是[11,12,13,14]！！！
  1,2,3的替换是为了希望之后能找到更优的解，但是如果没有4，5那1，2，3就没有任何意义，显示的是[1,2,3,14]，真实路径还是[11,12,13,14]！！！
  如果，有了4，5，那就是赋予了1，2，3意义。最后表现结果和真实路径会变成[1,2,3,4,5]。
  我理解这个算法：一直保留着局部最优解，又尝试不断跳出局部最优解，如果跳出去了，那全局最优解就是最后的局部最优解。如果没跳出去，那全局最优解就是当初的那个局部最优解，当初那个路径数组的长度。

  展开

  

   1
• 
  不喝酒的小强

  2019-01-05

  二分的方法好像不通用吧，如果数组是［7,8,9,1,2］，这个最长的是［7,8,9］，长度是3吧，二分结果应该是［1,2］长度为2

  作者回复: 你再想想，最后二分里的结果是 1 2 9，长度也是3

  

   1
• 
  宝鹏

  2019-12-11

  手动实现C++版下界二分查找
  int bs_lower_bound(const vector<int>& vec, int target) {
      int start = 0;
      int end = vec.size();
  
      while (start < end) {
          int mid = start + ((end - start) >> 2);
          if (vec[mid] < target)
              start = mid + 1;
          else
              end = mid;
      }
  
      return start;
  }

  展开

  

  
• 
  Aliliin

  2019-12-01

  PHP 的两种解法：
  /**
       * dp 动态规划的写法
       */
      function lengthOfLIS($nums)
      {
          $length = count($nums);
          if (empty($nums) || $length == 0) return 0;
          $res = 1;
          // 先定义好固定大小的数组 PHP 也可以先固定好。防止越界报错
          for ($k = 0; $k < $length; ++$k) $dp[$k] = 1;
          for ($i = 1; $i < $length; ++$i) {
              for ($j = 0; $j < $i; ++$j) {
                  // 只要 $j 小于 $i $i就可以利用之前组建好的结果进行上升
                  if ($nums[$j] < $nums[$i]) {
                      $dp[$i] = max($dp[$i], $dp[$j] + 1);
                  }
              }
              $res = max($res, $dp[$i]);
          }
          return $res;
      }
  
      /**
       * 二分查找
       */
      function lengthOfLIS1($nums)
      {
          if (empty($nums)) return 0;
          $res = 0;
          $tails = [];
          foreach ($nums as $num) {
              $i = 0;
              $j = $res;
              // 二分查找
              while ($i < $j) {
                  $m = intval(($i + $j) / 2);
                  if ($tails[$m] < $num) {
                      $i = $m + 1;
                  } else {
                      $j = $m;
                  }
              }
              $tails[$i] = $num;
              if ($res == $j) $res++;
          }
          return $res;
      }

  展开

  

  
• 
  Daven

  2019-05-27

  class Solution(object):
      def lengthOfLIS(self, nums):
          """
          :type nums: List[int]
          :rtype: int
          """
          if not nums: return 0
  
          dp = [1 for _ in range(len(nums))]
          for i in range(len(nums)):
              maxx = 0
              for j in range(i):
                  if nums[j] < nums[i] and dp[j] >= maxx:
                      maxx = dp[j]
                  dp[i] = maxx + 1
              
          return max(dp)

  展开

  

  
• 
  王磊

  2019-05-13

  二分查找找不到默认返回-1，还需要自己实现返回第一个比它大的数字，还没亲自实现过，java有现成函数吗

  作者回复: 二分模板里的 l 最后应该就指向那个大一点的元素，对吧？

  

  
• 
  Geek_a9389c

  2018-12-17

  不太明白Dp[n-1]不是最终解，而是max（Dp[0] ...Dp[n-1]）.Dp[n-1]是0到n-1，序列最长，上升子序列应该最长，而不是Dp[0]到Dp[n-2]

  

  
• 
  预见

  2018-12-03

  为啥C++的lower_bound可以这样简单的求出比 nums[i] 大的数。我在自己实现的二分查找里考虑了LIS所有值大于nums[i]的情况，有值等于nums[i]的情况等等。搞得程序判断语句较多，效率反而不是很快。老师不用考虑LIS中有值等于nums[i]的情况吗？

   1

  