数字问题-LeetCode 462、463、473、474、475、476、477、482（二分）
数字问题-LeetCode 462、463、473、474、475、476、477、482（二分）
作者：TeddyZhang，公众号：算法工程师之路
数字问题：
LeetCode # 462 463 473 474 475 476 477 482
1
编程题
【LeetCode #462】最少移动次数使数组元素相等
给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。
例如: 输入: [1,2,3] 输出: 2
解题思路：这个题目的关键是找出中位数，然后每个数字的移动目标都是这个中位数即可！ 注意，当数组长度为偶数时，中位数是中间两个数的平均值，因此我们需要分别去验证。
class Solution {
public:
int minMoves2(vector<int>& nums) {
if (nums.size() == ) return ;
sort(nums.begin(), nums.end());
int n = nums.size();
if (n & == ) return Solve(nums[n/], nums); // n为奇数，中位数为中间的数
else return min(Solve(nums[n/], nums), Solve(nums[n/-1], nums));
}
private:
int Solve(int target, vector<int>& nums) {
int res = ;
for(auto num: nums) {
res += abs(target - num);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements-ii
【LeetCode #463】岛屿的周长
给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
解题思路：直接进行遍历，对四个边界进行处理后，然后从行和列比较相邻两个数是否相同，如果不同，周长+1.
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int res = ;
for(int i = ; i < grid.size(); i++) {
for(int j = ; j < grid[i].size(); j++) {
if (i == && grid[i][j] == ) res++;
if (i == grid.size()-1 && grid[i][j] == ) res++;
if (j == && grid[i][j] == ) res++;
if (j == grid[i].size()-1 && grid[i][j] == ) res++;
if (i != ) {
if (grid[i][j] != grid[i-1][j]) res++;
}
if (j != ) {
if (grid[i][j] != grid[i][j-1]) res++;
}
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/island-perimeter
【LeetCode #473】火柴拼成正方形
还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例 1: 输入: [1,1,2,2,2] 输出: true
class Solution {
private:
bool dfs(vector<int>& nums, vector<bool>& vis, int i, int avg, int sum) {
vis[i] = true;
sum += nums[i];
if (sum == avg) return true;
for (int j = i-1; j >= ; j--) {
if (!vis[j] && nums[j] + sum <= avg) {
if (dfs(nums, vis, j, avg, sum)) return true;
vis[j] = false;
}
}
return false;
}
public:
bool makesquare(vector<int>& nums) {
if (nums.size() < ) return false;
sort(nums.begin(), nums.end());
vector<bool> vis(nums.size(), false);
int avg = , i = nums.size()-1;
for(auto num: nums) avg += num;
if (avg % ) return false;
avg /= ;
if (nums.back() > avg) return false; // 最大边大于边长
for(int j = ; j < ; j++) {
while(vis[i]) i--;
if (!dfs(nums, vis, i, avg, )) return false;
}
return true;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/matchsticks-to-square
【LeetCode #474】一和零
在计算机界中，我们总是追求用有限的资源获取最大的收益。 现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。 你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意: 给定 0 和 1 的数量都不会超过 100。 给定字符串数组的长度不会超过 600。
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
if (strs.empty() || (m <= && n <= )) return ;
vector<vector<int>> dp(m+, vector<int>(n+, ));
for(auto str: strs) {
int zero_cnt = , one_cnt = ;
for(auto ch: str) {
if (ch == '0') zero_cnt ++;
else one_cnt ++;
}
for(int i = m; i >= ; --i) {
for(int j = n; j >= ; --j) {
if (i >= zero_cnt && j >= one_cnt)
dp[i][j] = max(dp[i][j], dp[i-zero_cnt][j-one_cnt] + );
}
}
}
return dp[m][n];
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/ones-and-zeroes
【LeetCode #475】供暖器
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。
所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。
示例 1: 输入: [1,2,3],[2] 输出: 1 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
解题思路：
首先将house和heater数组进行排序，然后遍历house，每次遍历时，都去找离house最近的heater，然后得到最小距离，存为tmp。 最后结果就是所有house对应的tmp的最大值！
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
int maxLen = ;
for(int i = ; i < houses.size(); i++) {
int low = , high = heaters.size()-1;
int tmp = INT_MAX;
while(low <= high) {
int mid = low + (high-low) / ;
if (heaters[mid] == houses[i]) {
tmp = ; break;
}
else if (heaters[mid] > houses[i]) { // 暖气在房子的右边，应该再往左边找
tmp = min(tmp, heaters[mid] - houses[i]);
high = mid - ;
}
else {
tmp = min(tmp, houses[i] - heaters[mid]);
low = mid + ;
}
}
maxLen = max(tmp, maxLen);
}
return maxLen;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/heaters
【LeetCode #476】数字的补数
给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
解题思路：一个正整数的补数是2 ^ (二进制数的个数) - 1 -num. 比如5的补数是2，也就是2^3-1-5 = 2.
class Solution {
public:
int findComplement(int num) {
int sz = log(num) / log() + ;
return pow(, sz) - - num;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-complement/
【LeetCode #477】汉明距离总和
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中，任意两个数之间汉明距离的总和。
示例: 输入: 4, 14, 2 输出: 6
解题思路：
使用一个cnt数组保存nums数组中某 i 位是 1 的个数，比如cnt[3]=2，表示这些数中第3位是1的有两个，那么汉明距离就是2*（n-2）,其中n-2就是零的个数。
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
vector<int> cnt(, );
for(auto num: nums) {
int i = ;
while(num) {
if (num & ) {
cnt[i]++;
}
num = num >> ;
i++;
}
}
int res = ;
int n = nums.size();
for(auto c: cnt) {
res += c * (n-c);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/total-hamming-distance
【LeetCode #482】秘钥格式化
给定一个密钥字符串S，只包含字母，数字以及 '-'（破折号）。N 个 '-' 将字符串分成了 N+1 组。给定一个数字 K，重新格式化字符串，除了第一个分组以外，每个分组要包含 K 个字符，第一个分组至少要包含 1 个字符。两个分组之间用 '-'（破折号）隔开，并且将所有的小写字母转换为大写字母。
给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。
示例 1： 输入：S = "5F3Z-2e-9-w", K = 4 输出："5F3Z-2E9W"
class Solution {
public:
string licenseKeyFormatting(string S, int K) {
int num = K - (S.size()-count(S.begin(), S.end(), '-') % K); // 如果不能整除K，那么多余的将在第一个分组
string res = "";
for(auto ch: S) {
if (ch == '-') continue;
if (num == && res != "") res += '-';
res += toupper(ch);
num = (num+) % K;
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/license-key-formatting
腾讯云开发者
