C语言基础数据结构习题第二辑

C语言基础数据结构习题第二辑

🎆个人主页：夜幕下的人海

今日金句：知识源于辛勤劳作，所有成就皆为刻苦努力之果。——宋庆龄

文章目录

• 🎄一、链表特定区间的翻转
• 🎉二、移除链表中总和为零的节点
• 🚀三、链表数值相加
• 🏝️四、括号的最大嵌套程度
• 🚘五、规范字符串
• 🏖️六、根到叶的二进制数求和
• ⭐七、二叉树的倾斜度

🎄一、链表特定区间的翻转

题目描述：链表内指定区间翻转

解题思路：
1.首要处理特殊情形，若m等于n，表明反转区间仅有一个节点，无需开展任何操作，直接返回原链表的头节点head。
2.创建虚拟头节点ret，并令其next指针指向链表的头节点head。（虚拟头节点能简化边界状况的处理，比如当反转区间包含头节点时，可规避繁杂的头插操作。）
3.运用两个指针pm与pn，pn用于定位反转区间的前一个节点，pm用于定位反转区间的起始节点。
4.借助第一个for循环，将pm指向第m个节点，pn指向第m - 1个节点。
5.再通过第二个for循环，从第m个节点开始，逐个对节点进行反转，直至第n个节点。
6.最终返回虚拟头结点的下一个节点，也就是ret->next，此为反转后链表的头节点。

代码实现：

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) 
{
    struct ListNode* ret = (struct ListNode*)malloc(sizeof(struct ListNode));
    ret->next = head;
    struct ListNode* pm = ret;
    struct ListNode* pn = head;
    if(m == n)
    {
        return head;
    }
    for(int i = 0;i < m;i++)
    {
        pn = pm;
        pm = pm->next;
    }
    for(int i = m;i < n;i++)
    {
        struct ListNode* mid = pm->next;
        pm->next = mid->next;
        mid->next = pn->next;
        pn->next = mid;
    }
    return ret->next;
}

🎉二、移除链表中总和为零的节点

题目描述：从链表中删去总和值为零的节点

解题思路：
1.首先创建虚拟头节点ret，并将其next指针指向链表的头节点head。
2.运用指针prev从虚拟头节点开始对链表进行遍历。（prev的作用是记录当前需检查的子链表起始节点的前一个节点）
3.采用两层循环，外层循环用于遍历链表，内层循环负责检查子链表的和是否为0。
4.两层循环结束后，返回虚拟头节点ret的下一个节点，即处理后链表的头节点。

代码实现：

struct ListNode* removeZeroSumSublists(struct ListNode* head) {
    struct ListNode* ret = (struct ListNode*)malloc(sizeof(struct ListNode));
    ret->next = head;
    struct ListNode* prev = ret;
    while(prev)
    {
        int sum = 0;
        //内部计算结果
        struct ListNode* cur = prev->next;
        while(cur)
        {
            sum -= cur->val;
            if(sum == 0)
            {
                prev->next = cur->next;
            }
            cur = cur->next;
        }
        prev = prev->next;
    }
    return ret->next;
}

🚀三、链表数值相加

题目描述：链表求和

解题思路：
1.检查输入是否合法，若l1和l2均为空，则直接返回0。
2.创建虚拟头节点dummy，并初始化指针cur指向虚拟头节点，使用变量count表示进位。
3.通过while循环遍历两个链表，直至两个链表均为空。
4.在每次循环中，获取当前节点的值，创建新节点newnode，其值为计算结果，并将其连接到结果链表中。
5.若l1或l2不为空，持续判断，直至两个链表均为空。
6.若循环结束后count不为0，说明还有进位需处理，创建新节点并连接到结果链表末尾。

代码实现：

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    if(l1 && l2 == NULL)
    {
        return 0;
    }
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = dummy;
    //进位
    int count = 0;
    while(l1 || l2)
    {
        int val1 = (l1?l1->val:0);
        int val2 = (l2?l2->val:0);
        int sum = val1 + val2 + count;
        //获取个位
        int data = sum % 10;
        count = sum / 10;
        struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newnode->val = data;
        newnode->next = NULL;
        cur->next = newnode;
        cur = cur->next;
        if(l1)
        {
            l1 = l1->next;
        }
        if(l2)
        {
            l2 = l2->next;
        }
    }
    if(count)
    {
        struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newnode->val = count;
        newnode->next = NULL;
        cur->next = newnode;
    }
    return dummy->next;
}

