您现在的位置是:首页 > 正文

「双指针技巧解决一些数组问题」

2024-02-01 00:05:28阅读 2

0 分类

双指针分类为快慢指针,左右指针。左右指针,两个指针相向/背而行;快慢指针则是同向而行,一快一慢。

单链表很多都是快慢指针,之前已经写出过。

这次来看看双指针解决数组问题,另一大类的滑动窗口下次再说。

1 快慢指针刷题

1.1 删除有序数组中的重复项

在这里插入图片描述

题解

因为要原地修改数组,所以不能使用new一个新数组的方法,所以直接双指针技巧,一个慢指针slow,一个快指针fast,fast相当于在前面探路,当找到一个不重复的元素就赋值给slow,并且让slow往前走一步,这样进行原地修改即可,最后返回个数,因为是0~slow都是不重复的,所以个数应该是slow+1。

Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0)
        {
            return 0;
        }
        int slow = 0, fast = 0;
        while (fast < nums.size())
        {
            if (nums[slow] != nums[fast])
            {
                ++slow;//移动到下一个坑位存储
                nums[slow] = nums[fast];
            }
            ++fast;
        }
        return slow + 1;//因为slow是从下标0开始的,所以要返回slow+1
    }
};

结果

在这里插入图片描述

1.2 删除排序链表中的重复元素

在这里插入图片描述

题解

其实将上述的方法拓展到链表中即可,还是快慢指针的技巧,一个快指针在前面探路,然后有不重复的直接把slow->next = fast即可。

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return head;
        ListNode *slow = head, *fast = head;
        while (fast != nullptr)
        {
            if (fast->val != slow->val)
            {
                slow->next = fast;
                slow = slow->next;
            }
            fast = fast->next;
        }
        slow->next = nullptr;//最后断开重复的
        return head;
    }
};

结果

在这里插入图片描述

1.3 移除元素

在这里插入图片描述

题解

与第一题删除重复元素差不多,还是快慢指针的思路。

Code

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //int size = nums.size();
        int slow = 0, fast = 0;
        while (fast < nums.size())
        {
            if (nums[fast] != val)
            {
                nums[slow] = nums[fast];//这样就使得从0~slow这个区间,nums是不包含val的
                slow++;
            }
            fast++;
        }
        return slow;//0~slow不包含val,此时返回slow就行,就是个数
    }
};

所以归类出一个删除重复元素的模板:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //int size = nums.size();
        int slow = 0, fast = 0;
        while (fast < nums.size())
        {
            if (nums[fast] != val)
            {
                nums[slow] = nums[fast];//这样就使得从0~slow这个区间,nums是不包含val的
                slow++;
            }
            fast++;
        }
        return slow;//0~slow不包含val,此时返回slow就行,就是个数
    }
};

结果

在这里插入图片描述

1.4 移动0

在这里插入图片描述

题解

采用上述的删除模板,先把0全部删除,之后再进行末尾补0即可。

Code

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int p = removeElement(nums, 0);//去除0之后的数组长度
        for (; p < nums.size(); ++p)
        {
            nums[p] = 0;
        }
    }

    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~slow现在是不包含val的数
    }
};

2 左右指针刷题

2.1 二分查找

记住模板框架即可。

int binarySearch(vector<int> &nums, int target)
{
	sort(nums.begin(), nums.end());
	int left = 0, right = nums.size() - 1;
	while (left < right)
	{
		int mid = (left + right) / 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;
}

2.2 两数之和 II - 输入有序数组

在这里插入图片描述

题解

采用二分查找,具体如下方代码所示。

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //因为数组已经排序好了,所以无需sort
        int left = 0, right = nums.size() - 1;
        int sum = 0;
        vector<int> vec;
        vector<int> res = {-1, -1};
        while (left < right)
        {
            sum = nums[left] + nums[right];
            if (sum == target)
            {
                vec.push_back(left + 1);//下标从1开始,增大下标
                vec.push_back(right + 1);
                return vec;
            }
            if (sum < target)
            {
                ++left;//因为排序好了,小了就移动左指针,大了就移动右指针
            }
            if (sum > target)
            {
                --right;
            }
        }
        return res;
    }
};

结果

在这里插入图片描述

2.3 反转字符串

在这里插入图片描述

题解

直接左右指针边走边进行交换。

Code

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right)
        {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
        return;
    }
};

结果

在这里插入图片描述

2.4 最长回文子串

在这里插入图片描述

