层序遍历BFS
思路：
使用队列进行层次遍历，在遍历的过程中进行判断，一旦不满足奇偶树的条件，就可立即返回false,如果满足，继续层次遍历，直至整棵树层次遍历完成。
class Solution { public: const int N=1e6+10; bool isEvenOddTree(TreeNode* root) { queue<TreeNode*> qu; qu.push(root); int level = 0; while (!qu.empty()) { int size = qu.size(); int prev = level % 2 == 0 ? -N : N; //如果是奇数层，则需满足递减，取前驱为最大值,反之 for (int i = 0; i < size; i++) { TreeNode * node = qu.front(); //取出元素 qu.pop(); int value = node->val; if (level % 2 == value % 2) return false; //偶层奇值，奇层偶值 if ((level % 2 == 0 && value <= prev) || (level % 2 == 1 && value >= prev)) return false; //与前驱比较，偶层不满足递增，或者奇层不满递减 prev = value; //更新前驱 if (node->left != nullptr) qu.push(node->left); if (node->right != nullptr) qu.push(node->right); } level++; } return true; } };
sort的自定义排序
思路：
方法一：自定义排序
一种容易想到的方法是使用排序并自定义比较函数。
由于数组 arr2 规定了比较顺序，因此我们可以使用哈希表对该顺序进行映射：即对于数组 arr2中的第 i 个元素，我们将 (arr2[i],i) 这一键值对放入哈希表 rank 中，就可以很方便地对数组 arr1 中的元素进行比较。
比较函数的写法有很多种，例如我们可以使用最基础的比较方法，对于元素 x 和 y：
如果 x 和 y 都出现在哈希表中，那么比较它们对应的值 rank[x] 和 rank[y]；
如果 x 和 y 都没有出现在哈希表中，那么比较它们本身；
对于剩余的情况，出现在哈希表中的那个元素较小。
cmp中true与false的分析：
cmp默认为x<y，返回true则认为x<y且排升序，返回false则认为y<x且排升序
class Solution { public: vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) { unordered_map<int, int> rank; //对arr2的值标注顺序 for (int i = 0; i < arr2.size(); ++i) { rank[arr2[i]] = i; } //sort的自定义排序 sort(arr1.begin(), arr1.end(), [&](int x, int y) { if (rank.count(x)) { //如果x，y都存在则按照标注的顺序排 return rank.count(y) ? rank[x] < rank[y] : true; } else { //如果x，y都不在表中则比较本身 return rank.count(y) ? false : x < y; } //对于剩余情况，出现在表中的元素较小 } ); return arr1; } };
转换为OI的细节：rank在全局域中重名，需改为rank1
#include <iostream> #include <string> #include<unordered_map> #include<algorithm> #include<vector> using namespace std; bool cmp(int x, int y); unordered_map<int, int> rank1; int main() { vector<int> arr1= { 2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19 }; vector<int> arr2 = { 2, 1, 4, 3, 9, 6 }; for (int i = 0; i < arr2.size(); i++) rank1[arr2[i]] = i; sort(arr1.begin(), arr1.end(), cmp); for (auto ch : arr1) cout << ch << " "; return 0; } bool cmp(int x, int y) { if (rank1.count(x)) { //如果x，y都存在则按照标注的顺序排 return rank1.count(y) ? rank1[x] < rank1[y] : true; } else { //如果x，y都不在表中则比较本身 return rank1.count(y) ? false : x < y; } //对于剩余情况，出现在表中的元素较小 return true; }
方法二：
1、记录 arr1 数字出现的次数
2、找到 arr2 和 arr1 都出现的数字
3、找 arr1 有， arr2 没有的。
class Solution { public: vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) { int hash[1010]={0}; for(int i=0;i<arr1.size();i++) hash[arr1[i]]++; int idx=0; for(int i=0;i<arr2.size();i++) { while(hash[arr2[i]]>0) { arr1[idx++]=arr2[i]; hash[arr2[i]]--; } } //找 arr1 有， arr2 没有的 for(int i=0;i<1001;i++) { while(hash[i]>0) { arr1[idx++]=i; hash[i]--; } } return arr1; } };
string数组的使用
思路：
利用arr存单词顺序，tmp更新单词
class Solution { public: string sortSentence(string s) { vector<string> arr(9); //存放单词 string tmp=""; //当前单词 int n=0; //单词数量 for(auto c:s) { if(c>='0'&&c<='9') { arr[c-'0']=tmp; tmp=""; n++; } else if(c!=' ') tmp+=c; } string res=arr[1]; for(int i=2;i<=n;i++) res+=" "+arr[i]; return res; } };
双指针枚举
思路：
可以删除元素代表着可以只留下你想要的元素，所以只需要在数组中找出等于 x 或 x+1 的元素个数，就可以得到以 x 为最小值的和谐子序列的长度
class Solution { public: int findLHS(vector<int>& nums) { sort(nums.begin(),nums.end()); int begin=0; int res=0; for(int end=0;end<nums.size();end++) { while(nums[end]-nums[begin]>1) begin++; if(nums[end]-nums[begin]==1) res=max(res,end-begin+1); } return res; } };
方法二：哈希表
我们首先遍历一遍数组，得到哈希映射。随后遍历哈希映射，设当前遍历到的键值对为 (x,value)，那么我们就查询 x+1 在哈希映射中对应的统计次数，就得到了 x 和 x+1 出现的次数，和谐子序列的长度等于 x 和 x+1 出现的次数之和
class Solution { public: int findLHS(vector<int>& nums) { unordered_map<int,int> ump; int res=0; for(int n:nums) ump[n]++; for(auto [key,val]:ump) if(ump.count(key+1)) res=max(res,val+ump[key+1]); return res; } };
