【算法优选】双指针专题——贰

这篇具有很好参考价值的文章主要介绍了【算法优选】双指针专题——贰。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

😎前言

常⻅的双指针有两种形式,⼀种是对撞指针,⼀种是左右指针
对撞指针:⼀般⽤于顺序结构中,也称左右指针。

  • 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。

  • 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能在循环内部找到结果直接跳出循环),也就是:

left == right (两个指针指向同⼀个位置)
left > right (两个指针错开)

快慢指针:⼜称为⻳兔赛跑算法,其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。

这种⽅法对于处理环形链表或数组⾮常有⽤。其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,均可考虑使⽤快慢指针的思想。快慢指针的实现⽅式有很多种,最常⽤的⼀种就是:

  • 在⼀次循环中,每次让慢的指针向后移动⼀位,⽽快的指针往后移动两位,实现⼀快⼀慢

🌲快乐数

🚩题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1,那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

  • 示例 1:
    输入:n = 19
    输出:true
    解释:
    12 + 92 = 82
    82 + 22 = 68
    62 + 82 = 100
    12 + 02 + 02 = 1

  • 示例 2:
    输入:n = 2
    输出:false
    解释:(这⾥省去计算过程,只列出转换后的数)
    2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16
    往后就不必再计算了,因为出现了重复的数字,最后结果肯定不会是 1

class Solution {
    public boolean isHappy(int n) {

    }
}

🚩题⽬分析:

为了⽅便叙述,将「对于⼀个正整数,每⼀次将该数替换为它每个位置上的数字的平⽅和」这⼀个操作记为x 操作;
题⽬告诉我们,当我们不断重复 x 操作的时候,计算⼀定会「死循环」,死的⽅式有两种:

  • 情况⼀:⼀直在1 中死循环,即1 -> 1 -> 1 -> 1…
  • 情况⼆:在历史的数据中死循环,但始终变不到1

由于上述两种情况只会出现⼀种,因此,只要我们能确定循环是在「情况⼀」中进⾏,还是在「情况⼆」中进⾏,就能得到结果

简单证明:

  1. 经过⼀次变化之后的最⼤值 9^2 * 10 = 810 ( 2^31-1=2147483647 。选⼀个更⼤的最⼤ 9999999999),也就是变化的区间在 [1, 810] 之间;

  2. 根据「鸽巢原理」,⼀个数变化 811 次之后,必然会形成⼀个循环;

  3. 因此,变化的过程最终会⾛到⼀个圈⾥⾯,因此可以⽤「快慢指针」来解决

🚩算法思路:

根据上述的题⽬分析,我们可以知道,当重复执⾏ x 的时候,数据会陷⼊到⼀个「循环」之中。⽽「快慢指针」有⼀个特性,就是在⼀个圆圈中,快指针总是会追上慢指针的,也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是 1,那么这个数⼀定是快乐数;如果相遇位置不是 1 的话,那么就不是快乐数

补充知识:
如何求⼀个数n每个位置上的数字的平⽅和。

  1. 把数 n 每⼀位的数提取出来:
    循环迭代下⾯步骤:

int t = n % 10 提取个位;
n /= 10 ⼲掉个位;

直到 n 的值变为 0 ;

  1. 提取每⼀位的时候,⽤⼀个变量 tmp 记录这⼀位的平⽅与之前提取位数的平⽅和

tmp = tmp + t * t

🚩代码实现:

class Solution
{
    // 返回 n 这个数每⼀位上的平⽅和
    public int bitSum(int n) {
        int sum = 0;
        while(n != 0) {
            int t = n % 10;
            sum += t * t;
            n /= 10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        int slow = n;
        int fast = bitSum(n);
        while(slow != fast) {
            //走一步
            slow = bitSum(slow);
            //走两步
            fast = bitSum(bitSum(fast));
        }
        return slow == 1;
    }
}

🎋盛水最多的容器

🚩题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

  • 示例 1:
    输入:[1,8,6,2,5,4,8,3,7]
    输出:49
    【算法优选】双指针专题——贰,算法优选,算法,java,力扣,双指针解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

  • 示例 2:
    输入:height = [1,1]
    输出:1

class Solution {
    public int maxArea(int[] height) {

    }
}

🚩算法思路:

设两个指针 left , right 分别指向容器的左右两个端点,此时容器的容积

v = (right - left) * min( height[right], height[left])

容器的左边界为 height[left] ,右边界为 height[right] 。为了⽅便叙述,我们假设「左边边界」⼩于「右边边界」。

如果此时我们固定⼀个边界,改变另⼀个边界,⽔的容积会有如下变化形式:

  • 容器的宽度⼀定变⼩。

  • 由于左边界较⼩,决定了⽔的⾼度。如果改变左边界,新的⽔⾯⾼度不确定,但是⼀定不会超过右边的柱⼦⾼度,因此容器的容积可能会增⼤。

  • 如果改变右边界,⽆论右边界移动到哪⾥,新的⽔⾯的⾼度⼀定不会超过左边界,也就是不会超过现在的⽔⾯⾼度,但是由于容器的宽度减⼩,因此容器的容积⼀定会变⼩的。

由此可⻅,左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界,继续去判断下⼀个左右边界。

当我们不断重复上述过程,每次都可以舍去⼤量不必要的枚举过程,直到 left 与 right 相遇。期间产⽣的所有的容积⾥⾯的最⼤值,就是最终答案

🚩代码实现

public class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, ret = 0;
        while(left < right) {
            int v = Math.min(height[left], height[right]) * (right - left);
            ret = Math.max(ret, v);
            if(height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return ret;
    }
}

🎍有效三角形个数

🚩题目描述

给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。

