Tong's Blog

Welcome to my Blog

0%

刷题小知识：数组/链表

发表于 更新于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟

数组链表代表着计算机最基本的两种存储形式：顺序存储和链式存储。

主要算法：双指针，可分为

  • 中间向两端扩散
  • 两端向中间收缩
  • 快慢指针

1. 前缀和数组

前缀和技巧适⽤于快速、频繁地计算⼀个索引区间内的元素之和。

注：原始数组/矩阵不可变，频繁查询某个区间的累加和。

相关题目：

  1. 区域和检索 - 数组不可变（中等）

  2. ⼆维区域和检索 - 矩阵不可变（中等）

  3. 和为K的⼦数组（中等）

一维数组的前缀和

image-image-20220310181632054

新建一个preSum数组，preSum[i] 记录 nums[0..i-1] 的累加和

如果我想求索引区间[1, 4] 内的所有元素之和，就可以通过 preSum[5] - preSum[1] 得出。

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class PrefixSum {
 // 前缀和数组
private:
     vector<int> prefix;
public:
     /* 输⼊⼀个数组，构造前缀和 */
     PrefixSum(vector<int>& nums) {
     prefix.resize(nums.size() + 1, 0);
     // 计算 nums 的累加和
     for (int i = 1; i < prefix.size(); i++) {
         prefix[i] = prefix[i - 1] + nums[i - 1];
     	}
     }
 	/* 查询闭区间 [i, j] 的累加和 */
     int query(int i, int j) {
 	 	return prefix[j + 1] - prefix[i];
 	 }
}

二维数组前缀和

image-20220310183903115

如果我想计算红⾊的这个⼦矩阵的元素之和，可以⽤绿⾊矩阵减去蓝⾊矩阵减去橙⾊矩阵最后加上粉⾊矩 阵，⽽绿蓝橙粉这四个矩阵有⼀个共同的特点，就是左上⻆就是 (0, 0) 原点。

那么我们可以维护⼀个⼆维 preSum 数组，专⻔记录以原点为顶点的矩阵的元素之和，就可以⽤⼏次加减运算算出任何⼀个⼦矩阵的元素和：

2. 差分数组

相关题目：

  1. 区间加法（中等）

  2. 航班预订统计（中等）

  3. 拼⻋（中等）

差分数组的主要适⽤场景是频繁对原始数组的某个区间的元素进⾏增减。

对 nums 数组构造⼀个 diff 差分数组，**diff[i]** 就是 nums[i] 和 nums[i-1] 之差：

image-20220311120935829

这样构造差分数组 **diff**，就可以快速进⾏区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可：

把差分数组抽象成⼀个类，包含 increment ⽅法和 result ⽅法：

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
// 差分数组⼯具类
class Difference {   
private:
    vector<int> diff;	//差分数组
   
public:
    Difference(vector<int>& nums) {
        assert nums.size() > 0;
        diff,resize(nums.size());
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
        	diff[i] = nums[i] - nums[i - 1];
		}
    }
    
    /* 给闭区间 [i,j] 增加 val（可以是负数）*/
    void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.size()) { //当 j+1 >= diff.length 时，说明是对 nums[i] 及以后的整个数组都进⾏修改，那么就不需要再给 diff数组减 val 了。
            diff[j + 1] -= val;
        }
    }
    
    /* 返回结果数组 */
    vector<int> result() {
        vector<int> res(diff.size());
        res[0] = diff[0];
        for (int i = 1; i < diff.size(); i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

3. 滑动窗口

相关题目：

  1. 最⼩覆盖⼦串（困难）

  2. 字符串的排列（中等）

  3. 找到字符串中所有字⺟异位词（中等）

  4. ⽆重复字符的最⻓⼦串（中等）

滑动窗⼝算法的代码框架：

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
/* 滑动窗⼝算法框架 */
void slidingWindow(string s, string t) {
	unordered_map<char, int> need, window;	
    for (char c : t) need[c]++;
 	int left = 0, right = 0;	
    int valid = 0; 
	while (right < s.size()) {
		// c 是将移⼊窗⼝的字符
		char c = s[right];
		// 右移窗⼝
		right++;
		// 进⾏窗⼝内数据的⼀系列更新
		 ...
		/*** debug 输出的位置 ***/
		printf("window: [%d, %d)\n", left, right);
		/********************/
 
		// 判断左侧窗⼝是否要收缩
		while (window needs shrink) {
 		// d 是将移出窗⼝的字符
 		char d = s[left];
 		// 左移窗⼝
 		left++;
 		// 进⾏窗⼝内数据的⼀系列更新
 		...
 		}
	}
}

4. 二分搜索

相关题目：

  1. ⼆分查找（简单）

  2. 在排序数组中查找元素的第⼀个和最后⼀个位置（中等）

搜索一个元素，搜索区间两端闭，while带等号

搜索左右边界，左闭右开常用，while用小于号

零、二分查找框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(vector<int> nums, int target) {
    int left = 0, right = ...;
    while(...) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            ...
        } else if {
            left = ...
        } else if {
            right = ...
        }
    }
    return ...;
}

