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

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

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

    第一次for右往左遍历,记录下每个节点右边的最大值,并开辟一个数组保存在其中。第二次for左往右遍历找出每个节点左边的最大值,并计算面积。用双指针,当前节点能接多少雨水取决于左右两边最大值的最小值,设置左指针left和右指针right,通过左指针维护左边最大值leftmax,右指针维护右边最大值。当leftmax 199.二叉树的右视图

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

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

      队列实现层序遍历,打印每层最后一个节点值。用Queue容器实现需要用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].

      先根据区间左端点快排,再进行区间的合并。用ArrayList保存二维数组并转化为二维数组:
      List res=new ArrayList<>();
      res.add(new int[]{a,b});
      res.toArray(new int[res.size()][2])


    今日总结

    刷题

    欢迎分享,转载请注明来源:内存溢出

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

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-18

发表评论

登录后才能评论

评论列表(0条)

保存