leetcode 492-543 easy
2024-09-06 13:05:46
492. Construct the Rectangle
Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1].
But according to requirement 2, [1,4] is illegal; according to requirement 3, [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.
//[L,W] L要大于W,所以以W为基础,设W为一半迭代下去
//1.Because question requires L, D as close as possible, I start the finding from the middle point which is sqrt(area).
//2.when the Area divide Width have remainder , it should be the solution vector<int> constructRectangle(int area) {
for(int mid = sqrt(area); mid>; mid--)
if (!(area%mid))
return {area/mid, mid};
}
501. Find Mode in Binary Search Tree
BST众数
思路:由小到大inorder,O(n) time and O(1) space by inorder traversal
class Solution {
public:
int maxFreq = , currFreq = , precursor = INT_MIN;
vector<int> res; vector<int> findMode(TreeNode *root)
{
inorderTraversal(root);
return res;
} void inorderTraversal(TreeNode *root)
{
if (root == NULL) return; // Stop condition
inorderTraversal(root->left); // Traverse left subtree
if (precursor == root->val) currFreq++;
else currFreq = ;
if (currFreq > maxFreq)
{// Current node value has higher frequency than any previous visited
res.clear();
maxFreq = currFreq;
res.push_back(root->val);
}
else if (currFreq == maxFreq)
{// Current node value has a frequency equal to the highest of previous visited
res.push_back(root->val);
}
precursor = root->val; // Update the precursor
inorderTraversal(root->right); // Traverse right subtree
}
};
520. Detect Capital
- All letters in this word are capitals, like "USA".
- All letters in this word are not capitals, like "leetcode".
- Only the first letter in this word is capital if it has more than one letter, like "Google".
class Solution(object):
def detectCapitalUse(self, word):
c =
for i in word: //统计大字母
if i == i.upper():
c +=
return c == len(word) or (c == and word[] == word[].upper()) or c == ##三种情况,随便一种都行,全部为大/只有头字母为大/全部为小
530. Minimum Absolute Difference in BST
小到大树,从左下角开始递归,每次算当前节点的值减去前一个节点的值,根据该值来更新min
void inorderTraverse(TreeNode* root, int& val, int& min_dif) {
if (root->left != NULL) inorderTraverse(root->left, val, min_dif);
if (val >= ) min_dif = min(min_dif, root->val - val);
val = root->val;
if (root->right != NULL) inorderTraverse(root->right, val, min_dif);
}
int getMinimumDifference(TreeNode* root) {
auto min_dif = INT_MAX, val = -;
inorderTraverse(root, val, min_dif);
return min_dif;
}
538. Convert BST to Greater Tree
右边开始dfs,利用二叉树的右边比左边大的性质,递归加上右边的值
class Solution {
private:
int cur_sum = ;
public:
void travel(TreeNode* root){
if (!root) return;
if (root->right) travel(root->right); root->val = (cur_sum += root->val);
if (root->left) travel(root->left);
}
TreeNode* convertBST(TreeNode* root) {
travel(root);
return root;
}
};
543. Diameter of Binary Tree
找最长的路径,不一定包含头节点,可以是从左下到右下
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if(root == nullptr) return ;
int res = depth(root->left) + depth(root->right);
return max(res, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right))); //左右两个红框
} int depth(TreeNode* root){
if(root == nullptr) return ;
return + max(depth(root->left), depth(root->right)); //黑框
}
};
最新文章
- 利用QJSON将FDQuery转成JSON串
- business knowledge
- Unity浅析
- Unity3D 事件
- JAVA手记 JAVA入门(安装+Dos下运行)
- AT&;T ASSEMBLY FOR LINUX AND MAC (SYS_FORK)
- &;10 基本数据结构——指针和对象的实现,有根树的表示
- diff 文件比较
- 杭电2034——人见人爱A-B
- AS3 Signals
- CAS认证(2):认证过程
- 手动加入PE文件数字签名信息及格式具体解释图之下(历史代码,贴出学习)
- Dede推荐文章与热点文章不显示?
- web存储之webstorage
- HAProxy+Nginx 负载均衡
- 【Android Studio安装部署系列】二十九、Android Studio安装本地插件(以国际化方法插件AndroidLocalizationer为例)
- [ASP.NET] 如何利用Javascript分割檔案上傳至後端合併
- SQL 经典应用
- Dart server side call dll
- DBA角色职责