分析⼆分查找的⼀个技巧是：不要出现 else，⽽是把所有情况⽤ else if 写清楚，这样可以清楚地展现所有细节。

寻找一个数：存在返回其索引，不存在返回-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int binarySearch(vector<int> nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            return mid;
        }
        else if(nums[mid] < target) {
            left = mid + 1;
        }
        else if(nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

寻找左侧边界的二分搜索：

左闭右开区间写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int left_bound(vector<int> nums, int target) {
    if(nums.size() == 0) return -1;
    int left = 0;
    int right = nums.size();
    
    while(left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if(nums[mid] < target) {
            left = mid + 1;
        } else if(nums[mid] > target) {
            right = mid;
        }
    }
    // target ⽐所有数都⼤
    if (left == nums.length) return -1;
    // 类似之前算法的处理⽅式
	return nums[left] == target ? left : -1;
}

全闭区间写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int left_bound(vector<int> nums, int target) {
    int left = 0, right = nums.size() - 1;
    //搜索区间为[left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if(nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if(nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if(left >= nums.size() || nums[left] != target) {
        return -1;
    }
    return left;
}

寻找右侧边界的⼆分查找:

左闭右开写法（常见）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int right_bound(vector<int> nums, int target) {
    if(nums.size() == 0) return -1;
    int left = 0;
    int right = nums.size();
    
    while(left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1;  // 注意
        } else if(nums[mid] < target) {
            left = mid + 1;
        } else if(nums[mid] > target) {
            right = mid;
        }
    }
	if (left == 0) return -1;
	return nums[left-1] == target ? (left-1) : -1;
}

全闭区间写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int right_bound(vector<int> nums, int target) {
    int left = 0, right = nums.size() - 1;
    //搜索区间为[left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if(nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if(nums[mid] == target) {
            // 收缩左侧边界
            left = mid + 1;
        }
    }
    // 检查出界情况
    if(right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}

建议搜索区间全都统⼀成了两端都闭，便于记忆，只要修改两处即可变化出三种写法

5. 原地修改数组

相关题目：

  1. 删除有序数组中的重复项（简单）

  2. 删除排序链表中的重复元素（简单）

  3. 移除元素（简单）

  4. 移动零（简单）

有序数组/链表去重

通⽤解法：快慢指针技巧

有序数组去重：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int removeDuplicates(vector<int> nums) {
    if (nums.size() == 0) return 0;
    int slow = 0, fast = 0;
    while (fast < nums.size()) {
        if (nums[fast] != num[slow]) {
            slow++;
            // 维护 nums[0..slow] ⽆重复
            num[slow] = num[fast];
        }
        fast++;
    }
    // 数组⻓度为索引 + 1
    return slow + 1;
}

有序链表去重：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode deleteDuplicates(ListNode head) {
    if (head == nullptr) return nullptr;
    ListNode slow = head, fast = head;
    while (fast != nullptr) {
        if (fast -> val != slow -> val) {
            // nums[slow] = nums[fast];
            slow -> next = fast;
            // slow++;
            slow = slow -> next;
        }
        // fast++
        fast = fast -> next;
    }
    // 断开与后⾯重复元素的连接
    slow -> next = nullptr;
    return head;
}

数组原地删除元素：

