用数组写水仙花数(算法高阶、数论算法)、验证二叉搜索树(树、深度优先搜索)、跳跃游戏 II(贪心、数组)

用数组写水仙花数(算法高阶、数论算法)

定义一个整型数组 a[7]，在控制台输入任意的 7 个整数给数组赋值，输出数组中所 有的“水仙花数”。“水仙花数”是指一个三位数其各位数字的立方和等于该数本身。

解答：

import java.util.Scanner;
public class Test {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int arr[] = new int[7];
        System.out.println("请输入7个三位数：");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = in.nextInt();
        }
        System.out.println("数组中的水花仙数为：");
        for (int i = 0; i < arr.length; i++) {
            int x = arr[i] / 100;
            int y = arr[i] / 10 % 10;
            int z = arr[i] % 10;
            if (arr[i] == x * x * x + y * y * y + z * z * z)
                System.out.println(i);
        }
    }
}

验证二叉搜索树(树、深度优先搜索)

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3] 输出：true
示例 2：

输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

解答：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        if (root.left == null && root.right == null) {
            return true;
        }
        if (root.left != null) {
            TreeNode cur = root.left;
            while (cur.right != null) {
                cur = cur.right;
            }
            if (cur.val >= root.val) {
                return false;
            }
        }
        if (root.right != null) {
            TreeNode cur = root.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            if (cur.val <= root.val) {
                return false;
            }
        }
        boolean left = isValidBST(root.left);
        boolean right = isValidBST(root.right);
        return left && right;
    }
}

跳跃游戏 II(贪心、数组)

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:
假设你总是可以到达数组的最后一个位置。

解答：

class Solution {
    public int jump(int[] nums) {
        int end = 0;
        int steps = 0;
        int maxPosition = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}