数组与链表

最新推荐文章于 2024-10-23 15:56:10 发布

我也要当昏君

最新推荐文章于 2024-10-23 15:56:10 发布

阅读量602

点赞数 1

分类专栏：算法刷题文章标签：链表 leetcode 算法

本文链接： https://blog.csdn.net/qq_46118239/article/details/126525613

版权

算法刷题专栏收录该内容

35 篇文章 0 订阅

订阅专栏

数组与链表

数组原理、实战应用
设计变长数组
链表原理讲解、实战应用

数组原理、实战应用

C++: int a[100];
Java: int[] a = new int[100];
Python:a=[]
数组的基本特点:支持随机访问
数组的关键:索引与寻址
C++: a[i], *(a+i)
Java, Python: a[i]
数组在内存中是–段连续的存储空间

数组-插入元素

数组-删除元素

时间复杂度

实战

26.删除有序数组中的重复项
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};

283.移动零

https://leetcode.cn/problems/move-zeroes/

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

88.并两个有序数组
https://leetcode.cn/problems/merge-sorted-array/

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i=0;i<n;i++)
        {
            nums1[m+i]=nums2[i];
        }

        sort(nums1.begin(),nums1.end());
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // for(int i=0;i<n;i++)
        // {
        //     nums1[m+i]=nums2[i];
        // }

        // sort(nums1.begin(),nums1.end());

        int pos=m-- + n-- -1;
        while(m>=0 && n>=0)
        {
            nums1[pos--]=nums1[m]>nums2[n]?nums1[m--]:nums2[n--];
        }

        while(n>=0)
        {
            nums1[pos--]=nums2[n--];
        }
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }
};

设计变长数组

C++: vector
Java: ArrayList
Python: list

如何实现一个变长数组?

支持索引与随机访问
分配多长的连续空间?
空间不够用了怎么办?
空间剩余很多如何回收?

一个简易的实现方法

初始:空数组，分配常数空间，记录实际长度(size) 和容量(capacity)
Push back:若空间不够，重新申请2倍大小的连续空间，拷贝到新空间，释放旧空间
Pop back:若空间利用率(size/capacity) 不到25%，释放一半的空间
均摊0(1)
在空数组中连续插入n个元素，总插入/拷贝次数为n+n/2+n/4+…< 2n
一次扩容到下一次释放，至少需要再删除n- 2n*0.25=0.5n次

思考:若释放空间的阈值设定为50%，会发生什么情况?

链表原理讲解、实战应用

单链表(linked list)

单链表-插入

单链表-删除

双链表(double linked list)

时间复杂度

保护节点

实战

206.反转链表
https://leetcode.cn/problems/reverse-linked-list/

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

25. K个一组翻转链表
https://leetcode.cn/problems/reverse-nodes-in-k-group/

class Solution {
public:
    // 翻转一个子链表，并且返回新的头与尾
    pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
        ListNode* prev = tail->next;
        ListNode* p = head;
        while (prev != tail) {
            ListNode* nex = p->next;
            p->next = prev;
            prev = p;
            p = nex;
        }
        return {tail, head};
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* hair = new ListNode(0);
        hair->next = head;
        ListNode* pre = hair;

        while (head) {
            ListNode* tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (!tail) {
                    return hair->next;
                }
            }
            ListNode* nex = tail->next;
            // 这里是 C++17 的写法，也可以写成
            // pair<ListNode*, ListNode*> result = myReverse(head, tail);
            // head = result.first;
            // tail = result.second;
            tie(head, tail) = myReverse(head, tail);
            // 把子链表重新接回原链表
            pre->next = head;
            tail->next = nex;
            pre = tail;
            head = tail->next;
        }

        return hair->next;
    }
};

141.环形链表

https://leetcode.cn/problems/linked-list-cycle/

快慢指针法, 0(length) 时间，0(1) 空间
有环必定发生套圈(快慢指针相遇)，无环不会发生套圈(快指针到达null)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        while(fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            head = head->next;
            if(fast == head) return true;
        }

        return false;
    }
};

142.环形链表II

相遇时,有2(l+p)=l+p+k*r,其中k为整数(套的圈数)
即l=kr-p=(k-1) r+(r-p)
含义:从head走到st,等于从meet走到st,然后再绕几圈
此时开始让慢指针与head同时移动，必定在环的起始点相遇

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                while (head != slow ) {
                    head = head->next;
                    slow = slow->next;
                }
                return head;
            }
        }
        return nullptr;
    }
};