剑指offer -- 双指针

发表于 | 分类于
字数统计: 2.9k | 阅读时长 ≈ 12
马纳罗拉 -- 意大利

剑指offer – 双指针

剑指 Offer 18. 删除链表的节点

Difficulty: 简单

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

**注意：**此题对比原题有改动

示例 1:

1
2
3
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

1
2
3
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

  • 题目保证链表中节点的值互不相同
  • 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        // 如果要删除的节点是头节点
        if (head->val == val) return head->next;
        while (head->next->val != val) {
            head = head->next;
        }
        head->next = head->next->next;
        return dummy->next;
    }
};

时间复杂度： $O(N)$ ，N 为链表长度，删除操作平均需循环 N/2 次，最差 N 次。
空间复杂度： $O(1)$ ， dummy 占用常数大小额外空间。

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

Difficulty: 简单

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

1
2
3
输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

提示：

  1. 0 <= nums.length <= 50000
  2. 1 <= nums[i] <= 10000

Solution

方法一：非原地

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        int left = 0, right = n - 1;
        
        for (int i = 0; i < n; i++) {
            // 如果是奇数往左侧放置
            if (nums[i] % 2) {
                res[left] = nums[i];
                left++; // 指针右移
            }
            // 如果是偶数往右侧放置 
            else {
                res[right] = nums[i];
                right--; // 指针左移
            }
            // 循环退出条件
            if (left > right) break;
        }
        return res;
    }
};

时间复杂度： $O(N)$ ，N 为nums数组长度。
空间复杂度： $O(N)$ ， res 占用nums相同大小空间。

方法二：原地

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> exchange(vector<int>& nums)
    {
        int i = 0, j = nums.size() - 1;
        // 该方法的 while 循环操作与 快速排序的 partition 求取 pivot 过程相似
        while (i < j)
        {
            while(i < j && (nums[i] & 1) == 1) i++;
            while(i < j && (nums[j] & 1) == 0) j--;
            swap(nums[i], nums[j]);
        }
        return nums;
    }
};

**关键算法思路**可以参考 快速排序 算法中 partition 求取 pivot 过程。

时间复杂度： $O(N)$ ，N 为 nums 数组长度。
空间复杂度： $O(1)$ ， 原地交换操作，无额外消耗。

剑指 Offer 22. 链表中倒数第K个节点

Difficulty: 简单

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

1
2
3
给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

Solution

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        // 先让 head 向前移动 k 步骤
        while (k--) {
            head = head->next;
        }
        // 然后 dummy 与 head 同时移动，直到 head 到链表尾部，
        // 此时 dummy 指向的位置就是所需的位置
        while (head) {
            dummy = dummy->next;
            head = head->next;
        }
        return dummy->next;
    }
};

时间复杂度：$O(N) $ ， N 为链表长度；总体看， head 走了 N 步， dummy 走了 (N−k) 步。
空间复杂度： $O(1)$ ， dummy 使用常数大小的额外空间。

剑指 Offer 25. 合并两个排序的链表

Difficulty: 简单

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

Solution

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* res = new ListNode(0);
        ListNode* cur = res;
        // 如果 l1 为空节点，直接返回 l2
        if (!l1) return l2;
        // 如果 l2 为空节点，直接返回 l1
        else if (!l2) return l1;
        else {
            // l1 和 l2 都不是空的情况下，判断val
            while (l1 && l2) {
                // 如果 l2 val 更小则，先链接 l2
                if (l1->val > l2->val) {
                    cur->next = l2;
                    cur = cur->next;
                    l2 = l2->next;
                }
                // 如果 l1 val 更小则，先链接 l1 
                else {
                    cur->next = l1;
                    cur = cur->next;
                    l1 = l1->next;
                }
            }
            // 此时最后拼接上多余的节点
            cur->next = (!l1 ? l2 : l1);
        }
        return res->next;
    }
};

时间复杂度：$O(M + N) $ ， M 为 l1 长度， N 为 l2 长度
空间复杂度： $O(1)$ ， res，cur 使用常数大小的额外空间。

剑指 Offer 52. 两个链表的第一个公共节点

Difficulty: 简单

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表**：**

在节点 c1 开始相交。

示例 1：

1
2
3
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

1
2
3
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

1
2
3
4
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

  • 如果两个链表没有交点，返回 null.
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    	ListNode* A = headA, *B = headB;
        // 如果有相交点，则会在 A == B 时候返回
        // 如果没有相交点，也会 A = nullptr = B 时返回
        while (A != B) {
            // 如果 A 为 nullptr 时，将 A 指向 headB,否则 A 向后遍历
            A = !A ? headB : A->next;
            // 如果 B 为 nullptr 时，将 B 指向 headA,否则 B 向后遍历
            B = !B ? headA : B->next;
        }
        return A;
    }
};

时间复杂度：$O(M + N) $ ， M 为 l1 长度， N 为 l2 长度
空间复杂度： $O(1)$ ， A，B 使用常数大小的额外空间。

剑指 Offer 57. 和为s的两个数字

Difficulty: 简单

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

1
2
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：

1
2
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

Solution

方法一：哈希表（同两数之和）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // if (nums.size() <= 1) return {};
        unordered_set<int> set;
        for (const auto& num : nums) {
            int toFind = target - num;
            if (set.find(toFind) != set.end()) {
                return vector<int> {toFind, num};
            }
            set.insert(num);
        }
        return {};
    }
};

时间复杂度：$O(N) $ ，N 为数组长度。
空间复杂度： $O(N)$ ， 哈希表额外空间。

方法二：双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 双指针
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1;
        // 类同于二分查找
        while (left != right) {
            if (target > nums[left] + nums[right]) {
                left++;
            } else if (target < nums[left] + nums[right]) {
                right--;
            } else {
                return {nums[left], nums[right]};
            }
        }
        return {};
    }
};

时间复杂度：$O(N) $ ，N 为数组长度。
空间复杂度： $O(1)$ ， 无额外空间消耗。

剑指 Offer 58 - I. 翻转单词顺序

Difficulty: 简单

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。

示例 1：

1
2
输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

1
2
3
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

1
2
3
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

Solution

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
class Solution {
public:
    string reverseWords(string s) {
        // 反转整个字符串
        reverse(s.begin(), s.end());

        int n = s.size();
        int idx = 0;  // 用来指示单词位置
        for (int start = 0; start < n; ++start) {
            // 删除字符串前部分的空格
            if (s[start] != ' ') {
                // 填一个空白字符然后将idx移动到下一个单词的开头位置
                if (idx != 0) s[idx++] = ' ';

                // 循环遍历至单词的末尾
                int end = start;	// idx 从 0 开始计数， end 从 start 开始计数
                while (end < n && s[end] != ' ') s[idx++] = s[end++];

                // 反转整个单词
                reverse(s.begin() + idx - (end - start), s.begin() + idx);

                // 更新start，去找下一个单词
                start = end;
            }
        }
        // 删除最后的连续空格
        s.erase(s.begin() + idx, s.end());
        return s;
    }
};

时间复杂度： $O(N)$，N 为字符串长度

空间复杂度： $O(1)$，idx，start, end 使用常数大小的额外空间。

参考资料

图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com) 官方题解



----------- 本文结束 -----------




0%