当前位置:   article > 正文

数组、链表的应用及题目解析_数组和链表的简单题目

数组和链表的简单题目

1.数组操作复杂度

增加元素:O(n)

删除元素:O(n)

查找元素:O(1)

2.单链表

数组适宜查找,链表适宜增删

单链表的定义(C语言)
  • 首先定义一个头文件
# ifndef __LinkList_H__
# define __LinkList_H__

# include <stdio.h>
# include <stdlib.h>

typedef int DataType;
typedef struct node{
	DataType data;
	struct node *link;  //链接指针
}LinkNode,LinkList; 

# endif
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
单链表的操作
# include <LinkList.h>


void initList(LinkList&first){
	//初始化链表,建立只带有头指针的空链表
	first = (LinkNode *) malloc (sizeof(LinkNode));
	first -> link = NULL;
}


void clearList(LinkList&first){
	//清空链表,只保留头节点
	LinkNode *q;
	while(first->link != NULL){
		q = first -> link;
		first -> link = q -> link;
		free(q);
	} 
}


int Length(LinkList&first){
	LinkNode *p = first ->link;
	int count = 0;
	while(p != NULL){
		p = p -> link; count++;
		return count;
	}
}


LinkNode *Search(LinkList&first, DataType x){
	LinkNode *p = first -> link;
	while(p!=NULL && p->data != x) p = p->link;
	return p;  // 返回地址 
}


LinNode *Locate(LinkList&first, int i){
	//对第i个节点定位,返回第i个节点的地址 
	if(i<0) return NULL;
	LinkNode *p = first; int k = 0;
	while(p != NULL && k<i){
		p = p -> link; k++
		return p;
	}
}


bool Insert(LinkList&first, int i, DataType x) {
	LinkList *p = Locate(first, i-1);
	if (p==NULL) return false;
	LinkNode *s = (LinkNode*) malloc (sizeof(LinkNode));
	s -> data = x; s -> link = p->link; p -> link = s; 
	}
	return true;
}


bool Remove(LinkList&first, int i, DataType&x){
	//通过引用参数x保存被删除的值 
	LinkList *p = Locate(first, i-1);
	if(p == NULL || p -> link == NULL) return false;
	LinkNode *q = p -> link;
	p -> link = q -> link;
	x = q -> data; free(q);
	return true;	
}


void printList(LinkList&first){
	LinkNode *p;
	for(p = first -> link; p!=NULL; p=p -> link){
		printf("%d", p -> data);
	}
	printf("\n");
} 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
链表操作复杂度

添加删除:O(1)

查找:O(n)

如何提高链表线性查找效率

基本思想:升维、空间换时间

答案是:跳表。调表查询任意数据的时间复杂度为O(logn)

3.链表的python实现

class Node(object):    # 定义节点类
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class LinkedList(object):    # 单链表类,头部指针默认指向None
    def __init__(self):
        self.head = None   

    # 判断是否为空
    def is_null(self):
        return self.head is None

    # 插入元素
    def insert(self, ele):
        temp = Node(ele)
        temp.next = self.head
        self.head = temp

    # 判断链表长度
    def lenth(self):
        i = 0
        cur = self.head
        while cur != None:
            i += 1
            cur = cur.next
        return i

    # 遍历元素
    def travel(self):
        cur = self.head
        while cur:
            print(cur.data, end='<-')
            cur = cur.next

    # 删除元素
    def remove(self, ele):
        cur = self.head
        found = False
        pre = None  # 另一个结点指针
        while cur and not found:
            if cur.data == ele:
                pre.next = cur.next
                found = True
            else:
                pre = cur
                cur = cur.next

    # 查找元素
    def searh_ele(self, ele):
        cur = self.head
        found = False
        while cur:
            if cur.data == ele:
                found = True
            cur = cur.next
        return found
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

4.工程中的应用

**Linked List: **

LRU缓存

Skip List:

Redis

5.数组实战题目(leetcode)

1.移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
  • 1
  • 2

说明:

  • 必须在原数组上操作,不能拷贝额外的数组。
  • 尽量减少操作次数

