LeetCode刷題的一天（2）

前言

因為某些已知原因，我又開始在LeetCode上 真·刷題 了，
昨晚參加的是雙周賽，第一題很快就寫出來了，第二題寫完之后報錯，改完之后還超出時間限制了，后來發現，我理解錯了題目的意思，而且解法也不太好，

中等題·判斷一個數字是否可以表示成三的冪的和

題目

給你一個整數 n ，如果你可以將 n 表示成若干個不同的三的冪之和，請你回傳 true ，否則請回傳 false ，

對于一個整數 y ，如果存在整數 x 滿足 y == 3^x ，我們稱這個整數 y 是三的冪，

示例 1：

輸入：n = 12
輸出：true
解釋：12 = 3^1 + 3^2

示例 2：

輸入：n = 91
輸出：true
解釋：91 = 3^0 + 3^2 + 3^4

示例 3：

輸入：n = 21
輸出：false

提示：

1 <= n <= 107

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/check-if-number-is-a-sum-of-powers-of-three
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

思路

這個其實思路很直接，在紙上寫幾個3的冪就看出規律了，低次冪就算全部加起來，也抵不上一個高次冪，，
那就從上往下降維打擊了嘛，

1 3 9 27 81 243···

代碼實作

class Solution {
public:
    bool checkPowersOfThree(int n) {
        vector<int> keep;
        int j = 0;
        for (int i = 0;; i++) {
            j = pow(3, i);
            if (j <= n) {
                keep.push_back(j);
            }
            else
                break;
        }

        for (int sz = keep.size() - 1; sz >= 0; sz--) {
            if (n - keep[sz] > 0)
                n -= keep[sz];
            else if (n - keep[sz] < 0)
                continue;
            else
                return true;
        }
        return false;
    }
};

其實也可以不用這么復雜，就不用那個keep的陣列啦，這里寫這樣就，容易理解嘛，
如果不用那個keep陣列，那就直接找到當下最大的冪，然后一路往下減就行了，時間和空間相信都會有大幅的降低，

中等題·所有子字串美麗值之和

一個字串的 美麗值 定義為：出現頻率最高字符與出現頻率最低字符的出現次數之差，

比方說，"abaacc" 的美麗值為 3 - 1 = 2 ，

給你一個字串 s ，請你回傳它所有子字串的 美麗值 之和，

示例 1：

輸入：s = "aabcb"
輸出：5
解釋：美麗值不為零的字串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一個字串的美麗值都為 1 ，

示例 2：

輸入：s = "aabcbaa"
輸出：17

提示：

1 <= s.length <= 500
s 只包含小寫英文字母，

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sum-of-beauty-of-all-substrings
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

思路

這題吧，其實也很直觀的，但是我主觀的認為所有子字串不能重復，受了上一題的影響吧，
所以這題第一步我就對子串進行去重了，，，，，

如果不用去重的話，那相對就比較好辦了，反正是取出子集嘛，滑動視窗就好啦，不過我和大佬的區別就在于，我還是習慣性的把任務分解了，我先滑動取出子集，然后再遍歷子集進行取值，不知道各位是不是這樣想的，

我看了大佬的代碼，大佬的代碼簡潔多了，一邊滑動一邊取美麗數！！！
思維上還是有差距的，

直接看大佬的代碼吧，我就不獻丑了，

代碼實作

class Solution {
public:
    int beautySum(string s) {
        int n = s.size(), sum = 0;
        for(int len = 2; len <= n; ++len){
            int r = 0, l = 0, minN = INT_MAX, maxN = INT_MIN;
            vector<int> nums(26, 0); // 使用陣列存盤每個字符的數量
            while(r < n){ // 滑動視窗
                nums[s[r] - 'a']++;
                r++;
                if(r - l == len){
                    minN = INT_MAX;
                    maxN = INT_MIN;
                    for(int i = 0; i < 26; ++i){
                        if(nums[i] > 0){
                            minN = min(minN, nums[i]);
                            maxN = max(maxN, nums[i]);
                        }
                    }
                    sum += maxN - minN;
                    nums[s[l] - 'a']--;
                    l++;
                }
            }
        }
        return sum;
    }
};

作者：xiao-ryan
鏈接：https://leetcode-cn.com/problems/sum-of-beauty-of-all-substrings/solution/tan-xin-suan-fa-hua-dong-chuang-kou-by-x-jzvp/
來源：力扣（LeetCode） 著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

馬上又要開始單周賽了，，，