LeetCode_每日一题（8月）

拼搏现实的明天。 2023-03-04 04:29 8阅读 0赞

### 目录 ###

*  632.最小区间(没懂）
 *  114.二叉树展开为链表
 *  415.字符串相加

# 632.最小区间(没懂） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]

/**
     * Note: The returned array must be malloced, assume caller calls free().
     */
    
    #define maxn 100005
    
    int heap[maxn];
    int heap_count;
    int **rec, *nx;
    
    bool heap_comp(int *first, int *second) {
         //返回0 1
        return rec[*first][nx[*first]] < rec[*second][nx[*second]]; //当前区间小于最小区间？
    }
    
    void swap(int *first, int *second) {
         //更新最小区间
        int temp = *second;
        *second = *first;
        *first = temp;
        return;
    }
    
    void push(int num) {
        
        int pos = ++heap_count;
        heap[pos] = num;
        while (pos > 1) {
        
            if (heap_comp(&heap[pos], &heap[pos >> 1])) {
         
                swap(&heap[pos], &heap[pos >> 1]);
                pos >>= 1;
            } else
                break;
        }
        return;
    }
    
    void pop() {
         //
        int top_num = 1;
        int now;
        swap(&heap[top_num], &heap[heap_count--]);
        while ((now = (top_num << 1)) <= heap_count) {
        
            if (heap_comp(&heap[now + 1], &heap[now]) && now < heap_count) now++;
            if (heap_comp(&heap[now], &heap[top_num])) {
        
                swap(&heap[top_num], &heap[now]);
                top_num = now;
            } else
                break;
        }
    }
    
    int top() {
         return heap[1]; }
    
    int *smallestRange(int **nums, int numsSize, int *numsColSize, int *returnSize) {
         //主
        heap_count = 0;
        nx = (int *)malloc(sizeof(int) * numsSize);
        memset(nx, 0, sizeof(int) * numsSize);
        rec = nums;
    
        int rangeLeft = 0, rangeRight = 2147483647; //所求的最小区间的左右区间值
        int minValue = 0, maxValue = -2147483648;
        for (int i = 0; i < numsSize; ++i) {
        
            push(i); //
            maxValue = fmax(maxValue, nums[i][0]);
        }
    
        while (true) {
        
            int row = top(); //
            pop(); //
            minValue = nums[row][nx[row]];
            if (maxValue - minValue < rangeRight - rangeLeft) {
        
                rangeLeft = minValue;
                rangeRight = maxValue;
            }
            if (nx[row] == numsColSize[row] - 1) {
        
                break;
            }
            ++nx[row];
            maxValue = fmax(maxValue, nums[row][nx[row]]);
            push(row);
        }
        int *ret = malloc(sizeof(int) * 2); //初始化所求区间数组
        ret[0] = rangeLeft, ret[1] = rangeRight;
        *returnSize = 2;
        return ret;
    }

# 114.二叉树展开为链表 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 2]  
**方法一：前序遍历**  
将二叉树展开为单链表之后，单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。因此，可以对二叉树进行前序遍历，获得各节点被访问到的顺序。由于将二叉树展开为链表之后会破坏二叉树的结构，因此在前序遍历结束之后更新每个节点的左右子节点的信息，将二叉树展开为单链表。

前序遍历可以通过递归或者迭代的方式实现。以下代码通过递归实现前序遍历。

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    
    int num;
    
    void flatten(struct TreeNode* root) {
         //主
        num = 0;
        struct TreeNode** l = (struct TreeNode**)malloc(0);
        preorderTraversal(root, &l);
        for (int i = 1; i < num; i++) {
         //把遍历的数全部放到树右边
            struct TreeNode *prev = l[i - 1], *curr = l[i];
            prev->left = NULL;
            prev->right = curr;
        }
        free(l);
    }
    
    void preorderTraversal(struct TreeNode* root, struct TreeNode*** l) {
         //前序遍历
        if (root != NULL) {
        
            num++;
            (*l) = (struct TreeNode**)realloc((*l), sizeof(struct TreeNode*) * num);
            (*l)[num - 1] = root;
            preorderTraversal(root->left, l);
            preorderTraversal(root->right, l);
        }
    }

# 415.字符串相加 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 3]

char* addStrings(char* num1, char* num2) {
        
        //i,j:两个相加的字符串各自的长度，add:进位
        int i = strlen(num1) - 1, j = strlen(num2) - 1, add = 0;
        //初始化"和"
        char* ans = (char*)malloc(sizeof(char) * (fmax(i, j) + 3));
        //定义"和"的长度
        int len = 0;
    
        while (i >= 0 || j >= 0 || add != 0) {
        
            int x = i >= 0 ? num1[i] - '0' : 0; //对位数较短的数补0
            int y = j >= 0 ? num2[j] - '0' : 0;
    
            int result = x + y + add;
            ans[len++] = '0' + result % 10; //储存每一位计算的结果
            add = result / 10; //储存进位
            i--, j--;
        }
        // 计算完以后的答案需要翻转过来
        for (int i = 0; 2 * i < len; i++) {
        
            int t = ans[i];
            ans[i] = ans[len - i - 1], ans[len - i - 1] = t;
        }
        ans[len++] = 0; //"和"字符串结束的标志
    
        return ans;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]: /images/20230208/73a8e21dcc6342178fd7a64581b37e01.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]: /images/20230208/c3f321355ff14053a8932d03ca1ae58b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 2]: /images/20230208/b22c5aec8ce54715a333886af704b433.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 3]: /images/20230208/00f50176bcdb40848d06eaf22cfcdb45.png