?202. 快樂數(shù)?

202.?快樂數(shù)https://leetcode.cn/problems/happy-number/

題目：

編寫一個算法來判斷一個數(shù)?n?是不是快樂數(shù)。

「快樂數(shù)」?定義為：

• 對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和。
• 然后重復(fù)這個過程直到這個數(shù)變?yōu)?1，也可能是?無限循環(huán)?但始終變不到 1。
• 如果這個過程?結(jié)果為?1，那么這個數(shù)就是快樂數(shù)。

如果?n?是?快樂數(shù)?就返回?true?；不是，則返回?false?。

?解題思路：

?我們先通過這兩個測試用例來看看是什么情況

?我們發(fā)現(xiàn)不管是19還是2都會形成一個環(huán)狀結(jié)構(gòu)（19的環(huán)狀結(jié)構(gòu)內(nèi)都是1）

那這樣我們就可以使用快慢指針來操作！?。?/p>

定義一個slow和fast，slow一次走一步，fast一次走兩步

他們一定會相遇的，只不過相遇的時候會有兩種情況，相遇的數(shù)是1或者不是1

那為什么一定會形成環(huán)狀結(jié)構(gòu)呢？我們來簡單論證一下！

鴿巢原理：就是當(dāng)n個巢穴，n+1個鴿子的時候，一定至少有一個巢穴的鴿子>1

我們注意一下n的范圍，n最大為2的31次方，也就是2億多（10位數(shù)）,那我們將它放大10個9（也就是最大的那個10位數(shù)，我懶得打9了），也就是說，它最多就是10個9，經(jīng)過f操作最大就是9^2*10=810,也就是相當(dāng)于我們最多有810個位置，我們處理813次的f，肯定會有重復(fù)的數(shù)出現(xiàn)！

那同理：

?

解題代碼：

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?的整數(shù)數(shù)組?height?。有?n?條垂線，第?i?條線的兩個端點是?(i, 0)?和?(i, height[i])?。

找出其中的兩條線，使得它們與?x?軸共同構(gòu)成的容器可以容納最多的水。

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

說明：你不能傾斜容器。

解題思路：

體積V=h*w,當(dāng)我們利用雙指針從左右兩邊向中間逼近，w一定是減小的，只有當(dāng)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;
    }
};

?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-664913.html

到了這里，關(guān)于【算法挨揍日記】day02——雙指針?biāo)惴╛快樂數(shù)、盛最多水的容器的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！