算法学习

Day 1

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

// Java 快慢指针法 
// 定义一个自增的指针i 与指向自身索引的下一个位置的指针j(起始值)遍历比较，
// 如果相等则跳过不计入统计，若有不等，则需将j位置的值赋值i+1位置上(指针i始终比指针j慢一步)
class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int i = 0;
        for(int j = 1; j < nums.length; j++){
            if(nums[i] != nums[j]){
                i++;
                nums[i] = nums[j];
            }
        }
        return i+1;
    }
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

盛最多水的容器（中等）

给你 n 个非负整数 a1 ，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明： 你不能倾斜容器，且 n 的值至少为 2。

// Java  双指针法
class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int result = 0;
        while(left < right){
            int area = Math.min(height[left], height[right]) * (right - left);
            result = Math.max(area, result);
            //移动的始终是值最小的指针 因为左右指针距离不断缩小 移动值大的指针位置 计算的面积不可能是最大
            if(height[left] <= height[right]){
                //移动左指针
                ++left;
            }else{
                //移动右指针
                --right;
            }
        }
        return result;
    }
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

Day 2

N 叉树的前序遍历（简单）

给定一个 N 叉树，返回其节点值的前序遍历。

例如，给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]。

// 定义节点
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
    public List<Integer> preorder(Node root) {
        // 定义存储栈
        LinkedList<Node> stack = new LinkedList<>();
        // 定义输出链表
        LinkedList<Integer> output = new LinkedList<>();
        if(root == null){
            return output;
        }

        // 存入根节点
        stack.add(root);
        // 判空 从根节点开始节点遍历
        while(!stack.isEmpty()){
            // 取出栈顶节点
            Node topNode = stack.pollLast();
            // 取出节点值添加到输出栈中
            output.add(topNode.val);
            // 翻转当前节点下的子节点，以确保再次从栈顶poll出来的顺序满足前序
            Collections.reverse(topNode.children);
            // 遍历子节点，入栈    如果不为空 则继续遍历栈
            for(Node child: topNode.children){
                stack.add(child);
            }
        }
        return output;
    }
}

二叉树的前序遍历（中等）

给定一个二叉树，返回它的前序遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

// Java

Day 3

二叉树的最大深度（简单）

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

广度优先搜索法

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        // 队列存储树节点（LinkedList实现了Queue） 只允许在一端删除，在另一端插入 
        Queue<TreeNode> queueNode = new LinkedList<>();
        // 添加根结点 不推荐使用LinkedList的add remove方法（满队列add会异常）
        queueNode.offer(root);

        int depth = 0;
        while(!queueNode.isEmpty()){
            int size = queueNode.size();
            // 判断是否有节点
            while(size > 0){
                // 取出队列第一个元素 并删除之
                TreeNode node = queueNode.poll();
                if(node.left != null){
                    queueNode.offer(node.left);
                }
                if(node.right != null){
                    queueNode.offer(node.right);
                }
                size--;
            }
            depth++;
        }
        return depth;
    }
}

验证二叉搜索树（中等）

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

递归法

class Solution {
    public boolean isValidBST(TreeNode root) {
        return iterator(root, null, null);
    }

    /**
     * 左子节点∈(lower, node.val)
     * 右子节点∈(node.val, upper) 
     */
    private boolean iterator(TreeNode node, Integer lower, Integer upper) {
        if(node == null) {
            return true;
        }
        int cur = node.val;
        // 判断左右子节点跟当前节点值大小
        if(lower!=null && cur <= lower) { return false; }
        if(upper!=null && cur >= upper) { return false; }
        // 迭代遍历
        if(!iterator(node.left, lower, cur)) { return false; }
        if(!iterator(node.right, cur, upper)) { return false; }

        return true;
    }
}

Day 4

分类	难度	题目	描述
数组	简单	两数之和	https://leetcode-cn.com/problems/two-sum/
数组	中等	三数之和	https://leetcode-cn.com/problems/3sum/
链表	简单	环形链表	https://leetcode-cn.com/problems/linked-list-cycle
链表	中等	两两交换链表中的节点	https://leetcode-cn.com/problems/swap-nodes-in-pairs
二叉树	简单	二叉树的最大深度	https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
二叉树	简单	二叉树的最小深度	https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
二叉树	中等	二叉树的层序遍历	https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
递归	简单	泰波那契数	https://leetcode-cn.com/problems/n-th-tribonacci-number/
递归	中等	括号生成	https://leetcode-cn.com/problems/generate-parentheses/

算法学习

Day 1

Day 2

Day 3

Day 4

Day 5

Day 6

Day 7