中英文网站建设 pdf枣庄手机网站制作

当前位置： 首页 > news >正文

中英文网站建设 pdf,枣庄手机网站制作,网站制作器手机版,免费网站免费无遮挡本文涉及的知识点 图论 分类讨论 本题同解 【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目 LeetCode3017按距离统计房屋对数目 给你三个 正整数 n 、x 和 y 。 在城市中#xff0c;存在编号从 1 到 n 的房屋#xff0c;由 n 条街道相连。对所有 …本文涉及的知识点 图论 分类讨论 本题同解 【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目 LeetCode3017按距离统计房屋对数目 给你三个 正整数 n 、x 和 y 。 在城市中存在编号从 1 到 n 的房屋由 n 条街道相连。对所有 1 i n 都存在一条街道连接编号为 i 的房屋与编号为 i 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。 对于每个 k1 k n你需要找出所有满足要求的 房屋对 [house1, house2] 即从 house1 到 house2 需要经过的 最少 街道数为 k 。 返回一个下标从 1 开始且长度为 n 的数组 result 其中 result[k] 表示所有满足要求的房屋对的数量即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。 注意x 与 y 可以 相等 。 示例 1 输入n 3, x 1, y 3 输出[6,0,0] 解释让我们检视每个房屋对 对于房屋对 (1, 2)可以直接从房屋 1 到房屋 2。对于房屋对 (2, 1)可以直接从房屋 2 到房屋 1。对于房屋对 (1, 3)可以直接从房屋 1 到房屋 3。对于房屋对 (3, 1)可以直接从房屋 3 到房屋 1。对于房屋对 (2, 3)可以直接从房屋 2 到房屋 3。对于房屋对 (3, 2)可以直接从房屋 3 到房屋 2。 示例 2 输入n 5, x 2, y 4 输出[10,8,2,0,0] 解释对于每个距离 k 满足要求的房屋对如下对于 k 1满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), 以及 (5, 4)。对于 k 2满足要求的房屋对有 (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), 以及 (5, 3)。对于 k 3满足要求的房屋对有 (1, 5)以及 (5, 1) 。对于 k 4 和 k 5不存在满足要求的房屋对。 示例 3 输入n 4, x 1, y 1 输出[6,4,2,0] 解释对于每个距离 k 满足要求的房屋对如下对于 k 1满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), 以及 (4, 3)。对于 k 2满足要求的房屋对有 (1, 3), (3, 1), (2, 4), 以及 (4, 2)。对于 k 3满足要求的房屋对有 (1, 4), 以及 (4, 1)。对于 k 4不存在满足要求的房屋对。 分类讨论 假定x ! y 不失一般性令x y。 则x ↔ \leftrightarrow ↔ y ,是环。房屋z1和z2,令z1 z2 分类如下 分类一z1 x ,z2 x 。则两者经过的街道数为z2-z1。 分类二z1z2 ∈ \in ∈[x,y] 。min(z2-z1,y-z2z1-x1)。 分类三z1,z2 y。和分类一类似。 分类四z1 x z2 ∈ \in ∈[x,y]。 min(z2-z1,y-z21(x-z1)) 分类五z1 x ,z2 y 。则两者经过的街道数为(z1-x)1(z2-y)。通过x,y中中转多花 x1-y 由于y x故多化的0更优。 分类六z1 ∈ \in ∈[x,y]z2 y。 min(z2-z1,z1-x1(z2-y)) 总结后的分类 新分类一[z3,z4] 都不通过x ↔ \leftrightarrow ↔y 中转。包括分类一分类五及xy。 距离为1的数量为:z4-z3。 距离为2的数量为z4-z3-1 ⋮ \vdots ⋮ 新分类二两个点都在环上环的长度为len。则两点的合法距离只能 ∈ \in ∈[1,len/2] 原分类二。 如果len是偶数距离len/2的点对数量为len/2z5 → \rightarrow →z6 就是 z6 → \rightarrow →z5。 其它情况点对数量为len。 新分类三两个点分别在环两侧。分类五。 长度为3的点对1。 长度为4的点对2。 长度为5的点对3 。 令环左侧的点数为len1环右侧的点数为len2。计算距离为d的数量 minl max(0,d-3-(len2-1)) maxl min(len1-1,d-3) 距离为d的点对数量maxl - minl 1 。 新分类四环上一点一侧一点。原分类四六。 把环拆成两个就和新分类三基本一致。 拆分成{2,1,4}和{5,6}同时拆分成{3,4} {5,6} 交点4 被计算了两次要扣掉。 代码 核心代码 class Solution { public:vectorlong long countOfPairs(int n, int x, int y) {m_vRet.resize(n);if (x y) {Do1(1, n);return m_vRet;}if (x y) {swap(x, y);}Do1(1, x - 1);const int iCycLen y - x 1;Do2(iCycLen);Do1(y 1, n);Do4(iCycLen, x - 1);Do3(x - 1, 3, n - y);Do4(iCycLen, n - y);return m_vRet;}void Do1(int left, int r){for (int d 1; d r - left; d) {update(d, r - left 1 - d);}}void Do2(int iCycLen){for (int d 1; d iCycLen / 2; d){const int cnt ((0 iCycLen % 2) (iCycLen / 2 d)) ? iCycLen / 2 : iCycLen;update(d, cnt);}}void Do3(int len1, int iMidDis, int len2){for (int d 0; d len1 len2 - 2; d){const int minl max(0, d - (len2 - 1));const int maxl min(len1 - 1, d);update(d iMidDis, maxl - minl 1);}}void Do4(int iCycLen, int len){Do3((iCycLen1) / 2 , 1, len);Do3(iCycLen / 2 1, 1, len);for (int d 1; d len; d) {update(d, -1);}}inline void update(int d, int cnt){m_vRet[d - 1] cnt*2;}vectorlong long m_vRet; };测试用例 templateclass T void Assert(const T t1, const T t2) {assert(t1 t2); }templateclass T void Assert(const vectorT v1, const vectorT v2) {if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main() {int n, x, y;{Solution sln;n 6, x 1, y 5;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{ 12, 14, 4, 0, 0, 0 });}{Solution sln;n 3, x 2, y 2;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{4, 2, 0});}{Solution sln;n 4, x 1, y 1;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{6, 4, 2, 0});}{Solution sln;n 5, x 2, y 4;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{10, 8, 2, 0, 0});}{Solution sln;n 3, x 1, y 3;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{6, 0, 0});}{Solution sln;n 2, x 2, y 2;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{2, 0});} }扩展阅读 视频课程 有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176 相关下载 想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653 我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛 测试环境 操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用C实现。