当前位置：网站首页>leetcode SVM

leetcode SVM

2022-08-03 16:02:00 【Anan.3】

20. 有效的括号

在这里插入图片描述

此题是运用到数据结构中的栈，把左括号都入栈，当遇到右括号出栈进行比较，判断是否能够匹配，匹配成功则输出true，反之输出false

bool isValid(char * s){
    
    char *p=(char *)malloc(strlen(s));
    int i,j=0;
    for(i=0;i<strlen(s);i++){
    
        if(s[i]=='(' || s[i]=='{' || s[i]=='['){
    
            p[j++]=s[i];
        }
        if(s[i]==')'){
    
            if(j-1<0 || p[j-1]!='('){
    
                return 0;
            }else{
    
                j--;
            }
        }else if(s[i]=='}'){
    
            if(j-1<0 || p[j-1]!='{'){
    
                return 0;
            }else{
    
                j--;
            }
        }else if(s[i]==']'){
    
            if(j-1<0 || p[j-1]!='['){
    
                return 0;
            }else{
    
                j--;
            }
        }
    }
    free(p);
    if(j){
    
        return 0;
    }
    return 1;
}

378. 有序矩阵中第 K 小的元素

在这里插入图片描述

本题用冒泡排序会超时，因此我选择了qsort，对数组进行排序


int cmp(const void *a,const void *b){
    
    return (*(int *)a - *(int *)b);
}
int kthSmallest(int** matrix, int matrixSize, int* matrixColSize, int k){
    
    int *b=(int *)malloc(matrixSize * matrixSize * sizeof(int));
    int num=0;
    for(int i=0;i<matrixSize;i++){
    
        for(int j=0;j<matrixSize;j++){
    
            b[num++]=matrix[i][j];
        }
    }
    qsort(b,num,sizeof(int),cmp);
    return b[k-1];
}

206. 反转链表

在这里插入图片描述

定义指针cur，用来遍历链表，定义prev，存储cur上一个节点的位置，next，保存cur下一个节点的位置，通过prev和cur来调整每个节点指针的方向，next用来迭代，最后返回头指针head

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */


struct ListNode* reverseList(struct ListNode* head){
    
    struct ListNode *prev=NULL;
    struct ListNode *cur=head;
    while(cur!=NULL){
    
        struct ListNode *next=cur->next;
        cur->next=prev;
        prev=cur;
        cur=next;
    }
    head=prev;
    return head;

}

141. 环形链表

在这里插入图片描述

使用前后指针法，slow一次走一步，fast一次走两步，如果存在环，那么他们最终会在环中相遇，设为meet，如果不存在环，fast可能走到空或者最后一个节点，此时返回空.存在环，slow和fast会在环中meet处相遇，此时一个指针从head开始走，一个指针从meet开始走，他们会在环的入口处相遇

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
bool hasCycle(struct ListNode *head) {
    
    struct ListNode *slow=head,*fast=head;
    while(fast&&fast->next){
    
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast){
    
            struct ListNode *meet=slow;
            while(head!=meet){
    
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

237. 删除链表中的节点

在这里插入图片描述

本题可以将后一个节点的值赋给要删除的节点，然后用要删除的节点代替后一个节点，释放掉后一个节点

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
void deleteNode(struct ListNode* node) {
    
    struct ListNode *p=node->next;
    node->val=p->val;
    node->next=p->next;
    free(p);
}