广东海颐开发笔试编程题回顾

题目一

1、现以序列{22, 24, 30, 14, 10, 17, 15, 20, 16, 23}的顺序进行输入，请画出构造出的平衡二叉树?请写出实现二叉树左旋的代码?（具体题目忘记了，就随机搞个排序，思路和方法都是一样的）

图

顺序 {22, 14, 10, 17, 24, 30, 15, 20, 16, 23} 重新构建平衡二叉树如下：

       22
      /   \
    14     24
   /  \      \
 10   17     30
      / \      / 
     15 20   16
              \
               23
 

判断对错以及平衡思路：

1

衡二叉树的定义是任何节点的两个子树的高度差不超过1。在这个树中，每个节点的左子树和右子树的高度差都不超过1，因此是平衡的。

2

合规性判断：

• 平衡性：该二叉树是平衡的，因为每个节点的左右子树高度差都不超过1。

• 有序性：根据二叉搜索树（Binary Search Tree，BST）的性质，对于每个节点，其左子树上的所有节点都小于它，右子树上的所有节点都大于它。在这个树中，对于任何节点，其左子树上的节点值都小于该节点的值，右子树上的节点值都大于该节点的值，因此满足BST的有序性要求。

• 所有节点都包含在树中：所有给定的节点 {22, 14, 10, 17, 24, 30, 15, 20, 16, 23} 都包含在这颗树中。

因此，这个二叉树是合规的平衡二叉树（Balanced Binary Search Tree）。

以下是实现二叉树左旋操作的Python代码示例：

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
 
def left_rotate(root):
    if root is None or root.right is None:
        return root
 
    new_root = root.right
    root.right = new_root.left
    new_root.left = root
    return new_root
 
# 用于插入元素的辅助函数
def insert(root, key):
    if root is None:
        return TreeNode(key)
    
    if key < root.val:
        root.left = insert(root.left, key)
    elif key > root.val:
        root.right = insert(root.right, key)
    
    return root
 
# 中序遍历打印二叉树的辅助函数
def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end=" ")
        inorder_traversal(root.right)
 
# 创建一个示例树并插入一些元素
root = None
elements = [22, 14, 10, 17, 24, 30, 15, 20, 16, 23]
 
for element in elements:
    root = insert(root, element)
 
print("原始二叉树:")
inorder_traversal(root)
 
# 执行左旋操作
new_root = left_rotate(root)
 
print("\n左旋后的二叉树:")
inorder_traversal(new_root)

代码包括一个 left_rotate 函数，用于执行二叉树的左旋操作。我们首先构建了一个二叉树，然后对其执行左旋操作，并通过中序遍历来验证左旋操作的结果。左旋操作旋转了当前节点的右子树到当前节点的位置，从而改变了树的结构以保持平衡性。

以下是Java中实现二叉树左旋操作的示例代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
 
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
 
public class BinaryTree {
    // 左旋操作
    public TreeNode leftRotate(TreeNode root) {
        if (root == null || root.right == null) {
            return root;
        }
 
        TreeNode newRoot = root.right;
        root.right = newRoot.left;
        newRoot.left = root;
        return newRoot;
    }
 
    // 中序遍历打印二叉树
    public void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.val + " ");
            inorderTraversal(root.right);
        }
    }
 
    // 插入元素到二叉树
    public TreeNode insert(TreeNode root, int key) {
        if (root == null) {
            return new TreeNode(key);
        }
 
        if (key < root.val) {
            root.left = insert(root.left, key);
        } else if (key > root.val) {
            root.right = insert(root.right, key);
        }
 
        return root;
    }
 
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        TreeNode root = null;
        int[] elements = {22, 14, 10, 17, 24, 30, 15, 20, 16, 23};
 
        for (int element : elements) {
            root = tree.insert(root, element);
        }
 
        System.out.println("原始二叉树:");
        tree.inorderTraversal(root);
 
        // 执行左旋操作
        TreeNode newRoot = tree.leftRotate(root);
 
        System.out.println("\n左旋后的二叉树:");
        tree.inorderTraversal(newRoot);
    }
}

画图思路：

1. 首先，根据给定的元素序列构建初始的二叉树结构。根据题目的要求逐个插入元素来构建二叉树。

