# Untitled

unknown
plain_text
2 years ago
3.1 kB
2
Indexable
Never
```class Solution {
public:
int findComplement(int num) {
int not_num = 0;
int pos = 0;
while (num)
{
not_num = not_num | ((!(num & 1)) << pos++);
num = num >> 1;
}
return not_num;
}
};

class Solution {
public:
bool isPowerOfTwo(int n) {
if (n <= 0)
return false;

while (n > 1)
{
if ((n&1) != 0)
return false;
n = n >> 1;
}
return true;
}
};

class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums)
{
vector<vector<int>> result;
vector<int> dummy;
// Level 0
result.push_back(dummy);
if (nums.size() > 1)
{
sort(nums.begin(), nums.end());
}

// Level 1
map<vector<int>, int> mapping_set;
for (int i = 0; i < nums.size(); i++)
{
vector<int> tmp{nums[i]};
if (mapping_set.find(tmp) == mapping_set.end())
{
mapping_set[tmp] = i+1;
result.push_back(tmp);
}
}

// Level 2+
int checking_pos = 1;
int curr_size = 2;
while (curr_size < nums.size())
{
while (result[checking_pos].size() == curr_size - 1)
{
for (int i = mapping_set[result[checking_pos]]; i < nums.size(); i++)
{
vector<int> tmp = result[checking_pos];
tmp.push_back(nums[i]);
if (mapping_set.find(tmp) == mapping_set.end())
{
mapping_set[tmp] = i+1;
result.push_back(tmp);
}
}
checking_pos++;
}
curr_size++;
}

if (nums.size() > 1)
result.push_back(nums);
return result;
}
};

class Solution {
public:
int integerReplacement(int n) {
int num_of_steps = 0;
while (n != 1)
{
bool curr_bit = n & 1;
if (curr_bit)
{
if (n == INT_MAX)
{
n -= 1;
}
else
{
if ((n >> 1) & 1)
{
if (n > 3)
n += 1;
else
n -= 1;
}
else
{
if (n > 3)
n -= 1;
else
n += 1;
}
}
}
else
{
n = n >> 1;
}
std::cout << n << std::endl;
if (n +1 != INT_MAX) num_of_steps++;
}
return num_of_steps;
}
};```