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

本文主要是介绍leetcode解题思路分析（五十六）476 - 482 题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

每一位的汉明距离可以如此计算：假设有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 ONfor (auto num : nums) {         // loop over every elementint i = 0;while (num > 0) {           // check every bitcnt[i] += (num & 0x1);num >>= 1;i++;}}for (auto&& k : cnt) {           // loop over every bit countans += k * (n - k);}return ans;
}};

478. 在园内随机生成点
     给定圆的半径和圆心的 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 generationmt19937 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};}
};

479. 最大回文数乘积
     你需要找到由两个 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;}
};

480. 滑动窗口中位数
     给你一个数组 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 heappriority_queue<int, vector<int>, greater<int> > hi;     // min heapint i = 0;      // index of current incoming element being processed// initialize the heapswhile (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 windowmedians.push_back(k & 1 ? lo.top() : ((double)lo.top() + (double)hi.top()) * 0.5);if (i >= nums.size())break;                          // break if all elements processedint out_num = nums[i - k],          // outgoing elementin_num = nums[i++],             // incoming elementbalance = 0;                    // balance factor// number `out_num` exits windowbalance += (out_num <= lo.top() ? -1 : 1);hash_table[out_num]++;// number `in_num` enters windowif (!lo.empty() && in_num <= lo.top()) {balance++;lo.push(in_num);}else {balance--;hi.push(in_num);}// re-balance heapsif (balance < 0) {                  // `lo` needs more valid elementslo.push(hi.top());hi.pop();balance++;}if (balance > 0) {                  // `hi` needs more valid elementshi.push(lo.top());lo.pop();balance--;}// remove invalid numbers that should be discarded from heap topswhile (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;
}
};

481. 神奇字符串
     给定一个整数 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');}
};

482. 密钥格式化
     有一个密钥字符串 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;}
};

这篇关于leetcode解题思路分析（五十六）476 - 482 题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---