数据结构与算法：数组+链表

【数组】

实现一个支持动态扩容的数组
实现一个大小固定的有序数组，支持动态增删改操作
实现两个有序数组合并为一个有序数组
学习哈希表思想，并完成leetcode上的两数之和(1)及Happy Number(202)！(要求全部用哈希思想实现！)（选做）（注意：在第四天会进行继续学习）

练习：

1. 三数之和，Leetcode 13 https://leetcode-cn.com/problems/3sum/

思路：双指针

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            j = i+1
            k = n-1
            if i>0 and nums[i] == nums[i-1]:
                continue
            while j<k:
                if nums[i]+nums[j]+nums[k] == 0:
                    res.append([nums[i],nums[j],nums[k]])
                    k -= 1
                    j += 1
                    while j<k and nums[j] == nums[j-1]:
                        j += 1
                    while j<k and nums[k] == nums[k+1]:
                        k -= 1
                elif nums[i]+nums[j]+nums[k] > 0:
                    k -= 1
                else:
                    j += 1
        return res

2. 求众数，Leetcode 169 https://leetcode-cn.com/problems/majority-element/

思路：字典

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic={}
        for n in nums:
            if n in dic:
                dic[n]+=1
            else:
                dic[n]=1
        return max(dic, key=dic.get)

3. 求缺失的第一个正数 [作为可选]，Leetcode 41 https://leetcode-cn.com/problems/first-missing-positive/

思路：整理数组

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        j = 0
        while j < n and  j + 1 == nums[j]:
            j += 1
        return j + 1

【链表】

实现单链表、循环链表、双向链表，支持增删操作
实现单链表反转
实现两个有序的链表合并为一个有序链表
实现求链表的中间结点

　　练习：

1. 环形链表，Leetcode 141 https://leetcode-cn.com/problems/linked-list-cycle/

思路：1. 快慢指针 2. 字典 3. 集合

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        '''
        #快慢指针
        fast, slow=head, head
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
            if fast == slow:
                return True
        return False
        '''
        '''
        #字典,使用hash的去重思想
        dic={}
        while head:
            if head not in dic:
                dic[head]=1
                head=head.next
            else:
                return True
        return False
        
        '''
        #set,使用hash的去重思想
        hashset=set()
        while head:
            if head not in hashset:
                hashset.add(head)
                head=head.next
            else:
                return True
        return False

　　2.合并 k 个排序链表，Leetcode 23 https://leetcode-cn.com/problems/merge-k-sorted-lists/

　　思路：分而治之

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:return 
        n = len(lists)
        return self.merge(lists, 0, n-1)
    def merge(self,lists, left, right):
        if left == right:
            return lists[left]
        mid = (right + left) // 2
        l1 = self.merge(lists, left, mid)
        l2 = self.merge(lists, mid+1, right)
        return self.mergeTwoLists(l1, l2)
    def mergeTwoLists(self,l1, l2):
        if not l1:return l2
        if not l2:return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

秒客网

数据结构与算法：数组+链表

相关文章