算法--2023.1.9

1.力扣128-最长连续序列

class Solution {
    public int longestConsecutive(int[] nums) {
        //通过hashset保存去重复后的所有数据
        int n = nums.length;
        int res = 0;
        HashSet<Integer> set = new HashSet<>();
        for(int temp : nums){
            set.add(temp);
        }
        //一次遍历整个hashset，判断是否存在比当前值小一的值，若没有该值就是头节点，然后遍历他的后继、
        //该方法保证了每个节点只遍历一次，即时间复杂度O（n）
        for(int temp : set){
            if(set.contains(temp)&&!set.contains(temp-1)){
                int cur = temp+1;
                while(set.contains(cur)){
                    cur++;
                }
                res = Math.max(res,cur-temp);
            }
        }
        return res;
    }
}

2.力扣121-买卖股票的最佳时机

class Solution {
    public int maxProfit(int[] prices) {
        //注意，本题只有一次买卖机会，所有可以这样做
        int res = 0, min_price = prices[0];
        //res保存遍历到当前节点买卖的最大值，min_price保存遍历到当前节点的最小值
        int n = prices.length;
        for(int i = 1; i < n; i++){
            //在每次遍历中比较当前节点卖出最大的价格与之前最大差价的价格
            res = Math.max(prices[i]-min_price,res);
            min_price = Math.min(min_price,prices[i]);
        }
        return res;
    }
}

3.力扣114-二叉树展开为链表

class Solution {
    public void flatten(TreeNode root) {
        //从根节点开始，迭代遍历
        TreeNode temp = root;
        while(temp!=null){
            //如果该节点存在左子树，则将左子树放到该节点右子树的位置
            if(temp.left!=null){
                TreeNode cur = temp.right;
                temp.right = temp.left;
                temp.left = null;
                //找到根节点的左子树最后一个右节点的位置，将其后继节点设置为根结点之前的右节点
                TreeNode t = temp;
                while(t.right!=null){
                    t = t.right;
                }
                //将根结点的右节点，作为下一个根节点，迭代进行遍历。
                t.right = cur;
            }
            temp = temp.right;
        }

    }
}

4.力扣105--从前序与中序遍历构建二叉树　　

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeNode(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
        
    }
    public TreeNode buildTreeNode(int[] preorder, int left, int right, int[] inorder, int l, int r){
        if(left > right){
            return null;
        }
        int i = 0;
        for(;l+i<r;i++){
            if(inorder[l+i] == preorder[left]){
                break;
            }
        }
        TreeNode root = new TreeNode(preorder[left]);
        root.left = buildTreeNode(preorder,left+1,left+i,inorder,l,l+i-1);
        root.right = buildTreeNode(preorder,left+i+1,right,inorder,l+i+1,r);
        return root;
    }
}