300.最长递增子序列704.二分查找42.接雨水199.二叉树的右视图143.重排链表124.二叉树中的最大路径和56.合并区间_随笔

300.最长递增子序列704.二分查找42.接雨水199.二叉树的右视图143.重排链表124.二叉树中的最大路径和56.合并区间 300.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

动规。从前往后遍历，dp[i]表示以nums[i]为最右端的最长子序列长度，遍历j从0到i-1更新dp[i]时，if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);这里要理解的是，更新dp[i]过程中要找的是最长子序列中nums[i]的前驱节点，然后判断以该前驱节点为右端点的长度加1是否比dp[i]大，而不是从头开始一个个找串起来，这样想的话就和动规没什么关系了。

反过来也可以从后往前遍历，每次遍历找到比nums[i]大的nums[j]，并判断nums[j]有没有资格作为nums[i]的直接后继。时间复杂度为O( n 2 n^2 n2)

 for(int i=0;i  贪心+二分法。算法非常巧妙比较难想。设置一个数组d[]保存序列和len标记最长序列长度。数组d[]的更新分两种情况: 
  如果nums[i]大于d数组最大元素d[len]，则令nums[i]插入d[len]后面一个位置。如果nums[i]小于d数组最大元素，则把nums[i]放入d数组中第一个比nums[i]大的元素的位置。 
这里分析一下，首先d数组的保存的值一定是递增的，因为d数组的更新规则都没有破坏它的有序性，这点很重要，d数组有序才可以用二分法。那么思考一下为什么要把比当前d数组最大的数小的元素更新更新到d数组中，这样子做的话d数组保存的不一定是子序列。原因有两点，第一更新到d中并没有改变len值(不是插入)，对结果没有影响。第二这样子做是能够考虑到1,100,20,30的情况，也体现了贪心的思想，相同长度相同位置下把更小的数替换到d中。实际上，d[i]的含义是在整个nums数组中子序列长度为i时的最小末尾元素的值。
 第二个问题，d[len]存在为什么能保证一定存在长度为len的子序列，因为d[0]~ d[len-1]保存的并不一定是子序列。解释一下，因为数组是前往后遍历的，因此赋值(插入)到d[len]位置的第一个元素(在刚赋值的那个时间点)在nums数组中一定是出现在d[0]~d[len-1]元素之前的，也就是说如果存在长度为len-1的子序列，那么这个第一个插入到len位置的元素d[len]就可以加入其中，插入到len-1子序列末尾，构成长度为len的子序列。根据数学归纳法就可以得出，len子序列是一定存在的。
 数组d更新时，遇到第二种情况，就可以用二分法找到替换位置。时间复杂度为O(nlogn)。
  public int lengthOfLIS(int[] nums) {
       int len=0;
       int[] d=new int[nums.length];
       d[0]=nums[0];
       for(int i=1;id[len])
           {
               len++;
               d[len]=nums[i];
           }
           else
           {
               int low=0,high=len;
               while(low

704.二分查找

while(low<=high)这样写跳出循环就不需要再对nums[low]进行一次判断。 94.二叉树中序遍历

栈实现：要注意外层while循环跳出条件，要考虑到树只有右子树的情况。空间O(n)

  while(!stack.isEmpty()||curr!=null)//有左子树栈不为空或者只有右子树
     {
         while(curr!=null)
         {
             stack.push(curr);
             curr=curr.left;
         }
         curr=stack.pop();
         res.add(curr.val);
         curr=curr.right;
     }

线索二叉树：比较复杂，假设curr为当前遍历到的节点，分几种情况:

如果没有左孩子，那么访问当前节点，开始遍历右子树，curr=curr.right

如果有左子树，那么在左子树中找到curr的前驱节点pre。

（pre=curr.left; while(pre.right!=null&&pre.right!=curr) pre=pre.right;），这时候根据pre.right的情况(如果不分情况，只进行前驱节点指向curr *** 作，curr=curr.left，会导致后面curr的左子树访问完回到curr时，会继续访问左子树，无法判断左子树是处于还没进行访问，开始连接前驱节点的状态还是已经访问完毕的状态)由分为两种 *** 作：

若pre.right=null,则连接前驱，pre.right=curr;然后开始遍历左子树curr=curr.left。若pre.right=curr,则说明当前是已经访问完左子树，第二次回到curr节点的状态，这时候就访问当前节点curr，然后开始遍历右子树curr=curr.right。这里断不断开连接对后续 *** 作没有影响。

每个节点被访问两次，时间复杂度O(2n)=O(n)，空间复杂度O(1)。

42.接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

199.二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

容器实现需要用queue.size()来限制每层的访问次数

143.重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

找到链表中点+后半段链表原地逆置+合并链表。

要注意的是，合并链表之前记得链表要从中间断开。

124.二叉树中的最大路径和

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其最大路径和。

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

递归。每次fun(root),更新全局max=Math.max(max，root.val+fun(root.left)+fun(root.right))，返回的是以root节点为根的最大贡献值return root.val+Math.max(fun(root.left)，fun(root.right))。返回不能是加上左右子树的总和，因为要保证每个节点只计算一次，只有在确定根后才能把左右子树的贡献合起来。 56.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

res=new ArrayList<>();
res.add(new int[]{a,b});
res.toArray(new int[res.size()][2])

今日总结

刷题

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/zaji/5719801.html

300.最长递增子序列704.二分查找42.接雨水199.二叉树的右视图143.重排链表124.二叉树中的最大路径和56.合并区间

发表评论

评论列表（0条）