腾讯后端面试算法题（九）

本文主要是介绍腾讯后端面试算法题（九），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、平衡二叉树

链接:https://leetcode-cn.com/problems/balanced-binary-tree/
题目描述：

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

完整代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        return deepLengthDfs(root) >= 0;
    }

    int deepLengthDfs(TreeNode* root)
    {
        if(!root) return 0;
        int ld = deepLengthDfs(root->left);
        int rd = deepLengthDfs(root->right);
        if(ld >= 0 && rd >= 0 && abs(ld - rd) <= 1)
        {
            return max(ld , rd) + 1;
        }
        return -1;
    }
};

二、 两数相加

链接:https://leetcode-cn.com/problems/add-two-numbers/
题目描述：

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

完整代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* r1, ListNode* r2) {
        if(!r1) return r2;
        if(!r2) return r1;
        ListNode* root = new ListNode(0);
        ListNode* p = root;
        int ans = 0;
        while(r1 || r2 || ans)
        {
            int v1 = r1 ? r1->val : 0;
            int v2 = r2 ? r2->val : 0;
            int sum = v1 + v2 + ans;
            ListNode* t = new ListNode(sum%10);
            p->next = t;
            p = p->next;
            ans = sum/10;
            if(r1) r1 = r1->next;
            if(r2) r2 = r2->next;
        }
        return root->next;
    }
};

三、爬楼梯

链接：https://leetcode-cn.com/problems/climbing-stairs/
题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
4. 1 阶 + 1 阶 + 1 阶
5. 1 阶 + 2 阶
6. 2 阶 + 1 阶

完整代码：
解法：动态规划

class Solution {
public:
    int climbStairs(int n) {
        if(n == 1) return n;
        int dp[3] = {0};
        dp[0] = 1;
        dp[1] = 2;
        for(int i=2;i<n;i++)
        {
            dp[2] = dp[1];
            dp[1] = dp[0] + dp[1];
            dp[0] = dp[2];
        }
        return dp[1];
    }
};

这篇关于腾讯后端面试算法题（九）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！