数字问题-LeetCode 507、508、513、515、516、520、518（DP、BFS）
数字问题-LeetCode 507、508、513、515、516、520、518（DP、BFS）
作者：TeddyZhang，公众号：算法工程师之路
数字问题：
LeetCode # 507 508 509 513 515 516 520 518
1
编程题
【LeetCode #507】完美数
对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。
给定一个 整数 n， 如果他是完美数，返回 True，否则返回 False
示例： 输入: 28 输出: True 解释: 28 = 1 + 2 + 4 + 7 + 14
class Solution {
public:
bool checkPerfectNumber(int num) {
if (num == ) return false;
int res = num, i = ;
while(i <= res / ) {
if (res % i == ) num -= i;
i++;
}
return num == ;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/perfect-number
【LeetCode #508】出现次数最多的子树元素和
给出二叉树的根，找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的元素（不限顺序）。
解题思路：获取的是每棵子树的元素和，并使用哈希表来进行存储次数。然后遍历，得到出现次数最多的元素和。
class Solution {
public:
unordered_map<int, int> hashmap;
int maxSum = ;
vector<int> findFrequentTreeSum(TreeNode* root) {
vector<int> res;
treeSum(root);
for(auto it: hashmap) {
if (it.second == maxSum) res.push_back(it.first);
}
return res;
}
private:
int treeSum(TreeNode* root) {
if (root == nullptr) return ;
int sum = root->val;
sum += treeSum(root->left);
sum += treeSum(root->right);
hashmap[sum]++; // 统计每个和的个数
maxSum = max(maxSum, hashmap[sum]);
return sum;
}
};
那么如果需要计算的是二叉树每个路径的元素和，那么如何修改这个算法呢？注意上面的是每棵子树的元素和！
class Solution {
public:
vector<int> res;
vector<int> findFrequentTreeSum(TreeNode* root) {
treeSum(root, );
return res;
}
private:
void treeSum(TreeNode* root, int sum) {
sum += root->val;
if (root->left == nullptr && root->right == nullptr) {
res.push_back(sum);
return;
}
if (root->left != nullptr) treeSum(root->left, sum);
if (root->right != nullptr) treeSum(root->right, sum);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/most-frequent-subtree-sum
【LeetCode #509】斐波那契数
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。
示例 1： 输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
class Solution {
public:
int fib(int N) {
int a = , b = , c = ;
if (N == ) return ;
if (N == ) return ;
N--;
while(N--) {
c = a + b;
a = b;
b = c;
}
return c;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fibonacci-number
【LeetCode #513】找数左下角的值
给定一个二叉树，在树的最后一行找到最左边的值。
解题思路：从每一层从右向左入队列，最左边的节点一定是最后一个访问的节点。
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
que.push(root);
int res = ;
while(!que.empty()) {
TreeNode* tmp = que.front();
res = tmp->val;
que.pop();
if (tmp->right) que.push(tmp->right);
if (tmp->left) que.push(tmp->left);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value/
【LeetCode #515】在每个数行中找最大值
您需要在二叉树的每一行中找到最大的值。
解题思路：层次遍历即可
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> res;
if (root == nullptr) return res;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
int maxVal = INT_MIN;
while(size--) {
TreeNode* tmp = que.front();
maxVal = max(maxVal, tmp->val);
que.pop();
if (tmp->left) que.push(tmp->left);
if (tmp->right) que.push(tmp->right);
}
res.push_back(maxVal);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
【LeetCode #516】最长回文子序列
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1: 输入: "bbbab" 输出: 4
public:
int longestPalindromeSubseq(string s) {
if (s.empty()) return ;
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, ));
for(int i = n-1; i >= ; i--) {
dp[i][i] = ;
for(int j = i+; j < n; j++) {
if (s[i] == s[j])
dp[i][j] = dp[i+][j-1] + ;
else
dp[i][j] = max(dp[i+][j], dp[i][j-1]);
}
}
return dp[][n-1];
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence/
【LeetCode #520】检测大写字母
给定一个单词，你需要判断单词的大写使用是否正确。 我们定义，在以下情况时，单词的大写用法是正确的：
全部字母都是大写，比如"USA"。 单词中所有字母都不是大写，比如"leetcode"。 如果单词不只含有一个字母，只有首字母大写， 比如 "Google"。 否则，我们定义这个单词没有正确使用大写字母。
示例 1: 输入: "USA" 输出: True
class Solution {
public:
bool detectCapitalUse(string word) {
int n = word.size();
if (n == ) return true;
bool res;
char ch = word[];
int i = ;
if (ch >= 'a' && ch <= 'z') {
while(word[i] >= 'a' && word[i] <= 'z' && i < n) i++;
if (i == n) res = true;
else res = false;
} else {
if (word[] >= 'a' && word[] <= 'z') {
while(word[i] >= 'a' && word[i] <= 'z' && i < n) i++;
if (i == n) res = true;
else res = false;
}
if (word[] >= 'A' && word[] <= 'Z') {
while(word[i] >= 'A' && word[i] <= 'Z' && i < n) i++;
if (i == n) res = true;
else res = false;
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/detect-capital
【LeetCode #518】零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+);
dp[] = ;
for(auto coin: coins) {
for(int j = ; j <= amount; j++) {
if (j >= coin) {
dp[j] = dp[j] + dp[j-coin];
}
}
}
return dp[amount];
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/coin-change-2