题解

难点在于可以是奇数或者是偶数,找回文串应该是从中心上两边进行扩散。也算是一个算法穷举的思路。

Code

class Solution {
public:
    string longestPalindrome(string s) {
        string res = "";
        for(int i = 0; i < s.length(); i++){
            string s1 = findPalindrome(s, i, i);
            string s2 = findPalindrome(s, i, i+1);
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    string findPalindrome(string& s, int l, int r){
        while(l >= 0 && r < s.length() && s[l] == s[r]){
            l--;
            r++;
        }

        return s.substr(l+1, r-l-1); // C++中的子串函数substr(pos, count),第二参数count是子串长度,l+1是因为while最后一次判断的时候减去了1,所以得加回来。然后substr中的pos相当于起点,count相当于长度,长度=right - left - 1(减去1是因为最后while判断的时候right+1)
    }
};

结果

在这里插入图片描述

网站文章

  • cmake 链接已编译好的 *.so 库踩坑总结(一)

    cmake 链接已编译好的 *.so 库采坑总结

    2024-02-01 00:05:22
  • [CF套题] CF-1163

    CF-1163 传送门 # Penalty A B1 B2 C1 C2 D E F 3 (483) 464 +0 0:06 +1 01:13 +3 01:12 + 01:57 + 01:56 A 第一个人离开时候不增加,第二个人离开时候隔一个走开 当m=0时,答案为0 n为偶数时,如果2m&lt;=n那么答案为m,否则为n-m n为奇数时,如果2m&lt;=n那...

    2024-02-01 00:05:16
  • 提升效率!Django 中鲜为人知的内置命令

    提升效率!Django 中鲜为人知的内置命令

    【导语】:在我们使用Django框架开发应用或者网站的过程中,通常会用到许多命令进行管理,例如常用的runserver, makemigrations, migrate, shell等。此外,许多第三方包也提供了一些命令,我们可以在项目中使用这些命令,来简化开发流程。今天我们一起来学习一些有用的新命令。如果你还不熟悉Django,这里有一篇简单易上手的教程。1. diff...

    2024-02-01 00:04:48
  • 过河(动态规划)

    有一条河,河中有n块石头,现在从河的一边只能通过走石头到达对岸,每一步可以跨越至多3个石头。但是不幸的是,有一块石头被上一个过河的人踩松后被踩松了,所以为了安全后来的人就不能再踩这一块石头了。若现在有一个人想要到河的对岸去,他有多少种方法?注:若我们将石头从1到n进行编号的话,那么被踩松的石头编号为k。输入格式:多组输入对于每组输入在一行中给出2个整数n和...

    2024-02-01 00:04:43
  • 小波变换原理

    小波变换原理

    https://www.cnblogs.com/warmbeast/p/7809286.html 从傅里叶变换到小波变换,并不是一个完全抽象的东西,可以讲得很形象。小波变换有着明确的物理意义,如果我们...

    2024-02-01 00:04:35
  • C++:容器的基本功能与分类

    C++:容器的基本功能与分类

    容器的基本功能与分类容器类是容纳、包含一组元素或元素集合的对象。基于容器中元素的组织方式:顺序容器、关联容器按照与容器所关联的迭代器类型划分:可逆容器和随机访问容器容器的基本功能与分类容器unorde...

    2024-02-01 00:04:27
  • 前端安全知识

    前端安全知识

    原文连接 https://jkchao.cn/article/59d... XSS xss: 跨站脚本攻击(Cross Site Scripting)是最常见和基本的攻击 WEB 网站方法,攻击者通过注入非法的 html 标签或者 javascript 代码,从而当用户浏览该网页时,控制用户浏览器。 xss 主要分为三类: DOM x...

    2024-02-01 00:03:57
  • 虚拟服务器 双机,HA双机软件如何使用虚拟(VIP:Virtual IP)

    HA高可用,一般是对外提供一个固定IP地址或者固定域名供用户访问。固定域名方式需要域名解析为对应的ip地址,是一种分布式系统,这个和虚拟ip没关系。固定ip地址访问的方式,这个访问的ip又怎么知道服务...

    2024-02-01 00:03:50
  • visual studio客户端windows模式下调出cmd命令行

    visual studio客户端windows模式下调出cmd命令行

    visual studio 设置技巧

    2024-02-01 00:03:12
  • 关于rpm 命令的--changelog参数

    关于rpm 命令的--changelog参数

    2024-02-01 00:03:06