【算法刷题】Day8

本文介绍: 原题链接](https://leetcode.cn/problem s/container–wi th–most-wa t e r/先看题干，貌似就是求体积，再看示例，就是求两段之间最小的那个值乘两段之间的差值。判断是不是快乐数，就是看入环的数字是几，如果是 1 那么就是快乐数。这样我们可以直接删去 4 ，从 6 开始向 5 进行遍历。利用这样的规律，我们在看原数组，我们就可以这样解题。画完图我们就可以发现，这个跟曾经数据结构学过的。所以如果 4 不变，从右向左一个一个计算体积。拿到题，我们先看题干。

文章 目录

202. 快乐数
11. 盛最多水的容器

202. 快乐数

在这里插入图片描述

原题链接

题干：

拿到题，我们先看题干
把一个整数替换为每个位置上的数字平方和，有两种情况：

重复这个过程始终不到 1（无限死循环）
结果变成 1（快乐数）

接下来我们画图看一下是不是这两种情况
在这里插入图片描述

画完图我们就可以发现，这个跟曾经数据结构学过的判断链表是否有环非常相似
判断是不是快乐数，就是看入环的数字是几，如果是 1 那么就是快乐数

解法：

（快慢双指针）

定义快慢双指针 s low 和 fast
慢指针每次向后移动一位
快指针每次向后移动两位
判断相遇的值是不是 1

代码：

class Solution {
    public int isSum(int n) {
        int sum = 0;
        while(n != 0) {
            int t = n % 10;
            sum += t*t;
            n = n / 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = isSum(n);
        while(slow != fast) {
            slow = isSum(slow);
            fast = isSum(isSum(fast));
        }
        return slow == 1;
    }
}

在这里插入图片描述

11. 盛最多水的容器

在这里插入图片描述

在这里插入图片描述

原题链接

题干：

先看题干，貌似就是求体积，再看示例，就是求两段之间最小的那个值乘两段之间的差值

解法：

一：（暴力枚举）
运用两个 fo r 循环进行枚举
但是时间复杂度为 O(n2)
会导致时间溢出

二：（利用单调性，使用双指针）
这里我们先看一下什么是单调性
在这里插入图片描述
先用 [ 6, 2, 5, 4 ] 来举例
6 > 4
所以如果 4 不变，从右向左一个一个计算体积
4 * 3 = 12
2 * 2 = 4
4 * 1 = 4
发现只有第一个的体积是最大的
这样我们可以直接删去 4 ，从 6 开始向 5 进行遍历
这就是单调性

利用这样的规律，我们在看原数组，我们就可以这样解题
在这里插入图片描述

定义双指针 left 和 right
把最大的体积存放到 ret 中
left 和 right 比较大小
 left < right : left ++;
left > rig ht : rig ht–;
直到 left 和 right 相遇

代码：

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int 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;
    }
}