  • 示例 1:
    输入: nums = [2,2,3,4]
    输出: 3
    解释:有效的组合是:
    2,3,4 (使用第一个 2)
    2,3,4 (使用第二个 2)
    2,2,3

  • 示例 2:
    输入: nums = [4,2,3,4]
    输出: 4

class Solution {
    public int triangleNumber(int[] nums) {

    }
}

🚩算法思路:

先将数组排序。我们固定⼀个「最⻓边」,然后在⽐这条边⼩的有序数组中找
出⼀个⼆元组,使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的,我们可以利⽤「对撞指针」来优化。
设最⻓边枚举到 i 位置,区间 [left, right] 是 i 位置左边的区间(也就是⽐它⼩的区
间):

  • 如果 nums[left] + nums[right] > nums[i] :

▪ 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐ nums[i]⼤的⼆元组
▪ 满⾜条件的有right - left 种
▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕,right-- ,进⼊下⼀轮判断

  • 如果 nums[left] + nums[right] <= nums[i] :

▪ 说明 left 位置的元素是不可能与 [left + 1, right] =位置上的元素构成满⾜条件 的⼆元组
▪ left 位置的元素可以舍去, left++ 进⼊下轮循环

🚩代码实现:

class Solution {
    public int triangleNumber(int[] nums) {
        // 1. 优化:排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int ret = 0, n = nums.length;
        // 先固定最⼤的数
        for(int i = n - 1; i >= 2; i--)  {
            // 利⽤双指针快速统计出符合要求的三元组的个数
            int left = 0;
            int right = i - 1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[i]) {
                    ret += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
}

⭕总结

关于《【算法优选】双指针专题——贰》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!一起加油文章来源地址https://www.toymoban.com/news/detail-720798.html

到了这里,关于【算法优选】双指针专题——贰的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法优选】 滑动窗口专题——壹

    基本概念 滑动窗口是一种 基于双指针 的一种思想,两个指针指向的元素之间形成一个窗口。 分类:窗口有两类,一种是 固定大小类 的窗口,一类是 大小动态变化 的窗口。 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长

    2024年02月08日
    浏览(41)
  • 【算法优选】 二分查找专题——壹

    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用 顺序存储结构 ,而且表中元素按 有序排列 。 查找过程 : 首先,假设表中元素是按升序排列,将表中间位置记录的与查找比较,如果两者相等,

    2024年02月08日
    浏览(47)
  • 【算法优选】 二分查找专题——贰

    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用 顺序存储结构 ,而且表中元素按 有序排列 。 查找过程 : 首先,假设表中元素是按升序排列,将表中间位置记录的与查找比较,如果两者相等,

    2024年02月08日
    浏览(44)
  • 【算法优选】前缀和专题——叁

    含义 : 前缀和实际上就是对于长度为n的数组, 我们新建立一个数组长度为n+1,第i个元素的值为前i个元素的和(包括第i个元素) 。 特点 : 前缀和数组比原数组多一个长度。 前缀和的第0个元素的值为0。 根据前缀和数组的特点,求前缀和时。我们只需要用第i个元素的值

    2024年02月06日
    浏览(44)
  • 【算法优选】 前缀和专题——壹

    含义 : 前缀和实际上就是对于长度为n的数组, 我们新建立一个数组长度为n+1,第i个元素的值为前i个元素的和(包括第i个元素) 。 特点 : 前缀和数组比原数组多一个长度。 前缀和的第0个元素的值为0。 根据前缀和数组的特点,求前缀和时。我们只需要用第i个元素的值

    2024年02月08日
    浏览(39)
  • 【算法优选】 滑动窗口专题——贰

    基本概念 滑动窗口是一种 基于双指针 的一种思想,两个指针指向的元素之间形成一个窗口。 分类:窗口有两类,一种是 固定大小类 的窗口,一类是 大小动态变化 的窗口。 你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fru

    2024年02月08日
    浏览(48)
  • 【优选算法专栏】专题十:哈希表(一)

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:算法从入门到精通 🚚代码仓库:小小unicorn的代码仓库

    2024年04月13日
    浏览(35)
  • 【优选算法专栏】专题九:链表--------两数之和

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:算法从入门到精通 🚚代码仓库:小小unicorn的代码仓库

    2024年02月21日
    浏览(50)
  • 【优选算法】—— 双指针问题

    从今天开始,整个暑假期间。我将不定期给大家带来有关各种算法的题目,帮助大家攻克面试过程中可能会遇到的算法这一道难关。 目录 (一) 基本概念 (二)题目讲解 1、难度:easy 1️⃣移动零 2️⃣复写零 2、难度:medium 1️⃣快乐数 2️⃣盛⽔最多的容器 3、难度:di

    2024年02月13日
    浏览(25)
  • 大厂算法指南:优选算法 ——双指针篇(上)

    📕作者简介:非科班在读,纯技术博客分享,致力于C/C++,涉及Python、C/C++、Linux,数据结构,git企业级开发,Mysql等。 📗本文收录于算法指南,旨在帮助读者应对各大互联网大厂笔试题,构建完整的算法体系! 📘相关专栏C语言、C++、数据结构、Linux、前言科技喜欢C/C++/Linu

    2024年02月04日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包