2019-10-18 378 views 评论

Leetcode题目解析（191017）

因昨天晚上有事，故本次更新推迟了一天。

Leetcode 543：二叉树的直径

题目描述

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例

给定二叉树

/ \

2 3

/ \

4 5

返回3，它的长度路径[4,2,1,3]或者[5,2,1,3]

解题思路

最长长度一定是最长左子树的长度+最长右子树的长度+1，按照这个思路来走即可。

代码实现

int ans;
 int getDepth(TreeNode* root) {
     if (root == nullptr)
         return 0;
     int ll = getDepth(root->left);
     int rr = getDepth(root->right);
     ans = max(ans, ll+rr+1);
     return max(ll, rr) + 1;
 }
 int diameterOfBinaryTree(TreeNode* root) {
     ans = 1;
     getDepth(root);
     return ans - 1;
 }

int ans;

int getDepth(TreeNode* root) {

if (root == nullptr)

return 0;

int ll = getDepth(root->left);

int rr = getDepth(root->right);

ans = max(ans, ll+rr+1);

return max(ll, rr) + 1;

}

int diameterOfBinaryTree(TreeNode* root) {

ans = 1;

getDepth(root);

return ans - 1;

}

代码性能

运行耗时：16ms
内存消耗：19.7MB

Leetcode 560：和为k的子数组

题目描述

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例

输入:nums = [1,1,1], k = 2。输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

解题思路

我感觉没啥需要写的，很简单就看懂。复杂度O(n2)有一点高。

代码实现

int subarraySum(vector&amp; nums, int k) {
     if (nums.empty())
         return -1;
int count = 0;
     for (int i = 0; i &lt; nums.size(); i++)
     {
         int sum = 0;
         for (int j = i;j &lt; nums.size(); j++)
         {
             sum += nums[j];
             if (sum == k)
                 count++;
         }
     }
     return count;
 }