python

**思路1:**遍历数组,元素为0时,在列表后面增加一个0,再把此0删除

def moveZeroes(nums):
    for i in nums:
        if i == 0:
            nums.append(0)
            nums.remove(i)
  • 1
  • 2
  • 3
  • 4
  • 5

此方法思路清晰简单,但时间复杂度达 O ( n 2 ) O(n^2) On2!

**思路2:**使用 i 遍历数组,使用 j 记录非零元素,如果nums[i]不为零,则把它赋值给nums[j],赋值成功后,j移动到下一位 O(n)

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = j = 0
        while i < len(nums):
            if nums[i] != 0:
                nums[j] = nums[i]
                if i != j:
                    nums[i] = 0
                j += 1
            i += 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

另一种方法 O(n)

def moveZeroes(nums):
    j = 0
    for i in range(len(nums)):
        if nums[i] == 0:
            nums[i], nums[j] = nums[j], nums[i]
            j += 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
2.盛水最多的容器

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

示例:

输入:[1,8,6,2,5,4,8,3,7]
输出:49
  • 1
  • 2

**思路1:**暴力破解法 O ( n 2 ) O(n^2) O(n2)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_area = 0
        for i in range(len(height)-1):
            for j in range(i+1, len(height)):
                area = (j-i)*min(height[i], height[j])
                max_area = max(max_area, area)
        return max_area
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

思路二:双指针法 O(n)

使用两个指针分别指向数组头尾,右指针往左,左指针往右,重合时停止循环。每移动一次,比较两指针对应值大小,然后移动较小的值,即可得解

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height)-1
        max_area = 0
        while l < r:
            area = (r-l)*min(height[r], height[l])
            max_area = max(max_area, area)
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return max_area
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
3.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

**注意:**给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
  • 1
  • 2
  • 3
  • 4
  • 5

示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

思路:

仔细阅读题意后,发现其为斐波那契数列问题

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        else:
            f1 = 1
            f2 = 2
            for i in range(3, n+1):
                f2, f1 = f1+f2,f2
            return f2
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

不用递归是因为递归太慢,时间复杂度太高,但此方法复杂度只有O(n)

4.三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

思路1:暴力破解法 O ( n 3 ) O(n^3) O(n3)

思路2:排序+双指针 O ( n 2 ) O(n^2) O(n2)

设置两个运动指针i,j, 在运动之前,设置一个固定指针k,固定于最左侧,指针i、j分别指向(k, len(nums))位置。

  • 当nums[k]>0时,易知三数和大于0,直接break
  • 当nums[k]<=0时,若nums[i]+nums[j]>0,则移动j(j -= 1), 否则移动i指针。当移动指针时,发现移动后的数与前一位相等,直接跳过。i、j相遇时,循环结束

k移动时,若nums[k]=nums[k-1],结果会重复,直接跳过,指针i,j同理。

若数组长度小于3,返回空

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        if len(nums) < 3:
            return []
        for k in range(len(nums)-2):
            if nums[k] > 0:
                break
            if k > 0 and nums[k] == nums[k-1]:
                continue
            i, j = k+1, len(nums)-1
            while i < j:
                s = nums[k] + nums[i] + nums[j]
                if s < 0:
                    i += 1
                    while i < j and nums[i] == nums[i - 1]: 
                        i += 1
                elif s > 0:
                    j -= 1
                    while i < j and nums[j] == nums[j + 1]:
                        j -= 1
                else:
                    ans = [nums[k], nums[i], nums[j]]
                    res.append(ans)
                    j -= 1
                    i += 1
                    while i < j and nums[i] == nums[i - 1]:
                        i += 1
                    while i < j and nums[j] == nums[j + 1]:
                        j -= 1 
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

6.链表实战题目(leetcode)

1.反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
  • 1
  • 2

思路一:双指针加临时变量

