# 数字问题-LeetCode 462、463、473、474、475、476、477、482（二分）

##### 作者：TeddyZhang，公众号：算法工程师之路

LeetCode # 462 463 473 474 475 476 477 482

1

【LeetCode #462】最少移动次数使数组元素相等

```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 #463】岛屿的周长

```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 #473】火柴拼成正方形

```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 #474】一和零

```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 #475】供暖器

```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 #476】数字的补数

```class Solution {
public:
int findComplement(int num) {
int sz = log(num) / log() + ;
return pow(, sz) -  - num;
}
};
```

【LeetCode #477】汉明距离总和

```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 #482】秘钥格式化

```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;
}
};
```

0 条评论

• ### gcd，哈希问题-LeetCode 357、355、365、367、380

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。

• ### 位运算问题-LeetCode 136、137、260（只出现一次的数，异或运算）

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。你可以不使用额外...

• ### 最大堆，DP问题-LeetCode 373 374 376 377 605（DP，最大堆）

给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums...

• ### 算法训练营-第一周-数组链表

栈是一种线性逻辑结构，栈的元素只能后进先出。最早进入的元素存放的位置叫做栈底，最后进入的元素存放的位置叫栈顶。

• ### 【每日一练】第001期--两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

• ### 算法：递归和分治-实战

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 1022 D进制的A+B (20 分)

输入两个非负 10 进制整数 A 和 B (≤230−1)，输出 A+B 的 D (1<D≤10)进制数。

• ### 368. Largest Divisible Subset

思路 动态规划。将数组排序，设长度为n, 维持一个长度为n的dp数组，元素类型为pair<int, int>，pair第一个类型含义是以当前数为结尾的最长di...

• ### 每日算法系列【LeetCode 239】滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。