今天做了三题，对于stl的运用还不是很熟练：
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
我的做法：先用数组统计，然后想用类似前缀和的方法，结果因为数据量小还是用了暴力：
class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { int cnt[103]; memset(cnt,0,sizeof cnt); for(auto x:nums) cnt[x]++; vector<int> res; for(auto x:nums){ int sum = 0; for(int i = 0; i < x; i++) sum += cnt[i]; res.push_back(sum); } return res; } };
前缀和做法：
class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { int cnt[103]; memset(cnt,0,sizeof cnt); for(auto x:nums) cnt[x]++; vector<int> res; for(int i = 1; i < 101; i++) cnt[i] += cnt[i-1]; for(auto x:nums){ if(x != 0) res.push_back(cnt[x-1]); else res.push_back(0); } return res; } };
直接暴力：
class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { vector <int> ret; for (int i = 0; i < nums.size(); i++) { int cur = nums[i]; int s = 0; for (int j = 0; j < nums.size(); j++) { s += (nums[j] < nums[i]); //小技巧 } ret.push_back(s); } return ret; } };
现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。
排名规则如下：
参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。
给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。
请你返回能表示按排名系统 排序后 的所有团队排名的字符串。
考察自定义排序：
我的做法：用map统计字符的各个排名，然后把map复制到vector进行排序：
class Solution { public: string rankTeams(vector<string>& votes) { map<char,vector<int>> mp; for(auto v:votes){ for(int i = 0; i < v.size();i++){ mp[v[i]].resize(v.size());//map中的vector不懂怎么初始化 mp[v[i]][i]++; } } vector<pair<char,vector<int> >> s; for(auto m:mp){ s.push_back(m); } sort(s.begin(),s.end(),[](pair<char,vector<int>> a,pair<char,vector<int>> b){ return a.second > b.second || a.second == b.second && a.first < b.first; }); string res; for(auto x:s){ res += x.first; } return res; } };
参考解答然后对代码进行了优化：
class Solution { public: string rankTeams(vector<string>& votes) { map<char,vector<int>> mp; for(auto v:votes){ for(int i = 0; i < v.size();i++){ mp[v[i]].resize(v.size()); mp[v[i]][i]++; } } string res = votes[0]; sort(res.begin(),res.end(),[&](char a, char b){ return mp[a]> mp[b] || mp[a] == mp[b] && a < b; }); return res; } };
给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
我的做法：递归，WA了两次，终于知道要区分是不是链表的首节点了；
然后用map进行优化也是不行的：
classSolution {public:
map<pair<TreeNode*,ListNode*>,bool> mp;
ListNode* h;
boolisSubPath(ListNode* head, TreeNode* root){
h = head;
return issub(head,root);
}
boolissub(ListNode* p, TreeNode* root){
if(!p) returntrue;
if(!root) returnfalse;
//if(mp.count({root,head})) return mp[{root,head}];bool res = false;
if(root->val == p->val)
res = issub(p->next,root->left) || issub(p->next,root->right);
if( p == h)
res = res || issub(p,root->left) || issub(p,root->right);
//mp[{root,head}] = res;return res;
}
};
给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/linked-list-in-binary-tree著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
原文：https://www.cnblogs.com/Aliencxl/p/12391521.html