因昨天晚上有事，故本次更新推迟了一天。
Leetcode 543：二叉树的直径
题目描述
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例
给定二叉树
| 1 2 3 4 5 | 1 / \ 2 3 / \ 4 5 |
返回3，它的长度路径[4,2,1,3]或者[5,2,1,3]
解题思路
最长长度一定是最长左子树的长度+最长右子树的长度+1，按照这个思路来走即可。
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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)有一点高。
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | int subarraySum(vector& nums, int k) { if (nums.empty()) return -1; int count = 0; for (int i = 0; i < nums.size(); i++) { int sum = 0; for (int j = i;j < nums.size(); j++) { sum += nums[j]; if (sum == k) count++; } } return count; } |
代码性能
复杂度：O(n2)
执行用时：752ms
内存消耗：9.7MB
