Untitled

mail@pastecode.io avatar
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;
    }
};