1. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。

在 Java 中，编译器使用二进制补码(https://baike.baidu.com/item/二进制补码/5295284)记法来表示有符号整数。因此，在上面的示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：00000000000000000000000000001011

输出：3

解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000

输出：1

解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101

输出：31

解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

输入必须是长度为 32 的二进制串。

进阶：

如果多次调用这个函数，你将如何优化你的算法？

出处：

https://edu.csdn.net/practice/27007582

代码：

import java.util.*;
public class hammingWeight {
    public static class Solution {
        public int hammingWeight(int n) {
            int count = 0;
            while (n != 0) {
                if ((n & 1) == 1)
                    count++;
                n >>>= 1;
            }
            return count;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int n = 0b1011;
        System.out.println(s.hammingWeight(n));
        n = 0b10000000;
        System.out.println(s.hammingWeight(n));
        n = 0b11111111111111111111111111111101;
        System.out.println(s.hammingWeight(n));
    }
}

输出：

2. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) {     print(nums[i]); }

示例 1：

输入：nums = [3,2,2,3], val = 3

输出：2, nums = [2,2]

解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2

输出：5, nums = [0,1,4,0,3]

解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100

0 <= nums[i] <= 50

0 <= val <= 100

出处：

https://edu.csdn.net/practice/27007583

代码：

import java.util.*;
public class removeElement {
    public static class Solution {
        public int removeElement(int[] nums, int val) {
            int len = nums.length;
            for (int i = 0; i < len;) {
                if (nums[i] == val) {
                    nums[i] = nums[len - 1];
                    len--;
                } else {
                    i++;
                }
            }
            return len;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {3,2,2,3};
        System.out.println(s.removeElement(nums, 3));
        int[] nums2 = {0,1,2,2,3,0,4,2};
        System.out.println(s.removeElement(nums2, 2));
    }
}

输出：

3. 验证二叉搜索树

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

有效二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3]

输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]

输出：false

解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 10^4] 内

-2^31 <= Node.val <= 2^31 - 1

出处：

https://edu.csdn.net/practice/27007584

代码：

import java.util.*;
import java.util.LinkedList;
public class isValidBST {
    public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    public static 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;
        }
    }
    public static TreeNode createBinaryTree(Integer[] arr) {
        Vector<Integer> vec = new Vector<Integer>(Arrays.asList(arr));
        if (vec == null || vec.size() == 0) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(vec.get(0));
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode node = queue.poll();
                if (i < vec.size() && vec.get(i) != NULL) {
                    node.left = new TreeNode(vec.get(i));
                    queue.offer(node.left);
                }
                i++;
                if (i < vec.size() && vec.get(i) != NULL) {
                    node.right = new TreeNode(vec.get(i));
                    queue.offer(node.right);
                }
                i++;
            }
        }
        return root;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        Integer[] arr = {2,1,3}; 
        TreeNode root = createBinaryTree(arr);
        System.out.println(s.isValidBST(root));
        Integer[] arr2 = {5,1,4,NULL,NULL,3,6}; 
        TreeNode root2 = createBinaryTree(arr2);
        System.out.println(s.isValidBST(root2));
    }
}

输出：

true

false

Java每日一练(20230504)

1. 位1的个数

2. 移除元素

3. 验证二叉搜索树