内网网站建设,中山做网站专业的公司,网站要跟换域名怎么做,野望是什么意思点击蓝字“dotNET匠人”关注我哟加个“星标★”#xff0c;每日 7:15#xff0c;好文必达#xff01;前文传送门:C# 刷遍 Leetcode 面试题系列连载#xff08;1#xff09; - 入门与工具简介C#刷遍Leetcode面试题系列连载#xff08;2#xff09;: No.38 - 报数C#刷遍Le… 点击蓝字“dotNET匠人”关注我哟加个“星标★”每日 7:15好文必达前文传送门:C# 刷遍 Leetcode 面试题系列连载1 - 入门与工具简介C#刷遍Leetcode面试题系列连载2: No.38 - 报数C#刷遍Leetcode面试题系列连载3: No.728 - 自除数C#刷遍Leetcode面试题系列连载4: No.633 - 平方数之和C#刷遍Leetcode面试题系列连载5No.593 - 有效的正方形上一篇 LeetCode 面试题中我们分析了一道难度为 Medium 的数学题 - 有效的正方形提供了3种方法。今天我们继续来分析一道难度为 Medium 的面试题吧。今天要给大家分析的面试题是 LeetCode 上第 372 号问题LeetCode - 372. 超级次方https://leetcode.com/problems/super-pow/题目描述你的任务是计算 对 1337 取模a 是一个正整数b 是一个非常大的正整数且会以数组形式给出。示例 1:a 2
b [3]结果: 8
示例 2:a 2
b [1,0]结果: 1024
示例 3:a 2147483647
b [2,0,0]
结果: 1198
致谢特别感谢 Stomach_ache 添加这道题并创建所有测试用例。题目难度Medium提交次数6.3K通过次数2.3K通过率35.95%相关标签数学https://leetcode-cn.com/tag/math相似题目Pow(x, n)https://leetcode-cn.com/problems/powx-n相关知识与思路:理解题意:本题要求计算 % 1337输入中a是以十进制形式给出而b是以数组的形式给出的数组中依次存有十进制下的每位数字。解法1: 直接用字符串处理public class Solution
{public int SuperPow(int a, int[] b){int res 0;StringBuilder sb new StringBuilder();foreach (var item in b)sb.Append(item);int.TryParse(sb.ToString(), out int p);var val (int) Math.Pow(a, p);res val - (val / 1337)*1337;return res;}
}
会发现对数b较大时(示例3)会越界。因此需利用模运算的性质来优化~而模运算的常用性质如下分配率(a b) mod n [(a mod n) (b mod n) ] mod n。 mod n [(a mod n) (b mod n) ] mod n。d mod() (d mod a) a [(d \ a) mod b] [(d \ a \ b) mod c]其中\是欧几里德除法的商的算子。c mod(a b) (c mod a) [ (a b) ] mod b - [ (a b) ] mod a。除法 A/B mod n [(a mod n) ( mod n) ] mod n当b和n互质时右边被定义。反之亦然。相乘后的逆(Inverse multiplication)[( mod n) ( mod n) ] mod n a mod n。特殊性质:x % x ()另外与之相关的一个概念是同余(Congruence relation)。此题需用到分配率中的: mod n [(a mod n) (b mod n) ] mod n解法2 已AC代码:public class Solution
{const int Mod0 1337;public int SuperPow(int a, int[] b){if (b.Length 0)return 1;var res 1;for (int i b.Length - 1; i 0; i--){res powMod(a, b[i]) * res % Mod0;a powMod(a, 10);}return res;}private int powMod(int a, int m){a % Mod0;int result 1;for (int i 0; i m; i)result result * a % Mod0;return result;}
}
Rank:执行用时: 116 ms, 在所有 csharp 提交中击败了100.00%的用户.按理说如果将a%m改为a-(a/m)*m代码运行速度会变快些直接进行模运算确实会慢一些。解法3 已AC代码:public class Solution
{const int Mod0 1337;public int SuperPow(int a, int[] b){if (b.Length 0)return 1;var res 1;for (int i b.Length - 1; i 0; i--){var powModResult powMod(a, b[i]) * res;res powModResult - (powModResult / Mod0) * Mod0;a powMod(a, 10);}return res;}private int powMod(int a, int m){a a - (a / Mod0) * Mod0;int result 1;for (int i 0; i m; i)result result * a - (result * a / Mod0) * Mod0;return result;}
}
Rank:执行用时: 112 ms, 在所有 csharp 提交中击败了100.00%的用户示例代码: https://github.com/yanglr/Leetcode-CSharp/tree/master/leetcode372 .欢迎提出更佳的解决思路~最近正在看百度前副总裁的《俞军产品方法论》提升一下自己的产品思维。这本书2019年12月才由中信出版社出版良心好书推荐给大家~End作者简介Bravo Yeung计算机硕士知乎干货答主(2.3万关注者获73K 赞同, 34K 感谢, 210K 收藏)。曾在国内 Top3互联网视频直播公司短暂工作过后加入一家外企做软件开发至今。欢迎在留言区留下你的观点一起讨论提高。如果今天的文章让你有新的启发学习能力的提升上有新的认识欢迎转发分享给更多人。欢迎各位读者加入 .NET技术交流群在公众号后台回复“加群”或者“学习”即可。大家好我就是区块链本人。今天我要给你们介绍我的家族…只因写了一段爬虫公司200多人被一锅全端真实的上海IT圈张江男vs漕河泾男C#刷遍Leetcode面试题系列连载1 - 入门与工具简介.NET斗鱼直播弹幕客户端上写给.NET开发者看的Python3上手指南系列1Python3与C# 基础语法对比硬货 - 技术人也能轻松玩转公众号正确姿势竟然是...转发至朋友圈是对我最大的支持。朕已阅
