【每日刷题】Day25
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 238. 除自身以外数组的乘积 - 力扣（LeetCode）
2. 82. 删除排序链表中的重复元素 II - 力扣（LeetCode）
3. 445. 两数相加 II - 力扣（LeetCode）
1. 238. 除自身以外数组的乘积 - 力扣（LeetCode）
//思路：使用两个数组，分别存储左边元素的乘积和、右边元素的乘积和，在使用一个数组，存储这两个数组的每个位置元素的和。
int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
int * ans = (int*)malloc(sizeof(int)*numsSize);
int left[numsSize];//用于存储左边元素乘积和
int right[numsSize];//用于存储右边元素乘积和
int i = 0;
left[0] = 1;
for(i = 1;i<numsSize;i++)//计算原数组各个位置左边元素乘积
{
left[i] = left[i-1]*nums[i-1];
}
right[numsSize-1] = 1;
for(i = numsSize-2;i>=0;i--)//计算原数组各个位置右边元素乘积
{
right[i] = right[i+1]*nums[i+1];
}
for(i = 0;i<numsSize;i++)
{
ans[i] = left[i]*right[i];//相加则是原数组各个位置除自身以外的元素乘积和
}
*returnSize = numsSize;
return ans;
}
2. 82. 删除排序链表中的重复元素 II - 力扣（LeetCode）
//思路：哈希。这题由于链表中的元素存在小于0的，因此使用哈希时需要将小于0的数处理为＞0的数。因为数据范围为-100~100，因此，可以将＜0的数+201，将数据范围改为0~200，这样就可以使用哈希来解决。
typedef struct ListNode LN;
struct ListNode* deleteDuplicates(struct ListNode* head)
{
if(head==NULL)
{
return NULL;
}
if(head->next==NULL)
{
return head;
}
int hash[1000] = {0};
LN* pmove = head;
while(pmove)
{
if(pmove->val<0)
{
pmove->val+=201;//将链表中小于0的数处理为＞100的数
}
hash[pmove->val]+=1;//计算数据出现的次数
pmove = pmove->next;
}
LN* Sentry = (LN*)malloc(sizeof(LN));//新链表用于接收只出现一次的数
Sentry->next = NULL;
LN* newhead = Sentry;
if(head->val>100)//这里需要考虑链表中是否存在小于0的数，如果存在，则新链表接收数据的顺序需要相应改变
{
for(int i = 101;i<=200;i++)//先将＜0的数存入新链表
{
if(hash[i]==1)//==1说明数据只出现了一次，存入新链表
{
LN* newnode = (LN*)malloc(sizeof(LN));
newnode->next = NULL;
newnode->val = i-201;
newhead->next = newnode;
newhead = newhead->next;
}
}
for(int i = 0;i<=100;i++)//再存入＞0的数
{
if(hash[i]==1)
{
LN* newnode = (LN*)malloc(sizeof(LN));
newnode->next = NULL;
newnode->val = i;
newhead->next = newnode;
newhead = newhead->next;
}
}
}
else
{
for(int i = 0;i<=100;i++)//链表中不存在＜0的数则直接存储即可
{
if(hash[i]==1)
{
LN* newnode = (LN*)malloc(sizeof(LN));
newnode->next = NULL;
newnode->val = i;
newhead->next = newnode;
newhead = newhead->next;
}
}
}
return Sentry->next;
}
3. 445. 两数相加 II - 力扣（LeetCode）
//思路：使用两个数组arr1、arr2分别存储l1和l2的val。然后分别从后往前遍历数组相加存储进数组arr中，步骤和67. 二进制求和 - 力扣（LeetCode）//一致。最后再创建一个新链表，将数组arr中的数据存储进新链表返回
typedef struct ListNode LN;
int max(int x,int y)
{
return x>y?x:y;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
LN* Sentry = (LN*)malloc(sizeof(LN));//新链表的哨兵位
Sentry->next = NULL;
LN* newhead = Sentry;
int i = 0;
int j = 0;
int arr1[100] = {0};
int arr2[100] = {0};
int arr[101] = {0};
LN* pmove1 = l1;
LN* pmove2 = l2;
int flag = 0;
while(pmove1)//将l1的val存进arr1
{
arr1[i++] = pmove1->val;
pmove1 = pmove1->next;
}
while(pmove2)//将l2的val存进arr2
{
arr2[j++] = pmove2->val;
pmove2 = pmove2->next;
}
i--;//定位到数组的最后一个元素
j--;
int max1 = max(i,j);//用于判断arr数组中存储数据的长度，arr0下标的位置需要空出来
int max2 = max1;
while(i>=0||j>=0)
{
int x = (i>=0)?arr1[i]:0;
int y = (j>=0)?arr2[j]:0;
arr[max2+1] = (x+y+flag)%10;//max2+1能够保证arr中0位置空出，并且存储进arr1、arr2相加后的数
if(x+y+flag>=10)
{
flag = 1;
}
else
{
flag = 0;
}
max2--;
if(i>=0)
{
i--;
}
if(j>=0)
{
j--;
}
}
if(flag)//如果出了循环flag还为1，说明最高位也进了位，将arr数组0位置处的元素置为1
{
arr[0] = 1;
for(i = 0;i<=max1+1;i++)//从arr数组0位置开始将数据存入新链表
{
LN* newnode = (LN*)malloc(sizeof(LN));
newnode->next = NULL;
newnode->val = arr[i];
newhead->next = newnode;
newhead = newhead->next;
}
}
else
{
for(i = 1;i<=max1+1;i++)//如果flag为0，则说明最高位没有进1，则直接从arr数组1位置开始存入
{
LN* newnode = (LN*)malloc(sizeof(LN));
newnode->next = NULL;
newnode->val = arr[i];
newhead->next = newnode;
newhead = newhead->next;
}
}
return Sentry->next;
}
