LeetCode Weekly Contest 18A
500. Keyboard Row
- User Accepted: 471
- User Tried: 483
- Total Accepted: 485
- Total Submissions: 714
- Difficulty: Easy
Given a List of words, return the words that can be typed using letters of alphabet on only one row's of American keyboard like the image below.
Example 1:
Input: ["Hello", "Alaska", "Dad", "Peace"] Output: ["Alaska", "Dad"]
Note:
- You may use one character in the keyboard more than once.
- You may assume the input string will only contain letters of alphabet.
签到题， 但是，看了有些人 熟悉STL各种工具的，代码就几行，还需要不断努力啊
class Solution {
public:
void init(vector<int>& hash){
hash['q'-'a']=1; hash['w'-'a']=1; hash['e'-'a']=1; hash['r'-'a']=1; hash['t'-'a']=1;
hash['y'-'a']=1; hash['u'-'a']=1; hash['i'-'a']=1; hash['o'-'a']=1; hash['p'-'a']=1;
hash['a'-'a']=2; hash['s'-'a']=2; hash['d'-'a']=2; hash['f'-'a']=2; hash['g'-'a']=2;
hash['h'-'a']=2; hash['j'-'a']=2; hash['k'-'a']=2; hash['l'-'a']=2;
hash['z'-'a']=3; hash['x'-'a']=3; hash['c'-'a']=3; hash['v'-'a']=3; hash['b'-'a']=3;
hash['n'-'a']=3; hash['m'-'a']=3;
}
vector<string> findWords(vector<string>& words) {
vector<string> ans;
vector<int> hash(26, 0);
init(hash);
int val, t, flag;
for(int i=0; i<words.size(); ++i){
flag = 0;
if(words[i][0] >='A' && words[i][0]<='Z'){
val = hash[ words[i][0] - 'A' ];
}else if(words[i][0] >= 'a' && words[i][0]<='z'){
val = hash[ words[i][0] - 'a' ];
}
for(int j=1; j<words[i].size(); ++j){
if(words[i][j] >='A' && words[i][j]<='Z'){
t = hash[ words[i][j] - 'A' ];
}else if(words[i][j] >= 'a' && words[i][j]<='z'){
t = hash[ words[i][j] - 'a' ];
}
if(t != val){
flag = 1;
break;
}
}
if(flag == 0){
ans.push_back(words[i]);
}
}
return ans;
}
};
508. Most Frequent Subtree Sum
- User Accepted: 394
- User Tried: 413
- Total Accepted: 401
- Total Submissions: 737
- Difficulty: Medium
Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.
Examples 1
Input:
5 / 2 -3return [2, -3, 4], since all the values happen only once, return all of them in any order.
Examples 2
Input:
5 / 2 -5return [2], since 2 happens twice, however -5 only occur once.
Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.
在本题目中，做了一个尝试，就是将参数写入fun 的形参中参与 recursion，这样的速度慢多了， recursion的形参越少越好。
/**
* 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:
int findsum(map<int, int>& mp, TreeNode* root){
/*
if(root->left == NULL && root->right == NULL){
if(mp.find(root->val) == mp.end()){
mp[ root->val ] = 1;
}else{
mp[ root->val ] += 1;
}
return root->val;
}
*/
int s = root->val;
if(root->right){
s += findsum(mp, root->right);
}
if(root->left){
s += findsum(mp, root->left);
}
if(mp.find( s ) == mp.end()){
mp[s] = 1;
}else{
mp[s] += 1;
}
return s;
}
vector<int> findFrequentTreeSum(TreeNode* root) {
vector<int> ans;
if(root == NULL){
return ans;
}
map<int, int> mp;
int max_val = 0;
findsum(mp, root);
for(auto i=mp.begin(); i!=mp.end(); ++i){
if(max_val < i->second ){
max_val = i->second;
}
}
for(auto i=mp.begin(); i!=mp.end(); ++i){
if(i->second == max_val){
ans.push_back( i->first );
}
}
return ans;
}
};
502. IPO
- User Accepted: 136
- User Tried: 300
- Total Accepted: 140
- Total Submissions: 951
- Difficulty: Hard
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.
You are given several projects. For each project i, it has a pure profit Pi and a minimum capital of Ci is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.
To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.
Example 1:
Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
Note:
- You may assume all numbers in the input are non-negative integers.
- The length of Profits array and Capital array will not exceed 50,000.
- The answer is guaranteed to fit in a 32-bit signed integer.
对STL还是不够敏感，看了discuss才有思路。
方法是： 直接用 priority_queue 和 pair 进行模拟
class Solution {
public:
int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
vector<pair<int, int>> vt;
for(int i=0; i<Capital.size(); ++i){
vt.push_back( make_pair(Capital[i], Profits[i]) );
}
sort(vt.begin(), vt.end());
priority_queue<int> q;
int i = 0;
for(; i<vt.size(); ++i){
if(vt[i].first <= W){
q.push( vt[i].second );
}else{
break;
}
}
int ans = W;
for(int j=0; j<k; ++j){
if(!q.empty()){
ans += q.top(); q.pop();
}
for(; i<vt.size(); ++i){
if(vt[i].first <= ans){
q.push(vt[i].second);
}else{
break;
}
}
}
return ans;
}
};