贪心算法刷题笔记（C++）_C

文章目录

前言
会议安排
拼凑字符串
Hulfman编码
N皇后问题
总结

前言

本帖主要是记录在LeetCode刷题笔记，持续更新中。

会议安排

    // 1.会议室安排，输入为每个会议的起止时间，会议有冲突，要求尽可能多的会议。

        struct Agent{
            Agent(){
                name = "invalid";
                start = 0;
                end = 0;
            }
            Agent(std::string a, int b, int c){
                name = a;
                start = b;
                end = c;
            }
            std::string name;
            float start;
            float end;
            bool operator<(const Agent& b) const{
                return this->end < b.end;
            } 
        };
        std::vector<Agent> BestAgentArrange(std::vector<Agent> agents, float start){
            std::sort(agents.begin(), agents.end());// 按照结束时间的早晚排序
            std::vector<Agent> res;
            for(auto ele : agents){
                if(ele.start > start){
                    res.push_back(ele);
                    start += ele.end; //上一会议的结束时间作为开始时间
                }
            }
            return res;
        }

拼凑字符串

// 2.拼凑字符串使得字典数最小
    struct MyCompareDict{
        bool operator()(std::string& lhs, std::string& rhs){
            return lhs + rhs < rhs + lhs;
        }
    };
    
    std::string MinDictMerge(std::vector<std::string> ss){
        std::string res;
        sort(ss.begin(), ss.end(), MyCompareDict());
        for(auto ele : ss){
            res += ele;
        }
        return res;
    }

Hulfman编码

    // 3.Hulfman编码 要求list分割黄金,使得分割成本最低
    int HulfmanCode(const std::vector<int>& list){
        int res = 0;
        int cur = 0;
        std::priority_queue<int> temp(list.begin(),list.end());
        while(temp.size() > 1){
            cur = temp.top();
            temp.pop();
            cur += temp.top();
            temp.pop();
            res += cur;
        }
        return res;

    }

N皇后问题

描述：

N*N网格中放N个皇后，要求每二个皇后不在同一行同一列同一斜线。

返回摆法的数量。

解法：

暴力递归，深度优先，递归探讨每一行，探讨（for）该行的所有valid列，放过皇后的列记录下来，继续往下一行递归，所要种类数，记录所有该行该列的种类数，累加返回就是该行的种类总数。

边界条件，就是顺利完n行的返回1（一种摆法）。

/**
 * @file queen.cpp
 * @author Stephen Ding (1103037805@qq.com)
 * @brief 
 * @version 0.1
 * @date 2022-04-17
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include 
#include 
using namespace std;
class NQueen{
    public:
        int NQueenMethod(int n = 0){
            // n 表示 N个皇后，N*N网格
            if(n < 1) return 0;
            int record[n]; // i ： 0 ~ n-1 表示第i行，存储的数值j表示在该行的第j列放一个皇后
            return Process(0, record, n); // 从第0行开始，逐行处理
        }

        /**
         * @brief 
         * 
         * @param i 来到第i行
         * @param record 从上一行正确摆完后传过来的记录，即 0 ～ i-1 已经摆好了，剩下 i ～ n - 1 没有摆
         * @param n 定值
         * @return int 告诉上一行 你这种摆法，从我这一行（i）到下面 i ~ n - 1 能正确摆多少种方法
         */
        int Process(int i, int record[], int n){
            if(i == n) return 1; // 边界条件，能够走通所有的行，即到达终止行，即是一种摆法
            
            int res  = 0;
            
            // 遍历我这一行的所有的列，可以放一个皇后的列都进去，往下面去寻找多少种摆法，总和就是返回值
            for(int j = 0; j < n; ++j){
                if(isValid(record, i, j)){
                    // 第j列可以放
                    // 尝试在该列放，那么能有多少种摆法呢
                    record[i] = j;
                    int temp = Process(i+1, record, n);
                    // 累加
                    res = res + temp; 
                }
            }
            return res;   
        }

        
        bool isValid(int record[], int i, int j){
                // 只要确定 当前行i，在第j列摆放一个皇后，会不会和其他行的数值比较是否 同列 或者 同斜线
                for(int k = 0; k < i; ++k){
                    if(record[k] == j || abs(i - k) == abs(j - record[k])){
                        return false;
                    }
                }
                return true;
            }


};

int main (int argc, char** argv){
    NQueen test;
    int res = test.NQueenMethod(8);// res == 92;
    cout << res << endl;
}