怎么写代码自己制作网站,程序员做游戏还是做网站好,聚美优品返利网站怎么做,go cms wordpress大模型价格战越演越烈 昨天的 文章 提到#xff0c;自从 5 月 15 号#xff0c;字节跳动发布了击穿行业底价的豆包大模型后#xff0c;各大厂家纷纷跟进降价#xff0c;而且都不是普通降价#xff0c;要么降价 90% 以上#xff0c;要么直接免费。 今天是豆包… 大模型价格战越演越烈 昨天的 文章 提到自从 5 月 15 号字节跳动发布了击穿行业底价的豆包大模型后各大厂家纷纷跟进降价而且都不是普通降价要么降价 90% 以上要么直接免费。 今天是豆包发布会过去的第 8 天价格战还在继续且越演越烈。 腾讯混元大模型宣布全面降价其中主力模型之一的混元-lite更是从即日起免费使用。 科大讯飞也宣布讯飞星火 API 永久免费开放。 而在昨天5 月 22 号举办的 Baichuan 4 模型产品发布会上百川智能创始人兼 CEO 王小川也点评了最近的大模型价格战其声称在中国市场API 服务其实对创业公司是走不通的。 ... 回归主线。 来一道和「字节跳动校招」相关的算法原题。 题目描述 平台LeetCode 题号886 给定一组 n 人编号为 1, 2, ..., n 我们想把每个人分进任意大小的两组。 每个人都可能不喜欢其他人那么他们不应该属于同一组。 给定整数 n 和数组 dislikes 其中 表示不允许将编号为 和 的人归入同一组。 当可以用这种方法将所有人分进两组时返回 true否则返回 false。 示例 1 输入n 4, dislikes [[1,2],[1,3],[2,4]]输出true解释group1 [1,4], group2 [2,3] 示例 2 输入n 3, dislikes [[1,2],[1,3],[2,3]]输出false 示例 3 输入n 5, dislikes [[1,2],[2,3],[3,4],[4,5],[1,5]]输出false 提示 dislikes 中每一组都 不同 染色法 无论是从题目描述和对点边的描述这都是一道「染色法判定二分图」的模板题。 为了方便我们令 dislikes 为 ds将其长度记为 。 题目要求我们将 个点划分到两个集合中同时我们将每个 看做无向边的话可知集合内部无边即所有的边必然横跨两个集合之间。 使用 进行建图并将两个将要划分出的两个集合分别记为 A 和 B我们可以采用「染色」的方式尝试将所有点进行划分。 构建一个与点数相等的数组 color我们人为规定划分到集合 A 的点满足 划分到集合 B 的点满足 起始有 代表该点尚未被划分。 随后我们可以实现 DFS 函数为 boolean dfs(int u, int cur) 含义为尝试将点 u 上 cur 色。根据定义可知我们除了需要 color[u] cur 以外还需要遍历点 u 的所有出边处理其邻点将其划分到另一集合上若在处理过程中发生冲突则返回 false若能顺利染色则返回 true。 由于我们固定了颜色编号为 1 和 2因此 cur 的对立色可统一为 3 - cur。 最终我们根据能否给所有点染色成功来决定答案。 Java 代码 class Solution { int N 2010, M 2 * 10010; int[] he new int[N], e new int[M], ne new int[M], color new int[N]; int idx; void add(int a, int b) { e[idx] b; ne[idx] he[a]; he[a] idx; } boolean dfs(int u, int cur) { color[u] cur; for (int i he[u]; i ! -1; i ne[i]) { int j e[i]; if (color[j] cur) return false; if (color[j] 0 !dfs(j, 3 - cur)) return false; } return true; } public boolean possibleBipartition(int n, int[][] ds) { Arrays.fill(he, -1); for (int[] info : ds) { int a info[0], b info[1]; add(a, b); add(b, a); } for (int i 1; i n; i) { if (color[i] ! 0) continue; if (!dfs(i, 1)) return false; } return true; }} C 代码 class Solution {public: int he[2010], e[2 * 10010], ne[2 * 10010], color[2010], idx 0; void add(int a, int b) { e[idx] b; ne[idx] he[a]; he[a] idx; } bool dfs(int u, int cur) { color[u] cur; for (int i he[u]; i ! -1; i ne[i]) { int j e[i]; if (color[j] cur) return false; if (color[j] 0 !dfs(j, 3 - cur)) return false; } return true; } bool possibleBipartition(int n, vectorvectorint ds) { fill(he, he n 10, -1); for (const auto info : ds) { int a info[0], b info[1]; add(a, b); add(b, a); } for (int i 1; i n; i) { if (color[i] ! 0) continue; if (!dfs(i, 1)) return false; } return true; }}; Python 代码 class Solution: def possibleBipartition(self, n: int, ds: List[List[int]]) - bool: N, M 2010, 20010 he, e, ne, color [-1] * N, [0] * M, [0] * M, [0] * N idx 0 def add(a, b): nonlocal idx e[idx], ne[idx], he[a] b, he[a], idx idx 1 def dfs(u, cur): color[u] cur i he[u] while i ! -1: j e[i] if color[j] cur: return False if color[j] 0 and not dfs(j, 3 - cur): return False i ne[i] return True for info in ds: a, b info[0], info[1] add(a, b) add(b, a) for i in range(1, n 1): if color[i] ! 0: continue if not dfs(i, 1): return False return True TypeScript 代码 function possibleBipartition(n: number, ds: number[][]): boolean { const N 2010, M 2 * 10010 const he new Arraynumber(N).fill(-1), e new Arraynumber(M).fill(0), ne new Arraynumber(M).fill(0), color new Arraynumber(N).fill(0) let idx 0 function add(a: number, b: number): void { e[idx] b ne[idx] he[a] he[a] idx } function dfs(u: number, cur: number): boolean { color[u] cur for (let i he[u]; i ! -1; i ne[i]) { const j e[i]; if (color[j] cur) return false if (color[j] 0 !dfs(j, 3 - cur)) return false } return true } for (const info of ds) { const a info[0], b info[1] add(a, b); add(b, a) } for (let i 1; i n; i) { if (color[i] ! 0) continue if (!dfs(i, 1)) return false } return true} 时间复杂度 空间复杂度 反向点 并查集 我们知道对于 而言点 a 和点 b 必然位于不同的集合中同时由于只有两个候选集合因此这样的关系具有推断性即对于 和 可知 a 和 c 位于同一集合。 因此我们可以对于每个点 x 而言建议一个反向点 x n若点 x 位于集合 A 则其反向点 x n 位于集合 B反之同理。 基于此我们可以使用「并查集」维护所有点的连通性边维护变检查每个 的联通关系若 联通必然是其反向点联通所导致必然是此前的其他 导致的关系冲突必然不能顺利划分成两个集合返回 false否则返回 true。 Java 代码 class Solution { int[] p new int[4010]; int find(int x) { if (p[x] ! x) p[x] find(p[x]); return p[x]; } void union(int a, int b) { p[find(a)] p[find(b)]; } boolean query(int a, int b) { return find(a) find(b); } public boolean possibleBipartition(int n, int[][] ds) { for (int i 1; i 2 * n; i) p[i] i; for (int[] info : ds) { int a info[0], b info[1]; if (query(a, b)) return false; union(a, b n); union(b, a n); } return true; }} C 代码 class Solution {public: vectorint p; int find(int x) { if (p[x] ! x) p[x] find(p[x]); return p[x]; } void unionp(int a, int b) { p[find(a)] p[find(b)]; } bool query(int a, int b) { return find(a) find(b); } bool possibleBipartition(int n, vectorvectorint ds) { p.resize(2 * n 1); for (int i 1; i 2 * n; i) p[i] i; for (const auto info : ds) { int a info[0], b info[1]; if (query(a, b)) return false; unionp(a, b n); unionp(b, a n); } return true; }}; Python 代码 class Solution: def possibleBipartition(self, n: int, ds: List[List[int]]) - bool: p [i for i in range(0, 2 * n 10)] def find(x): if p[x] ! x: p[x] find(p[x]) return p[x] def union(a, b): p[find(a)] p[find(b)] def query(a, b): return find(a) find(b) for info in ds: a, b info[0], info[1] if query(a, b): return False else: union(a, b n) union(b, a n) return True TypeScript 代码 function possibleBipartition(n: number, ds: number[][]): boolean { const p new Arraynumber(4010).fill(0) function find(x: number): number { if (p[x] ! x) p[x] find(p[x]) return p[x] } function union(a: number, b: number): void { p[find(a)] p[find(b)] } function query(a: number, b: number): boolean { return find(a) find(b) } for (let i 1; i 2 * n; i) p[i] i for (const info of ds) { const a info[0], b info[1] if (query(a, b)) return false union(a, b n); union(b, a n) } return true} 时间复杂度 空间复杂度 最后 给大伙通知一下 全网最低价 LeetCode 会员目前仍可用 ~ 年度会员有效期加赠两个月; 季度会员有效期加赠两周 年度会员获 66.66 现金红包; 季度会员获 22.22 现金红包 年度会员参与当月丰厚专属实物抽奖中奖率 30%) 专属链接leetcode.cn/premium/?promoChannelacoier 我是宫水三叶每天都会分享算法知识并和大家聊聊近期的所见所闻。 欢迎关注明天见。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
