【每日刷题】Day52
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 2965. 找出缺失和重复的数字 - 力扣（LeetCode）
2. 350. 两个数组的交集 II - 力扣（LeetCode）
3. 2807. 在链表中插入最大公约数 - 力扣（LeetCode）
1. 2965. 找出缺失和重复的数字 - 力扣（LeetCode）
//思路：哈希表。维护一个长度为 (gridSize*(*gridColSize))的哈希表，将数组中的值作为键，键值+=1，键值等于2的键就是重复的数字，为0就是缺失的数字。
int* findMissingAndRepeatedValues(int** grid, int gridSize, int* gridColSize, int* returnSize)
{
int* ans = (int*)malloc(sizeof(int)*2);
int hash[10000] = {0};
for(int i = 0;i<gridSize;i++)
{
for(int j = 0;j<(*gridColSize);j++)
{
hash[grid[i][j]]+=1;
}
}
for(int i = 0;i<=gridSize*(*gridColSize);i++)
{
if(hash[i]==2)
{
ans[0] = i;
}
if(hash[i]==0)
{
ans[1] = i;
}
}
*returnSize = 2;
return ans;
}
2. 350. 两个数组的交集 II - 力扣（LeetCode）
//思路：哈希表。维护两个哈希表，分别存储nums1中元素出现的次数以及nums2中元素出现的次数。
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
int* ans = (int*)malloc(sizeof(int)*1000);
int count = 0;
int hash1[1001] = {0};
int hash2[1002] = {0};
int i = 0;
int j = 0;
while(i<nums1Size||j<nums2Size)
{
if(i<nums1Size)
{
hash1[nums1[i]]+=1;
i++;
}
if(j<nums2Size)
{
hash2[nums2[j]]+=1;
j++;
}
}
for(int i = 0;i<1001;i++)
{
if(hash1[i]!=0&&hash2[i]!=0&&(hash1[i]<=hash2[i]||hash1[i]>=hash2[i]))
{
int tmp = fmin(hash1[i],hash2[i]);
while(tmp)
{
ans[count++] = i;
tmp--;
}
}
}
*returnSize = count;
return ans;
}
3. 2807. 在链表中插入最大公约数 - 力扣（LeetCode）
//辗转相除法求最大公约数。
//辗转相除法：x = 100 ，y = 18
① int tmp = x%y (10)
② x = y (18)
③ y = tmp (10)
//重复上述过程，直到x%y==0，此时y就是最大公约数
typedef struct ListNode LN;
struct ListNode* insertGreatestCommonDivisors(struct ListNode* head)
{
LN* phead = head;
LN* pnext = phead->next;
while(pnext)
{
int x = phead->val;//100
int y = pnext->val;//18
while(x%y)
{
int tmp = x%y;//8
x = y;//x = 10
y = tmp;//y = 8
}
LN* newnode = (LN*)malloc(sizeof(LN));
newnode->val = y;
newnode->next = pnext;
phead->next = newnode;
phead = pnext;
pnext = phead->next;
}
return head;
}