2. 在每一步插入元素之后，观察树的结构并确定是否需要执行左旋操作。通常，左旋操作是在插入元素后，树的右子树的高度比左子树的高度大于1时执行。

3. 如果需要执行左旋操作，找到需要旋转的节点，然后执行左旋操作，将右子树旋转到当前节点的位置。

4. 重复步骤2和步骤3，直到所有元素都被插入并且树保持平衡。

代码思路：

1. 创建一个二叉树节点类 TreeNode，其中包括节点值、左子树和右子树的引用。

2. 创建一个二叉树类 BinaryTree，其中包括左旋操作的方法 leftRotate、插入元素的方法 insert，以及中序遍历打印树的方法 inorderTraversal。

3. 在 insert 方法中，按照给定的顺序逐个插入元素，插入后检查树的平衡情况，如果需要执行左旋操作，则执行左旋操作。

4. 在 leftRotate 方法中，执行左旋操作。将当前节点的右子树提升为新的根节点，调整子树的连接。

5. 在 main 方法中，创建一个空树并插入元素来构建初始的二叉树。

6. 执行左旋操作并使用中序遍历打印原始二叉树和左旋后的二叉树，以验证左旋操作的正确性。

题目二

给定整数n，返回所有小于非负整数n的质数的数量

示例1:

输入:n=1

输出: 4

解释:小于10的质数一共有4个，它们是2,3,5,7。

示例2: 输入: n=0

输出: 0

示例3:

输入:n=1

输出: 0

代码

就是判断质数问题，本人当时脑子有点乱，写的代码有些问题

public class CountPrimes {
    public int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
 
        boolean[] isPrime = new boolean[n];
        // 初始化所有数字为质数
        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }
 
        // 使用埃拉托斯特尼筛法找出质数
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
 
        // 统计质数的数量
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
 
        return count;
    }
 
    public static void main(String[] args) {
        CountPrimes solution = new CountPrimes();
        System.out.println(solution.countPrimes(10)); // 输出 4
        System.out.println(solution.countPrimes(0));  // 输出 0
        System.out.println(solution.countPrimes(1));  // 输出 0
    }
}

题目三

给定一组非负整数nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例1:

输入: nums = [10,2]

输出:”210”

示例2:

输入: nums = [3, 30,34, 5,9]

输出: "9534330”

代码：

class LargerNumberComparator(str):
    def __lt__(x, y):
        return x + y > y + x
 
def largestNumber(nums):
    # 将数字转换为字符串并按照自定义比较规则进行排序
    nums = sorted(map(str, nums), key=LargerNumberComparator)
    # 如果排序后的第一个数字是0，则整个结果是0
    if nums[0] == '0':
        return '0'
    # 否则，将排序后的数字连接起来得到最大的整数
    return ''.join(nums)
 
# 示例1
nums1 = [10, 2]
result1 = largestNumber(nums1)
print(result1)  # 输出: "210"
 
# 示例2
nums2 = [3, 30, 34, 5, 9]
result2 = largestNumber(nums2)
print(result2)  # 输出: "9534330"

代码

import java.util.Arrays;
import java.util.Comparator;
 
public class LargestNumber {
    public String largestNumber(int[] nums) {
        // 将数字转换为字符串并按照自定义比较规则进行排序
        String[] numStrs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numStrs[i] = String.valueOf(nums[i]);
        }
 
        Arrays.sort(numStrs, new LargerNumberComparator());
 
        // 如果排序后的第一个数字是0，则整个结果是0
        if (numStrs[0].equals("0")) {
            return "0";
        }
 
        // 否则，将排序后的数字连接起来得到最大的整数
        StringBuilder result = new StringBuilder();
        for (String numStr : numStrs) {
            result.append(numStr);
        }
 
        return result.toString();
    }
 
    private class LargerNumberComparator implements Comparator {
        @Override
        public int compare(String a, String b) {
            String order1 = a + b;
            String order2 = b + a;
            return order2.compareTo(order1);
        }
    }
 
    public static void main(String[] args) {
        LargestNumber solution = new LargestNumber();
        int[] nums1 = {10, 2};
        System.out.println(solution.largestNumber(nums1));  // 输出: "210"
 
        int[] nums2 = {3, 30, 34, 5, 9};
        System.out.println(solution.largestNumber(nums2));  // 输出: "9534330"
    }
}

输入测试：这样改