leetcode解题思路分析（五十六）476 - 482 题

小鱼儿 2023-01-01 07:57 155阅读 0赞

1.  数字的补数  
    给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

**正整数和1异或即按位取反，所以得到恰好大于该数的1111即可**

class Solution { 
    public:
        int findComplement(int num) { 
            int ret = 1;
            while (ret < num)
            { 
                ret = (ret << 1) + 1;
            }
            ret ^= num;
            return ret;
        }
    };

1.  汉明距离总和  
    两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。计算一个数组中，任意两个数之间汉明距离的总和。

**每一位的汉明距离可以如此计算：假设有n个1，m个0，则n和m相乘即得结果**

class Solution { 
    public:
    int totalHammingDistance(vector<int>& nums)
    { 
        if (nums.empty())
            return 0;
    
        int ans = 0, n = nums.size();
        vector<int> cnt(32, 0);         // count of elements with a particular bit ON
    
        for (auto num : nums) {          // loop over every element
            int i = 0;
            while (num > 0) {            // check every bit
                cnt[i] += (num & 0x1);
                num >>= 1;
                i++;
            }
        }
    
        for (auto&& k : cnt) {            // loop over every bit count
            ans += k * (n - k);
        }
    
        return ans;
    }
    
    };

1.  在园内随机生成点  
    给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数 randPoint 。

**可以采用拒绝采用法，但是更有的是分布式函数法。这种方法更像是数学公式计算，其原理为考虑单位圆内部的每一个圆环，生成的点落在半径为R的圆环上的概率应当与圆环的周长成正比。由于 f(x)在定义域上的积分为 1，因此可以求出 f(x)的表达式 f(x) = 2x。**

class Solution { 
    public:
        double rad, xc, yc;
        //c++11 random floating point number generation
        mt19937 rng{ random_device{ }()};
        uniform_real_distribution<double> uni{ 0, 1};
    
        Solution(double radius, double x_center, double y_center) { 
            rad = radius, xc = x_center, yc = y_center;
        }
    
        vector<double> randPoint() { 
            double d = rad * sqrt(uni(rng));
            double theta = uni(rng) * (2 * M_PI);
            return { d * cos(theta) + xc, d * sin(theta) + yc};
        }
    };

1.  最大回文数乘积  
    你需要找到由两个 n 位数的乘积组成的最大回文数。由于结果会很大，你只需返回最大回文数 mod 1337得到的结果。

**本题可以采用回溯剪纸遍历，但是最佳解法应该还是数学方法：将两个数表示为10的n次方减去x/y，然后回文序列也可以用类似方法表示，最终可求得满足条件的判定条件**

class Solution { 
    public:
        int largestPalindrome(int n) { 
            // n位数*n位数，结果的位数在2n-1 ~ 2n之间
            // 由于结果是回文数，需要枚举n位， 10^8太大了
            // 枚举n位吧
            int up = pow(10, n) - 1;
            int down = pow(10, n - 1);
            typedef long long LL;
            for (int h = 0; h < 2; ++h) { 
                for (int v = up; v >= down; --v) { 
                    string left = to_string(v);
                    string right(left.rbegin() + h, left.rend());
                    LL p = stoll(left + right);
                    for (LL k = up; k * k >= p; --k) { 
                        if (p % k == 0) return p % 1337;
                    }
                }
            }
            return -1;
        }
    };

1.  滑动窗口中位数  
    给你一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

**本题和数据流的中位数类似，采取大顶堆和小顶堆维持的方式获取中位数**

class Solution { 
    public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k)
    { 
        vector<double> medians;
        unordered_map<int, int> hash_table;
        priority_queue<int> lo;                                 // max heap
        priority_queue<int, vector<int>, greater<int> > hi;     // min heap
    
        int i = 0;      // index of current incoming element being processed
    
        // initialize the heaps
        while (i < k)
            lo.push(nums[i++]);
        for (int j = 0; j < k / 2; j++) { 
            hi.push(lo.top());
            lo.pop();
        }
    
        while (true) { 
            // get median of current window
            medians.push_back(k & 1 ? lo.top() : ((double)lo.top() + (double)hi.top()) * 0.5);
    
            if (i >= nums.size())
                break;                          // break if all elements processed
    
            int out_num = nums[i - k],          // outgoing element
                in_num = nums[i++],             // incoming element
                balance = 0;                    // balance factor
    
            // number `out_num` exits window
            balance += (out_num <= lo.top() ? -1 : 1);
            hash_table[out_num]++;
    
            // number `in_num` enters window
            if (!lo.empty() && in_num <= lo.top()) { 
                balance++;
                lo.push(in_num);
            }
            else { 
                balance--;
                hi.push(in_num);
            }
    
            // re-balance heaps
            if (balance < 0) {                   // `lo` needs more valid elements
                lo.push(hi.top());
                hi.pop();
                balance++;
            }
            if (balance > 0) {                   // `hi` needs more valid elements
                hi.push(lo.top());
                lo.pop();
                balance--;
            }
    
            // remove invalid numbers that should be discarded from heap tops
            while (hash_table[lo.top()]) { 
                hash_table[lo.top()]--;
                lo.pop();
            }
            while (!hi.empty() && hash_table[hi.top()]) { 
                hash_table[hi.top()]--;
                hi.pop();
            }
        }
    
        return medians;
    }
    };

1.  神奇字符串  
    给定一个整数 N 作为输入，返回神奇字符串 S 中前 N 个数字中的 ‘1’ 的数目。

**先构造神奇字符串，然后求解即可**

class Solution { 
    public:
        int magicalString(int n) 
        { 
            string s = "122";
            int i = 2;
            while (s.size() < n) 
            { 
                s += string(s[i++] - '0', s.back() ^ 0x3);
            }
    
            return count(s.begin(), s.begin() + n, '1');
        }
    };

1.  密钥格式化  
    有一个密钥字符串 S ，只包含字母，数字以及 ‘-’（破折号）。其中， N 个 ‘-’ 将字符串分成了 N+1 组。  
    给你一个数字 K，请你重新格式化字符串，使每个分组恰好包含 K 个字符。特别地，第一个分组包含的字符个数必须小于等于 K，但至少要包含 1 个字符。两个分组之间需要用 ‘-’（破折号）隔开，并且将所有的小写字母转换为大写字母。给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。

**倒序进行计数，每4个加一个-，然后每个字符变为大写，最后再颠倒序列即可**

class Solution { 
    public:
        char upper(char c) { 
            if (c >= 'a' && c <= 'z')
                return c - 'a' + 'A';
            return c;
        }
        string licenseKeyFormatting(string S, int K) { 
            string res;
            int count = 0;
            for (int i = S.size() - 1; i >= 0; --i) { 
                if (S[i] == '-') { 
                    continue;
                }
                res += upper(S[i]);
                if (++count % K == 0) { 
                    res += '-';
                }
            }
            while (!res.empty() && res.back() == '-')
                res.pop_back();
            reverse(res.begin(), res.end());
            return res;
        }
    };