设置两个指针pre, cur,用temp保存pre.next防丢失。

  • 初始化pre = None, cur = head
  • 开始循环:判断cur是否为空,为空则结束
    • 优先把cur当前值保存在temp里面,便于后续cur移动
    • 将cur.next指向pre
    • pre移动到下一个位置(cur位置),cur移动到temp位置
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head
        pre = None
        res = []
        while cur:
            temp = cur.next
            cur.next = pre
            pre, cur = cur, temp
        return pre
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

返回pre,相当于提起一串链子,只需要提起链头,整条链子便可提起

2.两两交换链表中的结点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.
  • 1

思路一:增加头结点前置指针结点

  • 增加前置指针结点prehead,它的next为头结点
  • 初始化:prehead, head, head.next头三个结点分别以cab简化
  • 进入循环,如果c.next, c.next.next不为空,则继续循环
    • c -> a.next (b)
    • a.next -> b.next,即将现在的a结点的next指向原先的b结点的 next
    • b.next -> a
    • c前置指针结点移动到下两位需要交换的数
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        prehead = ListNode(-1)
        prehead.next = head
        c = prehead
        while c.next and c.next.next:
            a, b = c.next, c.next.next
            c.next = b
            a.next = b.next
            b.next = a
            c = a
        return prehead.next
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

思路二:递归

从链表的头节点 head 开始递归。
每次递归都负责交换一对节点。由 firstNode 和 secondNode 表示要交换的两个节点。
下一次递归则是传递的是下一对需要交换的节点。若链表中还有节点,则继续递归。
交换了两个节点以后,返回 secondNode,因为它是交换后的新头。
在所有节点交换完成以后,我们返回交换后的头,实际上是原始链表的第二个节点。

class Solution(object):
    def swapPairs(self, head: ListNode) -> ListNode:
        """
        :type head: ListNode
        :rtype: ListNode
        """

        # If the list has no node or has only one node left.
        if not head or not head.next:
            return head

        # Nodes to be swapped
        first_node = head
        second_node = head.next

        # Swapping
        first_node.next  = self.swapPairs(second_node.next)
        second_node.next = first_node

        # Now the head is the second node
        return second_node
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
3.判断链表中是否有环

给定一个链表,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

如果链表中存在环,则返回 true 。 否则,返回 false 。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗

示例 1

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
  • 1
  • 2
  • 3

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
  • 1
  • 2
  • 3

示例 3

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
  • 1
  • 2
  • 3

思路一:快慢指针 O(n)

设置两个指针,一个快指针fast和一个慢指针slow, fast一次移动两个位置而slow一次移动一个位置,他们相等时,就判定为有环

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        fast = slow = head
        while fast and fast.next: # 空链表和一个元素链表不满足此循环
            fast = fast.next.next
            slow = slow.next
            if fast is slow:
                return True
        return False
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

思路二:哈希表 O(1)

python中的哈希表为集合set

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        nodes = set()
        while head:
            if head in nodes:
                return True
            nodes.add(head)
            head = head.next
        return False
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
4.环形链表ii

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。
  • 1
  • 2
  • 3

示例 2

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点
  • 1
  • 2
  • 3

思路:快慢指针 O(n)

快指针一次前进2步,慢指针前进一步,如果有环,它们必定相遇。

下面来推导他们相遇时的行进路程:

假设相遇时快慢指针分别走了f, s 步,则有 f = 2 s f=2s f=2s, 假设链表总长度为 a + b a+b a+b,其中b为环长度。

两指针在环内重合时,快指针多走了n圈, f = s + n b f = s+nb f=s+nb

两式相减可得: f = 2 n b , s = n b f = 2nb,s = nb f=2nbs=nb

设指针走到环口结点得步数为k, 则有 k = a + n b k = a+nb k=a+nb, 目前慢指针走了 n b nb nb, 只需要让其再走a步,便是环口,怎么才能让其走a步呢?

此时快慢指针是相遇状态,让快指针移动到头部,并让其后面每次只挪动一步,快慢指针再次相遇时,便是环的入口

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head
        while True:
            if not(fast and fast.next):
                return
            fast, slow = fast.next.next, slow.next
            if fast == slow:
                break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/642377
推荐阅读
相关标签
  

闽ICP备14008679号