1
2
3
4
5
6
7
8
9
10
11
int removeElement(vector<int> nums, int val) {
    int fast = 0, slow = 0;
    while(fast < nums.size()) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

原地修改，将数组中的所有值为 0 的元素移到数组末尾：

1
2
3
4
5
6
7
8
9
10
11
void moveZeroes(vector<int> nums) {
	// 去除 nums 中的所有 0
	// 返回去除 0 之后的数组⻓度
	int p = removeElement(nums, 0);
	// 将 p 之后的所有元素赋值为 0
	for (; p < nums.length; p++) {
		nums[p] = 0;
	}
}
// ⻅上⽂代码实现
int removeElement(vector<int> nums, int val);

6. 单链表

相关题目：

  1. 合并两个有序链表（简单）

  2. 合并K个升序链表（困难）

  3. 环形链表（简单）

  4. 环形链表 II（中等）

  5. 链表的中间结点（简单）

  6. 相交链表（简单）

  7. 删除链表的倒数第 N 个结点（中等）

合并两个有序链表

给定输⼊两个有序链表，把他俩合并成⼀个新的有序链表。

输入：l1 = [1, 2, 4], l2 = [1, 3, 4]

输出：[1, 1, 2, 3, 4, 4]

解法：设立虚拟头节点dummy，避免处理空指针

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
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 虚拟头结点
    ListNode* dummy = new ListNode(-1), *p = dummy;
    ListNode* p1 = l1, *p2 = l2;
    while(p1 != nullptr && p2 != nullptr) {
        // ⽐较 p1 和 p2 两个指针
 		// 将值较⼩的的节点接到 p 指针
        if(p1 -> val > p2 -> val) {
            p -> next = p2;
            p2 = p2 -> next;
        } else {
            p -> next = p1;
            p1 = p1 -> next;
        }
        // p 指针不断前进
        p = p -> next;
    }
    
    if(p1 != nullptr) {
        p -> next = p1;
    }
    
    if(p2 != nullptr) {
        p -> next = p2;
    }
    
    return dummy -> next;
}

合并k个升序链表

给定输⼊k个有序链表，把他们合并成⼀个新的有序链表。

输入：lists = [[1, 4, 5], [1, 3, 4], [2, 6]]

输出：[1, 1, 2, 3, 4, 4, 5, 6]

解法：优先级队列（二叉堆），把链表节点放⼊⼀个最⼩堆，就可以每次获得 k 个节点中的最⼩节点

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
class Solution {
private:
    struct Node {
        int val = 0;
        ListNode* p = nullptr;
        bool operator < (const Node & n) const{
            return n.val < val;
        }
    };
    // 优先级队列，最⼩堆
    priority_queue<Node> pq;
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;
        // 虚拟头结点
        ListNode* dummy = new ListNode(-1), *p = dummy;

        //将 k 个链表的头结点加⼊最⼩堆
        for(auto head : lists) {
            if(head != nullptr) {
                pq.push({head -> val, head});
            }
        }
        while (!pq.empty()) {
            // 获取最⼩节点，接到结果链表中
            ListNode* node = pq.top().p;
            pq.pop();
            p -> next = node;
            if(node -> next != nullptr) {
                pq.push({node -> next -> val, node -> next});
            }
            // p 指针不断前进
            p = p -> next;
        }
        return dummy -> next;
    }
};

单链表的倒数第k个节点

要点：只遍历⼀次链表，就算出倒数第 k 个节点

image-20220314210806020

指针p1指向head节点，开始走k步；

image-20220314211006249

指针p2指向head节点，p1和p2同时走，n-k步后p1走到链表末尾空指针结束，返回p2即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* findFromEnd(ListNode* head, int k) {
    ListNode* p1 = head;
    // p1 先⾛ k 步
    for (int i = 0; i < k; i++) {
        p1 = p1 -> next;
    }
    ListNode* p2 = head;
    // p1 和 p2 同时⾛ n - k 步
    while(p1 != nullptr) {
        p2 = p2 -> next;
        p1 = p1 -> next;
    }
    // p2 现在指向第 n - k 个节点
    return p2;
}

单链表中点

解法：让两个指针 slow 和 fast 分别指向链表头结点 head。 每当慢指针 slow 前进⼀步，快指针 fast 就前进两步，这样，当 fast ⾛到链表末尾时，slow 就指向了链 表中点。 

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* middleNode(ListNode* head) {
    // 快慢指针初始化指向 head
 	ListNode* slow = head, *fast = head;
 	// 快指针⾛到末尾时停⽌
    while(fast != nullptr && fast -> next != nullptr) {
        // 慢指针⾛⼀步，快指针⾛两步
 		slow = slow -> next;
 		fast = fast -> next -> next;
    }
    // 慢指针指向中点
    return slow;
}

