【每日刷題】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;

}