快乐数

题目描述

快乐数
编写一个算法来判断一个数 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

• 1 <= n <= 2^{31 - 1}

算法原理

这题的难点在于我们不知道一个数究竟是不是快乐数，如果不是的话，就会一直无限判断下去。

因此循环终止条件是这题的关键。其实有个简单的想法，我们可以一鼓作气求N次各数平方和，如果N次后都不是快乐数那就return false。
这种方法简单粗暴，但是正确率和效率相悖。如果N取太小，正确率较低；如果N取太大，效率较低。

现在我们考虑另外的解法。
首先有个问题是当这个数不是快乐数时，他有没有无限不循环的可能。
即令f(x)=x各数位平方和，令x_i=f(x_i-1)，是否存在x₀使得{x₀,x₁,…,x_n,…}为无限集。

事实上这是不可能的，我们来证明一下 ∃ i , j . i ≠ j s . t . x i , x j ∈ { x 0 , x 1 , . . . , x n , . . . } 且 x i = x j i . e . j − i 是 x n 的周期 \exist i,j. i\neq j s.t. x_i ,x_j \in \{x_0,x_1,...,x_n,...\}且x_i=x_j \\i.e. j-i是x_n的周期 ∃i,j.i=js.t.xi​,xj​∈{x0​,x1​,...,xn​,...}且xi​=xj​i.e.j−i是xn​的周期

首先根据题目给出的数据范围n <= 2^{31 - 1} =2,147,483,647<=9,999,999,999.
则f(x)<=10*9²=810
故 { x 0 , x 1 , . . . , x n , . . . } ⊂ { 1 , 2 , 3 , . . . , 810 } ∪ { x 0 } 故\{x_0,x_1,...,x_n,...\}\sub \{1,2,3,...,810\}\cup \{x_0\} 故{x0​,x1​,...,xn​,...}⊂{1,2,3,...,810}∪{x0​}

所以一个非快乐数最后一定会进入一个循环中。
不妨设这个非快乐数为x，经过N次f操作后进入循环，这个循环的周期为n。
定义slow和fast起始为x，slow每做一次f操作，fast就做两次f操作。记slow的f操作次数为t，则两者操作数差为t是连续的。因此fast和slow必然会存在无数次两者步数差为n的整数倍。
基于这个想法就可以实现这题的算法了/

算法实现

class Solution {
public:
	//取各数位平方和
    int Sum(int x)
    {
        int sum = 0, tmp = 0;
        while (x)
        {
            tmp = x % 10;
            sum += tmp * tmp;
            x /= 10;
        }
        return sum;
    }
    
    bool isHappy(int n) 
    {
        int fast, slow;
        fast = slow = n;
        while (1)
        {
            slow = Sum(slow);
            fast = Sum(Sum(fast));
            //快乐数
            if (fast == 1)
                return true;
            //非快乐数，且进入循环
            else if (fast == slow)
                return false;
        }
    }
};

盛水最多的容器

题目描述

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

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

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

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

算法原理

• 算法一：枚举法
  暴力求解自然是判断所有情况，时间复杂度为O(n²)
• 算法二：双指针

这题使用对撞指针，left一开始指向数组起点，right一开始指向数组最后一个元素。left和right分别表示容器的左右两侧。

首先left和right围成的容器，高度为min(left,right),宽度为(right-left),则容积为min(left,right)*(right-left)
不妨设height[left]<height[right].这时候right向左移动的话,min(left,right)*(right-left)必然减小。也就是说以left为左边界的已经不可能再取得更大的值了。这时候我们就可以舍弃left了，所以left应当向右移动。
height[left]>=height[right]也是同理判断。

虽然我们知道了left和right相互靠近时的舍弃逻辑，但我们不能确保这样不会遗漏情况。因此我们还需要证明这种操作最后能得到正确的结果。
以输入：[1,8,6,2,5,4,8,3,7]举例，事实上我们以i，j为容器的搜索空间是:

首先j势必要＞i的，因此搜索空间左下角就被剪去了：

搜索空间自然变成了右上角的白三角。我们的枚举法是一个一个遍历，因此时间复杂度是O(n²)。
此时我们以(0,6)为起点，由于height[0]<height[6]，根据前面的结果我们知道(0,1)、(0,2)、…、(0,5)的值都不可能大于(0,6)，因此我们排除的是：

最上方一行的搜索空间。
继续，left向右移动。此时height[1]>height[6],因此我们又知道(2,6)、…、(5,6)的情况被排除了，并且(0,6)的情况在第一次被排除了，所以没有遗漏情况，此时搜索空间变为：

可以看到这样下去，我们只需要用行次搜索即可遍历搜索空间。因此时间复杂度为O(n)

算法实现

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

有效三角形的个数

题目描述

有效三角形的个数
给定一个包含非负整数的数组 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

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

算法原理

对于三个数a、b、c能否作三角形的三边长度，其判断条件是a+b>c&&a+c>b&&b+c>a，显然判定条件繁多晦涩。

• 算法一：枚举法

解一道算法题自然要先考虑暴力求解，主要是看看有没有优化空间，如果说一些题目暴力解法就是最优解，那你还考虑什么巧妙解法不是浪费时间吗？
言归正传，这题的暴力解法自然是遍历数组，三层for循环考虑所有情况。因此时间复杂度O(n^3)

• 算法二：双指针

这题麻烦的地方是三角形有三个判定条件，但倘若我们限制a<=b<=c，那么判定条件就变成了a+b>c.
因此我们考虑先将数组升序排序，此时时间复杂度为O(nlogn).
固定c，取left指向数组起点，right指向c上一个元素。

当nums[left]+nums[right]>c时,由于nums升序，因此nums[left+i]+nums[right]>c,i>0&&left+i<right.
故以right为b的情况已考虑尽，right–。

当nums[left]+nums[right]<=c时，nums[left]+nums[right-i],i>0&&left+i<right.
故以left为a的情况已考虑尽，left++。

因此固定c的情况，需遍历一遍数组，时间复杂度O(n).
又需要遍历数组来当c，总时间复杂度O(n²).

算法实现

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        int ans = 0;
        for (int n = nums.size() - 1; n >= 2; n--)
        {
            int left = 0, right = n - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > nums[n])
                {
                    ans += right - left;
                    right--;
                }
                else
                    left++;
            }
        }
        return ans;
    }
};