注意：如果链表⻓度为偶数，也就是说中点有两个的时候，这个解法返回的节点是靠后的那个节点。

判断链表是否包含环

解法：快慢指针，每当慢指针 slow 前进⼀步，快指针 fast 就前进两步，如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和slow相遇，那肯定是 fast 超过了slow ⼀圈，说明链表中含有环。

只需要把寻找链表中点的代码稍加修改：

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
bool hasCycle(ListNode* head) {
    // 快慢指针初始化指向 head
 	ListNode* slow = head, *fast = head;
 	// 快指针⾛到末尾时停⽌
    while(fast != nullptr && fast -> next != nullptr) {
        // 慢指针⾛⼀步，快指针⾛两步
 		slow = slow -> next;
 		fast = fast -> next -> next;
        // 快慢指针相遇，说明含有环
        if(slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

/*计算环的起点*/
ListNode* detectCycle(ListNode* head) {
    ListNode* fast = head, *slow = head;
    while(fast != nullptr && fast -> next != nullptr) {
        slow = slow -> next;
 		fast = fast -> next -> next;
        // 快慢指针相遇，说明含有环
        if(slow == fast) break;
    }
    if (fast == nullptr || fast -> next == nullptr) {
 		// fast 遇到空指针说明没有环
 		return nullptr;
 	}
    // 重新指向头结点
	 slow = head;
 	// 快慢指针同步前进，相交点就是环起点
 	while (slow != fast) {
 		fast = fast -> next;
     	slow = slow -> next;
    }
    return slow;
    
}

两个链表是否相交

输⼊两个链表的头结点headA和 headB，这两个链表可能存在相交。如果相交，应该返回相交的那个节点；如果没相交，则返回 nullptr。

解法：可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相 当于「逻辑上」两条链表接在了⼀起。让 p1 和 p2 同时进⼊公共部分，也就是同时到达相交节点 c1

image-20220315104422008 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    ListNode* p1 = headA, *p2 = headB;
    while(p1 != p2) {
        // p1 ⾛⼀步，如果⾛到 A 链表末尾，转到 B 链表
        if(p1 == nullptr) {
            p1 = headB;
        } else {
            p1 = p1 -> next;
        }
        // p2 ⾛⼀步，如果⾛到 B 链表末尾，转到 A 链表
        if(p2 == nullptr) {
            p2 = headA;
        } else {
            p2 = p2 -> next;
        }
    }
    return p1;
}

7. 链表操作的递归实现

相关题目：

  1. 反转链表（简单）

  2. 反转链表II（中等）

递归反转整个链表

输⼊⼀个节点 head，将以head为起点的链表反转，并返回反转之后的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* reverse(ListNode* head) {
    //递归函数base case，如果链表只有⼀个节点的时候，直接返回即可
    if (head == nullptr || head -> next == nullptr) {
        return head;
    }
    //新的头结点是last, 将head之后部分反转
    ListNode* last = reverse(head -> next);
    head -> next -> next = head;
    //head 变成了最后⼀个节点，别忘了链表的末尾要指向 null
    head -> next = nullptr;
    return last;
}

反转链表前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
ListNode* successor = nullptr; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode* reverseN(ListNode* head, int n) {
	if (n == 1) {
 		// 记录第 n + 1 个节点
 		successor = head -> next;
 		return head;
 	}
 	// 以 head.next 为起点，需要反转前 n - 1 个节点
 	ListNode* last = reverseN(head -> next, n - 1);
 	head -> next -> next = head;
	// 让反转之后的 head 节点和后⾯的节点连起来
 	head -> next = successor;
 	return last;
}

//反转链表的任意区间[left, right]
ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (left == 1) return reverseN(head, right);
    head -> next = reverseBetween(head -> next, left - 1, right - 1);
    return head;
}

反转链表的一部分

给⼀个索引区间 [left, right]（索引从 1 开始），仅仅反转区间中的链表元素。

1
2
3
4
5
6
7
8
9
//接上部分反转链表代码
//反转链表的任意区间[left, right]
ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (left == 1) return reverseN(head, right);
    // 前进到反转的起点触发 base case
    head -> next = reverseBetween(head -> next, left - 1, right - 1);
    return head;
}