网站说明页内容维护,大型门户网站开发,vi设计公司网站,网站建设公司需要哪些202. 快乐数 202. 快乐数https://leetcode.cn/problems/happy-number/
题目#xff1a;
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为#xff1a;
对于一个正整数#xff0c;每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个… 202. 快乐数 202. 快乐数https://leetcode.cn/problems/happy-number/
题目
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true 不是则返回 false 。 解题思路 我们先通过这两个测试用例来看看是什么情况 我们发现不管是19还是2都会形成一个环状结构19的环状结构内都是1 那这样我们就可以使用快慢指针来操作 定义一个slow和fastslow一次走一步fast一次走两步 他们一定会相遇的只不过相遇的时候会有两种情况相遇的数是1或者不是1 那为什么一定会形成环状结构呢我们来简单论证一下 鸽巢原理就是当n个巢穴n1个鸽子的时候一定至少有一个巢穴的鸽子1 我们注意一下n的范围n最大为2的31次方也就是2亿多10位数,那我们将它放大10个9也就是最大的那个10位数我懒得打9了也就是说它最多就是10个9经过f操作最大就是9^2*10810,也就是相当于我们最多有810个位置我们处理813次的f肯定会有重复的数出现 那同理 解题代码
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和fastslow f(slow);fast f(fast);fast f(fast);if (slow fast slow 1)return true;while (slow ! fast){//更新slow和fastslow f(slow);fast f(fast);fast f(fast);}if (slow 1)return true;elsereturn false;}
}; 11. 盛最多水的容器
11. 盛最多水的容器https://leetcode.cn/problems/container-with-most-water/
题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。 解题思路 体积Vh*w,当我们利用双指针从左右两边向中间逼近w一定是减小的只有当h增大才可能增大 解题代码
class Solution {
public:int maxArea(vectorint height) {int left0;int rightheight.size()-1;int ret0;while(leftright){int vmin(height[left],height[right])*(right-left);retmax(v,ret);if(height[left] height[right]) left;else right--; }return ret;}
};
