前言
因为某些已知原因，我又开始在LeetCode上 真·刷题 了。
昨晚参加的是双周赛，第一题很快就写出来了，第二题写完之后报错，改完之后还超出时间限制了，后来发现，我理解错了题目的意思，而且解法也不太好。
中等题·判断一个数字是否可以表示成三的幂的和
题目
给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。
对于一个整数 y ，如果存在整数 x 满足 y == 3^x ，我们称这个整数 y 是三的幂。
示例 1：
输入：n = 12
输出：true
解释：12 = 3^1 + 3^2
- 1
- 2
- 3
示例 2：
输入：n = 91
输出：true
解释：91 = 3^0 + 3^2 + 3^4
- 1
- 2
- 3
示例 3：
输入：n = 21
输出：false
- 1
- 2
提示：
1 <= n <= 107
- 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-if-number-is-a-sum-of-powers-of-three
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
这个其实思路很直接，在纸上写几个3的幂就看出规律了。低次幂就算全部加起来，也抵不上一个高次幂。。
那就从上往下降维打击了嘛。
1 3 9 27 81 243···
- 1
代码实现
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; }
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
其实也可以不用这么复杂，就不用那个keep的数组啦，这里写这样就，容易理解嘛。
如果不用那个keep数组，那就直接找到当下最大的幂，然后一路往下减就行了，时间和空间相信都会有大幅的降低。
中等题·所有子字符串美丽值之和
一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。
比方说，"abaacc" 的美丽值为 3 - 1 = 2 。
- 1
给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。
示例 1：
输入：s = "aabcb"
输出：5
解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。
- 1
- 2
- 3
示例 2：
输入：s = "aabcbaa"
输出：17
- 1
- 2
提示：
1 <= s.length <= 500
s 只包含小写英文字母。
- 1
- 2
来源：力扣（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; }
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
作者：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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
马上又要开始单周赛了，，，
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/114478148