1.LeetCode:914. 卡牌分组
这道题还是需要一些数论意识的，要将所有的卡牌分成若干组，每组个数相同，且卡牌相同，我们首先会很自然的想到统计每个卡牌出现的次数，接下来要把这些相同的卡牌分成个数相同的若干组就需要计算这些出现次数的最大公因数了
比如示例1：[1,2,3,4,4,3,2,1]，1，2，3，4均出现了两次最大公因数为2可以分组，
再例如[1,2,3,4,4,3,2,1,1,1,5,5],1出现了四次，2，3，4，5出现了两次，最大公因数为2可以分组，而[1,1,1,2,2,2,3,3] ，1，2出现了三次，3出现了两次，最大公因数为1不能分组。
所以我们就需要求出所有卡牌出现次数的最大公因数，并判断是否大于1.
class Solution {
int (int a,int b){
return b==0?a:(b,a%b);
}
public:
bool hasGroupsSizeX(vector<int>& deck) {
int hash[10010];
memset(hash,0,sizeof(hash));
for(auto i:deck){
hash[i]++;
}
int p=-1;
for(int i=0;i<deck.size();++i){
if(hash[i]){
if(p==-1) p=hash[i];
else {
p=(p,hash[i]);
}
}
}
return p>1;
}
};
2.LeetCode:970. 强整数
给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。
如果某一整数可以表示为 x^i + y^j ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。
你可以按 任何顺序 返回答案。在你的回答中，每个值 最多 出现一次。
示例 1：
输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
示例 2：
输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]
提示：
1 <= x, y <= 100
0 <= bound <= 1e6
这道题就是吧x,y的任意次方进行组合，组合出不超过bound的所有数都是我们的答案，那么这里就简单了，先预处理出x,y所有不超过bound的次方，然后枚举即可。
class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
vector<int> px,py;
int prev=1;
for(int i=1;prev<=bound;++i){
px.push_back(prev);
prev*=x;
if(x==1) break;
}
prev=1;
for(int i=1;prev<=bound;++i){
py.push_back(prev);
prev*=y;
if(y==1) break;
}
int hash[1000010];
memset(hash,0,sizeof(hash));
for(int i=0;i<px.size();++i){
for(int j=0;j<py.size();++j){
int val=px[i]+py[j];
if(val<=bound) hash[val]=1;
}
}
vector<int> ans;
for(int i=1;i<=1000000;++i){
if(hash[i]) ans.push_back(i);
}
return ans;
}
};
3.LeetCode:1497. 检查数组对是否可以被 k 整除
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 True ；否则，返回 False
示例 1：
输入：arr = [1,2,3,4,5,10,6,7,8,9], k = 5
输出：true
示例 2：
输入：arr = [1,2,3,4,5,6], k = 7
输出：true
示例 3：
输入：arr = [1,2,3,4,5,6], k = 10
输出：false
提示：
arr.length == n
1 <= n <= 1e5
n 为偶数
-1e9 <= arr[i] <= 1e9
1 <= k <= 1e5
本题先把arr中的元素按模k同余归到一个等价类里（比如1,6 ,k=5,(1+4)%5=(6+4)%5）,然后在哈希表中查找余数相加为k的元素个数是否相等，不相等就返回false最后返回true，特殊的如果余数为0的话他们内部需要两两组合，这时候需要特殊判断这个等价类的个数是否是偶数。
class Solution {
public:
bool canArrange(vector<int>& arr, int k) {
int hash[100010];
memset(hash,0,sizeof(hash));
for(int i=0;i<arr.size();++i){
++hash[(arr[i]%k+k)%k];
}
if(hash[0]&1){
return false;
}
for(int i=1;i<k;++i){
if(hash[i]!=hash[k-i]){
return false;
}
}
return true;
}
};
4.LeetCode:面试题 17.05. 字母与数字
给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
示例 1:
输入: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”,“H”,“I”,“J”,“K”,“L”,“M”]
输出: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”]
示例 2:
输入: [“A”,“A”]
输出: []
提示：
array.length <= 100000
经典前缀和同源的题目了，这道题就利用前缀和数组统计array中数字和字母出现的次数，不过这里我们并不直接统计出现的次数而是将字母的权重看成-1，数字的权重看成1。
那么这样做的好处是，当两个元素i , j ( i < j )的前缀和相等的时候就说明 j的数字比字母（或者字母比数字）出现的次数多（或少）了相同的个数，而把 [0,j]这段元素去掉，剩下的字母和数字出现的次数正好相等，也就是前缀和为0。比如A1B, A1B2A
统计完前缀和后，我们利用一个哈希表来储存某个前缀和首次在数组中出现的下标，特殊的前缀和为0的时候我们设置为-1（为了和后面的做标计算统一）。首先遍历原数组，查找该位置的前缀和在数组中首次出现的位置，那么i-map[prev[i+1]]就是字母和数组出现次数相同的长度，如果大于之前维护的最大长度就更新最大长度和答案数组的区间[l,r]。
这里由于我们的map记录的是下标所以长度len和下标的加减一操作就需要根据自己的代码进行调整了。首先r=i是毫无疑问的，而l的计算就容易出错了。我们在找到某个前缀第一次在数组中出现的位置的时候需要吧改段字符串删除，比如上述例子的A1B,A1B2A,就需要吧A1B2A的A1B删去，也就是 i - map [ prev [ i + 1 ] ] ,(我们习惯的i-r+1是计算从一个下标到另一个下标的距离，这里是计算后一个字符串比前一个字符串多出的长度)，那么这样计算的情况下 就有 l = map[prev[i+1]]+1了。之前特意设置的map[0]=-1也是为了当前缀和为0的时候能有一个位置来做形式上的删除。
class Solution{
public:
vector<string> findLongestSubarray(vector<string>& array) {
int prev[100010];
unordered_map<int,int> map;
prev[0]=0;
for(int i=0;i<array.size();++i){
prev[i+1]=array[i][0]>='0'&&array[i][0]<='9'?prev[i]+1:prev[i]-1;
}
map[0]=-1;
int l=0,r=-1,max=-0x3f3f3f3f;
for(int i=0;i<array.size();++i){
if(map.find(prev[i+1])!=map.end()){
int len=i-map[prev[i+1]];
if(len>max){
max=len;
l=map[prev[i+1]]+1;
r=i;
}
}else {
map[prev[i+1]]=i;
}
}
vector<string> ans;
for(int i=l;i<=r;++i){
ans.push_back(array[i]);
}
return ans;
}
};
