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)); } }
输出：
3
1
31
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)); } }
输出：
2
5
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
