给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。
示例 1：
输入：nums = [1,2,3] 输出：3 解释： 只需要3次操作（注意每次操作会增加两个元素的值）： [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
示例 2：
输入：nums = [1,1,1] 输出：0
提示：
- n == nums.length
- 1 <= nums.length <= 105
- -109 <= nums[i] <= 109
- 答案保证符合 32-bit 整数
因为是n-1个元素加一，所以也可以理解为一个元素减一，那么只需要找到最小值，并且便利容器每个元素减去最小值的结果相加就可以了。
实现代码：class Solution {
public:
int minMoves(vector& nums) {
int num=nums[0];
for(int i=0;inums[i])
{
num=nums[i];
}
}
int res=0;
for(int i=0;i
官方解法：
class Solution {
public:
int minMoves(vector& nums) {
int minNum = *min_element(nums.begin(),nums.end());
int res = 0;
for (int num : nums) {
res += num - minNum;
}
return res;
}
};
很简洁了，使用的min_element找的最小值，原谅我刚看了c++ primer的vector也不知道有这个函数。
454. 四数相加 II 中等
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
- 0 <= i, j, k, l < n
- nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
提示：
- n == nums1.length
- n == nums2.length
- n == nums3.length
- n == nums4.length
- 1 <= n <= 200
- -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
解题思路：
自己想了半天啥也没想出来，只好看了解题，大概思路就是将ab分为一组，cd分为另一组，并存入map容器中去，然后map中的key为a，b的两数之和，值为两数之和出现的次数，然后再求cd的两数之和，将其值的负数拿到ab储存的容器中查找，若存在说明符合题目条件。
实现代码：
class Solution {
public:
int fourSumCount(vector& A, vector& B, vector& C, vector& D) {
int res=0;
mapab_map;
for(auto a:A)
{
for(auto b:B)
{
ab_map[a+b]++;
}
}
for(auto c:C)
{
for(auto d:D)
{
if(ab_map.find(0-(c+d))!=ab_map.end())
{
res+=ab_map[0-(c+d)];
}
}
}
return res;
}
};
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5WT3tBny-1635400440243)(C:UsersLenovoAppDataRoamingTyporatypora-user-imagesimage-20211020221423403.png)]
不太行，再试试官方解法
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1ZOrRtUX-1635400440245)(C:UsersLenovoAppDataRoamingTyporatypora-user-imagesimage-20211020221800324.png)]
看了看代码，官方解法判断cd和的负数在ab的map容器中是否存在的方法是count函数，而我使用的是find函数，可能会更耗时。改了一下代码，发现事与愿违。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XQikcFI9-1635400440247)(C:UsersLenovoAppDataRoamingTyporatypora-user-imagesimage-20211020222132285.png)]
仔细看，发现官方解法使用的是unordered_map，也就是无序map容器，仔细一想，元素是否排序对本题并无帮助，所以排序的话反而会执行时间。改掉再试试。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EURwapyI-1635400440250)(C:UsersLenovoAppDataRoamingTyporatypora-user-imagesimage-20211020222400239.png)]
很不错，执行时间明显变快了。
大佬解法：
class Solution {
public:
int fourSumCount(vector &A, vector &B, vector &C, vector &D) {
int res = 0;
map map;
for (const auto &a : A) for (const auto &b : B) ++map[a + b];
for (const auto &c : C) for (const auto &d : D) res += map[-(c + d)];
return res;
}
};
太简洁了！
66. 加一 简单
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0]
输出：[1]
提示：
- 1 <= digits.length <= 100
- 0 <= digits[i] <= 9
解题思路：
怎么解呢？第一个想到的方法是将数组转化为整数，本来以为这是个简单的方法，转化为整数十分容易，可是再将其转化为vector数组时才发现，自己还得把开头为9进位的情况单独列出一个if判断，好的，我加，可是还是提交失败了，看了报错信息与输入失败的样例，我…，还是直接修改数组吧。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lXfrUBzf-1635400440252)(C:UsersLenovoAppDataRoamingTyporatypora-user-imagesimage-20211021100826251.png)]
太艰难了，先是在重新输入为数组的时候卡了半天，又在开头为9导致进位的情况卡了半天，最后系统给了个长度为10的数组样例，int型肯定放不下，我改成long long型，结果直接又来了个19位的数组，qaq。
实现代码：
class Solution { //这是第一遍用的转换为整数的放大，对于10位数以内的还是很有效的(不考虑执行时间和内存占用的话)
public:
vector plusOne(vector& digits) {
int i;
long long sum, n=1;
for(i=0,sum=0;i
官方解法
class Solution {
public:
vector plusOne(vector& digits) {
int n = digits.size();
for (int i = n - 1; i >= 0; --i) {
if (digits[i] != 9) {
++digits[i];
for (int j = i + 1; j < n; ++j) {
digits[j] = 0;
}
return digits;
}
}
// digits 中所有的元素均为 9
vector ans(n + 1);
ans[0] = 1;
return ans;
}
};
思路很简单，若最后一位不为9，加个一就完事了，为9的话，一直往前找到不为9的数，加一并把后面的数(也就是都为9的数)置0就可以了。
67. 二进制求和 简单
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：
- 每个字符串仅由字符 '0' 或 '1' 组成。
- 1 <= a.length, b.length <= 10^4
- 字符串如果不是 "0" ，就都不含前导零。
解题思路：
首先想到的是找到最短的，然后将短的置为外层for循环，长的置为内层for循环，然后设置多个if条件，感觉很麻烦。实际做起来更麻烦，因为在实现的时候发现自己并不知道那个是长的，哪个是短的，那么就得把短的先用字符0给填充到与长的长度相等，然后继续算，又在第0位进位上卡了一会儿，要是没有vs的动态调试，今天一天估计都要被这道《简单的》题给搞混了，然后，不过最后好得是做出来了。
实现代码：
class Solution {
public:
string addBinary(string a, string b) {
char jinwei = '0';
string shortstr = "";
string longstr = "";
if (a.size() < b.size())
{
for (int i = 0; i < (b.size() - a.size()); i++)
shortstr += '0';
shortstr += a;
longstr = b;
}
else if (a.size() > b.size())
{
for (int i = 0; i < (a.size() - b.size()); i++)
shortstr += '0';
shortstr += b;
longstr = a;
}
else
{
shortstr = a;
longstr = b;
}
string newstr=longstr;
string str = "1";
for (int i = shortstr.size() - 1; i >= 0; i--)
{
if ((longstr[i] + shortstr[i] + jinwei) == 147)
{
newstr[i] = '1';
jinwei = '1';
if (i == 0)
newstr = str + newstr;
continue;
}
if ((longstr[i] + shortstr[i] + jinwei) == 146)
{
newstr[i] = '0';
jinwei = '1';
if (i == 0)
newstr = str + newstr;
continue;
}
if ((longstr[i] + shortstr[i] + jinwei) == 145)
{
newstr[i] = '1';
jinwei = '0';
continue;
}
if ((longstr[i] + shortstr[i] + jinwei) == 144)
{
newstr[i] = '0';
jinwei = '0';
continue;
}
}
return newstr;
}
};
好的一个复杂无用的解法就出来了。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vcj83sUc-1635400440253)(C:UsersLenovoAppDataRoamingTyporatypora-user-imagesimage-20211021145258329.png)]
不过虽说代码长而无用，但效果好像还不错？
官方解法：
class Solution {
public:
string addBinary(string a, string b) {
string ans;
reverse(a.begin(), a.end()); //首尾倒置
reverse(b.begin(), b.end());
int n = max(a.size(), b.size()), carry = 0; //取得最长的值，通过carry的值保留a b内元素的运算结果，以及进位值。
for (size_t i = 0; i < n; ++i) {
carry += i < a.size() ? (a.at(i) == '1') : 0; //通过三元表达式与间接接受运算解雇哦巧妙地解决了长度不同的问题，并且使用(a.at(i) == '1') : 0巧妙地解决了三元表达式在返回值上的限制
carry += i < b.size() ? (b.at(i) == '1') : 0;
ans.push_back((carry % 2) ? '1' : '0'); //在保存的时候判断此位的值，并巧妙地利用了三元表达式在不影响carry本身的值的情况下获得此位的值，使得carry技能求此位值，又能求进位值。
carry /= 2; //既清空了状态，又获得了进位值。
}
if (carry) { //使用carry作为首元素是否进位条件，解决了0+0等非进位导致首元素为0的问题。
ans.push_back('1'); //由于已经首尾倒置了，解决了无法头插的问题。
}
reverse(ans.begin(), ans.end());
return ans;
}
};
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dRSEHG9W-1635400440255)(C:UsersLenovoAppDataRoamingTyporatypora-user-imagesimage-20211021145514220.png)]
还有啥说的，太妙了。
优化代码
根据一位大佬的解法优化后的代码。
string addBinary(string a, string b) {
char jinwei = '0';
int al = a.size();
int bl = b.size();
while (al < bl) //补0更加简洁方便
{
a = '0' + a;
++al;
}
while (al > bl)
{
b = '0' + b;
++bl;
} //不再使用进位标志来记录进位，而是直接将前一位加一，并根据是否大于二判断是否产生了进位，与此位的值。
for (int j = a.size() - 1; j > 0; --j) //从后到前遍历所有的位数，同位相加
{
a[j] = a[j] - '0' + b[j];
if (a[j] >= '2') //若大于等于字符‘2’，需要进一
{
a[j] = (a[j] - '0') % 2 + '0';
a[j - 1] = a[j - 1] + 1;
}
}
a[0] = a[0] - '0' + b[0]; //将ab的第0位相加
if (a[0] >= '2') //若大于等于2，需要进一
{
a[0] = (a[0] - '0') % 2 + '0';
a = '1' + a;
}
return a;
}
1. 两数之和 简单
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个有效答案
解题思路：
想要尽可能地降低时间复杂度，就要让查找对应元素下标的方法尽可能简洁，而哈希表与此很匹配，所以就要使用哈希表，也就是无序map，一定要用无序。
实现代码：
class Solution { //直接cv了官方的，因为都大差不差
public:
vector twoSum(vector& nums, int target) {
unordered_map hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i; //这个一定要写在后面，假如是[3,2,4]，目标为6的话，先插入了3,使得查找的时候直接查到了3，直接就给返回了。所以千万要写在后面。
}
return {};
}
};
2. 两数相加 中等
难度中等6925收藏分享切换为英文接收动态反馈
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围 [1, 100] 内
- 0 <= Node.val <= 9
- 题目数据保证列表表示的数字不含前导零
解题思路：
这道题的买点就是链表了，把链表弄好就行了。
实现代码：
class Solution {
public:
ListNode* addTwonumbers(ListNode* l1, ListNode* l2) {
ListNode *head = nullptr, *tail = nullptr;
int carry = 0;
while (l1 || l2) {
int n1 = l1 ? l1->val: 0; //使用三元表达式接受值可以不用再单独设置循环计算长的链表多出来的值。
int n2 = l2 ? l2->val: 0;
int sum = n1 + n2 + carry;
if (!head) {
head = tail = new ListNode(sum % 10);
} else {
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
}
if (carry > 0) {
tail->next = new ListNode(carry);
}
return head;
}
};
代码没什么好说的，就是链表的操作，但是对于链表的定义挺有意思的。可以看到是直接使用了构造函数，以前记得听说过结构体内是无法定义函数的，这么来看构造函数还是可以定义的，方便又省事。
总结一下：在没有什么特别清晰的思路的时候，最好不要想着生代码，扎扎实实的把每一个条件都做好，然后再慢慢的优化代码，就是因为老想着走捷径才会在交代码的时候有一直通不过的案例。唉~，老老实实比较好，对于我这种小白来讲。
229. 求众数 II 中等
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：[3,2,3]
输出：[3]
示例 2：
输入：nums = [1]
输出：[1]
示例 3：
输入：[1,1,1,3,3,2,2,2]
输出：[1,2]
提示：
- 1 <= nums.length <= 5 * 104
- -109 <= nums[i] <= 109
解题思路：
很简单的题了，感觉似乎用到容器或链表这种结构体的题实现思路都不会太难的样子，直接创建一个unordered_map容器，然后值存放nums[i]，键存放出现次数…就可以了。
实现代码：
class Solution {
public:
vector majorityElement(vector& nums) {
unordered_map m;
int n=nums.size();
for(int i=0;i(n/3))
nums.push_back(it.first);
}
return nums;
}
};
官方代码1：
class Solution {
public:
vector majorityElement(vector& nums) {
int n = nums.size();
vector ans;
unordered_map cnt;
for (auto & v : nums) {
cnt[v]++;
}
for (auto & v : cnt) {
if (v.second > n / 3) {
ans.push_back(v.first);
}
}
return ans;
}
};
很简洁。
官方代码2：
class Solution {
public:
vector majorityElement(vector& nums) {
vector ans;
int element1 = 0;
int element2 = 0;
int vote1 = 0;
int vote2 = 0;
for (auto & num : nums) {
if (vote1 > 0 && num == element1) { //如果该元素为第一个元素，则计数加1
vote1++;
} else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素，则计数加1
vote2++;
} else if (vote1 == 0) { // 选择第一个元素
element1 = num;
vote1++;
} else if (vote2 == 0) { // 选择第二个元素
element2 = num;
vote2++;
} else { //如果三个元素均不相同，则相互抵消1次
vote1--;
vote2--;
}
}
int cnt1 = 0;
int cnt2 = 0;
for (auto & num : nums) {
if (vote1 > 0 && num == element1) {
cnt1++;
}
if (vote2 > 0 && num == element2) {
cnt2++;
}
}
// 检测元素出现的次数是否满足要求
if (vote1 > 0 && cnt1 > nums.size() / 3) {
ans.push_back(element1);
}
if (vote2 > 0 && cnt2 > nums.size() / 3) {
ans.push_back(element2);
}
return ans;
}
};
将空间复杂度降低到了O(1)，虽然更好，但感觉过于复杂了，贴上思路：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YVlkr2ia-1635400440257)(C:UsersLenovoAppDataRoamingTyporatypora-user-imagesimage-20211022111655629.png)]
230. 二叉搜索树中第K小的元素 中等
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
提示：
- 树中的节点数为 n 。
- 1 <= k <= n <= 104
- 0 <= Node.val <= 104
解题思路：
好的，又是考数据结构，二叉树，现学一下，学完了，用vector封装一下再排个序直接交，美滋滋。说到这里突然想起来vector是可以插入重复元素的，而我并没有排除重复元素，啊这，我是怎么通过的？？？？？总不能这道题的样例都不带重复元素的把。
实现代码
void preOrder(TreeNode* tree,vector &v)
{
if(tree)
{
v.push_back(tree->val);
preOrder(tree->left,v);
preOrder(tree->right,v);
}
}
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
vector v;
int res=0;
preOrder(root,v);
sort(v.begin(), v.end(), less() );
return v[k-1];
}
};
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ETi1MkoR-1635400440261)(C:UsersLenovoAppDataRoamingTyporatypora-user-imagesimage-20211022231245134.png)]
虽然存在未排除重复元素的缺陷，但还是提交成功了？？？？？
大佬解法 ★：
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int i = 0;
int ans=0;
function traversal = [&](TreeNode* node){
if(node == nullptr) return;
traversal(node->left);
if(i == k) return;
ans = node->val;
++i;
traversal(node->right);
};
traversal(root);
return ans;
}
};
这个解法感觉十分赞，执行时间与内存消耗感觉也十分不错，通过function函数表结合lambda表达式使用，方便又省事。
官方代码一：
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack stack;
while (root != nullptr || stack.size() > 0) {
while (root != nullptr) {
stack.push(root);
root = root->left;
}
root = stack.top();
stack.pop();
--k;
if (k == 0) {
break;
}
root = root->right;
}
return root->val;
}
};
这个就是把递归遍历改为了while循环遍历。写着麻烦点，但是省空间。
官方方法二
class MyBst {
public:
MyBst(TreeNode *root) {
this->root = root;
countNodeNum(root);
}
// 返回二叉搜索树中第k小的元素
int kthSmallest(int k) {
TreeNode *node = root;
while (node != nullptr) {
int left = getNodeNum(node->left);
if (left < k - 1) {
node = node->right;
k -= left + 1;
} else if (left == k - 1) {
break;
} else {
node = node->left;
}
}
return node->val;
}
private:
TreeNode *root;
unordered_map nodeNum;
// 统计以node为根结点的子树的结点数
int countNodeNum(TreeNode * node) {
if (node == nullptr) {
return 0;
}
nodeNum[node] = 1 + countNodeNum(node->left) + countNodeNum(node->right);
return nodeNum[node];
}
// 获取以node为根结点的子树的结点数
int getNodeNum(TreeNode * node) {
if (node != nullptr && nodeNum.count(node)) {
return nodeNum[node];
}else{
return 0;
}
}
};
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
MyBst bst(root);
return bst.kthSmallest(k);
}
};
官方方法三
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5zWZyeiq-1635400440262)(C:UsersLenovoAppDataRoamingTyporatypora-user-imagesimage-20211022233143814.png)]
// 平衡二叉搜索树结点
struct Node {
int val;
Node * parent;
Node * left;
Node * right;
int size;
int height;
Node(int val) {
this->val = val;
this->parent = nullptr;
this->left = nullptr;
this->right = nullptr;
this->height = 0; // 结点高度：以node为根节点的子树的高度（高度定义：叶结点的高度是0）
this->size = 1; // 结点元素数：以node为根节点的子树的节点总数
}
Node(int val, Node * parent) {
this->val = val;
this->parent = parent;
this->left = nullptr;
this->right = nullptr;
this->height = 0; // 结点高度：以node为根节点的子树的高度（高度定义：叶结点的高度是0）
this->size = 1; // 结点元素数：以node为根节点的子树的节点总数
}
Node(int val, Node * parent, Node * left, Node * right) {
this->val = val;
this->parent = parent;
this->left = left;
this->right = right;
this->height = 0; // 结点高度：以node为根节点的子树的高度（高度定义：叶结点的高度是0）
this->size = 1; // 结点元素数：以node为根节点的子树的节点总数
}
};
// 平衡二叉搜索树（AVL树）：允许重复值
class AVL {
public:
AVL(vector & vals) {
if (!vals.empty()) {
root = build(vals, 0, vals.size() - 1, nullptr);
}
}
// 根据vals[l:r]构造平衡二叉搜索树 -> 返回根结点
Node * build(vector & vals, int l, int r, Node * parent) {
int m = (l + r) >> 1;
Node * node = new Node(vals[m], parent);
if (l <= m - 1) {
node->left = build(vals, l, m - 1, node);
}
if (m + 1 <= r) {
node->right = build(vals, m + 1, r, node);
}
recompute(node);
return node;
}
// 返回二叉搜索树中第k小的元素
int kthSmallest(int k) {
Node * node = root;
while (node != nullptr) {
int left = getSize(node->left);
if (left < k - 1) {
node = node->right;
k -= left + 1;
} else if (left == k - 1) {
break;
} else {
node = node->left;
}
}
return node->val;
}
void insert(int v) {
if (root == nullptr) {
root = new Node(v);
} else {
// 计算新结点的添加位置
Node * node = subtreeSearch(root, v);
bool isAddLeft = v <= node->val; // 是否将新结点添加到node的左子结点
if (node->val == v) { // 如果值为v的结点已存在
if (node->left != nullptr) { // 值为v的结点存在左子结点，则添加到其左子树的最右侧
node = subtreeLast(node->left);
isAddLeft = false;
} else { // 值为v的结点不存在左子结点，则添加到其左子结点
isAddLeft = true;
}
}
// 添加新结点
Node * leaf = new Node(v, node);
if (isAddLeft) {
node->left = leaf;
} else {
node->right = leaf;
}
rebalance(leaf);
}
}
// 删除值为v的结点 -> 返回是否成功删除结点
bool Delete(int v) {
if (root == nullptr) {
return false;
}
Node * node = subtreeSearch(root, v);
if (node->val != v) { // 没有找到需要删除的结点
return false;
}
// 处理当前结点既有左子树也有右子树的情况
// 若左子树比右子树高度低，则将当前结点替换为右子树最左侧的结点，并移除右子树最左侧的结点
// 若右子树比左子树高度低，则将当前结点替换为左子树最右侧的结点，并移除左子树最右侧的结点
if (node->left != nullptr && node->right != nullptr) {
Node * replacement = nullptr;
if (node->left->height <= node->right->height) {
replacement = subtreeFirst(node->right);
} else {
replacement = subtreeLast(node->left);
}
node->val = replacement->val;
node = replacement;
}
Node * parent = node->parent;
Delete(node);
rebalance(parent);
return true;
}
private:
Node * root;
// 删除结点p并用它的子结点代替它，结点p至多只能有1个子结点
void Delete(Node * node) {
if (node->left != nullptr && node->right != nullptr) {
return;
// throw new Exception("Node has two children");
}
Node * child = node->left != nullptr ? node->left : node->right;
if (child != nullptr) {
child->parent = node->parent;
}
if (node == root) {
root = child;
} else {
Node * parent = node->parent;
if (node == parent->left) {
parent->left = child;
} else {
parent->right = child;
}
}
node->parent = node;
}
// 在以node为根结点的子树中搜索值为v的结点，如果没有值为v的结点，则返回值为v的结点应该在的位置的父结点
Node * subtreeSearch(Node * node, int v) {
if (node->val < v && node->right != nullptr) {
return subtreeSearch(node->right, v);
} else if (node->val > v && node->left != nullptr) {
return subtreeSearch(node->left, v);
} else {
return node;
}
}
// 重新计算node结点的高度和元素数
void recompute(Node * node) {
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
node->size = 1 + getSize(node->left) + getSize(node->right);
}
// 从node结点开始（含node结点）逐个向上重新平衡二叉树，并更新结点高度和元素数
void rebalance(Node * node) {
while (node != nullptr) {
int oldHeight = node->height, oldSize = node->size;
if (!isBalanced(node)) {
node = restructure(tallGrandchild(node));
recompute(node->left);
recompute(node->right);
}
recompute(node);
if (node->height == oldHeight && node->size == oldSize) {
node = nullptr; // 如果结点高度和元素数都没有变化则不需要再继续向上调整
} else {
node = node->parent;
}
}
}
// 判断node结点是否平衡
bool isBalanced(Node * node) {
return abs(getHeight(node->left) - getHeight(node->right)) <= 1;
}
// 获取node结点更高的子树
Node * tallChild(Node * node) {
if (getHeight(node->left) > getHeight(node->right)) {
return node->left;
} else {
return node->right;
}
}
// 获取node结点更高的子树中的更高的子树
Node * tallGrandchild(Node * node) {
Node * child = tallChild(node);
return tallChild(child);
}
// 重新连接父结点和子结点（子结点允许为空）
static void relink(Node * parent, Node * child, bool isLeft) {
if (isLeft) {
parent->left = child;
} else {
parent->right = child;
}
if (child != nullptr) {
child->parent = parent;
}
}
// 旋转操作
void rotate(Node * node) {
Node * parent = node->parent;
Node * grandparent = parent->parent;
if (grandparent == nullptr) {
root = node;
node->parent = nullptr;
} else {
relink(grandparent, node, parent == grandparent->left);
}
if (node == parent->left) {
relink(parent, node->right, true);
relink(node, parent, false);
} else {
relink(parent, node->left, false);
relink(node, parent, true);
}
}
// trinode操作
Node * restructure(Node * node) {
Node * parent = node->parent;
Node * grandparent = parent->parent;
if ((node == parent->right) == (parent == grandparent->right)) { // 处理需要一次旋转的情况
rotate(parent);
return parent;
} else { // 处理需要两次旋转的情况：第1次旋转后即成为需要一次旋转的情况
rotate(node);
rotate(node);
return node;
}
}
// 返回以node为根结点的子树的第1个元素
static Node * subtreeFirst(Node * node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
// 返回以node为根结点的子树的最后1个元素
static Node * subtreeLast(Node * node) {
while (node->right != nullptr) {
node = node->right;
}
return node;
}
// 获取以node为根结点的子树的高度
static int getHeight(Node * node) {
return node != nullptr ? node->height : 0;
}
// 获取以node为根结点的子树的结点数
static int getSize(Node * node) {
return node != nullptr ? node->size : 0;
}
};
class Solution {
public:
int kthSmallest(TreeNode * root, int k) {
// 中序遍历生成数值列表
vector inorderList;
inorder(root, inorderList);
// 构造平衡二叉搜索树
AVL avl(inorderList);
// 模拟1000次插入和删除操作
vector randomNums(1000);
std::random_device rd;
for (int i = 0; i < 1000; ++i) {
randomNums[i] = rd()%(10001);
avl.insert(randomNums[i]);
}
shuffle(randomNums); // 列表乱序
for (int i = 0; i < 1000; ++i) {
avl.Delete(randomNums[i]);
}
return avl.kthSmallest(k);
}
private:
void inorder(TreeNode * node, vector & inorderList) {
if (node->left != nullptr) {
inorder(node->left, inorderList);
}
inorderList.push_back(node->val);
if (node->right != nullptr) {
inorder(node->right, inorderList);
}
}
void shuffle(vector & arr) {
std::random_device rd;
int length = arr.size();
for (int i = 0; i < length; i++) {
int randIndex = rd()%length;
swap(arr[i],arr[randIndex]);
}
}
};
啥也不说了，这方法太离谱了，看看得了。
492. 构造矩形 简单
作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：
1. 你设计的矩形页面必须等于给定的目标面积。
2. 宽度 W 不应大于长度 L，换言之，要求 L >= W 。
3. 长度 L 和宽度 W 之间的差距应当尽可能小。
你需要按顺序输出你设计的页面的长度 L 和宽度 W。
示例：
输入: 4
输出: [2, 2]
解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。
但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 所以输出长度 L 为 2， 宽度 W 为 2。
说明:
- 给定的面积不大于 10,000,000 且为正整数。
- 你设计的页面的长度和宽度必须都是正整数。
解题思路：
首先想到的是将w初始化为area的一半，然后for循环去找最贴近w的l值，这种办法没毛病，就是遇到了个案例：1。行不通了，要不就得判断一下奇偶数，执行加一操作，但这样太麻烦了，索性直接看了官方思路，发现了sqrt函数，所以说这道题的考点就是数学函数呗。
实现代码：
class Solution {
public:
vector constructRectangle(int area) {
int l = 0;
int w = sqrt(1.0 * area);
for (; w >0; w--)
{
if (area % w == 0 )
{
l = area / w;
break;
}
}
vector v;
v.push_back(l);
v.push_back(w);
return v;
}
};
官方代码：★
class Solution {
public:
vector constructRectangle(int area) {
int w = sqrt(1.0 * area);
while (area % w) {
--w;
}
return {area / w, w};
}
};
唉，菜就是原罪，哪怕就这么简单个题，咱都能写那么臭。
526. 优美的排列 中等
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
- perm[i] 能够被 i 整除
- i 能够被 perm[i] 整除
给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
示例 1：
输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
- perm[1] = 1 能被 i = 1 整除
- perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
- perm[1] = 2 能被 i = 1 整除
- i = 2 能被 perm[2] = 1 整除
示例 2：
输入：n = 1
输出：1
解题思路：
看完题目，我觉得我是个傻子，脑子里没一点思路，根本不知道怎么写，只好去看了官方解法和评论区，发现暴力解法使用回溯写的。可我居然一点都不会？看完了官方解法还是没一点思路，问了一下做过这道题的同学才算懂了。但还是不会写，唉~~，只能一点一点磨了。时隔三个小时以后才终于搞懂了，唉，对于递归果然还是不太熟啊，明明很简单的一个东西，记得刚学c语言的时候就是被递归搞得生不如死的。
实现代码：
class Solution {
public:
vector use;
int ans = 0;
void dfs(int now,int N)
{
if (now > N)
{
ans++;
}
else
{
for (int i = 1; i <= N; i++)
{
if (use[i-1] == 0 && (now % i == 0 || i % now == 0))
{
use[i-1]=1;
dfs(now + 1, N);
use[i-1]=0;
}
}
}
}
int countArrangement(int N)
{
use = vector(N, 0);
dfs(1, N);
return ans;
}
};
官方代码1：
class Solution {
public:
vector> match;
vector vis;
int num;
void backtrack(int index, int n) {
if (index == n + 1) {
num++;
return;
}
for (auto &x : match[index]) {
if (!vis[x]) {
vis[x] = true;
backtrack(index + 1, n);
vis[x] = false;
}
}
}
int countArrangement(int n) {
vis.resize(n + 1);
match.resize(n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i % j == 0 || j % i == 0) {
match[i].push_back(j);
}
}
}
backtrack(1, n);
return num;
}
};
是先创建了一个二维数组，将每一位符合条件的数都预先计算出来了，这样在寻找符合标准的数时就不用再遍历n次，而是直接查找符合条件的数是否被使用，大大降低了时间复杂度，灰常的nice啊。
官方代码二：
class Solution {
public:
int countArrangement(int n) {
vector f(1 << n);
f[0] = 1;
for (int mask = 1; mask < (1 << n); mask++) {
int num = __builtin_popcount(mask);
for (int i = 0; i < n; i++) {
if (mask & (1 << i) && (num % (i + 1) == 0 || (i + 1) % num == 0)) {
f[mask] += f[mask ^ (1 << i)];
}
}
}
return f[(1 << n) - 1];
}
};
状态压缩与动态压缩，只看懂了状态压缩的概念，动态压缩是个什么鬼还是没明白，到最后是算看明白了，其实从本质上讲和递归差不多，都是一个状态的累积，但是递归是不断地向前积累。而这种方法则是直接借用前面的积累。编不下去了~~~~，总之就是一种具体的思想，比如f[100110]表示2，3，6的完美排序，表示2，3，6放在前三位的情况，那么我们只需要直到第三位可以放那些数字：3，6。所以只需要计算3，6放在第三位的时候，其它两位放在前两位的完美排序数量。也就是f[100110]+=f[000110]+=f[100010]。唉，感觉还是递归好用，如果n不小于5的话，感觉还是递归更好用一些。
__builtin_popcount() 这个函数是记录括号中数转化为二进制的话1的存在个数。
638. 大礼包 中等
在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。
还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。
返回 确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。
示例 1：
输入：price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
输出：14
解释：有 A 和 B 两种物品，价格分别为 ¥2 和 ¥5 。
大礼包 1 ，你可以以 ¥5 的价格购买 3A 和 0B 。
大礼包 2 ，你可以以 ¥10 的价格购买 1A 和 2B 。
需要购买 3 个 A 和 2 个 B ， 所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A 。
示例 2：
输入：price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
输出：11
解释：A ，B ，C 的价格分别为 ¥2 ，¥3 ，¥4 。
可以用 ¥4 购买 1A 和 1B ，也可以用 ¥9 购买 2A ，2B 和 1C 。
需要买 1A ，2B 和 1C ，所以付 ¥4 买 1A 和 1B（大礼包 1），以及 ¥3 购买 1B ， ¥4 购买 1C 。
不可以购买超出待购清单的物品，尽管购买大礼包 2 更加便宜。
提示：
- n == price.length
- n == needs.length
- 1 <= n <= 6
- 0 <= price[i] <= 10
- 0 <= needs[i] <= 10
- 1 <= special.length <= 100
- special[i].length == n + 1
- 0 <= special[i][j] <= 50
解题思路：
这道题纯纯的考验你的耐心，直接看代码吧，实现起来感觉还挺复杂的。
官方代码：★
class Solution {
public:
map, int> memo;
int shoppingOffers(vector& price, vector>& special, vector& needs) {
int n = price.size();
// 过滤不需要计算的大礼包，只保留需要计算的大礼包
vector> filterSpecial;
for (auto& sp : special) {
int totalCount = 0, totalPrice = 0;
for (int i = 0; i < n; ++i) {
totalCount += sp[i];
totalPrice += sp[i] * price[i];
}
if (totalCount > 0 && totalPrice > sp[n]) {
filterSpecial.emplace_back(sp);
}
}
return dfs(price, special, needs, filterSpecial, n);
}
// 记忆化搜索计算满足购物清单所需花费的最低价格
int dfs(vector price, const vector>& special, vector curNeeds, vector>& filterSpecial, int n)
{
if (!memo.count(curNeeds))
{
int minPrice = 0;
for (int i = 0; i < n; ++i)
{
minPrice += curNeeds[i] * price[i]; // 不购买任何大礼包，原价购买购物清单中的所有物品
}
for (auto& curSpecial : filterSpecial)
{
int specialPrice = curSpecial[n];
vector nxtNeeds; //定义在for循环里使得每进行一次循环，nxtneeds的值都能被重置
for (int i = 0; i < n; ++i)
{
if (curSpecial[i] > curNeeds[i])
{ // 不能购买超出购物清单指定数量的物品
break;
}
nxtNeeds.emplace_back(curNeeds[i] - curSpecial[i]); //计算剩余的需求，emplace_相同的尾插方式，但是执行效率更高
}
if (nxtNeeds.size() == n)
{ // 大礼包可以购买
minPrice = min(minPrice, dfs(price, special, nxtNeeds, filterSpecial, n) + specialPrice);
}
}
memo[curNeeds] = minPrice;
}
return memo[curNeeds];
}
};
240. 搜索二维矩阵 II 中等
编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= n, m <= 300
- -109 <= matrix[i][j] <= 109
- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
- -109 <= target <= 109
解题思路
首先想到的就是每一行判断一下，然后暴力搜索，这种方法其实比直接暴力搜索好不到哪，第二个方法就是直接从左下角的元素开始判断，因为左下角的元素最特殊，它是这一列最大的，这一行最小的，右上角也可以。所以若是target小于左下角，说明左下角这一行不存在target 所以把左下角上移，也就是删除最后一行，若target大于左下角，则target右移，也就是删掉了第一行。
实现代码：
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
int m = matrix[0].size()-1;
for (const auto& mat : matrix)
{
if (mat[0]<=target && mat[m]>=target)
{
for (int i : mat)
{
if (i == target)
return true;
}
}
}
return false;
}
};
优化代码：
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
int n = matrix[0].size();
int m=matrix.size()-1;
int j=0;
while(j=0)
{
if(matrix[m][j]==target) return true;
else if(matrix[m][j]>target) m--;
else j++;
}
return false;
}
};
结果很不错。
**另外发现一个点，就是for循环的时候，如果是这样：for(const auto& i: …) 的话可能会更节省时间，因为我用for(auto i: …)超时了。。。。。。。**可以看看这个文章
官方解法：(二分法)
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
for (const auto& row: matrix) {
auto it = lower_bound(row.begin(), row.end(), target);
if (it != row.end() && *it == target) {
return true;
}
}
return false;
}
};
lower_bound()函数的用法是查找不小于目标值的第一个元素。这个函数很不错。
496. 下一个更大元素 I 简单
给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
提示：
- 1 <= nums1.length <= nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 104
- nums1和nums2中所有整数 互不相同
- nums1 中的所有整数同样出现在 nums2 中
官方代码：单调链★
class Solution {
public:
vector nextGreaterElement(vector& nums1, vector& nums2) {
unordered_map hashmap;
stack st;
for (int i = nums2.size() - 1; i >= 0; --i) {
int num = nums2[i];
while (!st.empty() && num >= st.top()) {
st.pop();
}
hashmap[num] = st.empty() ? -1 : st.top();
st.push(num);
}
vector res(nums1.size());
for (int i = 0; i < nums1.size(); ++i) {
res[i] = hashmap[nums1[i]];
}
}
};
实现这个分两步先用单调链储存nums2里每个元素右侧的第一个最大值，因为nums1是nums2的子集，所以nums2每个元素右侧第一个最大值就是nums1每个元素右侧第一个最大值。用单调链实现可以降低时间复杂度，然后使用map容器存储结果。
301. 删除无效的括号 困难
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
- 1 <= s.length <= 25
- s 由小写英文字母以及括号 '(' 和 ')' 组成
- s 中至多含 20 个括号
解题思路：
是一道难题，做了以后发现雀食难做，有两个难点，就是如何找出所有符合条件的字符串，第二个难点就是如何去除重复的字符串，具体太复杂了，直接看源码吧。
大佬代码 ★
class Solution {
public:
vector removeInvalidParentheses(string s) {
vector res;
remove(move(s), {'(', ')'}, 0, 0, res);
return res;
}
void remove(std::string s, const vector& par, int m, int n, vector& res) {
//m为当前遍历到的需要修改的位置（即左括号<右括号时的位置），n为上一次修改的右括号位置
int stack = 0; //用于 记录左括号数-右括号
for(int i=m; i= 0) continue; //（1）左括号数量多于右括号，不执行下面的，继续遍历
//（2）左括号数量少于右括号，开始找要删除的右括号
for(int j=n; j<=i; j++) { //j从n往后遍历到i：寻找要删除的右括号
if(s[j]==par[1] && (j==n || s[j-1]!=par[1])) {
//j处是右括号 && j==n保证第一次顺利执行||前一个不是右括号，如果前面的和我是紧挨着的右括号，删除前面的和删我有什么区别（这里是去重）
//为什么j==n一定可以执行？ 因为n是上一次 修改的右括号 的位置
//这个地方以前是右括号，我给删掉了
//现在如果这个地方变成左括号了，那好，继续看后面的右括号
//如果这个地方又是右括号了，那不就是我上一层做的事情吗？我要再删除一次，直到我见到左括号
auto ss = s.substr(0, j) + s.substr(j+1);
remove(move(ss), par, i, j, res);
}
}
return;
}
//将当前子串逆转
reverse(s.begin(), s.end());
//处理左括号，为什么要逆置处理左括号？
//因为上面的遍历保证的是左括号>=右括号
//这次我们再保证右括号>=左括号，即可保证左括号==右括号，即匹配
//仔细推敲：数目相等其实未必匹配，但我们处理的时候是一发现不匹配就修改的
//即相当于解决每一个小错，相当于没有大错，需要自己体会一下
//此时传参互换了左右括号的位置，所以处理完左括号再执行到这步时候会执行else
if(par[0]=='(')
remove(move(s), {par[1], par[0]}, 0, 0, res);
else
res.push_back(move(s));
}
};
869. 重新排序得到 2 的幂 中等
给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：1
输出：true
示例 2：
输入：10
输出：false
示例 3：
输入：16
输出：true
示例 4：
输入：24
输出：false
示例 5：
输入：46
输出：true
提示：
- 1 <= N <= 10^9
解题思路：
这道题感觉出的很不错，想要解这道题可以先考虑两点，首先是如何找到合适的2的幂与N比较，我们可以通过整数的长度来判断，如果2的幂的长度刚好等于N的长度就比较，其他的可以忽略不计，第二点就是如何判断N的各种排序是否有一种等于2的幂次方呢？可以直接把N进行排序，如果排序的结果与2的幂次方排序后的结果相同就说明是符合的。
实现代码：
class Solution {
public:
bool reorderedPowerOf2(int n) {
multiset m1;
multiset m2;
string s2;
string s1 = to_string(n);
int l1 = s1.size();
int l2 = 0;
for (int i = 0; i < l1; i++)
{
m1.insert(s1[i]);
}
for (int i = 0;; i++)
{
s2 = to_string((int)(pow(2, i)));
if (s2.size() == l1)
{
for (int i = 0; i < l1; i++)
{
m2.insert(s2[i]);
}
if (m1 == m2)
return true;
else
m2.clear();
}
if (s2.size() > l1)
{
return false;
}
}
}
};
官方解法1
使用回溯加位运算，这个办法不太好，所以直接跳过。
官方解法2 ★
string countDigits(int n) {
string cnt(10, 0);
while (n) {
++cnt[n % 10];
n /= 10;
}
return cnt;
}
unordered_set powerOf2Digits;
int init = []() {
for (int n = 1; n <= 1e9; n <<= 1) {
powerOf2Digits.insert(countDigits(n));
}
return 0;
}();
class Solution {
public:
bool reorderedPowerOf2(int n) {
return powerOf2Digits.count(countDigits(n));
}
};
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：1
输出：true
示例 2：
输入：10
输出：false
示例 3：
输入：16
输出：true
示例 4：
输入：24
输出：false
示例 5：
输入：46
输出：true
提示：
- 1 <= N <= 10^9
解题思路：
这道题感觉出的很不错，想要解这道题可以先考虑两点，首先是如何找到合适的2的幂与N比较，我们可以通过整数的长度来判断，如果2的幂的长度刚好等于N的长度就比较，其他的可以忽略不计，第二点就是如何判断N的各种排序是否有一种等于2的幂次方呢？可以直接把N进行排序，如果排序的结果与2的幂次方排序后的结果相同就说明是符合的。
实现代码：
class Solution {
public:
bool reorderedPowerOf2(int n) {
multiset m1;
multiset m2;
string s2;
string s1 = to_string(n);
int l1 = s1.size();
int l2 = 0;
for (int i = 0; i < l1; i++)
{
m1.insert(s1[i]);
}
for (int i = 0;; i++)
{
s2 = to_string((int)(pow(2, i)));
if (s2.size() == l1)
{
for (int i = 0; i < l1; i++)
{
m2.insert(s2[i]);
}
if (m1 == m2)
return true;
else
m2.clear();
}
if (s2.size() > l1)
{
return false;
}
}
}
};
官方解法1
使用回溯加位运算，这个办法不太好，所以直接跳过。
官方解法2 ★
string countDigits(int n) {
string cnt(10, 0);
while (n) {
++cnt[n % 10];
n /= 10;
}
return cnt;
}
unordered_set powerOf2Digits;
int init = []() {
for (int n = 1; n <= 1e9; n <<= 1) {
powerOf2Digits.insert(countDigits(n));
}
return 0;
}();
class Solution {
public:
bool reorderedPowerOf2(int n) {
return powerOf2Digits.count(countDigits(n));
}
};
