专栏首页算法工程师之路数字问题-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

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538),作者:TeddyZhang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

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,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    会呼吸的Coder
  • Find the Duplicate Number

    Tyan
  • 算法:递归和分治-实战

    版权声明:本文为博主原创文章,遵循 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 个数字。滑动窗口每次只向右移动一位。

    godweiyang

扫码关注云+社区

领取腾讯云代金券