贪心算法

阅读数:0次

综述

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

题库

984. String Without AAA or BBB

生成字符串没有‘aaa’和’bbb’。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Input: A = 1, B = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.


class Solution {
public:
    string strWithout3a3b(int A, int B) {
       char a = 'a';
       char b = 'b';
       if (A < B) { // 保证A >= B，同时默认a是大的
           swap(A, B);
           swap(a, b);
       }
       string ans = "";
       while(A > 0 || B > 0) {
           if (A > 0) {
               ans += a;
               A--;
           }
           if (A > B) { //如果我比你还多，那我就多放一个
               ans += a;
               A--;
           }
           if (B > 0) {
               ans += b;
               B--;
           }
       }
       return ans;
    }
};

860. Lemonade Change

柠檬找零，每人买一个柠檬，（价值5）可能付5, 10, 20面值的钞票，问零钱是否能找开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int fives = 0; //考虑所有情况，简单模拟
        int tens = 0;
        for (int i = 0; i < bills.size(); i++) {
            if (bills[i] == 5)
                fives++;
            else if (bills[i] == 10) {
                if (fives >= 1) {
                    fives--;
                    tens++;
                }
                else
                    return false;
            }
            else {
                if (fives >= 1 && tens >= 1) {
                    fives--;
                    tens--;
                }
                else if (fives >= 3) {
                    fives -= 3;
                }
                else {
                    return false;
                }
            }
        }
        return true;
    }
};

55. Jump Game

跳跃游戏，数组中每个元素表示下一步的距离，问是否能跳到最后索引位置。

思路一

从倒数第一个开始，如果可以到最后一个，那么从这里截断，如果最后所剩只有一个元素，那么成功，反之失败

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = 1;
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (nums[i] >= n) {
                n = 1;
            }
            else {
                n++;
            }
            if (i == 0 && n > 1) {
                return false;
            }
        }
        return true;
    }
};

思路二：

考虑每次更新可否到达当前位置

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (k < i) return false;
            k = max(k, nums[i] + i);
        }
        return true;
    }
};

1029. Two City Scheduling

2N个人，分别去A，B两地，花费不同价格，要求A总共去N人，B也要去N人，总价最低：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        if (costs.empty())return 0;
        sort(costs.begin(), costs.end(), [](vector<int>a, vector<int>b){return a[1] - a[0] > b[1] - b[0];}); //每人只和自己比，去A比去B便宜更多的时候，肯定去A。
        int n = costs.size() / 2;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += costs[i][0] + costs[i+n][1];
        }
        return ans;
    }
};

1042. Flower Planting With No Adjacent

联通图染色问题，paths表示相邻的花园，相邻的花园中不能种同一种花，一种有四种花。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        vector<int>G[N];
        for (int i = 0; i < paths.size(); i++) { //建立邻接表
            G[paths[i][0] - 1].push_back(paths[i][1] - 1);
            G[paths[i][1] - 1].push_back(paths[i][0] - 1); 
        }
        vector<int>answer(N, 0); //初始化全部未染色
        for (int i = 0; i < N; i++) {
            set<int>color{1, 2, 3, 4};
            for (int j=0; j < G[i].size(); j++) {
                color.erase(answer[G[i][j]]);
            }
            answer[i] = *(color.begin());
        }
        return answer;
    }
};

1090. Largest Values From Labels

给一个集合，每个元素有一个值values[i]与标签labels[i]。这里要选择一个子集，使得子集的元素个数不超过num_wanted，而且相同标签的元素个数不超过use_limit。求子集的最大和。

1
2
3
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    struct term {
        int value, label;
    };
    static bool cmp(term a, term b) {
        return a.value > b.value;
    }
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
        vector<term> data;
        data.resize(values.size());
        int ml = 0;
        for (int i = 0; i < values.size(); i++) {
            data[i].value = values[i];
            data[i].label = labels[i];
            ml = max(ml, labels[i]);
        }
        sort(data.begin(), data.end(), cmp);

        vector<int> bucket;
        bucket.resize(ml+1);
        int num = 0;
        int sum = 0;
        for (int i = 0; i < data.size(); i++) {
            int lab = data[i].label;
            if (bucket[lab] < use_limit) {
                num++;
                bucket[lab]++;
                sum += data[i].value;
                if (num >= num_wanted) return sum;
            }
        }
        return sum;
    }
};

1094. Car Pooling

一辆车接旅客，根据旅客的人数，上下车位置，判断是否可以载完所有的旅客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
    
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        map<int, int> m;
        for(auto & t: trips){
            m[t[1]] += t[0];  // pick up
            m[t[2]] -= t[0];  // drop off
        }
        int passengers = 0;
        for(auto it: m){
            passengers += it.second;
            if(passengers > capacity) return false;
        }
        return true;
    }
};

1282. Group the People Given the Group Size They Belong To

用户分组归属问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

class Solution {//显示粗粒度分开，然后再按大小切分
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < groupSizes.size(); ++i) {
            groups[groupSizes[i]].push_back(i);
        }

        vector<vector<int>> ans;
        for (auto group = groups.begin(); group != groups.end(); ++group) {
            const int& gsize = group->first;
            vector<int>& users = group->second;
            for (auto iter = users.begin(); iter != users.end(); iter = next(iter, gsize)) {
                cout << *iter << endl;
                
                vector<int> dummy(iter, next(iter, gsize));
                ans.push_back(dummy);
            }
        }
        return ans;
    }
};

扫一扫，分享到微信

微信分享二维码
#上面是 yilia 主题配置自带 下面是我自己添加的js代码 //这是自定一个js文件,放在 layout\_parial\post 目录 leancloud.ejs中

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

试问岭南应不好，<br><br>却道：此心安处是吾乡。<br><br>