学习内容:

LeeCodeJava

LeeCode

674.最长连续递增序列(简单)

代码:

class Solution {
   public int findLengthOfLCIS(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int max=-1;
        int length=0;
        for (int i = 0; i < nums.length; i++) {
            if(i==0||nums[i]>nums[i-1]){
                length++;
                if(i==nums.length-1&&length>max){
                    max=length;
                }
            }else if(nums[i]<=nums[i-1]){
                if (max <= length) {
                    max = length;
                }
                length=1;
            }
        }
        return max;
    }
}

思路:

先利用一个对于长度的判断来防止空集合对于结果的影响,随后设定一个last值作为上一个元素的数值记录,如果这次的等于上次的,那么就将这次的计入.,否则进行判定,如果这个序列的值大于最大的,那么将其的长度作为最大的长度,随后将长度记录置零,重新技术.

注意点

1.要注意数组不能越界,所以要特别对于第一个进行检测.
2.要注意存在最后一个节点是顺延下去的情况,所以需要额外检测,如果是最后一个的话,需要强制导出一次length与max进行比较.

优解代码:

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int result = 0;
        int l = 0;
        int r = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = 1;
            l = i;
            r = i + 1;
            while ((r < nums.length) && (nums[l] < nums[r])) {
                l++;
                r++;
                count++;
            }
            i = r - 1;
            if (result < count) {
                result = count;
            }
        }
        return result;
    }
}

思路:

使用两个指针来保证逻辑的完整性,一个前,一个后,都可以使用++来处理,每个起始值都对应一个while来负责找到目标位置,减可以通过给while来添加限定条件来使得代码的逻辑更加完整,总而言之,虽然使用的内存只少了一点,但是比我的代码优雅很多.

130.二叉树展开为链表(中等)

我的代码

class Solution {
    public void flatten(TreeNode root) {
        ArrayList<TreeNode> treeNodeArrayList=new ArrayList<>();
        if(root==null){
            return;
        }
        preOrder(treeNodeArrayList,root);
        root.left=null;
        TreeNode cur=root;
        for (int i = 1; i < treeNodeArrayList.size(); i++) {
           cur.right=treeNodeArrayList.get(i);
           cur=cur.right;
        }
    }
    private void preOrder(ArrayList<TreeNode> arrayList,TreeNode cur){
        if(cur==null){
            return;
        }
        arrayList.add(new TreeNode(cur.val,null,null));
        preOrder(arrayList,cur.left);
        preOrder(arrayList,cur.right);
    }
}

初步思路:

无思路,据说可以使用原地算法,目前的想法,只有重新进行前序遍历,然后将Teenode的值输出.大致思路就是用cur来操作root节点,让root可以按照treearrayList的顺序,输出节点
注意,这种原地算法的要求是root不能改变原先的地址,不然会直接导致函数内的数据丢失.
改进方向:使用原先的节点,而不使用new.

改进代码

class Solution {
    public void flatten(TreeNode root) {
        if(root==null){
            return;
        }
        ArrayList<TreeNode> treeNodeArrayList=new ArrayList<>();
        preOrder(treeNodeArrayList,root);
        root.left=null;
        TreeNode cur=root;
        for (int i = 1; i < treeNodeArrayList.size(); i++) {
           cur.right=treeNodeArrayList.get(i);
           cur.right.left=null;
           cur=cur.right;
        }
    }
    private void preOrder(ArrayList<TreeNode> arrayList,TreeNode cur){
        if(cur==null){
            return;
        }
        arrayList.add(cur);
        preOrder(arrayList,cur.left);
        preOrder(arrayList,cur.right);
    }
}

结果发现需要的内存不降反增,改进失败.

优解代码

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.left);
        flatten(root.right);
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        //左侧空置
        root.right = left;
        //右侧的值变成左值
        TreeNode p = root;
        //用p缓存root
        while(p.right != null) {
            p = p.right;
            //根节点向右下移动
        }
        p.right = right;
        //使左节点的下一个变成右节点
    }
}

思路:

实质上是一个在先序遍历的过程中整理节点的过程,从底部开始整理;
1.左孩子移到右孩子的位置.
2.如果右孩子不是null的话,将光标向右孩子处移动,然后将原先的右孩子移动到现在右孩子(之前的左孩子)的右孩子处.
3.因为是从底部开始的,所以每个孩子实际上已经被规整成了一个一个的
4.使用while的原因是因为此时的左孩子不一定是一个,而可能是一串,所以需要找到现有左孩子最小的那个节点.
5,很优雅,很有效