[数据结构与算法]LeetCode 2021-07-14

LeetCode 2021.7.14.

array 数组

485、最大连续 1 的个数（简单）

方法一：遍历一遍数组

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int max=0,count=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0){
                if(count>max) max=count;
                count=0;
            }
            else count++;
        }
        if(count>max) max=count;
        return max;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。需要遍历数组一次。
空间复杂度：O(1)。

283、移动零（简单）

方法一：数零，移动覆盖

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int count=0,a=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0) count++;
        }
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=0) nums[a++]=nums[i];
        }
        for(int i=a;i<nums.size();i++){
            nums[i]=0;
        }
    }
};

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

27、移除元素（道理和上题一样）（简单）

方法一：数val，移动覆盖

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int count=0,a=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==val) count++;
        }
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=val) nums[a++]=nums[i];
        }
        return nums.size()-count;
    }
};

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

Linked list 链表(c语言)

203、移除链表元素

方法一：迭代

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* new=malloc(sizeof(struct ListNode));
    new->next=head;
    struct ListNode* temp=new; // 要重新指
    while(temp->next!=NULL){
        if(temp->next->val==val){
            temp->next=temp->next->next;
        }
        else temp=temp->next;
    }
    return new->next;
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
空间复杂度：O(1)。

方法二：递归
最后再判断头结点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    if(head==NULL) return head;
    else{
        head->next=removeElements(head->next,val);
        return head->val==val ? head->next : head;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。递归过程中需要遍历链表一次。
空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用栈，最多不会超过 n 层。