【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器

这篇具有很好参考价值的文章主要介绍了【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器,算法挨揍日记,Leetcode,算法,c++,职场和发展

 202. 快乐数 

202. 快乐数https://leetcode.cn/problems/happy-number/

题目:

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

「快乐数」 定义为:

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

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

【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器,算法挨揍日记,Leetcode,算法,c++,职场和发展

 解题思路:

 我们先通过这两个测试用例来看看是什么情况

【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器,算法挨揍日记,Leetcode,算法,c++,职场和发展

 我们发现不管是19还是2都会形成一个环状结构(19的环状结构内都是1)

那这样我们就可以使用快慢指针来操作!!!

定义一个slow和fast,slow一次走一步,fast一次走两步

他们一定会相遇的,只不过相遇的时候会有两种情况,相遇的数是1或者不是1

那为什么一定会形成环状结构呢?我们来简单论证一下!

鸽巢原理:就是当n个巢穴,n+1个鸽子的时候,一定至少有一个巢穴的鸽子>1

我们注意一下n的范围,n最大为2的31次方,也就是2亿多(10位数),那我们将它放大10个9(也就是最大的那个10位数,我懒得打9了),也就是说,它最多就是10个9,经过f操作最大就是9^2*10=810,也就是相当于我们最多有810个位置,我们处理813次的f,肯定会有重复的数出现!

那同理:

【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器,算法挨揍日记,Leetcode,算法,c++,职场和发展

 

解题代码:

class Solution {
public:
    int f(int n)
    {
        int arr[11] = { 0 };
        int i = 1;
        for (int i = 1; i < 11; ++i)
        {
            if (n < 10)
            {
                arr[i] = n;
                break;
            }
            arr[i] = n % 10;
            n = n / 10;
        }
        int x = 0;
        for (int i = 1; i < 11; ++i)
        {
            x += (arr[i] * arr[i]);
        }
        return x;
    }
    bool isHappy(int n) {
        //快慢双指针
        int slow = n;
        int fast = n;
        //更新slow和fast
        slow = f(slow);
        fast = f(fast);
        fast = f(fast);
        if (slow == fast && slow == 1)return true;
        while (slow != fast)
        {
            //更新slow和fast
            slow = f(slow);
            fast = f(fast);
            fast = f(fast);
        }
        if (slow == 1)
            return true;
        else
            return false;
    }
};

11. 盛最多水的容器

11. 盛最多水的容器https://leetcode.cn/problems/container-with-most-water/

题目描述:

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

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

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

说明:你不能倾斜容器。

【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器,算法挨揍日记,Leetcode,算法,c++,职场和发展

解题思路:

体积V=h*w,当我们利用双指针从左右两边向中间逼近,w一定是减小的,只有当h增大才可能增大

解题代码:

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

 

 文章来源地址https://www.toymoban.com/news/detail-664913.html

到了这里,关于【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【算法——双指针】LeetCode 11 盛最多水的容器

    题目描述: 解题思路:         如图所示:         1、我们考虑相距最远的两个柱子所能容纳水的面积。宽度是两根柱子之间的距离8;高度取决于两根柱子之间较短的那个,即左边柱子的高度3。水的面积就是3×8=24。         2、如果选择固定一根柱子,另外一根

    2024年02月12日
    浏览(32)
  • 【算法专题突破】双指针 - 盛最多水的容器(4)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:11. 盛最多水的容器 - 力扣(Leetcode)   这道题目也不难理解, 两边的柱子的盛水量是根据短的那边的柱子决定的, 而盛水量就是短的柱子的高度 * 宽度即可。  这道题可以用暴力枚举,两层for循环,肯定是可

    2024年02月10日
    浏览(37)
  • 【算法|双指针系列No.4】leetcode11. 盛最多水的容器

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(48)
  • 【算法挨揍日记】day01——双指针算法_移动零、 复写零

    283. 移动零 https://leetcode.cn/problems/move-zeroes/ 题目: 给定一个数组  nums ,编写一个函数将所有  0  移动到数组的末尾,同时保持非零元素的相对顺序。 请注意  ,必须在不复制数组的情况下原地对数组进行操作。    解题思路: 我们可以利用两个指针(dest和cur)的方法,

    2024年02月11日
    浏览(33)
  • 【算法】双指针——leetcode盛最多水的容器、剑指Offer57和为s的两个数字

    盛水最多的容器 (1)暴力解法   算法思路:我们枚举出所有的容器大小,取最大值即可。   容器容积的计算方式:   设两指针 i , j ,分别指向水槽板的最左端以及最右端,此时容器的宽度为 j - i 。由于容器的高度由两板中的较短的板决定,因此可得容积公式 :

    2024年02月13日
    浏览(48)
  • 【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字

       611. 有效三角形的个数 https://leetcode.cn/problems/valid-triangle-number/ 给定一个包含非负整数的数组  nums  ,返回其中可以组成三角形三条边的三元组个数。 本题是一个关于三角形是否能成立的题目,首先我们假设三角形的三边(a,b,c),我们要保证两边之和大于第三边    题

    2024年02月12日
    浏览(47)
  • 「优选算法刷题」:盛最多水的容器

    给定一个长度为  n  的整数数组  height  。有  n  条垂线,第  i  条线的两个端点是  (i, 0)  和  (i, height[i])  。 找出其中的两条线,使得它们与  x  轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明: 你不能倾斜容器。 示例 1: 示例 2: 这道

    2024年01月19日
    浏览(60)
  • 【力扣算法12】之 11. 盛最多水的容器 python

    给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明 :你不能倾斜容器。 输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂

    2024年02月16日
    浏览(48)
  • 【算法挨揍日记】day16——525. 连续数组、1314. 矩阵区域和

    525. 连续数组 给定一个二进制数组  nums  , 找到含有相同数量的  0  和  1  的最长连续子数组,并返回该子数组的长度。 本题的元素只有0和1,根据题目意思,我们可以把题目看成找一段最长的子区间使得区间的0 和1的数量相同,我们可以对其优化将所有的0变成-1,这样这

    2024年02月03日
    浏览(48)
  • 【算法挨揍日记】day04——15. 三数之和、18. 四数之和

      15. 三数之和 https://leetcode.cn/problems/3sum/ 给你一个整数数组  nums  ,判断是否存在三元组  [nums[i], nums[j], nums[k]]  满足  i != j 、 i != k  且  j != k  ,同时还满足  nums[i] + nums[j] + nums[k] == 0  。请你返回所有和为  0  且不重复的三元组。 注意: 答案中不可以包含重复的三元

    2024年02月09日
    浏览(55)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包