ARTS-week51

发表于 2019-07-21 分类于 ARTS 本文字数： 1.1k 阅读时长 ≈ 1 分钟

Algorithms

Minimum Moves to Equal Array Elements
思路: 找出数组中的最小值，然后累加每个数跟最小值之间的差值。

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        
        int min_num = nums[0];
        for (int i = 0; i < n; ++i) {
            min_num = min(min_num, nums[i]);
        }
        
        int result = 0;
        for (int i = 0; i < n; ++i) {
            result += nums[i] - min_num;
        }
        return result;
    }
};

Assign Cookies
思路: 贪婪算法。先对两个数组进行排序，每次先拿最小的饼干给贪婪指数最小的小孩。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int i = 0;
        int j = 0;
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        while (i < s.size() && j < g.size()) {
            if (s[i] >= g[j]) {
                ++j;
            }
            ++i;
        }
        return j;
    }
};