🏝️四、括号的最大嵌套程度

题目描述：括号的最大嵌套深度

解题思路：
1.首先创建三个变量：top用于记录当前括号的嵌套层数；count用于记录最大的嵌套深度；i用于遍历字符串的索引。
2.通过while循环遍历字符串，直至遇到字符串的结束符‘\0’。
3.遇到左括号时，top加1，利用fmax函数更新count，确保count始终记录最大嵌套深度。
4.遇到右括号时，top减1。
5.循环结束后，返回count，即最大嵌套深度。

代码实现：

int maxDepth(char* s) {
    int top = 0;
    int count = 0;
    int i = 0;
    while(s[i] != '\0')
    {
        if(s[i] == '(')
        {
            top++;
            count = fmax(top,count);
        }
        else if(s[i] == ')')
        {
            top--;
        }
        i++;
    }
    return count;
}

🚘五、规范字符串

题目描述：整理字符串

解题思路：
1.创建三个变量，i用于遍历字符串的索引；len表示字符串的长度；top用于模拟栈的栈顶指针，初始值为-1（表示栈为空）。
2.通过循环遍历字符串，每次将当前字符放入栈中。
3.检查栈顶的两个字符是否满足相邻且大小写不同的条件，若满足则移除这两个字符，否则继续处理下一个字符。
4.循环结束后，栈中剩余字符即为结果。

代码实现：

char* makeGood(char* s) {
    int i = 0;
    int len = strlen(s);
    int top = -1;
    for(i = 0;i<len;i++)
    {
        s[++top] = s[i];
        if(top > 0)
        {
            if(abs(s[top] - s[top - 1]) == 'a' - 'A')
            {
                top -= 2;
            }
        }
    }
    s[top + 1] = '\0';
    return s;
}

🏖️六、根到叶的二进制数求和

题目描述：从根到叶的二进制数之和

解题思路：
1.处理特殊情况，若当前节点为空，则返回0，表示无路径。
2.若节点非空，则将当前节点的值加入路径的二进制表示中。
3.若当前节点是叶子节点，则返回当前路径的二进制值val。
4.若当前节点不是叶子节点，递归计算左子树和右子树的路径和，并将结果相加。
5.在主函数中调用Count，从根节点开始，初始路径值为0。

代码实现：

//计算左右路径之和
int Count(struct TreeNode* root,int val)
{
    if(root == NULL)
    {
        return 0;
    }
    val = (val<<1) + root->val;
    if(root->left == NULL && root->right == NULL)
    {
        return val;
    }
    return Count(root->left,val) + Count(root->right,val);
}

int sumRootToLeaf(struct TreeNode* root) {
    return Count(root,0);
}

⭐七、二叉树的倾斜度

题目描述：二叉树的坡度

解题思路：
1.使用辅助函数Count，用于计算以root为根的子树的所有节点值之和。
2.运用辅助函数prevOrder，通过前序遍历计算整棵树的坡度，并将结果累加到sum中。
3.在主函数中定义变量ret，表示整棵树的坡度，调用prevOrder函数从根节点开始计算整棵树的倾斜度。
4.最后返回坡度ret。

代码实现：

int Count(struct TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return Count(root->left) + Count(root->right) + root->val;
}

void prevOrder(struct TreeNode* root,int* sum)
{
    if(root == NULL)
    {
        return;
    }
    int left = Count(root->left);
    int right = Count(root->right);
    (*sum) += abs(left - right);
    prevOrder(root->left,sum);
    prevOrder(root->right,sum);
}

int findTilt(struct TreeNode* root) {
    int ret = 0;
    prevOrder(root,&ret);
    return ret;
}

今日分享到此结束啦，若觉得不错，期望能给博主来个一键三连，感激大家的支持！愿这篇文章能帮到大家，咱们下期再会！