当前位置: 首页 > ai >正文

6.4 note

构造矩阵


class Solution {
private:
    vector<int> empty = {};
    // 返回每个数字(-1)所在的序号,可以是行或列, 如果为空则无效
    vector<int> topoSort(int k, vector<vector<int>>& conditions)
    {
        // 构建一个图: 范围1-k,这里故意留一个0空着,后续计算无需额外-1
        vector<vector<int>> g(k+1);
        // 入度: 范围1-k,这里故意留一个0空着,后续计算无需额外-1
        // vector<int> inDegrees(k+1);
        int inDegrees[k+1];
        memset(inDegrees, 0, sizeof(inDegrees));
        for (vector<int>& condition : conditions)
        {
            g[condition[0]].push_back(condition[1]);
            ++inDegrees[condition[1]];
        }

        // 拓扑排序使用队列
        queue<int> q;
        // 插入入度为0的节点
        for (int i = 1; i <= k; ++i)
        {
            if (inDegrees[i] == 0)
            {
                q.push(i);
            }
        }
        // 计算找到接点的序号:即优先级顺序
        int seq = 0;
        // 返回结果
        vector<int> res(k);
        while (q.size() > 0)
        {
            int curr = q.front();
            q.pop();
            res[curr-1] = seq++;
            for (int next : g[curr])
            {
                if (--inDegrees[next] == 0)
                {
                    q.push(next);
                }
            }
        }

        // 找不到则返回空
        return seq == k ? res : empty;
    }

public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<int> rows = topoSort(k, rowConditions);
        vector<int> cols = topoSort(k, colConditions);
        // 一旦发现有空的情况(即无法满足条件),就可以直接返回空
        if (rows.size() == 0 || cols.size() == 0)
        {
            return {};
        }

        vector<vector<int>> res(k, vector<int>(k));
        for (int i = 0; i < k; ++i)
        {
            // 这里需要额外+1,因为编号是 0~k-1
            res[rows[i]][cols[i]] = i+1;
        }

        return res;
     }
};
 

双指针➕找规律

要改变的最小次数就等于中值,可以通过两端做差再除以2得到最小的变化次数,

然后迭代下去即可,具体实参看代码,时间复杂度O(n)

代码:

class Solution {
public:
    int minOperations(int n) {
        int start = 0;
        int end = n-1;
        int res = 0;
        while(start<end){     //len长奇偶都无关
            res+=((end*2-1)-(start*2-1))/2;
            start++;
            end--;
        }
        return res;
    }
};

算法

1. 计算机编程语言是人类和计算机交流的语言工具。

2. 计算机的本质是状态机,内存里存储的所有数据构成了当前的状态;

3. 数据结构相当于告诉计算机怎么来记录当前的状态,算法相当于告诉计算机怎么根据当前的状态计算出下一个状态。

4. 空间复杂度就是你需要的必需存储的状态最多有多少;

5. 时间复杂度就是从初始状态到达最终状态中间需要多少步,这个和算法强相关,是算法关注的事情;

6. 程序在计算过程中,将问题层层分解之后,会有大量的中间过程数据,这个本质上就是记录问题的中间状态;中间过程数据就是由你设计的数据结 构来承载。

cpp性能优化

 单线程下, 智能指针作为参数传递的时候没有使用引用  每次都拷贝构造 造成了额外的 性能开销 。

只要是个类型变量都可以传参,例如share_ptr

 

错误贪心 lc3458

class Solution {

public:

    bool maxSubstringLength(string s, int k) {

        unordered_map<char,int> hash;

        for(auto c:s)

            hash[c]++;

        int cnt=0;

        for(auto& [a,b]:hash)

        {

            if(b==1) cnt++;

        }

        if(cnt>=k) return true;

        else return false;

    }

};

 

正确贪心:

class Solution {
public:
    bool maxSubstringLength(string s, int K) {
        int n = s.size();

        vector<int> pos[26];
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            pos[c].push_back(i);
        }

        typedef pair<int, int> pii;
        vector<pii> vec;
        // 枚举每一种子串
        for (int i = 0; i < 26; i++) if (!pos[i].empty()) {
            // 一开始先用这种字母的范围作为子串的范围
            int l = pos[i][0], r = pos[i].back();
            bool flag = true;
            while (flag) {
                flag = false;
                // 检查子串里是否出现了其它字母
                for (int j = 0; j < 26; j++) {
                    int cnt = upper_bound(pos[j].begin(), pos[j].end(), r) - lower_bound(pos[j].begin(), pos[j].end(), l);
                    if (cnt > 0 && cnt < pos[j].size()) {
                        // 有一种字母没有被完全包含,用它的范围更新子串的范围
                        l = min(l, pos[j][0]);
                        r = max(r, pos[j].back());
                        flag = true;
                    }
                }
            }
            // 得到了这种子串里的最短子串
            if (l > 0 || r < n - 1) vec.push_back({r, l});
        }

        // leetcode 435. 无重叠区间
        sort(vec.begin(), vec.end());
        int R = -1, cnt = 0;
        for (pii p : vec) if (p.second > R) {
            R = p.first;
            cnt++;
        }
        return cnt >= K;
    }
};

 

http://www.xdnf.cn/news/10893.html

相关文章:

  • c++ algorithm
  • 互联网 Web 网站
  • flex布局实现固定区域滚动
  • 贝利特价型号SPHSS03 液压伺服模块
  • maven在修改完配置之后新建项目还是不生效的原因
  • 13_pandas可视化_Matplotlib
  • Python库 Pympler 详解:内存分析与追踪工具
  • 父文档检索器引和RAG的context precision性能指标
  • docker-compose 方式搭建禅道(最新版)
  • 对接系统外部服务组件技术方案
  • 数据库包括哪些?关系型数据库是什么意思?
  • Percona Toolkit利器pt-config-diff:MySQL配置差异分析与实战指南
  • 【ROS2】各种相关概念汇总解释
  • 条形进度条
  • 【分层图 最短路 迪氏堆优化最短路】B4165 [BCSP-X 2024 12 月初中组] 贸易|普及+
  • SAP 自动编号的使用
  • 19-项目部署(Linux)
  • 爱普生Epson L3210打印机信息
  • 数据库OCP专业认证培训
  • 嵌入式笔试题+面试题
  • 佰力博科技与您探讨低温介电温谱测试仪的应用领域
  • 安全月报 | 傲盾DDoS攻击防御2025年5月简报
  • Python编程基础(四) | if语句
  • while和do-while循环
  • Office文档图片批量导出工具
  • 30天速通C++(九):深入理解deque
  • CppCon 2014 学习:Anatomy of a Smart Pointer
  • 格恩朗气体涡轮流量计 工业精准流量管理的卓越之选
  • Asp.net core 使用EntityFrame Work
  • 核心机制:流量控制