C 语言的 LeetCode 30 天挑战第3部分，共10部分

原创

笃信好学

发布于 2023-04-15 20:26:03

2780

文章被收录于专栏：笃信好学

网上找了视频，LeetCode 30 天挑战，用c语言写，记录一下，一共30个leetcode 算法题对应30天，大概需要写10篇，每篇3道题，手打下代码，外加记录一下。

第7题 (Min Stack)

设计一个最小的栈，有push(), pop(), top()和获得最小值的功能。C语言看起来一串，有点乱。得新复习一下。

//下面这个竟然过了，题目要求You must implement a solution with O(1) time complexity for each function.
//必须每个函数的时间复杂度都是1.思路就是 弄个变量存在struct里面,变量不确切，是个最小值的数组。
typedef struct {
    int* data;
    int size;
} MinStack;


MinStack* minStackCreate() {
    MinStack *s=malloc(sizeof(MinStack));
    s->data=NULL;
    s->size=0;
    return s;
}

void minStackPush(MinStack* obj, int val) {
    obj->data=realloc(obj->data,sizeof(int)*(obj->size+1));
    obj->data[obj->size]=val;
    obj->size++;
}

void minStackPop(MinStack* obj) {
    obj->size--;
}

int minStackTop(MinStack* obj) {
  return obj->data[obj->size-1];
}

int minStackGetMin(MinStack* obj) {
  int minval=obj->data[0];
  for(int i=1;i<obj->size;i++)
  {
     if(minval>obj->data[i])
     {
        minval=obj->data[i];
     } 
  }
    return minval;
}

void minStackFree(MinStack* obj) {
    free(obj->data);
    free(obj);
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, val);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackGetMin(obj);
 
 * minStackFree(obj);
*/

//题目要求You must implement a solution with O(1) time complexity for each function.
//必须每个函数的时间复杂度都是1.思路就是 弄个变量存在struct里面,变量不确切，是个最小值的数组。
//满足上面要求的代码
typedef struct {
    int* data;
    int size;
    int* mins;
} MinStack;


MinStack* minStackCreate() {
    MinStack *s=malloc(sizeof(MinStack));
    s->data=NULL;
    s->size=0;
    s->mins=NULL;
    return s;
}

void minStackPush(MinStack* obj, int val) {

    obj->data=realloc(obj->data,sizeof(int)*(obj->size+1));
    obj->mins=realloc(obj->mins,sizeof(int)*(obj->size+1));
    obj->data[obj->size]=val;
    if(obj->size==0){obj->size++; return;}
    if(obj->mins[obj->size-1]>val){
        obj->mins[obj->size]=val;
    }
    else{
        obj->mins[obj->size]=obj->mins[obj->size-1];
    }
    obj->size++;
}

void minStackPop(MinStack* obj) {
    obj->size--;
}

int minStackTop(MinStack* obj) {
  return obj->data[obj->size-1];
}

int minStackGetMin(MinStack* obj) {
  int minval=obj->data[0];
  for(int i=1;i<obj->size;i++)
  {
     if(minval>obj->data[i])
     {
        minval=obj->data[i];
     } 
  }
    return minval;
}

void minStackFree(MinStack* obj) {
    free(obj->data);
    free(obj);
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, val);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackGetMin(obj);
 
 * minStackFree(obj);
*/

第8题(Diameter of Binary Tree)

一个二叉树，找到两个节点最长距离，这个题不一定通过树根, 可以定是不是一定通过树根，来递归.

/** C语言的结构定义
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int diameterOfBinaryTree(struct TreeNode* root){

}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

 int maxdepth(struct TreeNode* root)
{
  if(root==NULL) return 0;
  int left= maxdepth(root->left);
  int right= maxdepth(root->right);

  if(left<right)
  {
    return right+1;
  }
  return left+1;
}

int diameterOfBinaryTree(struct TreeNode* root){
  if(root==NULL) return 0;
  int midval= maxdepth(root->left)+maxdepth(root->right);//要通过树根，把题目转换为求左右两侧数的高度
  int left=diameterOfBinaryTree(root->left);//不要通过树根，在左侧去递归
  int right=diameterOfBinaryTree(root->right);//不要通过树根，在右侧去递归

  int max=midval;
  if(midval<left)
  {
    max=left;
  }
  if(midval<right)
  {
    max=right;
  }

  return max;
}

第9题(Maximum Depth of Binary Tree)

延伸出来的简单题，求数的最大的高，被第8题用到了，树的树根左右递归。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root){

    if(root==NULL) return 0;
    int left_max=maxDepth(root->left);
    int right_max=maxDepth(root->right);
    if(left_max>right_max){
        return left_max+1;
    }
    return right_max+1;
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

leetcode