题目:给定链表头结点 head,该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums,该列表是上述链表中整型值的一个子集。 返回列表 nums 中组件的个数,这里对组件的定义为:链表中一段最长连续结点的值(该值必须在列表 nums 中)构成的集合。
示例 1: 输入: head = [0, 1, 2, 3], nums = [0, 1, 3] 输出 : 2 解释 : 链表中, 0 和 1 是相连接的,且 nums 中不包含 2,所以[0, 1] 是 nums 的一个组件,同理[3] 也是一个组件,故返回 2。
示例 2: 输入: head = [0, 1, 2, 3, 4], nums = [0, 3, 1, 4] 输出 : 2 解释 : 链表中,0 和 1 是相连接的,3 和 4 是相连接的,所以[0, 1] 和[3, 4] 是两个组件,故返回 2。
提示: 链表中节点数为n 1 <= n <= 10^4 0 <= Node.val < n Node.val 中所有值 不同 1 <= nums.length <= n 0 <= nums[i] < n nums 中所有值 不同
思路:用hash数组将 nums 数组中出现过的元素记录下来,然后遍历链表,如果可以组成 nums 数组的组件,就用 flag 标记为1,继续判断链表的下一个值是否是nums数组的组件,如果不是,就将上一个链表的组件 flag 统计到 ans 中,最后返回 ans ;如果是,就继续标记 flag 为1,一直迭代链表,直到空;如果一直迭代到空,flag 还是被标记为1,最后要处理这个1,把它统计到 ans 中;
int numComponents(struct ListNode* head, int* nums, int numsSize)
{
struct ListNode* cur = head;
//hash数组记录nums中出现过的元素
int hash[10000] = { 0 };
int flag = 0, ans = 0;
//将nums数组中出现过的元素在hash数组中标记为1
for (int i = 0; i < numsSize; i++)
{
hash[nums[i]] = 1;
}
while (cur)
{
//如果链表中的元素有在nums数组中出现过,用flag记录;如果是相连的元素一直出现,那flag也一直等于1,一整串相当于出现一次
if (hash[cur->val])
{
flag = 1;
}
//否则,或者一直出现的元素中断,用ans统计组件的个数;并将flag置0
else
{
ans += flag;
flag = 0;
}
//cur 迭代
cur = cur->next;
}
//最后处理被遗漏的flag,因为如果链表中的元素一直连着组成组件,直到链表为空,那么这个组件还没算进 ans
ans += flag;
return ans;
}
题目:给定一个长度为 n 的链表 head 对于列表中的每个节点,查找下一个 更大节点 的值。也就是说,对于每个节点,找到它旁边的第一个节点的值,这个节点的值严格大于它的值。 返回一个整数数组 answer ,其中 answer[i] 是第 i 个节点(从1开始)的下一个更大的节点的值。 如果第 i 个节点没有下一个更大的节点,设置 answer[i] = 0
示例 1: 输入:head = [2, 1, 5] 输出:[5, 5, 0]
示例 2: 输入:head = [2, 7, 4, 3, 5] 输出:[7, 0, 5, 5, 0]
提示: 链表中节点数为 n 1 <= n <= 10^4 1 <= Node.val <= 10^9
思路:暴力方法,直接遍历链表,寻找下一个更大的节点,如果遍历到空,即没有下一个更大的节点,就将 0 放入返回的数组,否则就将这个更大的节点放入返回数组;
int* nextLargerNodes(struct ListNode* head, int* returnSize)
{
struct ListNode* cur = head, * ptr = head;
//用len记录返回的长度,ret为返回的数组
int len = 0;
int* ret = (int*)malloc(sizeof(int) * 10000);
while (ptr)
{
//cur每次从ptr开始遍历
cur = ptr;
//寻找当前比 ptr 下一个更大节点
//cur的next不能为空,如果ptr的值大于等于cur的next的值,cur往后迭代
while (cur->next && ptr->val >= cur->next->val)
cur = cur->next;
//如果没找到下一个更大的节点,将0放入返回数组
if (cur->next == NULL)
ret[len++] = 0;
//如果找到,就将这个节点放入返回数组
else if (ptr->val < cur->next->val)
ret[len++] = cur->next->val;
//每次找完 ptr 往后迭代
ptr = ptr->next;
}
*returnSize = len;
return ret;
}