水滴笔试 - 0912

二叉树的层序遍历

题面

给定一个二叉树，返回该二叉树层序遍历的结果，(从左到右，一层一层地遍历)

例如：
给定的二叉树是 {3,9,20,#,#,15,7}，该二叉树层序遍历的结果是 [ [3],[9,20],[15,7] ]

提示:
$0 \leq $ 二叉树的结点数 $ \leq 1500$

思路与代码

使用队列实现层序遍历二叉树

从根节点开始，将每一层的节点依次加入队列，然后逐层处理队列中的节点，直到队列为空。每一层的节点处理时，将它们的子节点加入队列，以便在下一轮处理。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int len = q.size();
            vector<int> cur;
            
            for (int i = 0; i < len; i++) {
                TreeNode* node = q.front();
                q.pop();
                cur.push_back(node->val);
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            res.push_back(cur);
        }
        
        return res;
    }
};

链表排序

题面

给定一个节点数为 $n$ 的无序单链表，对其按升序排序。

数据范围：$0<n≤100000$，保证节点权值在 $[−10^9, 10^9]$之内。
要求：空间复杂度 $O(n)$，时间复杂度 $O(nlogn)$

示例：

输入：[-1,0,-2]
输出：{-2,-1,0}

思路与代码

归并排序模板题。

归并排序在链表上实现时可以保持时间复杂度为 $O(n logn)$，且空间复杂度为 $O(1)$

步骤：

1. 分割链表：使用递归的方法将链表分割成两个子链表，直到每个子链表只有一个节点。
2. 合并链表：将两个有序的子链表合并成一个有序的链表。合并时，比较两个链表的头节点，选择较小的节点作为合并后的链表的头节点，并继续比较后续节点。
3. 递归合并：递归地合并所有子链表，直到整个链表有序。

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        if (!head || !head->next) return head;
        
        // 找到链表的中点
        ListNode *slow = head, *fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 分割链表
        ListNode *mid = slow->next;
        slow->next = nullptr;
        
        // 递归排序左右两部分
        ListNode *left = sortInList(head);
        ListNode *right = sortInList(mid);
        
        // 合并两个有序链表
        return merge(left, right);
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode *tail = &dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        
        if (l1) tail->next = l1;
        if (l2) tail->next = l2;
        
        return dummy.next;
    }
};

数字组合

题面

给定一个数字 $n$,可以选择若干个数字，使得他们的和为 $n$。
其中选择的数字只能为1,5,10,25。
请问有多少种选择方式。

补充说明：

• $1≤n≤10^5$
• 请注意选择方案 $\{1,5\}$ 等价于 $\{5,1\}$，他们只算一种方案。
• 由于答案过大所以你需要返回答案对 $10^9 + 7$ 取模之后的值。

示例：

输入：6
输出：2
说明：可以分解为六个1相加或者一个1和一个5。

思路与代码

动态规划：需要找到所有可能的组合方式，使得这些组合的和等于给定的数字 $n$。

定义一个DP数组，其中 dp[i] 表示和为 $i$ 的组合方式的数量。

初始化： dp[0] = 1，因为和为 $0$ 的组合方式只有一种，即什么都不选。

状态转移： 对于每个数字 $1, 5, 10, 25$，我们遍历从当前数字 $x$ 到给定数字 $n$ 的所有可能的和 $i$，更新 dp[i] 的值。

即 dp[i] += dp[i - x]，表示当前的组合方式数量等于不使用当前数字时的组合方式数量加上使用当前数字时的组合方式数量。

class Solution {
public:
    int countWays(int n) {
        const int mod = 1e9 + 7;

        int a[] = {1, 5, 10, 25};
        vector<int> dp(n + 1, 0);
        dp[0] = 1;

        for (int x : a) {
            for (int i = x; i <= n; ++i) {
                dp[i] = (dp[i] + dp[i - x]) % mod;
            }
        }
        
        return dp[n];
    }
};