1. 507. Perfect Number
显然小于2的都不满足（尤其是负数的情况），进一步，显然质数都不满足，所以小于4的数，直接return false。
然后依次暴力枚举判断到sqrt（n），注意n = t * t的时候，t只需要加一次。好像不写这个也不会出错，因为没有这样的数满足条件。我没验证，需要的验证一下。
class Solution {
public:
bool checkPerfectNumber(int num) {
if(num <= ) return ;
int res = ;
int d = floor(sqrt(num));
for (int i = ; i <= d; i++) {
if(i == num) break;
if(num % i == ) {
res += i;
if(i != num / i) res += num / i;
if(res > num) return ;
}
}
return res == num;
}
};
2. 537. Complex Number Multiplication
按照题意完成就可以。
class Solution {
public:
string complexNumberMultiply(string a, string b) {
int x = , y = , m = , n = ;
sscanf(a.c_str(), "%d+%di", &x, &y);
sscanf(b.c_str(), "%d+%di", &m, &n);
stringstream ss;
int t1 = x * m - y * n, t2 = x * n + y * m;
ss << t1 << "+" << t2 << "i";
return ss.str();
}
};
3. 545. Boundary of Binary Tree
左扫一遍，叶子扫一遍，右边扫一遍，注意边界条件。编码比较多，注意特判。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> res;
vector<int> ri;
bool f;
void workleft(TreeNode* root) {
if(!root) return;
res.push_back(root->val);
if(root->left)
workleft(root->left);
else
workleft(root->right);
}
void work(TreeNode* root) {
if(!root) return;
if(!root->left && !root->right) {
if(!f) f = ;
else res.push_back(root->val);
}
work(root->left);
work(root->right);
}
void workright(TreeNode* root) {
if(!root) return;
ri.push_back(root->val);
if(root->right)
workright(root->right);
else
workright(root->left);
}
vector<int> boundaryOfBinaryTree(TreeNode* root) {
res.clear();
if(!root) return res;
res.push_back(root->val);
workleft(root->left);
if(root->left)
f = ;
else
f = ;
work(root->left);
work(root->right);
ri.clear();
workright(root->right);
reverse(ri.begin(), ri.end());
//cout << res.size() << " " << ri.size() << endl;
for (int i = ; i < ri.size(); i++) {
res.push_back(ri[i]);
//cout << ri[i] << endl;
}
return res;
}
};
4. 546. Remove Boxes
不会做，没有想法。看完题目，感觉跟burst ballon挺像的，因为枚举先删除的话，左右2边的会合在一起，使得后续的处理边的麻烦，应该是需要最后考虑，怎么进行合并，使得2边的问题变得独立。
从discuss里面看的答案。好像先把数组处理成字符，个数的形式，不是很好处理，需要寻找一种好的枚举方法，对问题进行化简。
刚开始，观察，如果一个字符只出现一次，那么这个字符对结果的贡献就是1，也就是说可以直接删除它，删除后左右2边的部分进行合并，这里有个问题，这个单独字符删除的时间，是否会影响最后的结果，不太确定。
我的想法是，处理成数字，个数的形式，然后依次枚举删除的字符。每次调用的时候，先进行单个字符的处理，然后合并相邻的，再递归调用，结果是tle。完全是暴力的解法。
下面的解法是，每次处理末尾的字符，使得问题规模缩小，然后考虑末尾的字符，可能跟前面的字符进行合并，然后进行搜索，有些段可能多次计算，采用记忆化搜索。这个想法的关键是，找到一种搜索的办法，缩减问题规模，同时不遗漏可能的解。
int dp[][][];
int work(vector<int>& b, int l, int r, int k) {
if(l > r) return ;
int& res = dp[l][r][k];
if(res != ) return res;
while(l < r && b[r - ] == b[r]) {
k++;
r--;
}
res = work(b, l, r - , ) + (k + ) * (k + );
for (int i = l; i < r; i++) {
if(b[i] == b[r]) {
res = max(res, work(b, l, i, k + ) + work(b, i + , r - , ));
}
}
return res;
}
int removeBoxes(vector<int>& boxes) {
memset(dp, , sizeof dp);
int n = boxes.size();
return work(boxes, , n - , );
}